]>
Commit | Line | Data |
---|---|---|
db9ecf05 | 1 | /* SPDX-License-Identifier: LGPL-2.1-or-later */ |
8530dc44 | 2 | |
a8fbdf54 TA |
3 | #include <errno.h> |
4 | #include <stdlib.h> | |
5 | #include <string.h> | |
6 | ||
62d74c78 | 7 | #include "alloc-util.h" |
a8fbdf54 | 8 | #include "macro.h" |
760877e9 | 9 | #include "sort-util.h" |
8530dc44 | 10 | #include "uid-range.h" |
b1d4f8e1 | 11 | #include "user-util.h" |
8530dc44 LP |
12 | |
13 | static bool uid_range_intersect(UidRange *range, uid_t start, uid_t nr) { | |
14 | assert(range); | |
15 | ||
16 | return range->start <= start + nr && | |
17 | range->start + range->nr >= start; | |
18 | } | |
19 | ||
20 | static void uid_range_coalesce(UidRange **p, unsigned *n) { | |
8530dc44 LP |
21 | assert(p); |
22 | assert(n); | |
23 | ||
196b5968 ZJS |
24 | for (unsigned i = 0; i < *n; i++) { |
25 | for (unsigned j = i + 1; j < *n; j++) { | |
8530dc44 LP |
26 | UidRange *x = (*p)+i, *y = (*p)+j; |
27 | ||
28 | if (uid_range_intersect(x, y->start, y->nr)) { | |
29 | uid_t begin, end; | |
30 | ||
31 | begin = MIN(x->start, y->start); | |
32 | end = MAX(x->start + x->nr, y->start + y->nr); | |
33 | ||
34 | x->start = begin; | |
35 | x->nr = end - begin; | |
36 | ||
37 | if (*n > j+1) | |
38 | memmove(y, y+1, sizeof(UidRange) * (*n - j -1)); | |
39 | ||
313cefa1 | 40 | (*n)--; |
8530dc44 LP |
41 | j--; |
42 | } | |
43 | } | |
44 | } | |
8530dc44 LP |
45 | } |
46 | ||
93bab288 YW |
47 | static int uid_range_compare(const UidRange *a, const UidRange *b) { |
48 | int r; | |
8530dc44 | 49 | |
93bab288 YW |
50 | r = CMP(a->start, b->start); |
51 | if (r != 0) | |
52 | return r; | |
8530dc44 | 53 | |
93bab288 | 54 | return CMP(a->nr, b->nr); |
8530dc44 LP |
55 | } |
56 | ||
57 | int uid_range_add(UidRange **p, unsigned *n, uid_t start, uid_t nr) { | |
58 | bool found = false; | |
59 | UidRange *x; | |
8530dc44 LP |
60 | |
61 | assert(p); | |
62 | assert(n); | |
63 | ||
64 | if (nr <= 0) | |
65 | return 0; | |
66 | ||
196b5968 | 67 | for (unsigned i = 0; i < *n; i++) { |
8530dc44 LP |
68 | x = (*p) + i; |
69 | if (uid_range_intersect(x, start, nr)) { | |
70 | found = true; | |
71 | break; | |
72 | } | |
73 | } | |
74 | ||
75 | if (found) { | |
76 | uid_t begin, end; | |
77 | ||
78 | begin = MIN(x->start, start); | |
79 | end = MAX(x->start + x->nr, start + nr); | |
80 | ||
81 | x->start = begin; | |
82 | x->nr = end - begin; | |
83 | } else { | |
84 | UidRange *t; | |
85 | ||
62d74c78 | 86 | t = reallocarray(*p, *n + 1, sizeof(UidRange)); |
8530dc44 LP |
87 | if (!t) |
88 | return -ENOMEM; | |
89 | ||
90 | *p = t; | |
91 | x = t + ((*n) ++); | |
92 | ||
93 | x->start = start; | |
94 | x->nr = nr; | |
95 | } | |
96 | ||
93bab288 | 97 | typesafe_qsort(*p, *n, uid_range_compare); |
8530dc44 LP |
98 | uid_range_coalesce(p, n); |
99 | ||
100 | return *n; | |
101 | } | |
102 | ||
103 | int uid_range_add_str(UidRange **p, unsigned *n, const char *s) { | |
104 | uid_t start, nr; | |
105 | const char *t; | |
106 | int r; | |
107 | ||
108 | assert(p); | |
109 | assert(n); | |
110 | assert(s); | |
111 | ||
112 | t = strchr(s, '-'); | |
113 | if (t) { | |
114 | char *b; | |
115 | uid_t end; | |
116 | ||
117 | b = strndupa(s, t - s); | |
118 | r = parse_uid(b, &start); | |
119 | if (r < 0) | |
120 | return r; | |
121 | ||
122 | r = parse_uid(t+1, &end); | |
123 | if (r < 0) | |
124 | return r; | |
125 | ||
126 | if (end < start) | |
127 | return -EINVAL; | |
128 | ||
129 | nr = end - start + 1; | |
130 | } else { | |
131 | r = parse_uid(s, &start); | |
132 | if (r < 0) | |
133 | return r; | |
134 | ||
135 | nr = 1; | |
136 | } | |
137 | ||
138 | return uid_range_add(p, n, start, nr); | |
139 | } | |
140 | ||
141 | int uid_range_next_lower(const UidRange *p, unsigned n, uid_t *uid) { | |
fed1e721 | 142 | uid_t closest = UID_INVALID, candidate; |
8530dc44 LP |
143 | |
144 | assert(p); | |
145 | assert(uid); | |
146 | ||
147 | candidate = *uid - 1; | |
148 | ||
196b5968 | 149 | for (unsigned i = 0; i < n; i++) { |
8530dc44 LP |
150 | uid_t begin, end; |
151 | ||
152 | begin = p[i].start; | |
153 | end = p[i].start + p[i].nr - 1; | |
154 | ||
155 | if (candidate >= begin && candidate <= end) { | |
156 | *uid = candidate; | |
157 | return 1; | |
158 | } | |
159 | ||
160 | if (end < candidate) | |
161 | closest = end; | |
162 | } | |
163 | ||
fed1e721 | 164 | if (closest == UID_INVALID) |
8530dc44 LP |
165 | return -EBUSY; |
166 | ||
167 | *uid = closest; | |
168 | return 1; | |
169 | } | |
170 | ||
171 | bool uid_range_contains(const UidRange *p, unsigned n, uid_t uid) { | |
8530dc44 LP |
172 | assert(p); |
173 | assert(uid); | |
174 | ||
196b5968 | 175 | for (unsigned i = 0; i < n; i++) |
8530dc44 LP |
176 | if (uid >= p[i].start && uid < p[i].start + p[i].nr) |
177 | return true; | |
178 | ||
179 | return false; | |
180 | } |