ptable.h

filter: Statementstmt 74.3% 81 / 109 Branchbran 51.6% 31 / 60 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 66.2% 112 / 169 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« Decoder.xs ↑ Summary srl_siphash.h »
1 /* Taken from Chocolateboy's autobox module. License same as perl's and
2 * this same as this module's license.
3 */
4  
5 /*
6 * This is a customized version of the pointer table implementation in sv.c
7 */
8  
9 #ifndef PTABLE_H_
10 #define PTABLE_H_
11  
12 #include <assert.h>
13 #include <limits.h>
14 #include "ppport.h"
15  
16 #if PTRSIZE == 8
17 /*
18 * This is one of Thomas Wang's hash functions for 64-bit integers from:
19 * http://www.concentric.net/~Ttwang/tech/inthash.htm
20 */
21 24 SRL_STATIC_INLINE U32 ptr_hash(PTRV u) {
22 24 u = (~u) + (u << 18);
23 24 u = u ^ (u >> 31);
24 24 u = u * 21;
25 24 u = u ^ (u >> 11);
26 24 u = u + (u << 6);
27 24 u = u ^ (u >> 22);
28 24 return (U32)u;
29 }
30 #else
31 /*
32 * This is one of Bob Jenkins' hash functions for 32-bit integers
33 * from: http://burtleburtle.net/bob/hash/integer.html
34 */
35 SRL_STATIC_INLINE U32 ptr_hash(PTRV u) {
36 u = (u + 0x7ed55d16) + (u << 12);
37 u = (u ^ 0xc761c23c) ^ (u >> 19);
38 u = (u + 0x165667b1) + (u << 5);
39 u = (u + 0xd3a2646c) ^ (u << 9);
40 u = (u + 0xfd7046c5) + (u << 3);
41 u = (u ^ 0xb55a4f09) ^ (u >> 16);
42 return u;
43 }
44 #endif
45  
46 #define PTABLE_HASH(ptr) ptr_hash(PTR2nat(ptr))
47  
48 #define PTABLE_FLAG_AUTOCLEAN 1
49  
50 typedef struct PTABLE_entry PTABLE_ENTRY_t;
51 typedef struct PTABLE PTABLE_t;
52 typedef struct PTABLE_iter PTABLE_ITER_t;
53  
54 struct PTABLE_entry {
55 struct PTABLE_entry *next;
56 void *key;
57 void *value;
58 };
59  
60 struct PTABLE {
61 struct PTABLE_entry **tbl_ary;
62 UV tbl_max;
63 UV tbl_items;
64 PTABLE_ITER_t *cur_iter; /* one iterator at a time can be auto-freed */
65 };
66  
67 struct PTABLE_iter {
68 struct PTABLE *table;
69 UV bucket_num;
70 struct PTABLE_entry *cur_entry;
71 };
72  
73 SRL_STATIC_INLINE PTABLE_t * PTABLE_new(void);
74 SRL_STATIC_INLINE PTABLE_t * PTABLE_new_size(const U8 size_base2_exponent);
75 SRL_STATIC_INLINE PTABLE_ENTRY_t * PTABLE_find(PTABLE_t *tbl, const void *key);
76 SRL_STATIC_INLINE void * PTABLE_fetch(PTABLE_t *tbl, const void *key);
77 SRL_STATIC_INLINE PTABLE_ENTRY_t * PTABLE_store(PTABLE_t *tbl, void *key, void *value);
78 SRL_STATIC_INLINE void PTABLE_delete(PTABLE_t *tbl, void *key);
79 SRL_STATIC_INLINE void PTABLE_grow(PTABLE_t *tbl);
80 SRL_STATIC_INLINE void PTABLE_clear(PTABLE_t *tbl);
81 SRL_STATIC_INLINE void PTABLE_clear_dec(pTHX_ PTABLE_t *tbl);
82 SRL_STATIC_INLINE void PTABLE_free(PTABLE_t *tbl);
83  
84 SRL_STATIC_INLINE PTABLE_ITER_t * PTABLE_iter_new(PTABLE_t *tbl);
85 SRL_STATIC_INLINE PTABLE_ITER_t * PTABLE_iter_new_flags(PTABLE_t *tbl, int flags);
86 SRL_STATIC_INLINE PTABLE_ITER_t * PTABLE_iter_reset(PTABLE_ITER_t *iter);
87 SRL_STATIC_INLINE PTABLE_ENTRY_t * PTABLE_iter_next(PTABLE_ITER_t *iter);
88 SRL_STATIC_INLINE void PTABLE_iter_free(PTABLE_ITER_t *iter);
89  
90 /* create a new pointer => pointer table */
91 SRL_STATIC_INLINE PTABLE_t *
92 48 PTABLE_new_size(const U8 size_base2_exponent)
93 {
94 PTABLE_t *tbl;
95 48 Newxz(tbl, 1, PTABLE_t);
96 48 tbl->tbl_max = (1 << size_base2_exponent) - 1;
97 48 tbl->tbl_items = 0;
98 48 tbl->cur_iter = NULL;
99 48 ▶ Newxz(tbl->tbl_ary, tbl->tbl_max + 1, PTABLE_ENTRY_t*);
Branch: 1 branch
BranchTrueFalseTotal
Newxz(tbl->tbl_ary, tbl->tbl_max + 1, PTABLE_ENTRY_t*); 0 48 48
100 48 return tbl;
101 }
102  
103 SRL_STATIC_INLINE PTABLE_t *
104 48 PTABLE_new(void)
105 {
106 48 return PTABLE_new_size(9);
107 }
108  
109 /* map an existing pointer using a table */
110 SRL_STATIC_INLINE PTABLE_ENTRY_t *
111 16 PTABLE_find(PTABLE_t *tbl, const void *key) {
112 PTABLE_ENTRY_t *tblent;
113 16 const UV hash = PTABLE_HASH(key);
114 16 tblent = tbl->tbl_ary[hash & tbl->tbl_max];
115 16 ▶ for (; tblent; tblent = tblent->next) {
Branch: 1 branch
BranchTrueFalseTotal
for (; tblent; tblent = tblent->next) { 4 12 16
116 4 ▶ if (tblent->key == key)
Branch: 1 branch
BranchTrueFalseTotal
if (tblent->key == key) 4 0 4
117 4 return tblent;
118 }
119 12 return NULL;
120 }
121  
122 SRL_STATIC_INLINE void *
123 8 PTABLE_fetch(PTABLE_t *tbl, const void *key)
124 {
125 8 PTABLE_ENTRY_t const *const tblent = PTABLE_find(tbl, key);
126 8 ▶ return tblent ? tblent->value : NULL;
Branch: 1 branch
BranchTrueFalseTotal
return tblent ? tblent->value : NULL; 4 4 8
127 }
128  
129 /* double the hash bucket size of an existing ptr table */
130  
131 SRL_STATIC_INLINE void
132 0 PTABLE_grow(PTABLE_t *tbl)
133 {
134 0 PTABLE_ENTRY_t **ary = tbl->tbl_ary;
135 0 const UV oldsize = tbl->tbl_max + 1;
136 0 UV newsize = oldsize * 2;
137 UV i;
138  
139 0 ▶ Renew(ary, newsize, PTABLE_ENTRY_t*);
Branch: 1 branch
BranchTrueFalseTotal
Renew(ary, newsize, PTABLE_ENTRY_t*); 0 0 0
140 0 ▶ Zero(&ary[oldsize], newsize - oldsize, PTABLE_ENTRY_t*);
Branch: 1 branch
BranchTrueFalseTotal
Zero(&ary[oldsize], newsize - oldsize, PTABLE_ENTRY_t*); 0 0 0
141 0 tbl->tbl_max = --newsize;
142 0 tbl->tbl_ary = ary;
143  
144 0 ▶ for (i = 0; i < oldsize; i++, ary++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < oldsize; i++, ary++) { 0 0 0
145 PTABLE_ENTRY_t **curentp, **entp, *ent;
146 0 ▶ if (!*ary)
Branch: 1 branch
BranchTrueFalseTotal
if (!*ary) 0 0 0
147 0 continue;
148 0 curentp = ary + oldsize;
149 0 ▶ for (entp = ary, ent = *ary; ent; ent = *entp) {
Branch: 1 branch
BranchTrueFalseTotal
for (entp = ary, ent = *ary; ent; ent = *entp) { 0 0 0
150 0 ▶ if ((newsize & PTABLE_HASH(ent->key)) != i) {
Branch: 1 branch
BranchTrueFalseTotal
if ((newsize & PTABLE_HASH(ent->key)) != i) { 0 0 0
151 0 *entp = ent->next;
152 0 ent->next = *curentp;
153 0 *curentp = ent;
154 0 continue;
155 } else {
156 0 entp = &ent->next;
157 }
158 }
159 }
160 0 }
161  
162 /* add a new entry to a pointer => pointer table */
163  
164 SRL_STATIC_INLINE PTABLE_ENTRY_t *
165 8 PTABLE_store(PTABLE_t *tbl, void *key, void *value)
166 {
167 8 PTABLE_ENTRY_t *tblent = PTABLE_find(tbl, key);
168  
169 8 ▶ if (tblent) {
Branch: 1 branch
BranchTrueFalseTotal
if (tblent) { 0 8 8
170 0 tblent->value = value;
171 } else {
172 8 const UV entry = PTABLE_HASH(key) & tbl->tbl_max;
173 8 Newx(tblent, 1, PTABLE_ENTRY_t);
174  
175 8 tblent->key = key;
176 8 tblent->value = value;
177 8 tblent->next = tbl->tbl_ary[entry];
178 8 tbl->tbl_ary[entry] = tblent;
179 8 tbl->tbl_items++;
180 8 ▶ if (tblent->next && (tbl->tbl_items > tbl->tbl_max))
Branch: 2 branches
BranchTrueFalseTotal
if (tblent->next && (tbl->tbl_items > tbl->tbl_max)) 0 8 8
if (tblent->next && (tbl->tbl_items > tbl->tbl_max)) 0 0 0
181 0 PTABLE_grow(tbl);
182 }
183  
184 8 return tblent;
185 }
186  
187  
188 /* remove all the entries from a ptr table */
189  
190 SRL_STATIC_INLINE void
191 310 PTABLE_clear(PTABLE_t *tbl)
192 {
193 310 ▶ if (tbl && tbl->tbl_items) {
Branch: 2 branches
BranchTrueFalseTotal
if (tbl && tbl->tbl_items) { 310 0 310
if (tbl && tbl->tbl_items) { 4 306 310
194 4 register PTABLE_ENTRY_t * * const array = tbl->tbl_ary;
195 4 UV riter = tbl->tbl_max;
196  
197 do {
198 2048 PTABLE_ENTRY_t *entry = array[riter];
199  
200 2056 ▶ while (entry) {
Branch: 1 branch
BranchTrueFalseTotal
while (entry) { 8 2048 2056
201 8 PTABLE_ENTRY_t * const oentry = entry;
202 8 entry = entry->next;
203 8 Safefree(oentry);
204 }
205  
206 /* chocolateboy 2008-01-08
207 *
208 * make sure we clear the array entry, so that subsequent probes fail
209 */
210  
211 2048 array[riter] = NULL;
212 2048 ▶ } while (riter--);
Branch: 1 branch
BranchTrueFalseTotal
} while (riter--); 2044 4 2048
213  
214 4 tbl->tbl_items = 0;
215 }
216 310 }
217  
218 SRL_STATIC_INLINE void
219 PTABLE_clear_dec(pTHX_ PTABLE_t *tbl)
220 {
221 if (tbl && tbl->tbl_items) {
222 register PTABLE_ENTRY_t * * const array = tbl->tbl_ary;
223 UV riter = tbl->tbl_max;
224  
225 do {
226 PTABLE_ENTRY_t *entry = array[riter];
227  
228 while (entry) {
229 PTABLE_ENTRY_t * const oentry = entry;
230 entry = entry->next;
231 if (oentry->value)
232 SvREFCNT_dec((SV*)(oentry->value));
233 Safefree(oentry);
234 }
235  
236 /* chocolateboy 2008-01-08
237 *
238 * make sure we clear the array entry, so that subsequent probes fail
239 */
240  
241 array[riter] = NULL;
242 } while (riter--);
243  
244 tbl->tbl_items = 0;
245 }
246 }
247  
248 /* remove one entry from a ptr table */
249  
250 SRL_STATIC_INLINE void
251 PTABLE_delete(PTABLE_t *tbl, void *key)
252 {
253 PTABLE_ENTRY_t *tblent;
254 PTABLE_ENTRY_t *tblent_prev;
255  
256 if (!tbl || !tbl->tbl_items) {
257 return;
258 } else {
259 const UV hash = PTABLE_HASH(key);
260 tblent_prev = NULL;
261 tblent = tbl->tbl_ary[hash & tbl->tbl_max];
262  
263 for (; tblent; tblent_prev = tblent, tblent = tblent->next) {
264 if (tblent->key == key) {
265 if (tblent_prev != NULL) {
266 tblent_prev->next = tblent->next;
267 }
268 else {
269 /* First entry in chain */
270 tbl->tbl_ary[hash & tbl->tbl_max] = tblent->next;
271 }
272 Safefree(tblent);
273 break;
274 }
275 }
276 }
277 }
278  
279  
280  
281 #define PTABLE_ITER_NEXT_ELEM(iter, tbl) \
282 STMT_START { \
283 if ((iter)->cur_entry && (iter)->cur_entry->next) { \
284 (iter)->cur_entry = (iter)->cur_entry->next; \
285 } \
286 else { \
287 do { \
288 if ((iter)->bucket_num > (tbl)->tbl_max) { \
289 (iter)->cur_entry = NULL; \
290 break; \
291 } \
292 (iter)->cur_entry = (tbl)->tbl_ary[(iter)->bucket_num++]; \
293 } while ((iter)->cur_entry == NULL); \
294 } \
295 } STMT_END
296  
297 /* Create new iterator object */
298 SRL_STATIC_INLINE PTABLE_ITER_t *
299 2 PTABLE_iter_new_flags(PTABLE_t *tbl, int flags)
300 {
301 PTABLE_ITER_t *iter;
302 2 Newx(iter, 1, PTABLE_ITER_t);
303 2 iter->table = tbl;
304  
305 2 ▶ if (flags & PTABLE_FLAG_AUTOCLEAN)
Branch: 1 branch
BranchTrueFalseTotal
if (flags & PTABLE_FLAG_AUTOCLEAN) 2 0 2
306 2 tbl->cur_iter = iter;
307 2 return PTABLE_iter_reset(iter);
308 }
309  
310 /* setup or reset new iterator object */
311 SRL_STATIC_INLINE PTABLE_ITER_t *
312 2 PTABLE_iter_reset(PTABLE_ITER_t *iter)
313 {
314 2 PTABLE_t *tbl = iter->table;
315 2 iter->bucket_num = 0;
316 2 iter->cur_entry = NULL;
317  
318 2 ▶ if (tbl->tbl_items == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (tbl->tbl_items == 0) { 0 2 2
319 /* Prevent hash bucket scanning.
320 * This can be a significant optimization on large, empty hashes. */
321 0 iter->bucket_num = INT_MAX;
322 0 return iter;
323 }
324 750 ▶ PTABLE_ITER_NEXT_ELEM(iter, tbl);
Branch: 4 branches
BranchTrueFalseTotal
PTABLE_ITER_NEXT_ELEM(iter, tbl); 0 2 2
PTABLE_ITER_NEXT_ELEM(iter, tbl); 0 0 0
PTABLE_ITER_NEXT_ELEM(iter, tbl); 0 748 748
PTABLE_ITER_NEXT_ELEM(iter, tbl); 746 2 748
325 assert(iter->cur_entry != NULL);
326 2 return iter;
327 }
328  
329 SRL_STATIC_INLINE PTABLE_ITER_t *
330 PTABLE_iter_new(PTABLE_t *tbl)
331 {
332 return PTABLE_iter_new_flags(tbl, 0);
333 }
334  
335  
336 /* Return next item from hash, NULL if at end */
337 SRL_STATIC_INLINE PTABLE_ENTRY_t *
338 6 PTABLE_iter_next(PTABLE_ITER_t *iter)
339 {
340 6 PTABLE_ENTRY_t *retval = iter->cur_entry;
341 6 PTABLE_t *tbl = iter->table;
342 286 ▶ PTABLE_ITER_NEXT_ELEM(iter, tbl);
Branch: 4 branches
BranchTrueFalseTotal
PTABLE_ITER_NEXT_ELEM(iter, tbl); 4 2 6
PTABLE_ITER_NEXT_ELEM(iter, tbl); 0 4 4
PTABLE_ITER_NEXT_ELEM(iter, tbl); 4 276 280
PTABLE_ITER_NEXT_ELEM(iter, tbl); 274 2 276
343 6 return retval;
344 }
345  
346 /* Free iterator object */
347 SRL_STATIC_INLINE void
348 2 PTABLE_iter_free(PTABLE_ITER_t *iter)
349 {
350 /* If we're the iterator that can be auto-cleaned by the PTABLE,
351 * then unregister. */
352 2 ▶ if (iter->table->cur_iter == iter)
Branch: 1 branch
BranchTrueFalseTotal
if (iter->table->cur_iter == iter) 2 0 2
353 2 iter->table->cur_iter = NULL;
354  
355 2 Safefree(iter);
356 2 }
357  
358 SRL_STATIC_INLINE void
359 PTABLE_debug_dump(PTABLE_t *tbl, void (*func)(PTABLE_ENTRY_t *e))
360 {
361 PTABLE_ENTRY_t *e;
362 PTABLE_ITER_t *iter = PTABLE_iter_new(tbl);
363 while (NULL != (e = PTABLE_iter_next(iter))) {
364 func(e);
365 }
366 PTABLE_iter_free(iter);
367 }
368  
369 /* clear and free a ptr table */
370  
371 SRL_STATIC_INLINE void
372 48 PTABLE_free(PTABLE_t *tbl)
373 {
374 48 ▶ if (!tbl)
Branch: 1 branch
BranchTrueFalseTotal
if (!tbl) 0 48 48
375 0 return;
376  
377 48 PTABLE_clear(tbl);
378 48 ▶ if (tbl->cur_iter) {
Branch: 1 branch
BranchTrueFalseTotal
if (tbl->cur_iter) { 0 48 48
379 0 PTABLE_ITER_t *it = tbl->cur_iter;
380 0 tbl->cur_iter = NULL; /* avoid circular checks */
381 0 PTABLE_iter_free(it);
382 }
383 48 Safefree(tbl->tbl_ary);
384 48 Safefree(tbl);
385 }
386  
387 #endif
« Decoder.xs ↑ Summary srl_siphash.h »