2 * Copyright (c) 2021, LabN Consulting, L.L.C
4 * This program is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License as published by the Free
6 * Software Foundation; either version 2 of the License, or (at your option)
9 * This program is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
14 * You should have received a copy of the GNU General Public License along
15 * with this program; see the file COPYING; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 static void sl_debug(struct skiplist
*l
)
29 printf("Skiplist %p has max level %d\n", l
, l
->level
);
30 for (i
= l
->level
; i
>= 0; --i
)
31 printf(" @%d: %d\n", i
, l
->level_stats
[i
]);
34 static void *scramble(int i
)
38 result
= (uintptr_t)(i
& 0xff) << 24;
39 result
|= (uintptr_t)i
>> 8;
41 return (void *)result
;
43 #define sampleSize 65536
44 static int sl_test(void)
48 void *keys
[sampleSize
];
52 l
= skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES
, NULL
, NULL
);
54 printf("%s: skiplist_new returned %p\n", __func__
, l
);
56 for (i
= 0; i
< 4; i
++) {
58 for (k
= 0; k
< sampleSize
; k
++) {
60 printf("%s: (%d:%d)\n", __func__
, i
, k
);
61 /* keys[k] = (void *)random(); */
62 keys
[k
] = scramble(k
);
63 if (skiplist_insert(l
, keys
[k
], keys
[k
])) {
65 printf("error in insert #%d,#%d\n", i
, k
);
69 printf("%s: inserts done\n", __func__
);
72 for (k
= 0; k
< sampleSize
; k
++) {
75 printf("[%d:%d]\n", i
, k
);
76 /* keys[k] = (void *)random(); */
77 if (skiplist_search(l
, keys
[k
], &v
)) {
79 printf("error in search #%d,#%d\n", i
, k
);
84 printf("search returned wrong value\n");
87 printf("%s: searches done\n", __func__
);
90 for (k
= 0; k
< sampleSize
; k
++) {
93 printf("<%d:%d>\n", i
, k
);
94 /* keys[k] = (void *)random(); */
95 if (skiplist_delete(l
, keys
[k
], keys
[k
])) {
97 printf("error in delete\n");
99 keys
[k
] = scramble(k
^ 0xf0f0f0f0);
100 if (skiplist_insert(l
, keys
[k
], keys
[k
])) {
102 printf("error in insert #%d,#%d\n", i
, k
);
106 printf("%s: del+inserts done\n", __func__
);
109 for (k
= 0; k
< sampleSize
; k
++) {
112 printf("{%d:%d}\n", i
, k
);
113 /* keys[k] = (void *)random(); */
114 if (skiplist_delete_first(l
)) {
116 printf("error in delete_first\n");
128 int main(int argc
, char **argv
)
130 int errors
= sl_test();