File Coverage

ptable.h
Criterion Covered Total %
statement 127 137 92.7
branch 60 80 75.0
condition n/a
subroutine n/a
pod n/a
total 187 217 86.1


line stmt bran cond sub pod time code
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
13             #include
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 5369633           SRL_STATIC_INLINE U32 ptr_hash(PTRV u) {
22 5369633           u = (~u) + (u << 18);
23 5369633           u = u ^ (u >> 31);
24 5369633           u = u * 21;
25 5369633           u = u ^ (u >> 11);
26 5369633           u = u + (u << 6);
27 5369633           u = u ^ (u >> 22);
28 5369633           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 159674           PTABLE_new_size(const U8 size_base2_exponent)
93             {
94             PTABLE_t *tbl;
95 159674           Newxz(tbl, 1, PTABLE_t);
96 159674           tbl->tbl_max = (1 << size_base2_exponent) - 1;
97 159674           tbl->tbl_items = 0;
98 159674           tbl->cur_iter = NULL;
99 159674 50         Newxz(tbl->tbl_ary, tbl->tbl_max + 1, PTABLE_ENTRY_t*);
100 159674           return tbl;
101             }
102              
103             SRL_STATIC_INLINE PTABLE_t *
104             PTABLE_new(void)
105             {
106             return PTABLE_new_size(9);
107             }
108              
109             /* map an existing pointer using a table */
110             SRL_STATIC_INLINE PTABLE_ENTRY_t *
111 3663644           PTABLE_find(PTABLE_t *tbl, const void *key) {
112             PTABLE_ENTRY_t *tblent;
113 3663644           const UV hash = PTABLE_HASH(key);
114 3663644           tblent = tbl->tbl_ary[hash & tbl->tbl_max];
115 4099794 100         for (; tblent; tblent = tblent->next) {
116 915298 100         if (tblent->key == key)
117 479148           return tblent;
118             }
119 3184496           return NULL;
120             }
121              
122             SRL_STATIC_INLINE void *
123 2071358           PTABLE_fetch(PTABLE_t *tbl, const void *key)
124             {
125 2071358           PTABLE_ENTRY_t const *const tblent = PTABLE_find(tbl, key);
126 2071358 100         return tblent ? tblent->value : NULL;
127             }
128              
129             /* double the hash bucket size of an existing ptr table */
130              
131             SRL_STATIC_INLINE void
132 4554           PTABLE_grow(PTABLE_t *tbl)
133             {
134 4554           PTABLE_ENTRY_t **ary = tbl->tbl_ary;
135 4554           const UV oldsize = tbl->tbl_max + 1;
136 4554           UV newsize = oldsize * 2;
137             UV i;
138              
139 4554 50         Renew(ary, newsize, PTABLE_ENTRY_t*);
140 4554 50         Zero(&ary[oldsize], newsize - oldsize, PTABLE_ENTRY_t*);
141 4554           tbl->tbl_max = --newsize;
142 4554           tbl->tbl_ary = ary;
143              
144 115914 100         for (i = 0; i < oldsize; i++, ary++) {
145             PTABLE_ENTRY_t **curentp, **entp, *ent;
146 111360 100         if (!*ary)
147 39459           continue;
148 71901           curentp = ary + oldsize;
149 185632 100         for (entp = ary, ent = *ary; ent; ent = *entp) {
150 113731 100         if ((newsize & PTABLE_HASH(ent->key)) != i) {
151 57490           *entp = ent->next;
152 57490           ent->next = *curentp;
153 57490           *curentp = ent;
154 57490           continue;
155             } else {
156 56241           entp = &ent->next;
157             }
158             }
159             }
160 4554           }
161              
162             /* add a new entry to a pointer => pointer table */
163              
164             SRL_STATIC_INLINE PTABLE_ENTRY_t *
165 1592243           PTABLE_store(PTABLE_t *tbl, void *key, void *value)
166             {
167 1592243           PTABLE_ENTRY_t *tblent = PTABLE_find(tbl, key);
168              
169 1592243 50         if (tblent) {
170 0           tblent->value = value;
171             } else {
172 1592243           const UV entry = PTABLE_HASH(key) & tbl->tbl_max;
173 1592243           Newx(tblent, 1, PTABLE_ENTRY_t);
174              
175 1592243           tblent->key = key;
176 1592243           tblent->value = value;
177 1592243           tblent->next = tbl->tbl_ary[entry];
178 1592243           tbl->tbl_ary[entry] = tblent;
179 1592243           tbl->tbl_items++;
180 1592243 100         if (tblent->next && (tbl->tbl_items > tbl->tbl_max))
    100          
181 4554           PTABLE_grow(tbl);
182             }
183              
184 1592243           return tblent;
185             }
186              
187              
188             /* remove all the entries from a ptr table */
189              
190             SRL_STATIC_INLINE void
191 2717819           PTABLE_clear(PTABLE_t *tbl)
192             {
193 2717819 50         if (tbl && tbl->tbl_items) {
    100          
194 771190           register PTABLE_ENTRY_t * * const array = tbl->tbl_ary;
195 771190           UV riter = tbl->tbl_max;
196              
197             do {
198 14957912           PTABLE_ENTRY_t *entry = array[riter];
199              
200 16550140 100         while (entry) {
201 1592228           PTABLE_ENTRY_t * const oentry = entry;
202 1592228           entry = entry->next;
203 1592228           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 14957912           array[riter] = NULL;
212 14957912 100         } while (riter--);
213              
214 771190           tbl->tbl_items = 0;
215             }
216 2717819           }
217              
218             SRL_STATIC_INLINE void
219 4           PTABLE_clear_dec(pTHX_ PTABLE_t *tbl)
220             {
221 4 50         if (tbl && tbl->tbl_items) {
    50          
222 4           register PTABLE_ENTRY_t * * const array = tbl->tbl_ary;
223 4           UV riter = tbl->tbl_max;
224              
225             do {
226 32           PTABLE_ENTRY_t *entry = array[riter];
227              
228 36 100         while (entry) {
229 4           PTABLE_ENTRY_t * const oentry = entry;
230 4           entry = entry->next;
231 4 50         if (oentry->value)
232 4           SvREFCNT_dec((SV*)(oentry->value));
233 4           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 32           array[riter] = NULL;
242 32 100         } while (riter--);
243              
244 4           tbl->tbl_items = 0;
245             }
246 4           }
247              
248             /* remove one entry from a ptr table */
249              
250             SRL_STATIC_INLINE void
251 19           PTABLE_delete(PTABLE_t *tbl, void *key)
252             {
253             PTABLE_ENTRY_t *tblent;
254             PTABLE_ENTRY_t *tblent_prev;
255              
256 19 50         if (!tbl || !tbl->tbl_items) {
    100          
257 4           return;
258             } else {
259 15           const UV hash = PTABLE_HASH(key);
260 15           tblent_prev = NULL;
261 15           tblent = tbl->tbl_ary[hash & tbl->tbl_max];
262              
263 15 100         for (; tblent; tblent_prev = tblent, tblent = tblent->next) {
264 11 50         if (tblent->key == key) {
265 11 50         if (tblent_prev != NULL) {
266 0           tblent_prev->next = tblent->next;
267             }
268             else {
269             /* First entry in chain */
270 11           tbl->tbl_ary[hash & tbl->tbl_max] = tblent->next;
271             }
272 11           Safefree(tblent);
273 11           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 18           PTABLE_iter_new_flags(PTABLE_t *tbl, int flags)
300             {
301             PTABLE_ITER_t *iter;
302 18           Newx(iter, 1, PTABLE_ITER_t);
303 18           iter->table = tbl;
304              
305 18 50         if (flags & PTABLE_FLAG_AUTOCLEAN)
306 0           tbl->cur_iter = iter;
307 18           return PTABLE_iter_reset(iter);
308             }
309              
310             /* setup or reset new iterator object */
311             SRL_STATIC_INLINE PTABLE_ITER_t *
312 18           PTABLE_iter_reset(PTABLE_ITER_t *iter)
313             {
314 18           PTABLE_t *tbl = iter->table;
315 18           iter->bucket_num = 0;
316 18           iter->cur_entry = NULL;
317              
318 18 50         if (tbl->tbl_items == 0) {
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 92 50         PTABLE_ITER_NEXT_ELEM(iter, tbl);
    0          
    50          
    100          
325             assert(iter->cur_entry != NULL);
326 18           return iter;
327             }
328              
329             SRL_STATIC_INLINE PTABLE_ITER_t *
330 18           PTABLE_iter_new(PTABLE_t *tbl)
331             {
332 18           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 40           PTABLE_iter_next(PTABLE_ITER_t *iter)
339             {
340 40           PTABLE_ENTRY_t *retval = iter->cur_entry;
341 40           PTABLE_t *tbl = iter->table;
342 90 100         PTABLE_ITER_NEXT_ELEM(iter, tbl);
    100          
    100          
    100          
343 40           return retval;
344             }
345              
346             /* Free iterator object */
347             SRL_STATIC_INLINE void
348 18           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 18 50         if (iter->table->cur_iter == iter)
353 0           iter->table->cur_iter = NULL;
354              
355 18           Safefree(iter);
356 18           }
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 159674           PTABLE_free(PTABLE_t *tbl)
373             {
374 159674 50         if (!tbl)
375 0           return;
376              
377 159674           PTABLE_clear(tbl);
378 159674 50         if (tbl->cur_iter) {
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 159674           Safefree(tbl->tbl_ary);
384 159674           Safefree(tbl);
385             }
386              
387             #endif