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. */
6 /* This header is designed to be included several times with different
7 * definitions for PTABLE_NAME and PTABLE_VAL_ALLOC/FREE(). */
9 #include "util.h" /* XSH_ASSERT() */
10 #include "mem.h" /* xPMS, XSH_SHARED_*() */
12 /* --- Configuration ------------------------------------------------------- */
14 #ifndef PTABLE_USE_DEFAULT
15 # define PTABLE_USE_DEFAULT 0
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
23 # define PTABLE_NAME ptable_default
24 # undef PTABLE_VAL_NEED_CONTEXT
25 # define PTABLE_VAL_NEED_CONTEXT 0
28 # error PTABLE_NAME must be defined
30 # ifndef PTABLE_VAL_NEED_CONTEXT
31 # define PTABLE_VAL_NEED_CONTEXT 1
36 # define PTABLE_PASTE(A, B) A ## B
37 # define PTABLE_JOIN(A, B) PTABLE_PASTE(A, B)
41 # define PTABLE_PREFIX(X) PTABLE_JOIN(PTABLE_NAME, X)
44 #ifndef PTABLE_NEED_SPLICE
45 # define PTABLE_NEED_SPLICE 0
48 #ifndef PTABLE_NEED_WALK
49 # define PTABLE_NEED_WALK 0
52 #ifndef PTABLE_NEED_STORE
53 # define PTABLE_NEED_STORE 1
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()
63 # define PTABLE_NEED_VIVIFY 1
66 #ifndef PTABLE_NEED_DELETE
67 # define PTABLE_NEED_DELETE 1
70 #ifndef PTABLE_NEED_CLEAR
71 # define PTABLE_NEED_CLEAR 1
74 #undef PTABLE_NEED_ENT_VIVIFY
75 #if PTABLE_NEED_SPLICE || PTABLE_NEED_STORE || PTABLE_NEED_VIVIFY
76 # define PTABLE_NEED_ENT_VIVIFY 1
78 # define PTABLE_NEED_ENT_VIVIFY 0
81 #undef PTABLE_NEED_ENT_DETACH
82 #if PTABLE_NEED_SPLICE || PTABLE_NEED_DELETE
83 # define PTABLE_NEED_ENT_DETACH 1
85 # define PTABLE_NEED_ENT_DETACH 0
88 /* ... Context for ptable_*() functions calling PTABLE_VAL_ALLOC/FREE() .... */
95 #if PTABLE_VAL_NEED_CONTEXT
102 # define pPTBL_ pPMS_
104 # define aPTBL_ aPMS_
107 /* --- <ptable> struct ----------------------------------------------------- */
110 typedef struct ptable_ent {
111 struct ptable_ent *next;
115 #define ptable_ent ptable_ent
116 #endif /* !ptable_ent */
119 typedef struct ptable {
124 #define ptable ptable
127 /* --- Private interface --------------------------------------------------- */
130 # define PTABLE_HASH(ptr) \
131 ((PTR2UV(ptr) >> 3) ^ (PTR2UV(ptr) >> (3 + 7)) ^ (PTR2UV(ptr) >> (3 + 17)))
134 #ifndef ptable_bucket
135 # define ptable_bucket(T, K) (PTABLE_HASH(K) & (T)->max)
138 #ifndef ptable_ent_find
139 static ptable_ent *ptable_ent_find(const ptable *t, const void *key) {
140 #define ptable_ent_find ptable_ent_find
142 const size_t idx = ptable_bucket(t, key);
145 for (; ent; ent = ent->next) {
152 #endif /* !ptable_ent_find */
154 #if PTABLE_NEED_ENT_VIVIFY
157 static void ptable_split(pPMS_ ptable *t) {
158 #define ptable_split(T) ptable_split(aPMS_ (T))
159 ptable_ent **ary = t->ary;
160 const size_t old_size = t->max + 1;
161 size_t new_size = old_size * 2;
164 XSH_SHARED_RECALLOC(ary, old_size, new_size, ptable_ent *);
168 for (i = 0; i < old_size; i++, ary++) {
169 ptable_ent **curentp, **entp, *ent;
175 curentp = ary + old_size;
178 if ((new_size & PTABLE_HASH(ent->key)) != i) {
180 ent->next = *curentp;
189 #endif /* !ptable_split */
191 #ifndef ptable_ent_vivify
192 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))
195 const size_t idx = ptable_bucket(t, key);
198 for (; ent; ent = ent->next) {
203 XSH_SHARED_ALLOC(ent, 1, ptable_ent);
206 ent->next = t->ary[idx];
210 if (ent->next && t->items > t->max)
215 #endif /* !ptable_ent_vivify */
217 #endif /* PTABLE_NEED_ENT_VIVIFY */
219 #if PTABLE_NEED_ENT_DETACH
221 #ifndef ptable_ent_detach
222 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 const size_t idx = ptable_bucket(t, key);
229 for (; ent; prev = ent, ent = ent->next) {
230 if (ent->key == key) {
232 prev->next = ent->next;
234 t->ary[idx] = ent->next;
241 #endif /* !ptable_ent_detach */
243 #endif /* PTABLE_NEED_ENT_DETACH */
245 /* --- Public interface ---------------------------------------------------- */
247 /* ... Common symbols ...................................................... */
250 static ptable *ptable_new(pPMS_ size_t init_buckets) {
251 #define ptable_new(B) ptable_new(aPMS_ (B))
254 if (init_buckets < 4) {
258 init_buckets |= init_buckets >> 1;
259 init_buckets |= init_buckets >> 2;
260 init_buckets |= init_buckets >> 4;
261 init_buckets |= init_buckets >> 8;
262 init_buckets |= init_buckets >> 16;
263 if (sizeof(init_buckets) > 4)
264 init_buckets |= init_buckets >> 32;
268 XSH_ASSERT(init_buckets >= 4 && ((init_buckets & (init_buckets - 1)) == 0));
270 XSH_SHARED_ALLOC(t, 1, ptable);
271 t->max = init_buckets - 1;
273 XSH_SHARED_CALLOC(t->ary, t->max + 1, ptable_ent *);
277 #endif /* !ptable_new */
280 static void *ptable_fetch(const ptable *t, const void *key) {
281 #define ptable_fetch ptable_fetch
282 const ptable_ent *ent = ptable_ent_find(t, key);
284 return ent ? ent->val : NULL;
286 #endif /* !ptable_fetch */
288 #if PTABLE_NEED_SPLICE
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))
294 void *old_val = NULL;
297 ent = ptable_ent_vivify(t, key);
301 ent = ptable_ent_detach(t, key);
304 XSH_SHARED_FREE(ent, 1, ptable_ent);
310 #endif /* !ptable_splice */
312 #endif /* PTABLE_NEED_SPLICE */
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))
320 register ptable_ent **array = t->ary;
324 for (entry = array[i]; entry; entry = entry->next)
326 cb(aTHX_ entry, userdata);
330 #endif /* !ptable_walk */
332 #endif /* PTABLE_NEED_WALK */
334 /* ... Specialized symbols ................................................. */
336 #if PTABLE_NEED_STORE
338 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_store)
339 static void PTABLE_PREFIX(_store)(pPTBL_ ptable *t, const void *key, void *val){
340 ptable_ent *ent = ptable_ent_vivify(t, key);
342 #ifdef PTABLE_VAL_FREE
343 PTABLE_VAL_FREE(ent->val);
350 # if PTABLE_USE_DEFAULT
351 # define ptable_default_store ptable_default_store
353 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_store) */
355 #endif /* PTABLE_NEED_STORE */
357 #if PTABLE_NEED_VIVIFY
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);
364 PTABLE_VAL_ALLOC(ent->val);
369 # if PTABLE_USE_DEFAULT
370 # define ptable_default_vivify ptable_default_vivify
372 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_vivify) */
374 #endif /* PTABLE_NEED_VIVIFY */
376 #if PTABLE_NEED_DELETE
378 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_delete)
379 static void PTABLE_PREFIX(_delete)(pPTBL_ ptable *t, const void *key) {
380 ptable_ent *ent = ptable_ent_detach(t, key);
382 #ifdef PTABLE_VAL_FREE
384 PTABLE_VAL_FREE(ent->val);
388 XSH_SHARED_FREE(ent, 1, ptable_ent);
390 # if PTABLE_USE_DEFAULT
391 # define ptable_default_delete ptable_default_delete
393 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_delete) */
395 #endif /* PTABLE_NEED_DELETE */
397 #if PTABLE_NEED_CLEAR
399 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_clear)
400 static void PTABLE_PREFIX(_clear)(pPTBL_ ptable *t) {
402 register ptable_ent **array = t->ary;
406 ptable_ent *entry = array[idx];
408 ptable_ent *nentry = entry->next;
409 #ifdef PTABLE_VAL_FREE
410 PTABLE_VAL_FREE(entry->val);
412 XSH_SHARED_FREE(entry, 1, ptable_ent);
421 # if PTABLE_USE_DEFAULT
422 # define ptable_default_clear ptable_default_clear
424 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_clear) */
426 #endif /* PTABLE_NEED_CLEAR */
428 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_free)
429 static void PTABLE_PREFIX(_free)(pPTBL_ ptable *t) {
432 PTABLE_PREFIX(_clear)(aPTBL_ t);
433 XSH_SHARED_FREE(t->ary, t->max + 1, ptable_ent *);
434 XSH_SHARED_FREE(t, 1, ptable);
436 # if PTABLE_USE_DEFAULT
437 # define ptable_default_free ptable_default_free
439 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_free) */
441 /* --- Cleanup ------------------------------------------------------------- */
443 #undef PTABLE_WAS_DEFAULT
444 #if PTABLE_USE_DEFAULT
445 # define PTABLE_WAS_DEFAULT 1
447 # define PTABLE_WAS_DEFAULT 0
451 #undef PTABLE_VAL_ALLOC
452 #undef PTABLE_VAL_FREE
453 #undef PTABLE_VAL_NEED_CONTEXT
454 #undef PTABLE_USE_DEFAULT
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
463 #undef PTABLE_NEED_ENT_VIVIFY
464 #undef PTABLE_NEED_ENT_DETACH