aboutsummaryrefslogtreecommitdiff
path: root/contrib/minizip/skipset.h
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/minizip/skipset.h')
-rw-r--r--contrib/minizip/skipset.h144
1 files changed, 72 insertions, 72 deletions
diff --git a/contrib/minizip/skipset.h b/contrib/minizip/skipset.h
index 5e648b9..9f0aad6 100644
--- a/contrib/minizip/skipset.h
+++ b/contrib/minizip/skipset.h
@@ -1,4 +1,4 @@
1// skipset.h -- set operations using a skiplist 1/* skipset.h -- set operations using a skiplist
2// Copyright (C) 2024 Mark Adler 2// Copyright (C) 2024 Mark Adler
3// See MiniZip_info.txt for the license. 3// See MiniZip_info.txt for the license.
4 4
@@ -50,20 +50,20 @@
50// Auxiliary functions available to the application: 50// Auxiliary functions available to the application:
51// - set_alloc() allocates memory with optional tracking (#define SET_TRACK) 51// - set_alloc() allocates memory with optional tracking (#define SET_TRACK)
52// - set_free() deallocates memory allocated by set_alloc() 52// - set_free() deallocates memory allocated by set_alloc()
53// - set_rand() returns 32 random bits (seeded by set_start()) 53// - set_rand() returns 32 random bits (seeded by set_start()) */
54 54
55#ifndef SKIPSET_H 55#ifndef SKIPSET_H
56#define SKIPSET_H 56#define SKIPSET_H
57 57
58#include <stdlib.h> // realloc(), free(), NULL, size_t 58#include <stdlib.h> /* realloc(), free(), NULL, size_t */
59#include <stddef.h> // ptrdiff_t 59#include <stddef.h> /* ptrdiff_t */
60#include <setjmp.h> // jmp_buf, longjmp() 60#include <setjmp.h> /* jmp_buf, longjmp() */
61#include <errno.h> // ENOMEM 61#include <errno.h> /* ENOMEM */
62#include <time.h> // time(), clock() 62#include <time.h> /* time(), clock() */
63#include <assert.h> // assert.h 63#include <assert.h> /* assert.h */
64#include "ints.h" // i16_t, ui32_t, ui64_t 64#include "ints.h" /* i16_t, ui32_t, ui64_t */
65 65
66// Structures and functions below noted as "--private--" should not be used by 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 67// the application. set_t is partially private and partially public -- see the
68// comments there. 68// comments there.
69 69
@@ -73,18 +73,18 @@
73 73
74// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / www.pcg-random.org 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) 75// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)
76// --private-- Random number generator state. 76// --private-- Random number generator state. */
77typedef struct { 77typedef struct {
78 ui64_t state; // 64-bit generator state 78 ui64_t state; /* 64-bit generator state */
79 ui64_t inc; // 63-bit sequence id 79 ui64_t inc; /* 63-bit sequence id */
80} set_rand_t; 80} set_rand_t;
81// --private-- Initialize the state *gen using seed and seq. seed seeds the 81/* --private-- Initialize the state *gen using seed and seq. seed seeds the
82// advancing 64-bit state. seq is a sequence selection constant. 82// advancing 64-bit state. seq is a sequence selection constant. */
83void set_seed(set_rand_t *gen, ui64_t seed, ui64_t seq) { 83void set_seed(set_rand_t *gen, ui64_t seed, ui64_t seq) {
84 gen->inc = (seq << 1) | 1; 84 gen->inc = (seq << 1) | 1;
85 gen->state = (seed + gen->inc) * 6364136223846793005ULL + gen->inc; 85 gen->state = (seed + gen->inc) * 6364136223846793005ULL + gen->inc;
86} 86}
87// Return 32 random bits, advancing the state *gen. 87/* Return 32 random bits, advancing the state *gen. */
88ui32_t set_rand(set_rand_t *gen) { 88ui32_t set_rand(set_rand_t *gen) {
89 ui64_t state = gen->state; 89 ui64_t state = gen->state;
90 gen->state = state * 6364136223846793005ULL + gen->inc; 90 gen->state = state * 6364136223846793005ULL + gen->inc;
@@ -92,40 +92,40 @@ ui32_t set_rand(set_rand_t *gen) {
92 int rot = state >> 59; 92 int rot = state >> 59;
93 return (mix >> rot) | (mix << ((-rot) & 31)); 93 return (mix >> rot) | (mix << ((-rot) & 31));
94} 94}
95// End of PCG32 code. 95/* End of PCG32 code. */
96 96
97// --private-- Linked-list node. 97/* --private-- Linked-list node. */
98typedef struct set_node_s set_node_t; 98typedef struct set_node_s set_node_t;
99struct set_node_s { 99struct set_node_s {
100 set_key_t key; // the key (not used for head or path) 100 set_key_t key; /* the key (not used for head or path) */
101 i16_t size; // number of allocated pointers in right[] 101 i16_t size; /* number of allocated pointers in right[] */
102 i16_t fill; // number of pointers in right[] filled in 102 i16_t fill; /* number of pointers in right[] filled in */
103 set_node_t **right; // pointer for each level, each to the right 103 set_node_t **right; /* pointer for each level, each to the right */
104}; 104};
105 105
106// A set. The application sets env, may use gen with set_rand(), and may read 106/* A set. The application sets env, may use gen with set_rand(), and may read
107// allocs and memory. The remaining variables are --private-- . 107// allocs and memory. The remaining variables are --private-- . */
108typedef struct set_s { 108typedef struct set_s {
109 set_node_t *head; // skiplist head -- no key, just links 109 set_node_t *head; /* skiplist head -- no key, just links */
110 set_node_t *path; // right[] is path to key from set_found() 110 set_node_t *path; /* right[] is path to key from set_found() */
111 set_node_t *node; // node under construction, in case of longjmp() 111 set_node_t *node; /* node under construction, in case of longjmp() */
112 i16_t depth; // maximum depth of the skiplist 112 i16_t depth; /* maximum depth of the skiplist */
113 ui64_t ran; // a precious trove of random bits 113 ui64_t ran; /* a precious trove of random bits */
114 set_rand_t gen; // random number generator state 114 set_rand_t gen; /* random number generator state */
115 jmp_buf env; // setjmp() environment for allocation errors 115 jmp_buf env; /* setjmp() environment for allocation errors */
116#ifdef SET_TRACK 116#ifdef SET_TRACK
117 size_t allocs; // number of allocations 117 size_t allocs; /* number of allocations */
118 size_t memory; // total amount of allocated memory (>= requests) 118 size_t memory; /* total amount of allocated memory (>= requests) */
119#endif 119#endif
120} set_t; 120} set_t;
121 121
122// Memory allocation and deallocation. set_alloc(set, ptr, size) returns a 122/* Memory allocation and deallocation. set_alloc(set, ptr, size) returns a
123// pointer to an allocation of size bytes if ptr is NULL, or the previous 123// pointer to an allocation of size bytes if ptr is NULL, or the previous
124// allocation ptr resized to size bytes. set_alloc() will never return NULL. 124// allocation ptr resized to size bytes. set_alloc() will never return NULL.
125// set_free(set, ptr) frees an allocation created by set_alloc(). These may be 125// set_free(set, ptr) frees an allocation created by set_alloc(). These may be
126// used by the application. e.g. if allocation tracking is desired. 126// used by the application. e.g. if allocation tracking is desired. */
127#ifdef SET_TRACK 127#ifdef SET_TRACK
128// Track the number of allocations and the total backing memory size. 128/* Track the number of allocations and the total backing memory size. */
129# if defined(_WIN32) 129# if defined(_WIN32)
130# include <malloc.h> 130# include <malloc.h>
131# define SET_ALLOC_SIZE(ptr) _msize(ptr) 131# define SET_ALLOC_SIZE(ptr) _msize(ptr)
@@ -162,7 +162,7 @@ void set_free(set_t *set, void *ptr) {
162 } 162 }
163} 163}
164#else 164#else
165// Without tracking. 165/* Without tracking. */
166void *set_alloc(set_t *set, void *ptr, size_t size) { 166void *set_alloc(set_t *set, void *ptr, size_t size) {
167 void *mem = realloc(ptr, size); 167 void *mem = realloc(ptr, size);
168 if (mem == NULL) 168 if (mem == NULL)
@@ -175,10 +175,10 @@ void set_free(set_t *set, void *ptr) {
175} 175}
176#endif 176#endif
177 177
178// --private-- Grow node's array right[] as needed to be able to hold at least 178/* --private-- Grow node's array right[] as needed to be able to hold at least
179// want links. If fill is true, assure that the first want links are filled in, 179// want links. If fill is true, assure that the first want links are filled in,
180// setting them to set->head if not previously filled in. Otherwise it is 180// setting them to set->head if not previously filled in. Otherwise it is
181// assumed that the first want links are about to be filled in. 181// assumed that the first want links are about to be filled in. */
182void set_grow(set_t *set, set_node_t *node, int want, int fill) { 182void set_grow(set_t *set, set_node_t *node, int want, int fill) {
183 if (node->size < want) { 183 if (node->size < want) {
184 int more = node->size ? node->size : 1; 184 int more = node->size ? node->size : 1;
@@ -194,7 +194,7 @@ void set_grow(set_t *set, set_node_t *node, int want, int fill) {
194 node->fill = (i16_t)want; 194 node->fill = (i16_t)want;
195} 195}
196 196
197// --private-- Return a new node. key is left uninitialized. 197/* --private-- Return a new node. key is left uninitialized. */
198set_node_t *set_node(set_t *set) { 198set_node_t *set_node(set_t *set) {
199 set_node_t *node = set_alloc(set, NULL, sizeof(set_node_t)); 199 set_node_t *node = set_alloc(set, NULL, sizeof(set_node_t));
200 node->size = 0; 200 node->size = 0;
@@ -203,11 +203,11 @@ set_node_t *set_node(set_t *set) {
203 return node; 203 return node;
204} 204}
205 205
206// --private-- Free the list linked from head, along with the keys. 206/* --private-- Free the list linked from head, along with the keys. */
207void set_sweep(set_t *set) { 207void set_sweep(set_t *set) {
208 set_node_t *step = set->head->right[0]; 208 set_node_t *step = set->head->right[0];
209 while (step != set->head) { 209 while (step != set->head) {
210 set_node_t *next = step->right[0]; // save link to next node 210 set_node_t *next = step->right[0]; /* save link to next node */
211 set_drop(set, step->key); 211 set_drop(set, step->key);
212 set_free(set, step->right); 212 set_free(set, step->right);
213 set_free(set, step); 213 set_free(set, step);
@@ -215,59 +215,59 @@ void set_sweep(set_t *set) {
215 } 215 }
216} 216}
217 217
218// Initialize a new set. set->env must be initialized using setjmp() before 218/* Initialize a new set. set->env must be initialized using setjmp() before
219// set_start() is called. A longjmp(set->env, ENOMEM) will be used to handle a 219// set_start() is called. A longjmp(set->env, ENOMEM) will be used to handle a
220// memory allocation failure during any of the operations. (See setjmp.h and 220// memory allocation failure during any of the operations. (See setjmp.h and
221// errno.h.) The set can still be used if this happens, assuming that it didn't 221// errno.h.) The set can still be used if this happens, assuming that it didn't
222// happen during set_start(). Whether set_start() completed or not, set_end() 222// happen during set_start(). Whether set_start() completed or not, set_end()
223// can be used to free the set's memory after a longjmp(). 223// can be used to free the set's memory after a longjmp(). */
224void set_start(set_t *set) { 224void set_start(set_t *set) {
225#ifdef SET_TRACK 225#ifdef SET_TRACK
226 set->allocs = 0; 226 set->allocs = 0;
227 set->memory = 0; 227 set->memory = 0;
228#endif 228#endif
229 set->head = set->path = set->node = NULL; // in case set_node() fails 229 set->head = set->path = set->node = NULL; /* in case set_node() fails */
230 set->path = set_node(set); 230 set->path = set_node(set);
231 set->head = set_node(set); 231 set->head = set_node(set);
232 set_grow(set, set->head, 1, 1); // one link back to head for an empty set 232 set_grow(set, set->head, 1, 1); /* one link back to head for an empty set */
233 *(unsigned char *)&set->head->key = 137; // set id 233 *(unsigned char *)&set->head->key = 137; /* set id */
234 set->depth = 0; 234 set->depth = 0;
235 set_seed(&set->gen, ((ui64_t)(ptrdiff_t)set << 32) ^ 235 set_seed(&set->gen, ((ui64_t)(ptrdiff_t)set << 32) ^
236 ((ui64_t)time(NULL) << 12) ^ clock(), 0); 236 ((ui64_t)time(NULL) << 12) ^ clock(), 0);
237 set->ran = 1; 237 set->ran = 1;
238} 238}
239 239
240// Return true if *set appears to be in a usable state. If *set has been zeroed 240/* Return true if *set appears to be in a usable state. If *set has been zeroed
241// out, then set_ok(set) will be false and set_end(set) will be safe. 241// out, then set_ok(set) will be false and set_end(set) will be safe. */
242int set_ok(set_t *set) { 242int set_ok(set_t *set) {
243 return set->head != NULL && 243 return set->head != NULL &&
244 set->head->right != NULL && 244 set->head->right != NULL &&
245 *(unsigned char *)&set->head->key == 137; 245 *(unsigned char *)&set->head->key == 137;
246} 246}
247 247
248// Empty the set. This frees the memory used for the previous set contents. 248/* Empty the set. This frees the memory used for the previous set contents.
249// After set_clear(), *set is ready for use, as if after a set_start(). 249// After set_clear(), *set is ready for use, as if after a set_start(). */
250void set_clear(set_t *set) { 250void set_clear(set_t *set) {
251 assert(set_ok(set) && "improper use"); 251 assert(set_ok(set) && "improper use");
252 252
253 // Free all the keys and their nodes. 253 /* Free all the keys and their nodes. */
254 set_sweep(set); 254 set_sweep(set);
255 255
256 // Leave the head and path allocations as is. Clear their contents, with 256 /* Leave the head and path allocations as is. Clear their contents, with
257 // head pointing to itself and setting depth to zero, for an empty set. 257 // head pointing to itself and setting depth to zero, for an empty set. */
258 set->head->right[0] = set->head; 258 set->head->right[0] = set->head;
259 set->head->fill = 1; 259 set->head->fill = 1;
260 set->path->fill = 0; 260 set->path->fill = 0;
261 set->depth = 0; 261 set->depth = 0;
262} 262}
263 263
264// Done using the set -- free all allocations. The only operation on *set 264/* Done using the set -- free all allocations. The only operation on *set
265// permitted after this is set_start(). Though another set_end() would do no 265// permitted after this is set_start(). Though another set_end() would do no
266// harm. This can be done at any time after a set_start(), or after a longjmp() 266// harm. This can be done at any time after a set_start(), or after a longjmp()
267// on any allocation failure, including during a set_start(). 267// on any allocation failure, including during a set_start(). */
268void set_end(set_t *set) { 268void set_end(set_t *set) {
269 if (set->head != NULL) { 269 if (set->head != NULL) {
270 // Empty the set and free the head node. 270 /* Empty the set and free the head node. */
271 if (set->head->right != NULL) { 271 if (set->head->right != NULL) {
272 set_sweep(set); 272 set_sweep(set);
273 set_free(set, set->head->right); 273 set_free(set, set->head->right);
@@ -276,13 +276,13 @@ void set_end(set_t *set) {
276 set->head = NULL; 276 set->head = NULL;
277 } 277 }
278 if (set->path != NULL) { 278 if (set->path != NULL) {
279 // Free the path work area. 279 /* Free the path work area. */
280 set_free(set, set->path->right); 280 set_free(set, set->path->right);
281 set_free(set, set->path); 281 set_free(set, set->path);
282 set->path = NULL; 282 set->path = NULL;
283 } 283 }
284 if (set->node != NULL) { 284 if (set->node != NULL) {
285 // Free the node that was under construction when longjmp() hit. 285 /* Free the node that was under construction when longjmp() hit. */
286 set_drop(set, set->node->key); 286 set_drop(set, set->node->key);
287 set_free(set, set->node->right); 287 set_free(set, set->node->right);
288 set_free(set, set->node); 288 set_free(set, set->node);
@@ -290,12 +290,12 @@ void set_end(set_t *set) {
290 } 290 }
291} 291}
292 292
293// Look for key. Return 1 if found or 0 if not. This also puts the path to get 293/* Look for key. Return 1 if found or 0 if not. This also puts the path to get
294// there in set->path, for use by set_insert(). 294// there in set->path, for use by set_insert(). */
295int set_found(set_t *set, set_key_t key) { 295int set_found(set_t *set, set_key_t key) {
296 assert(set_ok(set) && "improper use"); 296 assert(set_ok(set) && "improper use");
297 297
298 // Start at depth and work down and right as determined by key comparisons. 298 /* Start at depth and work down and right as determined by key comparisons. */
299 set_node_t *head = set->head, *here = head; 299 set_node_t *head = set->head, *here = head;
300 int i = set->depth; 300 int i = set->depth;
301 set_grow(set, set->path, i + 1, 0); 301 set_grow(set, set->path, i + 1, 0);
@@ -306,25 +306,25 @@ int set_found(set_t *set, set_key_t key) {
306 set->path->right[i] = here; 306 set->path->right[i] = here;
307 } while (i--); 307 } while (i--);
308 308
309 // See if the key matches. 309 /* See if the key matches. */
310 here = here->right[0]; 310 here = here->right[0];
311 return here != head && set_cmp(here->key, key) == 0; 311 return here != head && set_cmp(here->key, key) == 0;
312} 312}
313 313
314// Insert the key key. Return 0 on success, or 1 if key is already in the set. 314/* Insert the key key. Return 0 on success, or 1 if key is already in the set. */
315int set_insert(set_t *set, set_key_t key) { 315int set_insert(set_t *set, set_key_t key) {
316 assert(set_ok(set) && "improper use"); 316 assert(set_ok(set) && "improper use");
317 317
318 if (set_found(set, key)) 318 if (set_found(set, key))
319 // That key is already in the set. 319 /* That key is already in the set. */
320 return 1; 320 return 1;
321 321
322 // Randomly generate a new level-- level 0 with probability 1/2, 1 with 322 /* Randomly generate a new level-- level 0 with probability 1/2, 1 with
323 // probability 1/4, 2 with probability 1/8, etc. 323 // probability 1/4, 2 with probability 1/8, etc. */
324 int level = 0; 324 int level = 0;
325 for (;;) { 325 for (;;) {
326 if (set->ran == 1) 326 if (set->ran == 1)
327 // Ran out. Get another 32 random bits. 327 /* Ran out. Get another 32 random bits. */
328 set->ran = set_rand(&set->gen) | (1ULL << 32); 328 set->ran = set_rand(&set->gen) | (1ULL << 32);
329 int bit = set->ran & 1; 329 int bit = set->ran & 1;
330 set->ran >>= 1; 330 set->ran >>= 1;
@@ -335,14 +335,14 @@ int set_insert(set_t *set, set_key_t key) {
335 level++; 335 level++;
336 } 336 }
337 if (level > set->depth) { 337 if (level > set->depth) {
338 // The maximum depth is now deeper. Update the structures. 338 /* The maximum depth is now deeper. Update the structures. */
339 set_grow(set, set->path, level + 1, 1); 339 set_grow(set, set->path, level + 1, 1);
340 set_grow(set, set->head, level + 1, 1); 340 set_grow(set, set->head, level + 1, 1);
341 set->depth = (i16_t)level; 341 set->depth = (i16_t)level;
342 } 342 }
343 343
344 // Make a new node for the provided key, and insert it in the lists up to 344 /* Make a new node for the provided key, and insert it in the lists up to
345 // and including level. 345 // and including level. */
346 set->node = set_node(set); 346 set->node = set_node(set);
347 set->node->key = key; 347 set->node->key = key;
348 set_grow(set, set->node, level + 1, 0); 348 set_grow(set, set->node, level + 1, 0);
@@ -357,5 +357,5 @@ int set_insert(set_t *set, set_key_t key) {
357 357
358#else 358#else
359#error ** another skiplist set already created here 359#error ** another skiplist set already created here
360// Would need to implement a prefix in order to support multiple sets. 360/* Would need to implement a prefix in order to support multiple sets. */
361#endif 361#endif
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-16 15:16:14 +0000