xsh/ptable.h

filter: Statementstmt 94.2% 132 / 140 Branchbran 83.3% 40 / 48 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 91.4% 172 / 188 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xsh/threads.h ↑ Summary
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 /* --- <ptable> 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 121522 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 121522 const size_t idx = ptable_bucket(t, key);
143  
144 121522 ent = t->ary[idx];
145 130570 ▶ for (; ent; ent = ent->next) {
Branch: 1 branch
BranchTrueFalseTotal
for (; ent; ent = ent->next) { 11315 119255 130570
146 11315 ▶ if (ent->key == key)
Branch: 1 branch
BranchTrueFalseTotal
if (ent->key == key) 2267 9048 11315
147 2267 return ent;
148 }
149  
150 119255 return NULL;
151 }
152 #endif /* !ptable_ent_find */
153  
154 #if PTABLE_NEED_ENT_VIVIFY
155  
156 #ifndef ptable_split
157 17 static void ptable_split(pPMS_ ptable *t) {
158 #define ptable_split(T) ptable_split(aPMS_ (T))
159 17 ptable_ent **ary = t->ary;
160 17 const size_t old_size = t->max + 1;
161 17 size_t new_size = old_size * 2;
162 size_t i;
163  
164 17 XSH_SHARED_RECALLOC(ary, old_size, new_size, ptable_ent *);
165 17 t->max = --new_size;
166 17 t->ary = ary;
167  
168 1425 ▶ for (i = 0; i < old_size; i++, ary++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < old_size; i++, ary++) { 1408 17 1425
169 ptable_ent **curentp, **entp, *ent;
170  
171 1408 ent = *ary;
172 1408 ▶ if (!ent)
Branch: 1 branch
BranchTrueFalseTotal
if (!ent) 520 888 1408
173 520 continue;
174 888 entp = ary;
175 888 curentp = ary + old_size;
176  
177 do {
178 1416 ▶ if ((new_size & PTABLE_HASH(ent->key)) != i) {
Branch: 1 branch
BranchTrueFalseTotal
if ((new_size & PTABLE_HASH(ent->key)) != i) { 698 718 1416
179 698 *entp = ent->next;
180 698 ent->next = *curentp;
181 698 *curentp = ent;
182 } else {
183 718 entp = &ent->next;
184 }
185 1416 ent = *entp;
186 1416 ▶ } while (ent);
Branch: 1 branch
BranchTrueFalseTotal
} while (ent); 528 888 1416
187 }
188 17 }
189 #endif /* !ptable_split */
190  
191 #ifndef ptable_ent_vivify
192 113198 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 113198 const size_t idx = ptable_bucket(t, key);
196  
197 113198 ent = t->ary[idx];
198 121032 ▶ for (; ent; ent = ent->next) {
Branch: 1 branch
BranchTrueFalseTotal
for (; ent; ent = ent->next) { 7834 113198 121032
199 7834 ▶ if (ent->key == key)
Branch: 1 branch
BranchTrueFalseTotal
if (ent->key == key) 0 7834 7834
200 0 return ent;
201 }
202  
203 113198 XSH_SHARED_ALLOC(ent, 1, ptable_ent);
204 113198 ent->key = key;
205 113198 ent->val = NULL;
206 113198 ent->next = t->ary[idx];
207 113198 t->ary[idx] = ent;
208  
209 113198 t->items++;
210 113198 ▶ if (ent->next && t->items > t->max)
Branch: 2 branches
BranchTrueFalseTotal
if (ent->next && t->items > t->max) 7047 106151 113198
if (ent->next && t->items > t->max) 17 7030 7047
211 17 ptable_split(t);
212  
213 113198 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 98560 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 98560 const size_t idx = ptable_bucket(t, key);
226  
227 98560 prev = NULL;
228 98560 ent = t->ary[idx];
229 109290 ▶ for (; ent; prev = ent, ent = ent->next) {
Branch: 1 branch
BranchTrueFalseTotal
for (; ent; prev = ent, ent = ent->next) { 10730 98560 109290
230 10730 ▶ if (ent->key == key) {
Branch: 1 branch
BranchTrueFalseTotal
if (ent->key == key) { 0 10730 10730
231 0 ▶ if (prev)
Branch: 1 branch
BranchTrueFalseTotal
if (prev) 0 0 0
232 0 prev->next = ent->next;
233 else
234 0 t->ary[idx] = ent->next;
235 0 break;
236 }
237 }
238  
239 98560 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 ▶ if (init_buckets < 4) {
Branch: 1 branch
BranchTrueFalseTotal
if (init_buckets < 4) { 0 45 45
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 121522 static void *ptable_fetch(const ptable *t, const void *key) {
281 #define ptable_fetch ptable_fetch
282 121522 const ptable_ent *ent = ptable_ent_find(t, key);
283  
284 121522 ▶ return ent ? ent->val : NULL;
Branch: 1 branch
BranchTrueFalseTotal
return ent ? ent->val : NULL; 2267 119255 121522
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 113198 static void PTABLE_PREFIX(_store)(pPTBL_ ptable *t, const void *key, void *val){
340 113198 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 113198 ent->val = val;
347  
348 113198 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 98560 static void PTABLE_PREFIX(_delete)(pPTBL_ ptable *t, const void *key) {
380 98560 ptable_ent *ent = ptable_ent_detach(t, key);
381  
382 #ifdef PTABLE_VAL_FREE
383 98560 ▶ if (ent) {
Branch: 1 branch
BranchTrueFalseTotal
if (ent) { 0 98560 98560
384 0 PTABLE_VAL_FREE(ent->val);
385 }
386 #endif
387  
388 98560 XSH_SHARED_FREE(ent, 1, ptable_ent);
389 98560 }
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 58891 static void PTABLE_PREFIX(_clear)(pPTBL_ ptable *t) {
401 58891 ▶ if (t && t->items) {
Branch: 4 branches
BranchTrueFalseTotal
if (t && t->items) { 30 0 30
if (t && t->items) { 15 15 30
if (t && t->items) { 58861 0 58861
if (t && t->items) { 27611 31250 58861
402 27626 register ptable_ent **array = t->ary;
403 27626 size_t idx = t->max;
404  
405 do {
406 1501856 ptable_ent *entry = array[idx];
407 1615054 ▶ while (entry) {
Branch: 2 branches
BranchTrueFalseTotal
while (entry) { 1107 1504 2611
while (entry) { 112091 1500352 1612443
408 113198 ptable_ent *nentry = entry->next;
409 #ifdef PTABLE_VAL_FREE
410 1107 PTABLE_VAL_FREE(entry->val);
411 #endif
412 113198 XSH_SHARED_FREE(entry, 1, ptable_ent);
413 113198 entry = nentry;
414 }
415 1501856 array[idx] = NULL;
416 1501856 ▶ } while (idx--);
Branch: 2 branches
BranchTrueFalseTotal
} while (idx--); 1489 15 1504
} while (idx--); 1472741 27611 1500352
417  
418 27626 t->items = 0;
419 }
420 58891 }
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 if (!t)
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
« xsh/threads.h ↑ Summary