1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * Copyright (c) 2021, LabN Consulting, L.L.C
9 static void sl_debug(struct skiplist
*l
)
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
]);
21 static void *scramble(int i
)
25 result
= (uintptr_t)(i
& 0xff) << 24;
26 result
|= (uintptr_t)i
>> 8;
28 return (void *)result
;
30 #define sampleSize 65536
31 static int sl_test(void)
35 void *keys
[sampleSize
];
39 l
= skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES
, NULL
, NULL
);
41 printf("%s: skiplist_new returned %p\n", __func__
, l
);
43 for (i
= 0; i
< 4; i
++) {
45 for (k
= 0; k
< sampleSize
; k
++) {
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
])) {
52 printf("error in insert #%d,#%d\n", i
, k
);
56 printf("%s: inserts done\n", __func__
);
59 for (k
= 0; k
< sampleSize
; k
++) {
62 printf("[%d:%d]\n", i
, k
);
63 /* keys[k] = (void *)random(); */
64 if (skiplist_search(l
, keys
[k
], &v
)) {
66 printf("error in search #%d,#%d\n", i
, k
);
71 printf("search returned wrong value\n");
74 printf("%s: searches done\n", __func__
);
77 for (k
= 0; k
< sampleSize
; k
++) {
80 printf("<%d:%d>\n", i
, k
);
81 /* keys[k] = (void *)random(); */
82 if (skiplist_delete(l
, keys
[k
], keys
[k
])) {
84 printf("error in delete\n");
86 keys
[k
] = scramble(k
^ 0xf0f0f0f0);
87 if (skiplist_insert(l
, keys
[k
], keys
[k
])) {
89 printf("error in insert #%d,#%d\n", i
, k
);
93 printf("%s: del+inserts done\n", __func__
);
96 for (k
= 0; k
< sampleSize
; k
++) {
99 printf("{%d:%d}\n", i
, k
);
100 /* keys[k] = (void *)random(); */
101 if (skiplist_delete_first(l
)) {
103 printf("error in delete_first\n");
115 int main(int argc
, char **argv
)
117 int errors
= sl_test();