diff options
Diffstat (limited to 'contrib/minizip/skipset.h')
-rw-r--r-- | contrib/minizip/skipset.h | 144 |
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. */ |
77 | typedef struct { | 77 | typedef 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. */ |
83 | void set_seed(set_rand_t *gen, ui64_t seed, ui64_t seq) { | 83 | void 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. */ |
88 | ui32_t set_rand(set_rand_t *gen) { | 88 | ui32_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. */ |
98 | typedef struct set_node_s set_node_t; | 98 | typedef struct set_node_s set_node_t; |
99 | struct set_node_s { | 99 | struct 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-- . */ |
108 | typedef struct set_s { | 108 | typedef 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. */ |
166 | void *set_alloc(set_t *set, void *ptr, size_t size) { | 166 | void *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. */ |
182 | void set_grow(set_t *set, set_node_t *node, int want, int fill) { | 182 | void 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. */ |
198 | set_node_t *set_node(set_t *set) { | 198 | set_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. */ |
207 | void set_sweep(set_t *set) { | 207 | void 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(). */ |
224 | void set_start(set_t *set) { | 224 | void 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. */ |
242 | int set_ok(set_t *set) { | 242 | int 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(). */ |
250 | void set_clear(set_t *set) { | 250 | void 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(). */ |
268 | void set_end(set_t *set) { | 268 | void 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(). */ |
295 | int set_found(set_t *set, set_key_t key) { | 295 | int 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. */ |
315 | int set_insert(set_t *set, set_key_t key) { | 315 | int 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 |