1/* jobs.rs Ranges, as a sorted array. */
2#include "mesh/range_set.h"
3#include "mesh/mt.h"
4
5#include <stdlib.h>
6#include <string.h>
7
8static void insert_at(rs_set *r, size_t i, uint64_t s, uint64_t e) {
9    if (r->n == r->cap) {
10        r->cap = r->cap ? r->cap * 2 : 8;
11        r->s = mt_realloc(r->s, r->cap * sizeof *r->s);
12        r->e = mt_realloc(r->e, r->cap * sizeof *r->e);
13    }
14    memmove(r->s + i + 1, r->s + i, (r->n - i) * sizeof *r->s);
15    memmove(r->e + i + 1, r->e + i, (r->n - i) * sizeof *r->e);
16    r->s[i] = s, r->e[i] = e;
17    r->n++;
18}
19
20static void remove_range(rs_set *r, size_t i, size_t j) {
21    if (i == j) return;
22    memmove(r->s + i, r->s + j, (r->n - j) * sizeof *r->s);
23    memmove(r->e + i, r->e + j, (r->n - j) * sizeof *r->e);
24    r->n -= j - i;
25}
26
27rs_set rs_of(uint64_t s, uint64_t e) {
28    rs_set r = {0};
29    rs_insert(&r, s, e);
30    return r;
31}
32
33bool rs_is_empty(const rs_set *r) { return r->n == 0; }
34
35uint64_t rs_len(const rs_set *r) {
36    uint64_t n = 0;
37    for (size_t i = 0; i < r->n; i++) {
38        uint64_t d = r->e[i] - r->s[i];
39        n = n > UINT64_MAX - d ? UINT64_MAX : n + d;
40    }
41    return n;
42}
43
44size_t rs_count(const rs_set *r) { return r->n; }
45bool rs_first(const rs_set *r, uint64_t *x) { return r->n ? (*x = r->s[0], true) : false; }
46bool rs_end(const rs_set *r, uint64_t *x) { return r->n ? (*x = r->e[r->n - 1], true) : false; }
47
48bool rs_contains(const rs_set *r, uint64_t x) {
49    for (size_t i = r->n; i-- > 0;)
50        if (r->s[i] <= x) return x < r->e[i];
51    return false;
52}
53
54void rs_insert(rs_set *r, uint64_t s, uint64_t e) {
55    if (s >= e) return;
56    /* Every range that overlaps or touches [s, e) merges into it. */
57    size_t i = 0;
58    while (i < r->n && r->e[i] < s) i++;
59    size_t j = i;
60    while (j < r->n && r->s[j] <= e) {
61        if (r->s[j] < s) s = r->s[j];
62        if (r->e[j] > e) e = r->e[j];
63        j++;
64    }
65    remove_range(r, i, j);
66    insert_at(r, i, s, e);
67}
68
69void rs_add(rs_set *r, uint64_t x) { rs_insert(r, x, x == UINT64_MAX ? x : x + 1); }
70
71void rs_union(rs_set *r, const rs_set *o) {
72    for (size_t i = 0; i < o->n; i++) rs_insert(r, o->s[i], o->e[i]);
73}
74
75bool rs_remove(rs_set *r, uint64_t s, uint64_t e) {
76    if (s >= e) return false;
77    bool any = false;
78    for (size_t i = 0; i < r->n;) {
79        uint64_t a = r->s[i], b = r->e[i];
80        if (b <= s || a >= e) {
81            i++;
82            continue;
83        }
84        any = true;
85        remove_range(r, i, i + 1);
86        if (a < s) insert_at(r, i++, a, s);
87        if (b > e) insert_at(r, i++, e, b);
88    }
89    return any;
90}
91
92bool rs_take(rs_set *r, uint64_t x) { return rs_remove(r, x, x == UINT64_MAX ? x : x + 1); }
93
94void rs_subtract(rs_set *r, const rs_set *o) {
95    for (size_t i = 0; i < o->n; i++) rs_remove(r, o->s[i], o->e[i]);
96}
97
98bool rs_eq(const rs_set *a, const rs_set *b) {
99    return a->n == b->n && (!a->n || (!memcmp(a->s, b->s, a->n * sizeof *a->s) && !memcmp(a->e, b->e, a->n * sizeof *a->e)));
100}
101
102rs_set rs_clone(const rs_set *r) {
103    rs_set c = {0};
104    for (size_t i = 0; i < r->n; i++) insert_at(&c, i, r->s[i], r->e[i]);
105    return c;
106}
107
108void rs_free(rs_set *r) {
109    free(r->s);
110    free(r->e);
111    *r = (rs_set){0};
112}