==> tests/omap.c <==1/* mesh-omap against a plain sorted array: random puts, deletes, takes, navigation, clones and
2 * split-offs, with one- and three-word keys; values that own memory are released exactly once. */
3#include "mesh/omap.h"
4#include "mesh/check.h"
5
6#include <stdlib.h>
7#include <string.h>
8
9static uint64_t rng = 88172645463325252u;
10static uint64_t rnd(uint64_t n) {
11 rng ^= rng << 13;
12 rng ^= rng >> 7;
13 rng ^= rng << 17;
14 return rng % n;
15}
16
17static long live; /* boxed values alive */
18static void box_free(void *v) {
19 free(*(uint64_t **)v);
20 live--;
21}
22static void box_copy(void *dst, const void *src) {
23 uint64_t *b = malloc(sizeof *b);
24 *b = **(uint64_t *const *)src;
25 *(uint64_t **)dst = b;
26 live++;
27}
28
29/* The reference: keys and values in a sorted array (keys of kw words). */
30typedef struct {
31 uint64_t k[3];
32 uint64_t v;
33} ent;
34static ent ref[4096];
35static size_t nref;
36static unsigned kw;
37
38static int kcmp(const uint64_t *a, const uint64_t *b) {
39 for (unsigned i = 0; i < kw; i++)
40 if (a[i] != b[i]) return a[i] < b[i] ? -1 : 1;
41 return 0;
42}
43static long ref_find(const uint64_t *k) {
44 for (size_t i = 0; i < nref; i++)
45 if (kcmp(ref[i].k, k) == 0) return (long)i;
46 return -1;
47}
48static void ref_put(const uint64_t *k, uint64_t v) {
49 long i = ref_find(k);
50 if (i >= 0) {
51 ref[i].v = v;
52 return;
53 }
54 size_t at = 0;
55 while (at < nref && kcmp(ref[at].k, k) < 0) at++;
56 memmove(&ref[at + 1], &ref[at], (nref - at) * sizeof(ent));
57 memset(&ref[at], 0, sizeof(ent));
58 memcpy(ref[at].k, k, 8 * kw);
59 ref[at].v = v;
60 nref++;
61}
62static void ref_del(const uint64_t *k) {
63 long i = ref_find(k);
64 if (i < 0) return;
65 memmove(&ref[i], &ref[i + 1], (nref - (size_t)i - 1) * sizeof(ent));
66 nref--;
67}
68
69static void key(uint64_t *k) {
70 for (unsigned i = 0; i < kw; i++) k[i] = rnd(kw == 1 ? 600 : 6);
71}
72
73static void same(const momap *m) {
74 CHECK_U(momap_len(m), nref);
75 uint64_t k[3];
76 size_t i = 0;
77 for (uint64_t **v = momap_first(m, k); v; v = momap_next(m, k, k), i++) {
78 if (!CHECK(i < nref)) return;
79 CHECK(kcmp(k, ref[i].k) == 0);
80 CHECK_U(**v, ref[i].v);
81 }
82 CHECK_U(i, nref);
83 /* The cursor walks the same entries in the same order. */
84 momap_iter it;
85 momap_iter_init(&it, m);
86 const uint64_t *ik;
87 i = 0;
88 for (uint64_t **v = momap_iter_next(&it, &ik); v; v = momap_iter_next(&it, &ik), i++) {
89 if (!CHECK(i < nref)) break;
90 CHECK(kcmp(ik, ref[i].k) == 0 && **v == ref[i].v);
91 }
92 CHECK_U(i, nref);
93 i = nref;
94 for (uint64_t **v = momap_last(m, k); v; v = momap_prev(m, k, k)) {
95 i--;
96 CHECK(kcmp(k, ref[i].k) == 0);
97 }
98 CHECK_U(i, 0);
99}
100
101static void run(unsigned words) {
102 kw = words;
103 nref = 0;
104 momap *m = momap_new(kw, sizeof(uint64_t *), box_free, box_copy);
105 for (int step = 0; step < 6000; step++) {
106 uint64_t k[3] = {0, 0, 0};
107 key(k);
108 switch (rnd(6)) {
109 case 0:
110 case 1:
111 case 2: {
112 bool fresh;
113 uint64_t **v = momap_put(m, k, &fresh);
114 CHECK(fresh == (ref_find(k) < 0));
115 if (fresh) {
116 *v = malloc(sizeof **v);
117 live++;
118 }
119 **v = (uint64_t)step;
120 ref_put(k, (uint64_t)step);
121 break;
122 }
123 case 3: CHECK(momap_del(m, k) == (ref_find(k) >= 0)); ref_del(k); break;
124 case 4: {
125 uint64_t *out = NULL;
126 bool had = ref_find(k) >= 0;
127 CHECK(momap_take(m, k, &out) == had);
128 if (had) {
129 CHECK_U(*out, ref[ref_find(k)].v);
130 free(out);
131 live--;
132 }
133 ref_del(k);
134 break;
135 }
136 default: {
137 /* Navigation around k. */
138 uint64_t got[3];
139 long fl = -1, ce = -1, nx = -1, pv = -1;
140 for (size_t i = 0; i < nref; i++) {
141 int c = kcmp(ref[i].k, k);
142 if (c <= 0) fl = (long)i;
143 if (c < 0) pv = (long)i;
144 if (c >= 0 && ce < 0) ce = (long)i;
145 if (c > 0 && nx < 0) nx = (long)i;
146 }
147 uint64_t **v = momap_floor(m, k, got);
148 CHECK((v != NULL) == (fl >= 0));
149 if (v && fl >= 0) CHECK(kcmp(got, ref[fl].k) == 0);
150 v = momap_ceil(m, k, got);
151 CHECK((v != NULL) == (ce >= 0));
152 if (v && ce >= 0) CHECK(kcmp(got, ref[ce].k) == 0);
153 v = momap_next(m, k, got);
154 CHECK((v != NULL) == (nx >= 0));
155 if (v && nx >= 0) CHECK(kcmp(got, ref[nx].k) == 0);
156 v = momap_prev(m, k, got);
157 CHECK((v != NULL) == (pv >= 0));
158 if (v && pv >= 0) CHECK(kcmp(got, ref[pv].k) == 0);
159 }
160 }
161 if (step % 500 == 0) same(m);
162 }
163 same(m);
164 CHECK_I(live, (long)nref);
165 /* A clone is deep and equal; changing it leaves the original alone. */
166 momap *c = momap_clone(m);
167 CHECK_I(live, 2 * (long)nref);
168 same(c);
169 momap_clear(c);
170 CHECK_U(momap_len(c), 0);
171 same(m);
172 momap_free(c);
173 /* split_off: everything >= at moves. */
174 uint64_t at[3] = {300, 3, 3};
175 size_t below = 0;
176 for (size_t i = 0; i < nref; i++)
177 if (kcmp(ref[i].k, at) < 0) below++;
178 momap *hi = momap_split_off(m, at);
179 CHECK_U(momap_len(m), below);
180 CHECK_U(momap_len(hi), nref - below);
181 uint64_t k[3];
182 if (momap_len(hi)) {
183 CHECK(momap_first(hi, k) != NULL);
184 CHECK(kcmp(k, at) >= 0);
185 }
186 if (momap_len(m)) {
187 CHECK(momap_last(m, k) != NULL);
188 CHECK(kcmp(k, at) < 0);
189 }
190 momap_free(hi);
191 momap_free(m);
192 CHECK_I(live, 0);
193}
194
195int main(void) {
196 run(1);
197 run(3);
198 /* Plain values: no callbacks, byte copies. */
199 momap *m = momap_new(1, sizeof(uint32_t), NULL, NULL);
200 for (uint32_t i = 0; i < 1000; i++) *(uint32_t *)momap_put1(m, (i * 7919u) % 1000, NULL) = i;
201 CHECK_U(momap_len(m), 1000);
202 uint64_t k = 0;
203 uint32_t n = 0;
204 for (uint32_t *v = momap_first(m, &k); v; v = momap_next(m, &k, &k)) CHECK_U(k, n++);
205 momap *c = momap_clone(m);
206 for (uint64_t i = 0; i < 1000; i += 2) CHECK(momap_del1(c, i));
207 CHECK_U(momap_len(c), 500);
208 CHECK_U(momap_len(m), 1000);
209 CHECK(momap_get1(c, 2) == NULL && momap_get1(m, 2) != NULL);
210 momap_free(c);
211 momap_free(m);
212 return mesh_check_done();
213}