|
1
|
/* skipset.h -- set operations using a skiplist |
|
2
|
// Copyright (C) 2024-2026 Mark Adler |
|
3
|
// See MiniZip_info.txt for the license. |
|
4
|
|
|
5
|
// This implements a skiplist set, i.e. just keys, no data, with ~O(log n) time |
|
6
|
// insert and search operations. The application defines the type of a key, and |
|
7
|
// provides a function to compare two keys. |
|
8
|
|
|
9
|
// This header is not definitions of functions found in another source file -- |
|
10
|
// it creates the set functions, with the application's key type, right where |
|
11
|
// the #include is. Before this header is #included, these must be defined: |
|
12
|
// |
|
13
|
// 1. A macro or typedef for set_key_t, the type of a key. |
|
14
|
// 2. A macro or function set_cmp(a, b) to compare two keys. The return values |
|
15
|
// are < 0 for a < b, 0 for a == b, and > 0 for a > b. |
|
16
|
// 3. A macro or function set_drop(s, k) to release the key k's resources, if |
|
17
|
// any, when doing a set_end() or set_clear(). s is a pointer to the set |
|
18
|
// that key is in, for use with set_free() if desired. |
|
19
|
// |
|
20
|
// Example usage: |
|
21
|
// |
|
22
|
// typedef int set_key_t; |
|
23
|
// #define set_cmp(a, b) ((a) < (b) ? -1 : (a) == (b) ? 0 : 1) |
|
24
|
// #define set_drop(s, k) |
|
25
|
// #include "skipset.h" |
|
26
|
// |
|
27
|
// int test(void) { // return 0: good, 1: bad, -1: out of memory |
|
28
|
// set_t set; |
|
29
|
// if (setjmp(set.env)) |
|
30
|
// return -1; |
|
31
|
// set_start(&set); |
|
32
|
// set_insert(&set, 2); |
|
33
|
// set_insert(&set, 1); |
|
34
|
// set_insert(&set, 7); |
|
35
|
// int bad = !set_found(&set, 2); |
|
36
|
// bad = bad || set_found(&set, 5); |
|
37
|
// set_end(&set); |
|
38
|
// return bad; |
|
39
|
// } |
|
40
|
// |
|
41
|
// Interface summary (see more details below): |
|
42
|
// - set_t is the type of the set being operated on (a set_t pointer is passed) |
|
43
|
// - set_start() initializes a new, empty set (initialize set.env first) |
|
44
|
// - set_insert() inserts a new key into the set, or not if it's already there |
|
45
|
// - set_found() determines whether or not a key is in the set |
|
46
|
// - set_end() ends the use of the set, freeing all memory |
|
47
|
// - set_clear() empties the set, equivalent to set_end() and then set_start() |
|
48
|
// - set_ok() checks if set appears to be usable, i.e. started and not ended |
|
49
|
// |
|
50
|
// Auxiliary functions available to the application: |
|
51
|
// - set_alloc() allocates memory with optional tracking (#define SET_TRACK) |
|
52
|
// - set_free() deallocates memory allocated by set_alloc() |
|
53
|
// - set_rand() returns 32 random bits (seeded by set_start()) */ |
|
54
|
|
|
55
|
#ifndef SKIPSET_H |
|
56
|
#define SKIPSET_H |
|
57
|
|
|
58
|
#include <stdlib.h> /* realloc(), free(), NULL, size_t */ |
|
59
|
#include <stddef.h> /* ptrdiff_t */ |
|
60
|
#include <setjmp.h> /* jmp_buf, longjmp() */ |
|
61
|
#include <errno.h> /* ENOMEM */ |
|
62
|
#include <time.h> /* time(), clock() */ |
|
63
|
#include <assert.h> /* assert.h */ |
|
64
|
#include "ints.h" /* i16_t, ui32_t, ui64_t */ |
|
65
|
|
|
66
|
/* Structures and functions below noted as "--private--" should not be used by |
|
67
|
// the application. set_t is partially private and partially public -- see the |
|
68
|
// comments there. |
|
69
|
|
|
70
|
// There is no POSIX random() in MSVC, and rand() is awful. For portability, we |
|
71
|
// cannot rely on a library function for random numbers. Instead we use the |
|
72
|
// fast and effective algorithm below, invented by Melissa O'Neill. |
|
73
|
|
|
74
|
// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / www.pcg-random.org |
|
75
|
// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website) |
|
76
|
// --private-- Random number generator state. */ |
|
77
|
typedef struct { |
|
78
|
ui64_t state; /* 64-bit generator state */ |
|
79
|
ui64_t inc; /* 63-bit sequence id */ |
|
80
|
} set_rand_t; |
|
81
|
/* --private-- Initialize the state *gen using seed and seq. seed seeds the |
|
82
|
// advancing 64-bit state. seq is a sequence selection constant. */ |
|
83
|
void set_seed(set_rand_t *gen, ui64_t seed, ui64_t seq) { |
|
84
|
gen->inc = (seq << 1) | 1; |
|
85
|
gen->state = (seed + gen->inc) * 6364136223846793005ULL + gen->inc; |
|
86
|
} |
|
87
|
/* Start a unique random number sequence using bits from noise sources. */ |
|
88
|
void set_uniq(set_rand_t *gen, const void *ptr) { |
|
89
|
set_seed(gen, ((ui64_t)(ptrdiff_t)ptr << 32) ^ |
|
90
|
((ui64_t)time(NULL) << 12) ^ clock(), 0); |
|
91
|
} |
|
92
|
/* Return 32 random bits, advancing the state *gen. */ |
|
93
|
ui32_t set_rand(set_rand_t *gen) { |
|
94
|
ui64_t state = gen->state; |
|
95
|
gen->state = state * 6364136223846793005ULL + gen->inc; |
|
96
|
ui32_t mix = (ui32_t)(((state >> 18) ^ state) >> 27); |
|
97
|
int rot = state >> 59; |
|
98
|
return (mix >> rot) | (mix << ((-rot) & 31)); |
|
99
|
} |
|
100
|
/* End of PCG32 code. */ |
|
101
|
|
|
102
|
/* --private-- Linked-list node. */ |
|
103
|
typedef struct set_node_s set_node_t; |
|
104
|
struct set_node_s { |
|
105
|
set_key_t key; /* the key (not used for head or path) */ |
|
106
|
i16_t size; /* number of allocated pointers in right[] */ |
|
107
|
i16_t fill; /* number of pointers in right[] filled in */ |
|
108
|
set_node_t **right; /* pointer for each level, each to the right */ |
|
109
|
}; |
|
110
|
|
|
111
|
/* A set. The application sets env, may use gen with set_rand(), and may read |
|
112
|
// allocs and memory. The remaining variables are --private-- . */ |
|
113
|
typedef struct set_s { |
|
114
|
set_node_t *head; /* skiplist head -- no key, just links */ |
|
115
|
set_node_t *path; /* right[] is path to key from set_found() */ |
|
116
|
set_node_t *node; /* node under construction, in case of longjmp() */ |
|
117
|
i16_t depth; /* maximum depth of the skiplist */ |
|
118
|
ui64_t ran; /* a precious trove of random bits */ |
|
119
|
set_rand_t gen; /* random number generator state */ |
|
120
|
jmp_buf env; /* setjmp() environment for allocation errors */ |
|
121
|
#ifdef SET_TRACK |
|
122
|
size_t allocs; /* number of allocations */ |
|
123
|
size_t memory; /* total amount of allocated memory (>= requests) */ |
|
124
|
#endif |
|
125
|
} set_t; |
|
126
|
|
|
127
|
/* Memory allocation and deallocation. set_alloc(set, ptr, size) returns a |
|
128
|
// pointer to an allocation of size bytes if ptr is NULL, or the previous |
|
129
|
// allocation ptr resized to size bytes. set_alloc() will never return NULL. |
|
130
|
// set_free(set, ptr) frees an allocation created by set_alloc(). These may be |
|
131
|
// used by the application. e.g. if allocation tracking is desired. */ |
|
132
|
#ifdef SET_TRACK |
|
133
|
/* Track the number of allocations and the total backing memory size. */ |
|
134
|
# if defined(_WIN32) |
|
135
|
# include <malloc.h> |
|
136
|
# define SET_ALLOC_SIZE(ptr) _msize(ptr) |
|
137
|
# elif defined(__MACH__) |
|
138
|
# include <malloc/malloc.h> |
|
139
|
# define SET_ALLOC_SIZE(ptr) malloc_size(ptr) |
|
140
|
# elif defined(__linux__) |
|
141
|
# include <malloc.h> |
|
142
|
# define SET_ALLOC_SIZE(ptr) malloc_usable_size(ptr) |
|
143
|
# elif defined(__FreeBSD__) |
|
144
|
# include <malloc_np.h> |
|
145
|
# define SET_ALLOC_SIZE(ptr) malloc_usable_size(ptr) |
|
146
|
# elif defined(__NetBSD__) |
|
147
|
# include <jemalloc/jemalloc.h> |
|
148
|
# define SET_ALLOC_SIZE(ptr) malloc_usable_size(ptr) |
|
149
|
# else // e.g. OpenBSD |
|
150
|
# define SET_ALLOC_SIZE(ptr) 0 |
|
151
|
# endif |
|
152
|
// With tracking. |
|
153
|
void *set_alloc(set_t *set, void *ptr, size_t size) { |
|
154
|
size_t had = ptr == NULL ? 0 : SET_ALLOC_SIZE(ptr); |
|
155
|
void *mem = realloc(ptr, size); |
|
156
|
if (mem == NULL) |
|
157
|
longjmp(set->env, ENOMEM); |
|
158
|
set->allocs += ptr == NULL; |
|
159
|
set->memory += SET_ALLOC_SIZE(mem) - had; |
|
160
|
return mem; |
|
161
|
} |
|
162
|
void set_free(set_t *set, void *ptr) { |
|
163
|
if (ptr != NULL) { |
|
164
|
set->allocs--; |
|
165
|
set->memory -= SET_ALLOC_SIZE(ptr); |
|
166
|
free(ptr); |
|
167
|
} |
|
168
|
} |
|
169
|
#else |
|
170
|
/* Without tracking. */ |
|
171
|
void *set_alloc(set_t *set, void *ptr, size_t size) { |
|
172
|
void *mem = realloc(ptr, size); |
|
173
|
if (mem == NULL) |
|
174
|
longjmp(set->env, ENOMEM); |
|
175
|
return mem; |
|
176
|
} |
|
177
|
void set_free(set_t *set, void *ptr) { |
|
178
|
(void)set; |
|
179
|
free(ptr); |
|
180
|
} |
|
181
|
#endif |
|
182
|
|
|
183
|
/* --private-- Grow node's array right[] as needed to be able to hold at least |
|
184
|
// want links. If fill is true, assure that the first want links are filled in, |
|
185
|
// setting them to set->head if not previously filled in. Otherwise it is |
|
186
|
// assumed that the first want links are about to be filled in. */ |
|
187
|
void set_grow(set_t *set, set_node_t *node, int want, int fill) { |
|
188
|
if (node->size < want) { |
|
189
|
int more = node->size ? node->size : 1; |
|
190
|
while (more < want) |
|
191
|
more <<= 1; |
|
192
|
node->right = set_alloc(set, node->right, |
|
193
|
(size_t)more * sizeof(set_node_t *)); |
|
194
|
node->size = (i16_t)more; |
|
195
|
} |
|
196
|
int i; |
|
197
|
if (fill) |
|
198
|
for (i = node->fill; i < want; i++) |
|
199
|
node->right[i] = set->head; |
|
200
|
node->fill = (i16_t)want; |
|
201
|
} |
|
202
|
|
|
203
|
/* --private-- Return a new node. key is left uninitialized. */ |
|
204
|
set_node_t *set_node(set_t *set) { |
|
205
|
set_node_t *node = set_alloc(set, NULL, sizeof(set_node_t)); |
|
206
|
node->size = 0; |
|
207
|
node->fill = 0; |
|
208
|
node->right = NULL; |
|
209
|
return node; |
|
210
|
} |
|
211
|
|
|
212
|
/* --private-- Free the list linked from head, along with the keys. */ |
|
213
|
void set_sweep(set_t *set) { |
|
214
|
set_node_t *step = set->head->right[0]; |
|
215
|
while (step != set->head) { |
|
216
|
set_node_t *next = step->right[0]; /* save link to next node */ |
|
217
|
set_drop(set, step->key); |
|
218
|
set_free(set, step->right); |
|
219
|
set_free(set, step); |
|
220
|
step = next; |
|
221
|
} |
|
222
|
} |
|
223
|
|
|
224
|
/* Initialize a new set. set->env must be initialized using setjmp() before |
|
225
|
// set_start() is called. A longjmp(set->env, ENOMEM) will be used to handle a |
|
226
|
// memory allocation failure during any of the operations. (See setjmp.h and |
|
227
|
// errno.h.) The set can still be used if this happens, assuming that it didn't |
|
228
|
// happen during set_start(). Whether set_start() completed or not, set_end() |
|
229
|
// can be used to free the set's memory after a longjmp(). */ |
|
230
|
void set_start(set_t *set) { |
|
231
|
#ifdef SET_TRACK |
|
232
|
set->allocs = 0; |
|
233
|
set->memory = 0; |
|
234
|
#endif |
|
235
|
set->head = set->path = set->node = NULL; /* in case set_node() fails */ |
|
236
|
set->path = set_node(set); |
|
237
|
set->head = set_node(set); |
|
238
|
set_grow(set, set->head, 1, 1); /* one link back to head for an empty set */ |
|
239
|
*(unsigned char *)&set->head->key = 137; /* set id */ |
|
240
|
set->depth = 0; |
|
241
|
set_uniq(&set->gen, set); |
|
242
|
set->ran = 1; |
|
243
|
} |
|
244
|
|
|
245
|
/* Return true if *set appears to be in a usable state. If *set has been zeroed |
|
246
|
// out, then set_ok(set) will be false and set_end(set) will be safe. */ |
|
247
|
int set_ok(set_t *set) { |
|
248
|
return set->head != NULL && |
|
249
|
set->head->right != NULL && |
|
250
|
*(unsigned char *)&set->head->key == 137; |
|
251
|
} |
|
252
|
|
|
253
|
/* Empty the set. This frees the memory used for the previous set contents. |
|
254
|
// After set_clear(), *set is ready for use, as if after a set_start(). */ |
|
255
|
void set_clear(set_t *set) { |
|
256
|
assert(set_ok(set) && "improper use"); |
|
257
|
|
|
258
|
/* Free all the keys and their nodes. */ |
|
259
|
set_sweep(set); |
|
260
|
|
|
261
|
/* Leave the head and path allocations as is. Clear their contents, with |
|
262
|
// head pointing to itself and setting depth to zero, for an empty set. */ |
|
263
|
set->head->right[0] = set->head; |
|
264
|
set->head->fill = 1; |
|
265
|
set->path->fill = 0; |
|
266
|
set->depth = 0; |
|
267
|
} |
|
268
|
|
|
269
|
/* Done using the set -- free all allocations. The only operation on *set |
|
270
|
// permitted after this is set_start(). Though another set_end() would do no |
|
271
|
// harm. This can be done at any time after a set_start(), or after a longjmp() |
|
272
|
// on any allocation failure, including during a set_start(). */ |
|
273
|
void set_end(set_t *set) { |
|
274
|
if (set->head != NULL) { |
|
275
|
/* Empty the set and free the head node. */ |
|
276
|
if (set->head->right != NULL) { |
|
277
|
set_sweep(set); |
|
278
|
set_free(set, set->head->right); |
|
279
|
} |
|
280
|
set_free(set, set->head); |
|
281
|
set->head = NULL; |
|
282
|
} |
|
283
|
if (set->path != NULL) { |
|
284
|
/* Free the path work area. */ |
|
285
|
set_free(set, set->path->right); |
|
286
|
set_free(set, set->path); |
|
287
|
set->path = NULL; |
|
288
|
} |
|
289
|
if (set->node != NULL) { |
|
290
|
/* Free the node that was under construction when longjmp() hit. */ |
|
291
|
set_drop(set, set->node->key); |
|
292
|
set_free(set, set->node->right); |
|
293
|
set_free(set, set->node); |
|
294
|
set->node = NULL; |
|
295
|
} |
|
296
|
} |
|
297
|
|
|
298
|
/* Look for key. Return 1 if found or 0 if not. This also puts the path to get |
|
299
|
// there in set->path, for use by set_insert(). */ |
|
300
|
int set_found(set_t *set, set_key_t key) { |
|
301
|
assert(set_ok(set) && "improper use"); |
|
302
|
|
|
303
|
/* Start at depth and work down and right as determined by key comparisons. */ |
|
304
|
set_node_t *head = set->head, *here = head; |
|
305
|
int i = set->depth; |
|
306
|
set_grow(set, set->path, i + 1, 0); |
|
307
|
do { |
|
308
|
while (here->right[i] != head && |
|
309
|
set_cmp(here->right[i]->key, key) < 0) |
|
310
|
here = here->right[i]; |
|
311
|
set->path->right[i] = here; |
|
312
|
} while (i--); |
|
313
|
|
|
314
|
/* See if the key matches. */ |
|
315
|
here = here->right[0]; |
|
316
|
return here != head && set_cmp(here->key, key) == 0; |
|
317
|
} |
|
318
|
|
|
319
|
/* Insert the key key. Return 0 on success, or 1 if key is already in the set. */ |
|
320
|
int set_insert(set_t *set, set_key_t key) { |
|
321
|
assert(set_ok(set) && "improper use"); |
|
322
|
|
|
323
|
if (set_found(set, key)) |
|
324
|
/* That key is already in the set. */ |
|
325
|
return 1; |
|
326
|
|
|
327
|
/* Randomly generate a new level-- level 0 with probability 1/2, 1 with |
|
328
|
// probability 1/4, 2 with probability 1/8, etc. */ |
|
329
|
int level = 0; |
|
330
|
for (;;) { |
|
331
|
if (set->ran == 1) |
|
332
|
/* Ran out. Get another 32 random bits. */ |
|
333
|
set->ran = set_rand(&set->gen) | (1ULL << 32); |
|
334
|
int bit = set->ran & 1; |
|
335
|
set->ran >>= 1; |
|
336
|
if (bit) |
|
337
|
break; |
|
338
|
assert(level < 32767 && |
|
339
|
"Overhead, without any fuss, the stars were going out."); |
|
340
|
level++; |
|
341
|
} |
|
342
|
if (level > set->depth) { |
|
343
|
/* The maximum depth is now deeper. Update the structures. */ |
|
344
|
set_grow(set, set->path, level + 1, 1); |
|
345
|
set_grow(set, set->head, level + 1, 1); |
|
346
|
set->depth = (i16_t)level; |
|
347
|
} |
|
348
|
|
|
349
|
/* Make a new node for the provided key, and insert it in the lists up to |
|
350
|
// and including level. */ |
|
351
|
set->node = set_node(set); |
|
352
|
set->node->key = key; |
|
353
|
set_grow(set, set->node, level + 1, 0); |
|
354
|
int i; |
|
355
|
for (i = 0; i <= level; i++) { |
|
356
|
set->node->right[i] = set->path->right[i]->right[i]; |
|
357
|
set->path->right[i]->right[i] = set->node; |
|
358
|
} |
|
359
|
set->node = NULL; |
|
360
|
return 0; |
|
361
|
} |
|
362
|
|
|
363
|
#else |
|
364
|
#error ** another skiplist set already created here |
|
365
|
/* Would need to implement a prefix in order to support multiple sets. */ |
|
366
|
#endif |
|
367
|
|