==> src/ranges.c <==1/* jobs.rs's Ranges over a sorted array of [start, end) pairs: disjoint and never touching. */
2#include "mesh/jobs/ranges.h"
3#include "mesh/debug_str.h"
4
5#include <stdlib.h>
6#include <string.h>
7
8static void grow(mj_ranges *r, size_t need) {
9 if (need <= r->cap) return;
10 size_t cap = r->cap ? r->cap * 2 : 4;
11 while (cap < need) cap *= 2;
12 r->v = mxrealloc(r->v, cap * sizeof *r->v);
13 r->cap = cap;
14}
15
16mj_ranges mj_ranges_of(uint64_t s, uint64_t e) {
17 mj_ranges r = {0};
18 mj_ranges_insert(&r, s, e);
19 return r;
20}
21
22void mj_ranges_free(mj_ranges *r) {
23 free(r->v);
24 *r = (mj_ranges){0};
25}
26
27void mj_ranges_clear(mj_ranges *r) { r->n = 0; }
28
29mj_ranges mj_ranges_clone(const mj_ranges *r) {
30 mj_ranges c = {0};
31 if (r->n) {
32 grow(&c, r->n);
33 memcpy(c.v, r->v, r->n * sizeof *r->v);
34 c.n = r->n;
35 }
36 return c;
37}
38
39bool mj_ranges_eq(const mj_ranges *a, const mj_ranges *b) {
40 return a->n == b->n && (a->n == 0 || memcmp(a->v, b->v, a->n * sizeof *a->v) == 0);
41}
42
43uint64_t mj_ranges_len(const mj_ranges *r) {
44 uint64_t n = 0;
45 for (size_t i = 0; i < r->n; i++) {
46 uint64_t d = r->v[i][1] - r->v[i][0];
47 n = n > UINT64_MAX - d ? UINT64_MAX : n + d;
48 }
49 return n;
50}
51
52bool mj_ranges_first(const mj_ranges *r, uint64_t *x) {
53 if (!r->n) return false;
54 *x = r->v[0][0];
55 return true;
56}
57
58bool mj_ranges_end(const mj_ranges *r, uint64_t *e) {
59 if (!r->n) return false;
60 *e = r->v[r->n - 1][1];
61 return true;
62}
63
64/* The index of the last range starting at or before x, or -1. */
65static long floor_at(const mj_ranges *r, uint64_t x) {
66 size_t lo = 0, hi = r->n;
67 while (lo < hi) {
68 size_t mid = lo + (hi - lo) / 2;
69 if (r->v[mid][0] <= x) lo = mid + 1;
70 else hi = mid;
71 }
72 return (long)lo - 1;
73}
74
75/* The index of the last range starting before x, or -1. */
76static long below(const mj_ranges *r, uint64_t x) {
77 size_t lo = 0, hi = r->n;
78 while (lo < hi) {
79 size_t mid = lo + (hi - lo) / 2;
80 if (r->v[mid][0] < x) lo = mid + 1;
81 else hi = mid;
82 }
83 return (long)lo - 1;
84}
85
86bool mj_ranges_contains(const mj_ranges *r, uint64_t x) {
87 long i = floor_at(r, x);
88 return i >= 0 && x < r->v[i][1];
89}
90
91void mj_ranges_insert(mj_ranges *r, uint64_t s, uint64_t e) {
92 if (s >= e) return;
93 /* Every range starting at or before e that reaches s (touching included) merges in. */
94 long hi = floor_at(r, e), lo = hi;
95 while (lo >= 0 && r->v[lo][1] >= s) {
96 if (r->v[lo][0] < s) s = r->v[lo][0];
97 if (r->v[lo][1] > e) e = r->v[lo][1];
98 lo--;
99 }
100 size_t first = (size_t)(lo + 1), gone = (size_t)(hi - lo);
101 if (gone == 0) {
102 grow(r, r->n + 1);
103 memmove(&r->v[first + 1], &r->v[first], (r->n - first) * sizeof *r->v);
104 r->n++;
105 } else if (gone > 1) {
106 memmove(&r->v[first + 1], &r->v[first + gone], (r->n - first - gone) * sizeof *r->v);
107 r->n -= gone - 1;
108 }
109 r->v[first][0] = s;
110 r->v[first][1] = e;
111}
112
113void mj_ranges_add(mj_ranges *r, uint64_t x) { mj_ranges_insert(r, x, x == UINT64_MAX ? x : x + 1); }
114
115void mj_ranges_union(mj_ranges *r, const mj_ranges *o) {
116 if (r == o) return;
117 for (size_t i = 0; i < o->n; i++) mj_ranges_insert(r, o->v[i][0], o->v[i][1]);
118}
119
120bool mj_ranges_remove(mj_ranges *r, uint64_t s, uint64_t e) {
121 if (s >= e) return false;
122 /* Every range starting before e that ends after s. */
123 long hi = below(r, e), lo = hi;
124 while (lo >= 0 && r->v[lo][1] > s) lo--;
125 size_t first = (size_t)(lo + 1), gone = (size_t)(hi - lo);
126 if (gone == 0) return false;
127 uint64_t keep[2][2];
128 size_t nkeep = 0;
129 if (r->v[first][0] < s) {
130 keep[nkeep][0] = r->v[first][0];
131 keep[nkeep++][1] = s;
132 }
133 if (r->v[first + gone - 1][1] > e) {
134 keep[nkeep][0] = e;
135 keep[nkeep++][1] = r->v[first + gone - 1][1];
136 }
137 size_t tail = r->n - first - gone;
138 grow(r, r->n - gone + nkeep);
139 memmove(&r->v[first + nkeep], &r->v[first + gone], tail * sizeof *r->v);
140 memcpy(&r->v[first], keep, nkeep * sizeof *r->v);
141 r->n = r->n - gone + nkeep;
142 return true;
143}
144
145bool mj_ranges_take(mj_ranges *r, uint64_t x) { return mj_ranges_remove(r, x, x == UINT64_MAX ? x : x + 1); }
146
147void mj_ranges_subtract(mj_ranges *r, const mj_ranges *o) {
148 if (r == o) {
149 r->n = 0;
150 return;
151 }
152 for (size_t i = 0; i < o->n; i++) mj_ranges_remove(r, o->v[i][0], o->v[i][1]);
153}
154
155mj_ranges mj_ranges_intersect(const mj_ranges *a, const mj_ranges *b) {
156 mj_ranges r = {0};
157 for (size_t i = 0; i < a->n; i++) {
158 uint64_t s = a->v[i][0], e = a->v[i][1];
159 for (long j = below(b, e); j >= 0 && b->v[j][1] > s; j--)
160 mj_ranges_insert(&r, s > b->v[j][0] ? s : b->v[j][0], e < b->v[j][1] ? e : b->v[j][1]);
161 }
162 return r;
163}
164
165mj_ranges mj_ranges_take_front(mj_ranges *r, uint64_t n) {
166 mj_ranges got = {0};
167 uint64_t left = n;
168 while (left > 0 && r->n) {
169 uint64_t s = r->v[0][0], e = r->v[0][1];
170 uint64_t k = e - s < left ? e - s : left;
171 mj_ranges_insert(&got, s, s + k);
172 mj_ranges_remove(r, s, s + k);
173 left -= k;
174 }
175 return got;
176}
177
178bool mj_ranges_nth(const mj_ranges *r, uint64_t k, uint64_t *x) {
179 uint64_t left = k;
180 for (size_t i = 0; i < r->n; i++) {
181 uint64_t d = r->v[i][1] - r->v[i][0];
182 if (left < d) {
183 *x = r->v[i][0] + left;
184 return true;
185 }
186 left -= d;
187 }
188 return false;
189}
190
191void mj_ranges_word(const mj_ranges *r, msb *out) {
192 if (!r->n) {
193 msb_putc(out, '-');
194 return;
195 }
196 for (size_t i = 0; i < r->n; i++) {
197 if (i) msb_putc(out, ',');
198 if (r->v[i][1] == UINT64_MAX) msb_printf(out, "%llu-", (unsigned long long)r->v[i][0]);
199 else msb_printf(out, "%llu-%llu", (unsigned long long)r->v[i][0], (unsigned long long)r->v[i][1]);
200 }
201}
202
203char *mj_ranges_word_new(const mj_ranges *r) {
204 msb b = {0};
205 mj_ranges_word(r, &b);
206 return msb_take(&b);
207}
208
209/* Rust's `x.replace('_', "").parse::<u64>()`: an optional '+', then decimal digits, no overflow. */
210static bool num(const char *s, size_t n, uint64_t *out) {
211 uint64_t v = 0;
212 size_t digits = 0, i = 0;
213 /* Underscores vanish first, so "+_1" is "+1". */
214 while (i < n && s[i] == '_') i++;
215 if (i < n && s[i] == '+') i++;
216 for (; i < n; i++) {
217 char c = s[i];
218 if (c == '_') continue;
219 if (c < '0' || c > '9') return false;
220 uint64_t d = (uint64_t)(c - '0');
221 if (v > (UINT64_MAX - d) / 10) return false;
222 v = v * 10 + d;
223 digits++;
224 }
225 if (!digits) return false;
226 *out = v;
227 return true;
228}
229
230static bool bad(const char *s, char **err) {
231 if (err) {
232 msb b = {0};
233 msb_puts(&b, "items ");
234 mdebug_str(&b, s, strlen(s));
235 msb_puts(&b, ": `<n>` (0..n), or `a-b` (half-open), `a-` (endless), `a`, comma-separated");
236 *err = msb_take(&b);
237 }
238 return false;
239}
240
241bool mj_ranges_parse(const char *s, mj_ranges *out, char **err) {
242 mj_ranges r = {0};
243 if (strcmp(s, "-") == 0) {
244 *out = r;
245 return true;
246 }
247 const char *p = s;
248 for (;;) {
249 const char *comma = strchr(p, ',');
250 size_t len = comma ? (size_t)(comma - p) : strlen(p);
251 const char *dash = memchr(p, '-', len);
252 uint64_t a, b;
253 if (dash) {
254 size_t la = (size_t)(dash - p), lb = len - la - 1;
255 if (!num(p, la, &a)) goto fail;
256 if (lb == 0) mj_ranges_insert(&r, a, UINT64_MAX);
257 else {
258 if (!num(dash + 1, lb, &b) || a >= b) goto fail;
259 mj_ranges_insert(&r, a, b);
260 }
261 } else {
262 if (!num(p, len, &a)) goto fail;
263 mj_ranges_add(&r, a);
264 }
265 if (!comma) break;
266 p = comma + 1;
267 }
268 *out = r;
269 return true;
270fail:
271 mj_ranges_free(&r);
272 return bad(s, err);
273}