File Coverage

xsh/ptable.h
Criterion Covered Total %
statement 96 104 92.3
branch 42 52 80.7
condition n/a
subroutine n/a
pod n/a
total 138 156 88.4


line stmt bran cond sub pod time code
1             /* This is a pointer table implementation essentially copied from the ptr_table
2             * implementation in perl's sv.c, except that it has been modified to use memory
3             * shared across threads.
4             * Copyright goes to the original authors, bug reports to me. */
5              
6             /* This header is designed to be included several times with different
7             * definitions for PTABLE_NAME and PTABLE_VAL_ALLOC/FREE(). */
8              
9             #include "util.h" /* XSH_ASSERT() */
10             #include "mem.h" /* xPMS, XSH_SHARED_*() */
11              
12             /* --- Configuration ------------------------------------------------------- */
13              
14             #ifndef PTABLE_USE_DEFAULT
15             # define PTABLE_USE_DEFAULT 0
16             #endif
17              
18             #if PTABLE_USE_DEFAULT
19             # if defined(PTABLE_VAL_ALLOC) || defined(PTABLE_VAL_FREE)
20             # error the default ptable is only available when PTABLE_VAL_ALLOC/FREE are unset
21             # endif
22             # undef PTABLE_NAME
23             # define PTABLE_NAME ptable_default
24             # undef PTABLE_VAL_NEED_CONTEXT
25             # define PTABLE_VAL_NEED_CONTEXT 0
26             #else
27             # ifndef PTABLE_NAME
28             # error PTABLE_NAME must be defined
29             # endif
30             # ifndef PTABLE_VAL_NEED_CONTEXT
31             # define PTABLE_VAL_NEED_CONTEXT 1
32             # endif
33             #endif
34              
35             #ifndef PTABLE_JOIN
36             # define PTABLE_PASTE(A, B) A ## B
37             # define PTABLE_JOIN(A, B) PTABLE_PASTE(A, B)
38             #endif
39              
40             #ifndef PTABLE_PREFIX
41             # define PTABLE_PREFIX(X) PTABLE_JOIN(PTABLE_NAME, X)
42             #endif
43              
44             #ifndef PTABLE_NEED_SPLICE
45             # define PTABLE_NEED_SPLICE 0
46             #endif
47              
48             #ifndef PTABLE_NEED_WALK
49             # define PTABLE_NEED_WALK 0
50             #endif
51              
52             #ifndef PTABLE_NEED_STORE
53             # define PTABLE_NEED_STORE 1
54             #endif
55              
56             #ifndef PTABLE_NEED_VIVIFY
57             # define PTABLE_NEED_VIVIFY 0
58             #elif PTABLE_NEED_VIVIFY
59             # undef PTABLE_NEED_VIVIFY
60             # ifndef PTABLE_VAL_ALLOC
61             # error need to define PTABLE_VAL_ALLOC() to use ptable_vivify()
62             # endif
63             # define PTABLE_NEED_VIVIFY 1
64             #endif
65              
66             #ifndef PTABLE_NEED_DELETE
67             # define PTABLE_NEED_DELETE 1
68             #endif
69              
70             #ifndef PTABLE_NEED_CLEAR
71             # define PTABLE_NEED_CLEAR 1
72             #endif
73              
74             #undef PTABLE_NEED_ENT_VIVIFY
75             #if PTABLE_NEED_SPLICE || PTABLE_NEED_STORE || PTABLE_NEED_VIVIFY
76             # define PTABLE_NEED_ENT_VIVIFY 1
77             #else
78             # define PTABLE_NEED_ENT_VIVIFY 0
79             #endif
80              
81             #undef PTABLE_NEED_ENT_DETACH
82             #if PTABLE_NEED_SPLICE || PTABLE_NEED_DELETE
83             # define PTABLE_NEED_ENT_DETACH 1
84             #else
85             # define PTABLE_NEED_ENT_DETACH 0
86             #endif
87              
88             /* ... Context for ptable_*() functions calling PTABLE_VAL_ALLOC/FREE() .... */
89              
90             #undef pPTBL
91             #undef pPTBL_
92             #undef aPTBL
93             #undef aPTBL_
94              
95             #if PTABLE_VAL_NEED_CONTEXT
96             # define pPTBL pTHX
97             # define pPTBL_ pTHX_
98             # define aPTBL aTHX
99             # define aPTBL_ aTHX_
100             #else
101             # define pPTBL pPMS
102             # define pPTBL_ pPMS_
103             # define aPTBL aPMS
104             # define aPTBL_ aPMS_
105             #endif
106              
107             /* --- struct ----------------------------------------------------- */
108              
109             #ifndef ptable_ent
110             typedef struct ptable_ent {
111             struct ptable_ent *next;
112             const void * key;
113             void * val;
114             } ptable_ent;
115             #define ptable_ent ptable_ent
116             #endif /* !ptable_ent */
117              
118             #ifndef ptable
119             typedef struct ptable {
120             ptable_ent **ary;
121             size_t max;
122             size_t items;
123             } ptable;
124             #define ptable ptable
125             #endif /* !ptable */
126              
127             /* --- Private interface --------------------------------------------------- */
128              
129             #ifndef PTABLE_HASH
130             # define PTABLE_HASH(ptr) \
131             ((PTR2UV(ptr) >> 3) ^ (PTR2UV(ptr) >> (3 + 7)) ^ (PTR2UV(ptr) >> (3 + 17)))
132             #endif
133              
134             #ifndef ptable_bucket
135             # define ptable_bucket(T, K) (PTABLE_HASH(K) & (T)->max)
136             #endif
137              
138             #ifndef ptable_ent_find
139 21367           static ptable_ent *ptable_ent_find(const ptable *t, const void *key) {
140             #define ptable_ent_find ptable_ent_find
141             ptable_ent *ent;
142 21367           const size_t idx = ptable_bucket(t, key);
143              
144 21367           ent = t->ary[idx];
145 23601 100         for (; ent; ent = ent->next) {
146 4466 100         if (ent->key == key)
147 2232           return ent;
148             }
149              
150 19135           return NULL;
151             }
152             #endif /* !ptable_ent_find */
153              
154             #if PTABLE_NEED_ENT_VIVIFY
155              
156             #ifndef ptable_split
157 9           static void ptable_split(pPMS_ ptable *t) {
158             #define ptable_split(T) ptable_split(aPMS_ (T))
159 9           ptable_ent **ary = t->ary;
160 9           const size_t old_size = t->max + 1;
161 9           size_t new_size = old_size * 2;
162             size_t i;
163              
164 9           XSH_SHARED_RECALLOC(ary, old_size, new_size, ptable_ent *);
165 9           t->max = --new_size;
166 9           t->ary = ary;
167              
168 1161 100         for (i = 0; i < old_size; i++, ary++) {
169             ptable_ent **curentp, **entp, *ent;
170              
171 1152           ent = *ary;
172 1152 100         if (!ent)
173 413           continue;
174 739           entp = ary;
175 739           curentp = ary + old_size;
176              
177             do {
178 1162 100         if ((new_size & PTABLE_HASH(ent->key)) != i) {
179 625           *entp = ent->next;
180 625           ent->next = *curentp;
181 625           *curentp = ent;
182             } else {
183 537           entp = &ent->next;
184             }
185 1162           ent = *entp;
186 1162 100         } while (ent);
187             }
188 9           }
189             #endif /* !ptable_split */
190              
191             #ifndef ptable_ent_vivify
192 17926           static ptable_ent *ptable_ent_vivify(pPMS_ ptable *t, const void *key) {
193             #define ptable_ent_vivify(T, K) ptable_ent_vivify(aPMS_ (T), (K))
194             ptable_ent *ent;
195 17926           const size_t idx = ptable_bucket(t, key);
196              
197 17926           ent = t->ary[idx];
198 19786 100         for (; ent; ent = ent->next) {
199 1860 50         if (ent->key == key)
200 0           return ent;
201             }
202              
203 17926           XSH_SHARED_ALLOC(ent, 1, ptable_ent);
204 17926           ent->key = key;
205 17926           ent->val = NULL;
206 17926           ent->next = t->ary[idx];
207 17926           t->ary[idx] = ent;
208              
209 17926           t->items++;
210 17926 100         if (ent->next && t->items > t->max)
    100          
211 9           ptable_split(t);
212              
213 17926           return ent;
214             }
215             #endif /* !ptable_ent_vivify */
216              
217             #endif /* PTABLE_NEED_ENT_VIVIFY */
218              
219             #if PTABLE_NEED_ENT_DETACH
220              
221             #ifndef ptable_ent_detach
222 15176           static ptable_ent *ptable_ent_detach(ptable *t, const void *key) {
223             #define ptable_ent_detach ptable_ent_detach
224             ptable_ent *prev, *ent;
225 15176           const size_t idx = ptable_bucket(t, key);
226              
227 15176           prev = NULL;
228 15176           ent = t->ary[idx];
229 18878 100         for (; ent; prev = ent, ent = ent->next) {
230 3702 50         if (ent->key == key) {
231 0 0         if (prev)
232 0           prev->next = ent->next;
233             else
234 0           t->ary[idx] = ent->next;
235 0           break;
236             }
237             }
238              
239 15176           return ent;
240             }
241             #endif /* !ptable_ent_detach */
242              
243             #endif /* PTABLE_NEED_ENT_DETACH */
244              
245             /* --- Public interface ---------------------------------------------------- */
246              
247             /* ... Common symbols ...................................................... */
248              
249             #ifndef ptable_new
250 45           static ptable *ptable_new(pPMS_ size_t init_buckets) {
251             #define ptable_new(B) ptable_new(aPMS_ (B))
252             ptable *t;
253              
254 45 50         if (init_buckets < 4) {
255 0           init_buckets = 4;
256             } else {
257 45           init_buckets--;
258 45           init_buckets |= init_buckets >> 1;
259 45           init_buckets |= init_buckets >> 2;
260 45           init_buckets |= init_buckets >> 4;
261 45           init_buckets |= init_buckets >> 8;
262 45           init_buckets |= init_buckets >> 16;
263             if (sizeof(init_buckets) > 4)
264 45           init_buckets |= init_buckets >> 32;
265 45           init_buckets++;
266             }
267              
268             XSH_ASSERT(init_buckets >= 4 && ((init_buckets & (init_buckets - 1)) == 0));
269              
270 45           XSH_SHARED_ALLOC(t, 1, ptable);
271 45           t->max = init_buckets - 1;
272 45           t->items = 0;
273 45           XSH_SHARED_CALLOC(t->ary, t->max + 1, ptable_ent *);
274              
275 45           return t;
276             }
277             #endif /* !ptable_new */
278              
279             #ifndef ptable_fetch
280 21367           static void *ptable_fetch(const ptable *t, const void *key) {
281             #define ptable_fetch ptable_fetch
282 21367           const ptable_ent *ent = ptable_ent_find(t, key);
283              
284 21367 100         return ent ? ent->val : NULL;
285             }
286             #endif /* !ptable_fetch */
287              
288             #if PTABLE_NEED_SPLICE
289              
290             #ifndef ptable_splice
291             static void *ptable_splice(pPMS_ ptable *t, const void *key, void *new_val) {
292             #define ptable_splice(T, K, V) ptable_splice(aPMS_ (T), (K), (V))
293             ptable_ent *ent;
294             void *old_val = NULL;
295              
296             if (new_val) {
297             ent = ptable_ent_vivify(t, key);
298             old_val = ent->val;
299             ent->val = new_val;
300             } else {
301             ent = ptable_ent_detach(t, key);
302             if (ent) {
303             old_val = ent->val;
304             XSH_SHARED_FREE(ent, 1, ptable_ent);
305             }
306             }
307              
308             return old_val;
309             }
310             #endif /* !ptable_splice */
311              
312             #endif /* PTABLE_NEED_SPLICE */
313              
314             #if PTABLE_NEED_WALK
315              
316             #ifndef ptable_walk
317             static void ptable_walk(pTHX_ ptable *t, void (*cb)(pTHX_ ptable_ent *ent, void *userdata), void *userdata) {
318             #define ptable_walk(T, CB, UD) ptable_walk(aTHX_ (T), (CB), (UD))
319             if (t && t->items) {
320             register ptable_ent **array = t->ary;
321             size_t i = t->max;
322             do {
323             ptable_ent *entry;
324             for (entry = array[i]; entry; entry = entry->next)
325             if (entry->val)
326             cb(aTHX_ entry, userdata);
327             } while (i--);
328             }
329             }
330             #endif /* !ptable_walk */
331              
332             #endif /* PTABLE_NEED_WALK */
333              
334             /* ... Specialized symbols ................................................. */
335              
336             #if PTABLE_NEED_STORE
337              
338             #if !PTABLE_USE_DEFAULT || !defined(ptable_default_store)
339 17926           static void PTABLE_PREFIX(_store)(pPTBL_ ptable *t, const void *key, void *val){
340 17926           ptable_ent *ent = ptable_ent_vivify(t, key);
341              
342             #ifdef PTABLE_VAL_FREE
343 1107           PTABLE_VAL_FREE(ent->val);
344             #endif
345              
346 17926           ent->val = val;
347              
348 17926           return;
349             }
350             # if PTABLE_USE_DEFAULT
351             # define ptable_default_store ptable_default_store
352             # endif
353             #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_store) */
354              
355             #endif /* PTABLE_NEED_STORE */
356              
357             #if PTABLE_NEED_VIVIFY
358              
359             #if !PTABLE_USE_DEFAULT || !defined(ptable_default_vivify)
360             static void *PTABLE_PREFIX(_vivify)(pPTBL_ ptable *t, const void *key) {
361             ptable_ent *ent = ptable_ent_vivify(t, key);
362              
363             if (!ent->val) {
364             PTABLE_VAL_ALLOC(ent->val);
365             }
366              
367             return ent->val;
368             }
369             # if PTABLE_USE_DEFAULT
370             # define ptable_default_vivify ptable_default_vivify
371             # endif
372             #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_vivify) */
373              
374             #endif /* PTABLE_NEED_VIVIFY */
375              
376             #if PTABLE_NEED_DELETE
377              
378             #if !PTABLE_USE_DEFAULT || !defined(ptable_default_delete)
379 15176           static void PTABLE_PREFIX(_delete)(pPTBL_ ptable *t, const void *key) {
380 15176           ptable_ent *ent = ptable_ent_detach(t, key);
381              
382             #ifdef PTABLE_VAL_FREE
383 15176 50         if (ent) {
384 0           PTABLE_VAL_FREE(ent->val);
385             }
386             #endif
387              
388 15176           XSH_SHARED_FREE(ent, 1, ptable_ent);
389 15176           }
390             # if PTABLE_USE_DEFAULT
391             # define ptable_default_delete ptable_default_delete
392             # endif
393             #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_delete) */
394              
395             #endif /* PTABLE_NEED_DELETE */
396              
397             #if PTABLE_NEED_CLEAR
398              
399             #if !PTABLE_USE_DEFAULT || !defined(ptable_default_clear)
400 11421           static void PTABLE_PREFIX(_clear)(pPTBL_ ptable *t) {
401 11421 50         if (t && t->items) {
    100          
    50          
    100          
402 5449           register ptable_ent **array = t->ary;
403 5449           size_t idx = t->max;
404              
405             do {
406 208928           ptable_ent *entry = array[idx];
407 226854 100         while (entry) {
    100          
408 17926           ptable_ent *nentry = entry->next;
409             #ifdef PTABLE_VAL_FREE
410 1107           PTABLE_VAL_FREE(entry->val);
411             #endif
412 17926           XSH_SHARED_FREE(entry, 1, ptable_ent);
413 17926           entry = nentry;
414             }
415 208928           array[idx] = NULL;
416 208928 100         } while (idx--);
    100          
417              
418 5449           t->items = 0;
419             }
420 11421           }
421             # if PTABLE_USE_DEFAULT
422             # define ptable_default_clear ptable_default_clear
423             # endif
424             #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_clear) */
425              
426             #endif /* PTABLE_NEED_CLEAR */
427              
428             #if !PTABLE_USE_DEFAULT || !defined(ptable_default_free)
429 45           static void PTABLE_PREFIX(_free)(pPTBL_ ptable *t) {
430 45 50         if (!t)
    50          
431 0           return;
432 45           PTABLE_PREFIX(_clear)(aPTBL_ t);
433 45           XSH_SHARED_FREE(t->ary, t->max + 1, ptable_ent *);
434 45           XSH_SHARED_FREE(t, 1, ptable);
435             }
436             # if PTABLE_USE_DEFAULT
437             # define ptable_default_free ptable_default_free
438             # endif
439             #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_free) */
440              
441             /* --- Cleanup ------------------------------------------------------------- */
442              
443             #undef PTABLE_WAS_DEFAULT
444             #if PTABLE_USE_DEFAULT
445             # define PTABLE_WAS_DEFAULT 1
446             #else
447             # define PTABLE_WAS_DEFAULT 0
448             #endif
449              
450             #undef PTABLE_NAME
451             #undef PTABLE_VAL_ALLOC
452             #undef PTABLE_VAL_FREE
453             #undef PTABLE_VAL_NEED_CONTEXT
454             #undef PTABLE_USE_DEFAULT
455              
456             #undef PTABLE_NEED_SPLICE
457             #undef PTABLE_NEED_WALK
458             #undef PTABLE_NEED_STORE
459             #undef PTABLE_NEED_VIVIFY
460             #undef PTABLE_NEED_DELETE
461             #undef PTABLE_NEED_CLEAR
462              
463             #undef PTABLE_NEED_ENT_VIVIFY
464             #undef PTABLE_NEED_ENT_DETACH