]>
Commit | Line | Data |
---|---|---|
acddc0ed | 1 | // SPDX-License-Identifier: GPL-2.0-or-later |
c324b10f PZ |
2 | /* |
3 | * Copyright (c) 2021, LabN Consulting, L.L.C | |
c324b10f PZ |
4 | */ |
5 | ||
6 | #include <zebra.h> | |
7 | #include <skiplist.h> | |
8 | ||
9 | static void sl_debug(struct skiplist *l) | |
10 | { | |
11 | int i; | |
12 | ||
13 | if (!l) | |
14 | return; | |
15 | ||
16 | printf("Skiplist %p has max level %d\n", l, l->level); | |
17 | for (i = l->level; i >= 0; --i) | |
18 | printf(" @%d: %d\n", i, l->level_stats[i]); | |
19 | } | |
20 | ||
21 | static void *scramble(int i) | |
22 | { | |
23 | uintptr_t result; | |
24 | ||
25 | result = (uintptr_t)(i & 0xff) << 24; | |
26 | result |= (uintptr_t)i >> 8; | |
27 | ||
28 | return (void *)result; | |
29 | } | |
30 | #define sampleSize 65536 | |
31 | static int sl_test(void) | |
32 | { | |
33 | struct skiplist *l; | |
34 | register int i, k; | |
35 | void *keys[sampleSize]; | |
36 | void *v = NULL; | |
37 | int errors = 0; | |
38 | ||
39 | l = skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES, NULL, NULL); | |
40 | ||
41 | printf("%s: skiplist_new returned %p\n", __func__, l); | |
42 | ||
43 | for (i = 0; i < 4; i++) { | |
44 | ||
45 | for (k = 0; k < sampleSize; k++) { | |
46 | if (!(k % 10000)) | |
47 | printf("%s: (%d:%d)\n", __func__, i, k); | |
48 | /* keys[k] = (void *)random(); */ | |
49 | keys[k] = scramble(k); | |
50 | if (skiplist_insert(l, keys[k], keys[k])) { | |
51 | ++errors; | |
52 | printf("error in insert #%d,#%d\n", i, k); | |
53 | } | |
54 | } | |
55 | ||
56 | printf("%s: inserts done\n", __func__); | |
57 | sl_debug(l); | |
58 | ||
59 | for (k = 0; k < sampleSize; k++) { | |
60 | ||
61 | if (!(k % 10000)) | |
62 | printf("[%d:%d]\n", i, k); | |
63 | /* keys[k] = (void *)random(); */ | |
64 | if (skiplist_search(l, keys[k], &v)) { | |
65 | ++errors; | |
66 | printf("error in search #%d,#%d\n", i, k); | |
67 | } | |
68 | ||
69 | if (v != keys[k]) { | |
70 | ++errors; | |
71 | printf("search returned wrong value\n"); | |
72 | } | |
73 | } | |
74 | printf("%s: searches done\n", __func__); | |
75 | ||
76 | ||
77 | for (k = 0; k < sampleSize; k++) { | |
78 | ||
79 | if (!(k % 10000)) | |
80 | printf("<%d:%d>\n", i, k); | |
81 | /* keys[k] = (void *)random(); */ | |
82 | if (skiplist_delete(l, keys[k], keys[k])) { | |
83 | ++errors; | |
84 | printf("error in delete\n"); | |
85 | } | |
86 | keys[k] = scramble(k ^ 0xf0f0f0f0); | |
87 | if (skiplist_insert(l, keys[k], keys[k])) { | |
88 | ++errors; | |
89 | printf("error in insert #%d,#%d\n", i, k); | |
90 | } | |
91 | } | |
92 | ||
93 | printf("%s: del+inserts done\n", __func__); | |
94 | sl_debug(l); | |
95 | ||
96 | for (k = 0; k < sampleSize; k++) { | |
97 | ||
98 | if (!(k % 10000)) | |
99 | printf("{%d:%d}\n", i, k); | |
100 | /* keys[k] = (void *)random(); */ | |
101 | if (skiplist_delete_first(l)) { | |
102 | ++errors; | |
103 | printf("error in delete_first\n"); | |
104 | } | |
105 | } | |
106 | } | |
107 | ||
108 | sl_debug(l); | |
109 | ||
110 | skiplist_free(l); | |
111 | ||
112 | return errors; | |
113 | } | |
114 | ||
115 | int main(int argc, char **argv) | |
116 | { | |
117 | int errors = sl_test(); | |
118 | ||
119 | if (errors) | |
120 | return 1; | |
121 | return 0; | |
122 | } |