1 /*
2 * Copyright (c) 2019 David Lamparter, for NetDEF, Inc.
3 *
4 * Permission to use, copy, modify, and distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
7 *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15 */
16
17 /* C++ called, they want their templates back */
18 #define item concat(item_, TYPE)
19 #define itm concat(itm_, TYPE)
20 #define head concat(head_, TYPE)
21 #define list concat(TYPE, )
22 #define list_head concat(TYPE, _head)
23 #define list_item concat(TYPE, _item)
24 #define list_cmp concat(TYPE, _cmp)
25 #define list_hash concat(TYPE, _hash)
26 #define list_init concat(TYPE, _init)
27 #define list_fini concat(TYPE, _fini)
28 #define list_const_first concat(TYPE, _const_first)
29 #define list_first concat(TYPE, _first)
30 #define list_const_next concat(TYPE, _const_next)
31 #define list_next concat(TYPE, _next)
32 #define list_next_safe concat(TYPE, _next_safe)
33 #define list_count concat(TYPE, _count)
34 #define list_add concat(TYPE, _add)
35 #define list_add_head concat(TYPE, _add_head)
36 #define list_add_tail concat(TYPE, _add_tail)
37 #define list_add_after concat(TYPE, _add_after)
38 #define list_find concat(TYPE, _find)
39 #define list_find_lt concat(TYPE, _find_lt)
40 #define list_find_gteq concat(TYPE, _find_gteq)
41 #define list_del concat(TYPE, _del)
42 #define list_pop concat(TYPE, _pop)
43
44 #define ts_hash concat(ts_hash_, TYPE)
45
46 #ifndef REALTYPE
47 #define REALTYPE TYPE
48 #endif
49
50 PREDECL(REALTYPE, list)
51 struct item {
52 uint64_t val;
53 struct list_item itm;
54 int scratchpad;
55 };
56
57 #if IS_SORTED(REALTYPE)
58 static int list_cmp(const struct item *a, const struct item *b);
59
60 #if IS_HASH(REALTYPE)
61 static uint32_t list_hash(const struct item *a);
DECLARE(REALTYPE,list,struct item,itm,list_cmp,list_hash)62 DECLARE(REALTYPE, list, struct item, itm, list_cmp, list_hash)
63
64 static uint32_t list_hash(const struct item *a)
65 {
66 #ifdef SHITTY_HASH
67 /* crappy hash to get some hash collisions */
68 return a->val ^ (a->val << 29) ^ 0x55AA0000U;
69 #else
70 return jhash_1word(a->val, 0xdeadbeef);
71 #endif
72 }
73
74 #else
DECLARE(REALTYPE,list,struct item,itm,list_cmp)75 DECLARE(REALTYPE, list, struct item, itm, list_cmp)
76 #endif
77
78 static int list_cmp(const struct item *a, const struct item *b)
79 {
80 if (a->val > b->val)
81 return 1;
82 if (a->val < b->val)
83 return -1;
84 return 0;
85 }
86
87 #else /* !IS_SORTED */
88 DECLARE(REALTYPE, list, struct item, itm)
89 #endif
90
91 #define NITEM 10000
92 struct item itm[NITEM];
93 static struct list_head head = concat(INIT_, REALTYPE)(head);
94
ts_hash(const char * text,const char * expect)95 static void ts_hash(const char *text, const char *expect)
96 {
97 int64_t us = monotime_since(&ref, NULL);
98 SHA256_CTX ctx;
99 struct item *item;
100 unsigned i = 0;
101 uint8_t hash[32];
102 char hashtext[65];
103 uint32_t swap_count, count;
104
105 count = list_count(&head);
106 swap_count = htonl(count);
107
108 SHA256_Init(&ctx);
109 SHA256_Update(&ctx, &swap_count, sizeof(swap_count));
110
111 frr_each (list, &head, item) {
112 struct {
113 uint32_t val_upper, val_lower, index;
114 } hashitem = {
115 htonl(item->val >> 32),
116 htonl(item->val & 0xFFFFFFFFULL),
117 htonl(i),
118 };
119 SHA256_Update(&ctx, &hashitem, sizeof(hashitem));
120 i++;
121 assert(i <= count);
122 }
123 SHA256_Final(hash, &ctx);
124
125 for (i = 0; i < sizeof(hash); i++)
126 sprintf(hashtext + i * 2, "%02x", hash[i]);
127
128 printfrr("%7"PRId64"us %-25s %s%s\n", us, text,
129 expect ? " " : "*", hashtext);
130 if (expect && strcmp(expect, hashtext)) {
131 printfrr("%-21s %s\n", "EXPECTED:", expect);
132 assert(0);
133 }
134 monotime(&ref);
135 }
136 /* hashes will have different item ordering */
137 #if IS_HASH(REALTYPE) || IS_HEAP(REALTYPE)
138 #define ts_hashx(pos, csum) ts_hash(pos, NULL)
139 #else
140 #define ts_hashx(pos, csum) ts_hash(pos, csum)
141 #endif
142
concat(test_,TYPE)143 static void concat(test_, TYPE)(void)
144 {
145 size_t i, j, k, l;
146 struct prng *prng;
147 struct item *item, *prev __attribute__((unused));
148 struct item dummy __attribute__((unused));
149
150 memset(itm, 0, sizeof(itm));
151 for (i = 0; i < NITEM; i++)
152 itm[i].val = i;
153
154 printfrr("%s start\n", str(TYPE));
155 ts_start();
156
157 list_init(&head);
158 assert(list_first(&head) == NULL);
159
160 ts_hash("init", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119");
161
162 #if IS_SORTED(REALTYPE)
163 prng = prng_new(0);
164 k = 0;
165 for (i = 0; i < NITEM; i++) {
166 j = prng_rand(prng) % NITEM;
167 if (itm[j].scratchpad == 0) {
168 list_add(&head, &itm[j]);
169 itm[j].scratchpad = 1;
170 k++;
171 }
172 #if !IS_HEAP(REALTYPE)
173 else
174 assert(list_add(&head, &itm[j]) == &itm[j]);
175 #endif
176 }
177 assert(list_count(&head) == k);
178 assert(list_first(&head) != NULL);
179 ts_hashx("fill", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
180
181 k = 0;
182
183 #if IS_ATOMIC(REALTYPE)
184 struct list_head *chead = &head;
185 struct item *citem, *cprev = NULL;
186
187 frr_each(list, chead, citem) {
188 #else
189 const struct list_head *chead = &head;
190 const struct item *citem, *cprev = NULL;
191
192 frr_each(list_const, chead, citem) {
193 #endif
194
195 #if IS_HASH(REALTYPE) || IS_HEAP(REALTYPE)
196 /* hash table doesn't give sorting */
197 (void)cprev;
198 #else
199 assert(!cprev || cprev->val < citem->val);
200 #endif
201 cprev = citem;
202 k++;
203 }
204 assert(list_count(chead) == k);
205 ts_ref("walk");
206
207 #if IS_UNIQ(REALTYPE)
208 prng_free(prng);
209 prng = prng_new(0);
210
211 for (i = 0; i < NITEM; i++) {
212 j = prng_rand(prng) % NITEM;
213 dummy.val = j;
214 assert(list_find(&head, &dummy) == &itm[j]);
215 }
216 ts_ref("find");
217
218 for (i = 0; i < NITEM; i++) {
219 j = prng_rand(prng) % NITEM;
220 memset(&dummy, 0, sizeof(dummy));
221 dummy.val = j;
222 if (itm[j].scratchpad)
223 assert(list_add(&head, &dummy) == &itm[j]);
224 else {
225 assert(list_add(&head, &dummy) == NULL);
226 assert(list_del(&head, &dummy) != NULL);
227 }
228 }
229 ts_hashx("add-dup", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
230
231 #elif IS_HEAP(REALTYPE)
232 /* heap - partially sorted. */
233 prev = NULL;
234 l = k / 2;
235 for (i = 0; i < l; i++) {
236 item = list_pop(&head);
237 if (prev)
238 assert(prev->val < item->val);
239 item->scratchpad = 0;
240 k--;
241 prev = item;
242 }
243 ts_hash("pop", NULL);
244
245 #else /* !IS_UNIQ(REALTYPE) && !IS_HEAP(REALTYPE) */
246 for (i = 0; i < NITEM; i++) {
247 j = prng_rand(prng) % NITEM;
248 memset(&dummy, 0, sizeof(dummy));
249 dummy.val = j;
250
251 list_add(&head, &dummy);
252 if (itm[j].scratchpad) {
253 struct item *lt, *gteq, dummy2;
254
255 assert(list_next(&head, &itm[j]) == &dummy ||
256 list_next(&head, &dummy) == &itm[j]);
257
258 memset(&dummy2, 0, sizeof(dummy));
259 dummy2.val = j;
260 lt = list_find_lt(&head, &dummy2);
261 gteq = list_find_gteq(&head, &dummy2);
262
263 assert(gteq == &itm[j] || gteq == &dummy);
264 if (lt)
265 assert(list_next(&head, lt) == &itm[j] ||
266 list_next(&head, lt) == &dummy);
267 else
268 assert(list_first(&head) == &itm[j] ||
269 list_first(&head) == &dummy);
270 } else if (list_next(&head, &dummy))
271 assert(list_next(&head, &dummy)->val > j);
272 assert(list_del(&head, &dummy) != NULL);
273 }
274 ts_hash("add-dup+find_{lt,gteq}", "a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
275 #endif
276 #if !IS_HASH(REALTYPE) && !IS_HEAP(REALTYPE)
277 prng_free(prng);
278 prng = prng_new(123456);
279
280 l = 0;
281 for (i = 0; i < NITEM; i++) {
282 struct item *lt, *gteq, *tmp;
283
284 j = prng_rand(prng) % NITEM;
285 dummy.val = j;
286
287 lt = list_find_lt(&head, &dummy);
288 gteq = list_find_gteq(&head, &dummy);
289
290 if (lt) {
291 assert(lt->val < j);
292 tmp = list_next(&head, lt);
293 assert(tmp == gteq);
294 assert(!tmp || tmp->val >= j);
295 } else
296 assert(gteq == list_first(&head));
297
298 if (gteq)
299 assert(gteq->val >= j);
300 }
301 ts_ref("find_{lt,gteq}");
302 #endif /* !IS_HASH */
303
304 prng_free(prng);
305 prng = prng_new(0);
306
307 l = 0;
308 for (i = 0; i < NITEM; i++) {
309 (void)prng_rand(prng);
310 j = prng_rand(prng) % NITEM;
311 if (itm[j].scratchpad == 1) {
312 assert(list_del(&head, &itm[j]) != NULL);
313 itm[j].scratchpad = 0;
314 l++;
315 }
316 }
317 assert(l + list_count(&head) == k);
318 ts_hashx("del", "cb2e5d80f08a803ef7b56c15e981b681adcea214bebc2f55e12e0bfb242b07ca");
319
320 frr_each_safe(list, &head, item) {
321 assert(item->scratchpad != 0);
322
323 if (item->val & 1) {
324 assert(list_del(&head, item) != NULL);
325 item->scratchpad = 0;
326 l++;
327 }
328 }
329 assert(l + list_count(&head) == k);
330 ts_hashx("frr_each_safe+del", "e0beb71dd963a75af05b722b8e71b61b304587d860c8accdc4349067542b86bb");
331
332 #else /* !IS_SORTED */
333 prng = prng_new(0);
334 k = 0;
335 for (i = 0; i < NITEM; i++) {
336 j = prng_rand(prng) % NITEM;
337 if (itm[j].scratchpad == 0) {
338 list_add_tail(&head, &itm[j]);
339 itm[j].scratchpad = 1;
340 k++;
341 }
342 }
343 assert(list_count(&head) == k);
344 assert(list_first(&head) != NULL);
345 ts_hash("fill / add_tail", "eabfcf1413936daaf20965abced95762f45110a6619b84aac7d38481bce4ea19");
346
347 for (i = 0; i < NITEM / 2; i++) {
348 j = prng_rand(prng) % NITEM;
349 if (itm[j].scratchpad == 1) {
350 assert(list_del(&head, &itm[j]) != NULL);
351 itm[j].scratchpad = 0;
352 k--;
353 }
354 }
355 ts_hash("del-prng", "86d568a95eb429dab3162976c5a5f3f75aabc835932cd682aa280b6923549564");
356
357 l = 0;
358 while ((item = list_pop(&head))) {
359 assert(item->scratchpad != 0);
360
361 item->scratchpad = 0;
362 l++;
363 }
364 assert(l == k);
365 assert(list_count(&head) == 0);
366 assert(list_first(&head) == NULL);
367 ts_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119");
368
369 prng_free(prng);
370 prng = prng_new(0x1e5a2d69);
371
372 k = 0;
373 for (i = 0; i < NITEM; i++) {
374 j = prng_rand(prng) % NITEM;
375 if (itm[j].scratchpad == 0) {
376 list_add_head(&head, &itm[j]);
377 itm[j].scratchpad = 1;
378 k++;
379 }
380 }
381 assert(list_count(&head) == k);
382 assert(list_first(&head) != NULL);
383 ts_hash("fill / add_head", "3084d8f8a28b8c756ccc0a92d60d86f6d776273734ddc3f9e1d89526f5ca2795");
384
385 for (i = 0; i < NITEM / 2; i++) {
386 j = prng_rand(prng) % NITEM;
387 if (itm[j].scratchpad == 1) {
388 assert(list_del(&head, &itm[j]) != NULL);
389 itm[j].scratchpad = 0;
390 k--;
391 }
392 }
393 ts_hash("del-prng", "dc916fa7ea4418792c7c8232d74df2887f9975ead4222f4b977be6bc0b52285e");
394
395 l = 0;
396 while ((item = list_pop(&head))) {
397 assert(item->scratchpad != 0);
398
399 item->scratchpad = 0;
400 l++;
401 }
402 assert(l == k);
403 assert(list_count(&head) == 0);
404 assert(list_first(&head) == NULL);
405 ts_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119");
406
407 prng_free(prng);
408 prng = prng_new(0x692d1e5a);
409
410 k = 0;
411 for (i = 0; i < NITEM; i++) {
412 j = prng_rand(prng) % NITEM;
413 if (itm[j].scratchpad == 0) {
414 if (prng_rand(prng) & 1) {
415 list_add_tail(&head, &itm[j]);
416 } else {
417 list_add_head(&head, &itm[j]);
418 }
419 itm[j].scratchpad = 1;
420 k++;
421 }
422 }
423 assert(list_count(&head) == k);
424 assert(list_first(&head) != NULL);
425 ts_hash("fill / add_{head,tail}", "93fa180a575c96e4b6c3775c2de7843ee3254dd6ed5af699bbe155f994114b06");
426
427 for (i = 0; i < NITEM * 3; i++) {
428 int op = prng_rand(prng);
429 j = prng_rand(prng) % NITEM;
430
431 if (op & 1) {
432 /* delete or pop */
433 if (op & 2) {
434 item = list_pop(&head);
435 if (!item)
436 continue;
437 } else {
438 item = &itm[j];
439 if (item->scratchpad == 0)
440 continue;
441 assert(list_del(&head, item) != NULL);
442 }
443 item->scratchpad = 0;
444 k--;
445 } else {
446 item = &itm[j];
447 if (item->scratchpad != 0)
448 continue;
449
450 item->scratchpad = 1;
451 k++;
452
453 switch ((op >> 1) & 1) {
454 case 0:
455 list_add_head(&head, item);
456 break;
457 case 1:
458 list_add_tail(&head, item);
459 break;
460 default:
461 assert(0);
462 }
463 }
464 }
465 assert(list_count(&head) == k);
466 assert(list_first(&head) != NULL);
467 ts_hash("prng add/del", "4909f31d06bb006efca4dfeebddb8de071733ddf502f89b6d532155208bbc6df");
468
469 #if !IS_ATOMIC(REALTYPE)
470 /* variant with add_after */
471
472 for (i = 0; i < NITEM * 3; i++) {
473 int op = prng_rand(prng);
474 j = prng_rand(prng) % NITEM;
475
476 if (op & 1) {
477 /* delete or pop */
478 if (op & 2) {
479 item = list_pop(&head);
480 if (!item)
481 continue;
482 } else {
483 item = &itm[j];
484 if (item->scratchpad == 0)
485 continue;
486 assert(list_del(&head, item) != NULL);
487 }
488 item->scratchpad = 0;
489 k--;
490 } else {
491 item = &itm[j];
492 if (item->scratchpad != 0)
493 continue;
494
495 item->scratchpad = 1;
496 k++;
497
498 switch ((op >> 1) & 3) {
499 case 0:
500 list_add_head(&head, item);
501 break;
502 case 1:
503 list_add_tail(&head, item);
504 break;
505 case 2:
506 case 3:
507 prev = NULL;
508 l = 0;
509 do {
510 j = prng_rand(prng) % NITEM;
511 prev = &itm[j];
512 if (prev->scratchpad == 0
513 || prev == item)
514 prev = NULL;
515 l++;
516 } while (!prev && l < 10);
517 list_add_after(&head, prev, item);
518 break;
519 default:
520 assert(0);
521 }
522 }
523 }
524 assert(list_count(&head) == k);
525 assert(list_first(&head) != NULL);
526 ts_hash("prng add/after/del", "84c5fc83294eabebb9808ccbba32a303c4fca084db87ed1277d2bae1f8c5bee4");
527 #endif
528
529 l = 0;
530 #endif
531
532 while ((item = list_pop(&head))) {
533 assert(item->scratchpad != 0);
534
535 item->scratchpad = 0;
536 l++;
537 }
538 assert(l == k);
539 assert(list_count(&head) == 0);
540 assert(list_first(&head) == NULL);
541 ts_hash("pop", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119");
542
543 list_fini(&head);
544 ts_ref("fini");
545 ts_end();
546 printfrr("%s end\n", str(TYPE));
547 }
548
549 #undef ts_hashx
550
551 #undef item
552 #undef itm
553 #undef head
554 #undef list
555 #undef list_head
556 #undef list_item
557 #undef list_cmp
558 #undef list_hash
559 #undef list_init
560 #undef list_fini
561 #undef list_first
562 #undef list_next
563 #undef list_next_safe
564 #undef list_count
565 #undef list_add
566 #undef list_add_head
567 #undef list_add_tail
568 #undef list_add_after
569 #undef list_find
570 #undef list_find_lt
571 #undef list_find_gteq
572 #undef list_del
573 #undef list_pop
574
575 #undef REALTYPE
576 #undef TYPE
577