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 1008098 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 1008098 const size_t idx = ptable_bucket(t, key);
143  
144 1008098 ent = t->ary[idx];
145 1266638 ▶ for (; ent; ent = ent->next) {
Branch: 1 branch
BranchTrueFalseTotal
for (; ent; ent = ent->next) { 571099 695539 1266638
146 571099 ▶ if (ent->key == key)
Branch: 1 branch
BranchTrueFalseTotal
if (ent->key == key) 312559 258540 571099
147 312559 return ent;
148 }
149  
150 695539 return NULL;
151 }
152 #endif /* !ptable_ent_find */
153  
154 #if PTABLE_NEED_ENT_VIVIFY
155  
156 #ifndef ptable_split
157 69 static void ptable_split(pPMS_ ptable *t) {
158 #define ptable_split(T) ptable_split(aPMS_ (T))
159 69 ptable_ent **ary = t->ary;
160 69 const size_t old_size = t->max + 1;
161 69 size_t new_size = old_size * 2;
162 size_t i;
163  
164 69 XSH_SHARED_RECALLOC(ary, old_size, new_size, ptable_ent *);
165 69 t->max = --new_size;
166 69 t->ary = ary;
167  
168 201381 ▶ for (i = 0; i < old_size; i++, ary++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < old_size; i++, ary++) { 201312 69 201381
169 ptable_ent **curentp, **entp, *ent;
170  
171 201312 ent = *ary;
172 201312 ▶ if (!ent)
Branch: 1 branch
BranchTrueFalseTotal
if (!ent) 73634 127678 201312
173 73634 continue;
174 127678 entp = ary;
175 127678 curentp = ary + old_size;
176  
177 do {
178 201352 ▶ if ((new_size & PTABLE_HASH(ent->key)) != i) {
Branch: 1 branch
BranchTrueFalseTotal
if ((new_size & PTABLE_HASH(ent->key)) != i) { 100396 100956 201352
179 100396 *entp = ent->next;
180 100396 ent->next = *curentp;
181 100396 *curentp = ent;
182 } else {
183 100956 entp = &ent->next;
184 }
185 201352 ent = *entp;
186 201352 ▶ } while (ent);
Branch: 1 branch
BranchTrueFalseTotal
} while (ent); 73674 127678 201352
187 }
188 69 }
189 #endif /* !ptable_split */
190  
191 #ifndef ptable_ent_vivify
192 488534 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 488534 const size_t idx = ptable_bucket(t, key);
196  
197 488534 ent = t->ary[idx];
198 614143 ▶ for (; ent; ent = ent->next) {
Branch: 1 branch
BranchTrueFalseTotal
for (; ent; ent = ent->next) { 125609 488534 614143
199 125609 ▶ if (ent->key == key)
Branch: 1 branch
BranchTrueFalseTotal
if (ent->key == key) 0 125609 125609
200 0 return ent;
201 }
202  
203 488534 XSH_SHARED_ALLOC(ent, 1, ptable_ent);
204 488534 ent->key = key;
205 488534 ent->val = NULL;
206 488534 ent->next = t->ary[idx];
207 488534 t->ary[idx] = ent;
208  
209 488534 t->items++;
210 488534 ▶ if (ent->next && t->items > t->max)
Branch: 2 branches
BranchTrueFalseTotal
if (ent->next && t->items > t->max) 95813 392721 488534
if (ent->next && t->items > t->max) 69 95744 95813
211 69 ptable_split(t);
212  
213 488534 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 361944 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 361944 const size_t idx = ptable_bucket(t, key);
226  
227 361944 prev = NULL;
228 361944 ent = t->ary[idx];
229 598714 ▶ for (; ent; prev = ent, ent = ent->next) {
Branch: 1 branch
BranchTrueFalseTotal
for (; ent; prev = ent, ent = ent->next) { 236770 361944 598714
230 236770 ▶ if (ent->key == key) {
Branch: 1 branch
BranchTrueFalseTotal
if (ent->key == key) { 0 236770 236770
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 361944 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 40 static ptable *ptable_new(pPMS_ size_t init_buckets) {
251 #define ptable_new(B) ptable_new(aPMS_ (B))
252 ptable *t;
253  
254 40 ▶ if (init_buckets < 4) {
Branch: 1 branch
BranchTrueFalseTotal
if (init_buckets < 4) { 0 40 40
255 0 init_buckets = 4;
256 } else {
257 40 init_buckets--;
258 40 init_buckets |= init_buckets >> 1;
259 40 init_buckets |= init_buckets >> 2;
260 40 init_buckets |= init_buckets >> 4;
261 40 init_buckets |= init_buckets >> 8;
262 40 init_buckets |= init_buckets >> 16;
263 if (sizeof(init_buckets) > 4)
264 40 init_buckets |= init_buckets >> 32;
265 40 init_buckets++;
266 }
267  
268 XSH_ASSERT(init_buckets >= 4 && ((init_buckets & (init_buckets - 1)) == 0));
269  
270 40 XSH_SHARED_ALLOC(t, 1, ptable);
271 40 t->max = init_buckets - 1;
272 40 t->items = 0;
273 40 XSH_SHARED_CALLOC(t->ary, t->max + 1, ptable_ent *);
274  
275 40 return t;
276 }
277 #endif /* !ptable_new */
278  
279 #ifndef ptable_fetch
280 1008098 static void *ptable_fetch(const ptable *t, const void *key) {
281 #define ptable_fetch ptable_fetch
282 1008098 const ptable_ent *ent = ptable_ent_find(t, key);
283  
284 1008098 ▶ return ent ? ent->val : NULL;
Branch: 1 branch
BranchTrueFalseTotal
return ent ? ent->val : NULL; 312559 695539 1008098
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 488534 static void PTABLE_PREFIX(_store)(pPTBL_ ptable *t, const void *key, void *val){
340 488534 ptable_ent *ent = ptable_ent_vivify(t, key);
341  
342 #ifdef PTABLE_VAL_FREE
343 127901 PTABLE_VAL_FREE(ent->val);
344 #endif
345  
346 488534 ent->val = val;
347  
348 488534 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 361944 static void PTABLE_PREFIX(_delete)(pPTBL_ ptable *t, const void *key) {
380 361944 ptable_ent *ent = ptable_ent_detach(t, key);
381  
382 #ifdef PTABLE_VAL_FREE
383 361944 ▶ if (ent) {
Branch: 1 branch
BranchTrueFalseTotal
if (ent) { 0 361944 361944
384 0 PTABLE_VAL_FREE(ent->val);
385 }
386 #endif
387  
388 361944 XSH_SHARED_FREE(ent, 1, ptable_ent);
389 361944 }
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 182812 static void PTABLE_PREFIX(_clear)(pPTBL_ ptable *t) {
401 182812 ▶ if (t && t->items) {
Branch: 4 branches
BranchTrueFalseTotal
if (t && t->items) { 20 0 20
if (t && t->items) { 19 1 20
if (t && t->items) { 182792 0 182792
if (t && t->items) { 89980 92812 182792
402 89999 register ptable_ent **array = t->ary;
403 89999 size_t idx = t->max;
404  
405 do {
406 3705568 ptable_ent *entry = array[idx];
407 4194102 ▶ while (entry) {
Branch: 2 branches
BranchTrueFalseTotal
while (entry) { 127901 201568 329469
while (entry) { 360633 3504000 3864633
408 488534 ptable_ent *nentry = entry->next;
409 #ifdef PTABLE_VAL_FREE
410 127901 PTABLE_VAL_FREE(entry->val);
411 #endif
412 488534 XSH_SHARED_FREE(entry, 1, ptable_ent);
413 488534 entry = nentry;
414 }
415 3705568 array[idx] = NULL;
416 3705568 ▶ } while (idx--);
Branch: 2 branches
BranchTrueFalseTotal
} while (idx--); 201549 19 201568
} while (idx--); 3414020 89980 3504000
417  
418 89999 t->items = 0;
419 }
420 182812 }
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 40 static void PTABLE_PREFIX(_free)(pPTBL_ ptable *t) {
430 40 if (!t)
431 0 return;
432 40 PTABLE_PREFIX(_clear)(aPTBL_ t);
433 40 XSH_SHARED_FREE(t->ary, t->max + 1, ptable_ent *);
434 40 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