diff options
Diffstat (limited to 'contrib/minizip/skipset.h')
-rw-r--r-- | contrib/minizip/skipset.h | 33 |
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. |
76 | typedef struct { | 77 | typedef 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. |
82 | void set_seed(set_rand_t *gen, uint64_t seed, uint64_t seq) { | 83 | void 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. |
87 | uint32_t set_rand(set_rand_t *gen) { | 88 | ui32_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) { | |||
97 | typedef struct set_node_s set_node_t; | 98 | typedef struct set_node_s set_node_t; |
98 | struct set_node_s { | 99 | struct 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 |