summaryrefslogtreecommitdiff
path: root/src/shared
diff options
context:
space:
mode:
Diffstat (limited to 'src/shared')
-rw-r--r--src/shared/uid-range.c205
-rw-r--r--src/shared/uid-range.h34
2 files changed, 239 insertions, 0 deletions
diff --git a/src/shared/uid-range.c b/src/shared/uid-range.c
new file mode 100644
index 0000000000..74c3be4a13
--- /dev/null
+++ b/src/shared/uid-range.c
@@ -0,0 +1,205 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+/***
+ This file is part of systemd.
+
+ Copyright 2014 Lennart Poettering
+
+ systemd is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by
+ the Free Software Foundation; either version 2.1 of the License, or
+ (at your option) any later version.
+
+ systemd is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include "util.h"
+#include "uid-range.h"
+
+static bool uid_range_intersect(UidRange *range, uid_t start, uid_t nr) {
+ assert(range);
+
+ return range->start <= start + nr &&
+ range->start + range->nr >= start;
+}
+
+static void uid_range_coalesce(UidRange **p, unsigned *n) {
+ unsigned i, j;
+
+ assert(p);
+ assert(n);
+
+ for (i = 0; i < *n; i++) {
+ for (j = i + 1; j < *n; j++) {
+ UidRange *x = (*p)+i, *y = (*p)+j;
+
+ if (uid_range_intersect(x, y->start, y->nr)) {
+ uid_t begin, end;
+
+ begin = MIN(x->start, y->start);
+ end = MAX(x->start + x->nr, y->start + y->nr);
+
+ x->start = begin;
+ x->nr = end - begin;
+
+ if (*n > j+1)
+ memmove(y, y+1, sizeof(UidRange) * (*n - j -1));
+
+ (*n) --;
+ j--;
+ }
+ }
+ }
+
+}
+
+static int uid_range_compare(const void *a, const void *b) {
+ const UidRange *x = a, *y = b;
+
+ if (x->start < y->start)
+ return -1;
+ if (x->start > y->start)
+ return 1;
+
+ if (x->nr < y->nr)
+ return -1;
+ if (x->nr > y->nr)
+ return 1;
+
+ return 0;
+}
+
+int uid_range_add(UidRange **p, unsigned *n, uid_t start, uid_t nr) {
+ bool found = false;
+ UidRange *x;
+ unsigned i;
+
+ assert(p);
+ assert(n);
+
+ if (nr <= 0)
+ return 0;
+
+ for (i = 0; i < *n; i++) {
+ x = (*p) + i;
+ if (uid_range_intersect(x, start, nr)) {
+ found = true;
+ break;
+ }
+ }
+
+ if (found) {
+ uid_t begin, end;
+
+ begin = MIN(x->start, start);
+ end = MAX(x->start + x->nr, start + nr);
+
+ x->start = begin;
+ x->nr = end - begin;
+ } else {
+ UidRange *t;
+
+ t = realloc(*p, sizeof(UidRange) * (*n + 1));
+ if (!t)
+ return -ENOMEM;
+
+ *p = t;
+ x = t + ((*n) ++);
+
+ x->start = start;
+ x->nr = nr;
+ }
+
+ qsort(*p, *n, sizeof(UidRange), uid_range_compare);
+ uid_range_coalesce(p, n);
+
+ return *n;
+}
+
+int uid_range_add_str(UidRange **p, unsigned *n, const char *s) {
+ uid_t start, nr;
+ const char *t;
+ int r;
+
+ assert(p);
+ assert(n);
+ assert(s);
+
+ t = strchr(s, '-');
+ if (t) {
+ char *b;
+ uid_t end;
+
+ b = strndupa(s, t - s);
+ r = parse_uid(b, &start);
+ if (r < 0)
+ return r;
+
+ r = parse_uid(t+1, &end);
+ if (r < 0)
+ return r;
+
+ if (end < start)
+ return -EINVAL;
+
+ nr = end - start + 1;
+ } else {
+ r = parse_uid(s, &start);
+ if (r < 0)
+ return r;
+
+ nr = 1;
+ }
+
+ return uid_range_add(p, n, start, nr);
+}
+
+int uid_range_next_lower(const UidRange *p, unsigned n, uid_t *uid) {
+ uid_t closest = (uid_t) -1, candidate;
+ unsigned i;
+
+ assert(p);
+ assert(uid);
+
+ candidate = *uid - 1;
+
+ for (i = 0; i < n; i++) {
+ uid_t begin, end;
+
+ begin = p[i].start;
+ end = p[i].start + p[i].nr - 1;
+
+ if (candidate >= begin && candidate <= end) {
+ *uid = candidate;
+ return 1;
+ }
+
+ if (end < candidate)
+ closest = end;
+ }
+
+ if (closest == (uid_t) -1)
+ return -EBUSY;
+
+ *uid = closest;
+ return 1;
+}
+
+bool uid_range_contains(const UidRange *p, unsigned n, uid_t uid) {
+ unsigned i;
+
+ assert(p);
+ assert(uid);
+
+ for (i = 0; i < n; i++)
+ if (uid >= p[i].start && uid < p[i].start + p[i].nr)
+ return true;
+
+ return false;
+}
diff --git a/src/shared/uid-range.h b/src/shared/uid-range.h
new file mode 100644
index 0000000000..d3dac8df63
--- /dev/null
+++ b/src/shared/uid-range.h
@@ -0,0 +1,34 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+#pragma once
+
+/***
+ This file is part of systemd.
+
+ Copyright 2014 Lennart Poettering
+
+ systemd is free software; you can redistribute it and/or modify it
+ under the terms of the GNU Lesser General Public License as published by
+ the Free Software Foundation; either version 2.1 of the License, or
+ (at your option) any later version.
+
+ systemd is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include <sys/types.h>
+
+typedef struct UidRange {
+ uid_t start, nr;
+} UidRange;
+
+int uid_range_add(UidRange **p, unsigned *n, uid_t start, uid_t nr);
+int uid_range_add_str(UidRange **p, unsigned *n, const char *s);
+
+int uid_range_next_lower(const UidRange *p, unsigned n, uid_t *uid);
+bool uid_range_contains(const UidRange *p, unsigned n, uid_t uid);