1/* jobs.rs's `ranges` test, ported, and the set operations against a bitset over random operations. */
2#include "mesh/jobs/ranges.h"
3#include "mesh/check.h"
4
5#include <stdlib.h>
6#include <string.h>
7
8static void word_is(const mj_ranges *r, const char *want) {
9    char *w = mj_ranges_word_new(r);
10    CHECK_S(w, want);
11    free(w);
12}
13
14static mj_ranges parsed(const char *s) {
15    mj_ranges r = {0};
16    char *err = NULL;
17    if (!mj_ranges_parse(s, &r, &err)) {
18        CHECK(!"parse");
19        free(err);
20    }
21    return r;
22}
23
24static void the_rust_test(void) {
25    mj_ranges r = {0};
26    mj_ranges_insert(&r, 10, 20);
27    mj_ranges_insert(&r, 30, 40);
28    mj_ranges_insert(&r, 20, 25);
29    word_is(&r, "10-25,30-40");
30    mj_ranges_insert(&r, 24, 31);
31    word_is(&r, "10-40");
32    CHECK(mj_ranges_remove(&r, 15, 17));
33    word_is(&r, "10-15,17-40");
34    CHECK(!mj_ranges_remove(&r, 15, 17));
35    CHECK_U(mj_ranges_len(&r), 28);
36    CHECK(mj_ranges_contains(&r, 14) && !mj_ranges_contains(&r, 15) && mj_ranges_contains(&r, 17) && !mj_ranges_contains(&r, 40));
37    uint64_t x;
38    CHECK(mj_ranges_nth(&r, 0, &x) && x == 10);
39    CHECK(mj_ranges_nth(&r, 5, &x) && x == 17);
40    CHECK(!mj_ranges_nth(&r, 28, &x));
41    mj_ranges f = mj_ranges_take_front(&r, 7);
42    word_is(&f, "10-15,17-19");
43    word_is(&r, "19-40");
44    mj_ranges hundred = mj_ranges_of(0, 100), p = parsed("5-10,50,99-200");
45    mj_ranges i = mj_ranges_intersect(&hundred, &p);
46    word_is(&i, "5-10,50-51,99-100");
47    mj_ranges e7 = parsed("7-");
48    CHECK_U(mj_ranges_len(&e7), UINT64_MAX - 7);
49    word_is(&e7, "7-");
50    mj_ranges junk = {0};
51    char *err = NULL;
52    CHECK(!mj_ranges_parse("5-5", &junk, &err));
53    CHECK_S(err, "items \"5-5\": `<n>` (0..n), or `a-b` (half-open), `a-` (endless), `a`, comma-separated");
54    free(err);
55    err = NULL;
56    CHECK(!mj_ranges_parse("x", &junk, &err));
57    free(err);
58    mj_ranges e = parsed("0-");
59    mj_ranges t = mj_ranges_take_front(&e, 3);
60    word_is(&t, "0-3");
61    word_is(&e, "3-");
62    mj_ranges dash = parsed("-");
63    CHECK(mj_ranges_is_empty(&dash));
64    word_is(&dash, "-");
65    mj_ranges u = parsed("1_000-2_000,7");
66    word_is(&u, "7-8,1000-2000");
67    CHECK(!mj_ranges_parse("", &junk, NULL) && !mj_ranges_parse("1,", &junk, NULL) && !mj_ranges_parse("-5", &junk, NULL));
68    CHECK(!mj_ranges_parse("18446744073709551616", &junk, NULL));
69    for (mj_ranges *z[] = {&r, &f, &hundred, &p, &i, &e7, &e, &t, &dash, &u}, **q = z; q < z + 10; q++) mj_ranges_free(*q);
70}
71
72static uint64_t rng = 0x9e3779b97f4a7c15u;
73static uint64_t rnd(uint64_t n) {
74    rng ^= rng << 13;
75    rng ^= rng >> 7;
76    rng ^= rng << 17;
77    return rng % n;
78}
79
80#define N 300
81static void bits_of(const mj_ranges *r, bool *b) {
82    memset(b, 0, N);
83    for (size_t i = 0; i < r->n; i++) {
84        CHECK(r->v[i][0] < r->v[i][1]);
85        if (i) CHECK(r->v[i - 1][1] < r->v[i][0]); /* disjoint and never touching */
86        for (uint64_t x = r->v[i][0]; x < r->v[i][1] && x < N; x++) b[x] = true;
87    }
88}
89
90static void random_ops(void) {
91    mj_ranges r = {0};
92    bool ref[N] = {0}, got[N];
93    for (int step = 0; step < 20000; step++) {
94        uint64_t s = rnd(N), e = s + rnd(20);
95        if (e > N) e = N;
96        switch (rnd(5)) {
97        case 0:
98        case 1:
99            mj_ranges_insert(&r, s, e);
100            for (uint64_t x = s; x < e; x++) ref[x] = true;
101            break;
102        case 2: {
103            bool any = false;
104            for (uint64_t x = s; x < e; x++) any |= ref[x], ref[x] = false;
105            CHECK(mj_ranges_remove(&r, s, e) == any);
106            break;
107        }
108        case 3: {
109            mj_ranges o = mj_ranges_of(s, e), in = mj_ranges_intersect(&r, &o);
110            bits_of(&in, got);
111            for (uint64_t x = 0; x < N; x++) CHECK(got[x] == (ref[x] && x >= s && x < e));
112            mj_ranges_free(&o);
113            mj_ranges_free(&in);
114            break;
115        }
116        default: {
117            uint64_t k = rnd(40), want = 0, n = 0, x;
118            bool has = false;
119            for (uint64_t y = 0; y < N; y++)
120                if (ref[y] && n++ == k) {
121                    want = y;
122                    has = true;
123                    break;
124                }
125            CHECK(mj_ranges_nth(&r, k, &x) == has);
126            if (has) CHECK_U(x, want);
127            CHECK(mj_ranges_contains(&r, s) == ref[s]);
128        }
129        }
130        if (step % 97 == 0) {
131            bits_of(&r, got);
132            uint64_t n = 0;
133            for (int x = 0; x < N; x++) {
134                CHECK(got[x] == ref[x]);
135                n += ref[x];
136            }
137            CHECK_U(mj_ranges_len(&r), n);
138            /* The word form parses back to the same set. */
139            char *w = mj_ranges_word_new(&r);
140            mj_ranges back = {0};
141            CHECK(mj_ranges_parse(w, &back, NULL) && mj_ranges_eq(&back, &r));
142            mj_ranges_free(&back);
143            free(w);
144        }
145    }
146    mj_ranges_free(&r);
147}
148
149int main(void) {
150    the_rust_test();
151    random_ops();
152    return mesh_check_done();
153}