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.h33
1 files changed, 17 insertions, 16 deletions
diff --git a/contrib/minizip/skipset.h b/contrib/minizip/skipset.h
index 381aa13..5e648b9 100644
--- a/contrib/minizip/skipset.h
+++ b/contrib/minizip/skipset.h
@@ -56,11 +56,12 @@
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 <setjmp.h> // jmp_buf, longjmp() 60#include <setjmp.h> // jmp_buf, longjmp()
60#include <errno.h> // ENOMEM 61#include <errno.h> // ENOMEM
61#include <stdint.h> // int16_t, uint32_t, uint64_t
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 65
65// 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
66// 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
@@ -74,20 +75,20 @@
74// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website) 75// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)
75// --private-- Random number generator state. 76// --private-- Random number generator state.
76typedef struct { 77typedef struct {
77 uint64_t state; // 64-bit generator state 78 ui64_t state; // 64-bit generator state
78 uint64_t inc; // 63-bit sequence id 79 ui64_t inc; // 63-bit sequence id
79} set_rand_t; 80} set_rand_t;
80// --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
81// advancing 64-bit state. seq is a sequence selection constant. 82// advancing 64-bit state. seq is a sequence selection constant.
82void set_seed(set_rand_t *gen, uint64_t seed, uint64_t seq) { 83void set_seed(set_rand_t *gen, ui64_t seed, ui64_t seq) {
83 gen->inc = (seq << 1) | 1; 84 gen->inc = (seq << 1) | 1;
84 gen->state = (seed + gen->inc) * 6364136223846793005ULL + gen->inc; 85 gen->state = (seed + gen->inc) * 6364136223846793005ULL + gen->inc;
85} 86}
86// Return 32 random bits, advancing the state *gen. 87// Return 32 random bits, advancing the state *gen.
87uint32_t set_rand(set_rand_t *gen) { 88ui32_t set_rand(set_rand_t *gen) {
88 uint64_t state = gen->state; 89 ui64_t state = gen->state;
89 gen->state = state * 6364136223846793005ULL + gen->inc; 90 gen->state = state * 6364136223846793005ULL + gen->inc;
90 uint32_t mix = (uint32_t)(((state >> 18) ^ state) >> 27); 91 ui32_t mix = (ui32_t)(((state >> 18) ^ state) >> 27);
91 int rot = state >> 59; 92 int rot = state >> 59;
92 return (mix >> rot) | (mix << ((-rot) & 31)); 93 return (mix >> rot) | (mix << ((-rot) & 31));
93} 94}
@@ -97,8 +98,8 @@ uint32_t set_rand(set_rand_t *gen) {
97typedef struct set_node_s set_node_t; 98typedef struct set_node_s set_node_t;
98struct set_node_s { 99struct set_node_s {
99 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)
100 int16_t size; // number of allocated pointers in right[] 101 i16_t size; // number of allocated pointers in right[]
101 int16_t fill; // number of pointers in right[] filled in 102 i16_t fill; // number of pointers in right[] filled in
102 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
103}; 104};
104 105
@@ -108,8 +109,8 @@ typedef struct set_s {
108 set_node_t *head; // skiplist head -- no key, just links 109 set_node_t *head; // skiplist head -- no key, just links
109 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()
110 set_node_t *node; // node under construction, in case of longjmp() 111 set_node_t *node; // node under construction, in case of longjmp()
111 int16_t depth; // maximum depth of the skiplist 112 i16_t depth; // maximum depth of the skiplist
112 uint64_t ran; // a precious trove of random bits 113 ui64_t ran; // a precious trove of random bits
113 set_rand_t gen; // random number generator state 114 set_rand_t gen; // random number generator state
114 jmp_buf env; // setjmp() environment for allocation errors 115 jmp_buf env; // setjmp() environment for allocation errors
115#ifdef SET_TRACK 116#ifdef SET_TRACK
@@ -184,13 +185,13 @@ void set_grow(set_t *set, set_node_t *node, int want, int fill) {
184 while (more < want) 185 while (more < want)
185 more <<= 1; 186 more <<= 1;
186 node->right = set_alloc(set, node->right, more * sizeof(set_node_t *)); 187 node->right = set_alloc(set, node->right, more * sizeof(set_node_t *));
187 node->size = (int16_t)more; 188 node->size = (i16_t)more;
188 } 189 }
189 int i; 190 int i;
190 if (fill) 191 if (fill)
191 for (i = node->fill; i < want; i++) 192 for (i = node->fill; i < want; i++)
192 node->right[i] = set->head; 193 node->right[i] = set->head;
193 node->fill = (int16_t)want; 194 node->fill = (i16_t)want;
194} 195}
195 196
196// --private-- Return a new node. key is left uninitialized. 197// --private-- Return a new node. key is left uninitialized.
@@ -231,8 +232,8 @@ void set_start(set_t *set) {
231 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
232 *(unsigned char *)&set->head->key = 137; // set id 233 *(unsigned char *)&set->head->key = 137; // set id
233 set->depth = 0; 234 set->depth = 0;
234 set_seed(&set->gen, ((uint64_t)(uintptr_t)set << 32) ^ 235 set_seed(&set->gen, ((ui64_t)(ptrdiff_t)set << 32) ^
235 ((uint64_t)time(NULL) << 12) ^ clock(), 0); 236 ((ui64_t)time(NULL) << 12) ^ clock(), 0);
236 set->ran = 1; 237 set->ran = 1;
237} 238}
238 239
@@ -337,7 +338,7 @@ int set_insert(set_t *set, set_key_t key) {
337 // The maximum depth is now deeper. Update the structures. 338 // The maximum depth is now deeper. Update the structures.
338 set_grow(set, set->path, level + 1, 1); 339 set_grow(set, set->path, level + 1, 1);
339 set_grow(set, set->head, level + 1, 1); 340 set_grow(set, set->head, level + 1, 1);
340 set->depth = (int16_t)level; 341 set->depth = (i16_t)level;
341 } 342 }
342 343
343 // 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