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" /* VOID2(), XSH_ASSERT(), xPMS */
11 /* --- Configuration ------------------------------------------------------- */
13 #ifndef PTABLE_USE_DEFAULT
14 # define PTABLE_USE_DEFAULT 0
17 #if PTABLE_USE_DEFAULT
18 # if defined(PTABLE_VAL_ALLOC) || defined(PTABLE_VAL_FREE)
19 # error the default ptable is only available when PTABLE_VAL_ALLOC/FREE are unset
22 # define PTABLE_NAME ptable_default
23 # undef PTABLE_VAL_NEED_CONTEXT
24 # define PTABLE_VAL_NEED_CONTEXT 0
27 # error PTABLE_NAME must be defined
29 # ifndef PTABLE_VAL_NEED_CONTEXT
30 # define PTABLE_VAL_NEED_CONTEXT 1
35 # define PTABLE_PASTE(A, B) A ## B
36 # define PTABLE_JOIN(A, B) PTABLE_PASTE(A, B)
40 # define PTABLE_PREFIX(X) PTABLE_JOIN(PTABLE_NAME, X)
43 #ifndef PTABLE_NEED_SPLICE
44 # define PTABLE_NEED_SPLICE 0
47 #ifndef PTABLE_NEED_WALK
48 # define PTABLE_NEED_WALK 0
51 #ifndef PTABLE_NEED_STORE
52 # define PTABLE_NEED_STORE 1
55 #ifndef PTABLE_NEED_VIVIFY
56 # define PTABLE_NEED_VIVIFY 0
57 #elif PTABLE_NEED_VIVIFY
58 # undef PTABLE_NEED_VIVIFY
59 # ifndef PTABLE_VAL_ALLOC
60 # error need to define PTABLE_VAL_ALLOC() to use ptable_vivify()
62 # define PTABLE_NEED_VIVIFY 1
65 #ifndef PTABLE_NEED_DELETE
66 # define PTABLE_NEED_DELETE 1
69 #ifndef PTABLE_NEED_CLEAR
70 # define PTABLE_NEED_CLEAR 1
73 #undef PTABLE_NEED_ENT_VIVIFY
74 #if PTABLE_NEED_SPLICE || PTABLE_NEED_STORE || PTABLE_NEED_VIVIFY
75 # define PTABLE_NEED_ENT_VIVIFY 1
77 # define PTABLE_NEED_ENT_VIVIFY 0
80 #undef PTABLE_NEED_ENT_DETACH
81 #if PTABLE_NEED_SPLICE || PTABLE_NEED_DELETE
82 # define PTABLE_NEED_ENT_DETACH 1
84 # define PTABLE_NEED_ENT_DETACH 0
87 /* ... Context for ptable_*() functions calling PTABLE_VAL_ALLOC/FREE() .... */
94 #if PTABLE_VAL_NEED_CONTEXT
101 # define pPTBL_ pPMS_
103 # define aPTBL_ aPMS_
106 /* --- <ptable> struct ----------------------------------------------------- */
109 typedef struct ptable_ent {
110 struct ptable_ent *next;
114 #define ptable_ent ptable_ent
115 #endif /* !ptable_ent */
118 typedef struct ptable {
123 #define ptable ptable
126 /* --- Private interface --------------------------------------------------- */
129 # define PTABLE_HASH(ptr) \
130 ((PTR2UV(ptr) >> 3) ^ (PTR2UV(ptr) >> (3 + 7)) ^ (PTR2UV(ptr) >> (3 + 17)))
133 #ifndef ptable_bucket
134 # define ptable_bucket(T, K) (PTABLE_HASH(K) & (T)->max)
137 #ifndef ptable_ent_find
138 static ptable_ent *ptable_ent_find(const ptable *t, const void *key) {
139 #define ptable_ent_find ptable_ent_find
141 const size_t idx = ptable_bucket(t, key);
144 for (; ent; ent = ent->next) {
151 #endif /* !ptable_ent_find */
153 #if PTABLE_NEED_ENT_VIVIFY
156 static void ptable_split(pPMS_ ptable *t) {
157 #define ptable_split(T) ptable_split(aPMS_ (T))
158 ptable_ent **ary = t->ary;
159 const size_t old_size = t->max + 1;
160 size_t new_size = old_size * 2;
163 ary = VOID2(ptable_ent **,
164 PerlMemShared_realloc(ary, new_size * sizeof *ary));
165 Zero(ary + old_size, new_size - old_size, sizeof *ary);
169 for (i = 0; i < old_size; i++, ary++) {
170 ptable_ent **curentp, **entp, *ent;
176 curentp = ary + old_size;
179 if ((new_size & PTABLE_HASH(ent->key)) != i) {
181 ent->next = *curentp;
190 #endif /* !ptable_split */
192 #ifndef ptable_ent_vivify
193 static ptable_ent *ptable_ent_vivify(pPMS_ ptable *t, const void *key) {
194 #define ptable_ent_vivify(T, K) ptable_ent_vivify(aPMS_ (T), (K))
196 const size_t idx = ptable_bucket(t, key);
199 for (; ent; ent = ent->next) {
204 ent = VOID2(ptable_ent *, PerlMemShared_malloc(sizeof *ent));
208 ent->next = t->ary[idx];
212 if (ent->next && t->items > t->max)
217 #endif /* !ptable_ent_vivify */
219 #endif /* PTABLE_NEED_ENT_VIVIFY */
221 #if PTABLE_NEED_ENT_DETACH
223 #ifndef ptable_ent_detach
224 static ptable_ent *ptable_ent_detach(ptable *t, const void *key) {
225 #define ptable_ent_detach ptable_ent_detach
226 ptable_ent *prev, *ent;
227 const size_t idx = ptable_bucket(t, key);
231 for (; ent; prev = ent, ent = ent->next) {
232 if (ent->key == key) {
234 prev->next = ent->next;
236 t->ary[idx] = ent->next;
243 #endif /* !ptable_ent_detach */
245 #endif /* PTABLE_NEED_ENT_DETACH */
247 /* --- Public interface ---------------------------------------------------- */
249 /* ... Common symbols ...................................................... */
252 static ptable *ptable_new(pPMS_ size_t init_buckets) {
253 #define ptable_new(B) ptable_new(aPMS_ (B))
256 if (init_buckets < 4) {
260 init_buckets |= init_buckets >> 1;
261 init_buckets |= init_buckets >> 2;
262 init_buckets |= init_buckets >> 4;
263 init_buckets |= init_buckets >> 8;
264 init_buckets |= init_buckets >> 16;
265 if (sizeof(init_buckets) > 4)
266 init_buckets |= init_buckets >> 32;
270 XSH_ASSERT(init_buckets >= 4 && ((init_buckets & (init_buckets - 1)) == 0));
272 t = VOID2(ptable *, PerlMemShared_malloc(sizeof *t));
273 t->max = init_buckets - 1;
275 t->ary = VOID2(ptable_ent **,
276 PerlMemShared_calloc(t->max + 1, sizeof *t->ary));
279 #endif /* !ptable_new */
282 static void *ptable_fetch(const ptable *t, const void *key) {
283 #define ptable_fetch ptable_fetch
284 const ptable_ent *ent = ptable_ent_find(t, key);
286 return ent ? ent->val : NULL;
288 #endif /* !ptable_fetch */
290 #if PTABLE_NEED_SPLICE
292 #ifndef ptable_splice
293 static void *ptable_splice(pPMS_ ptable *t, const void *key, void *new_val) {
294 #define ptable_splice(T, K, V) ptable_splice(aPMS_ (T), (K), (V))
296 void *old_val = NULL;
299 ent = ptable_ent_vivify(t, key);
303 ent = ptable_ent_detach(t, key);
306 PerlMemShared_free(ent);
312 #endif /* !ptable_splice */
314 #endif /* PTABLE_NEED_SPLICE */
319 static void ptable_walk(pTHX_ ptable *t, void (*cb)(pTHX_ ptable_ent *ent, void *userdata), void *userdata) {
320 #define ptable_walk(T, CB, UD) ptable_walk(aTHX_ (T), (CB), (UD))
322 register ptable_ent **array = t->ary;
326 for (entry = array[i]; entry; entry = entry->next)
328 cb(aTHX_ entry, userdata);
332 #endif /* !ptable_walk */
334 #endif /* PTABLE_NEED_WALK */
336 /* ... Specialized symbols ................................................. */
338 #if PTABLE_NEED_STORE
340 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_store)
341 static void PTABLE_PREFIX(_store)(pPTBL_ ptable *t, const void *key, void *val){
342 ptable_ent *ent = ptable_ent_vivify(t, key);
344 #ifdef PTABLE_VAL_FREE
345 PTABLE_VAL_FREE(ent->val);
352 # if PTABLE_USE_DEFAULT
353 # define ptable_default_store ptable_default_store
355 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_store) */
357 #endif /* PTABLE_NEED_STORE */
359 #if PTABLE_NEED_VIVIFY
361 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_vivify)
362 static void *PTABLE_PREFIX(_vivify)(pPTBL_ ptable *t, const void *key) {
363 ptable_ent *ent = ptable_ent_vivify(t, key);
366 PTABLE_VAL_ALLOC(ent->val);
371 # if PTABLE_USE_DEFAULT
372 # define ptable_default_vivify ptable_default_vivify
374 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_vivify) */
376 #endif /* PTABLE_NEED_VIVIFY */
378 #if PTABLE_NEED_DELETE
380 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_delete)
381 static void PTABLE_PREFIX(_delete)(pPTBL_ ptable *t, const void *key) {
382 ptable_ent *ent = ptable_ent_detach(t, key);
384 #ifdef PTABLE_VAL_FREE
386 PTABLE_VAL_FREE(ent->val);
390 PerlMemShared_free(ent);
392 # if PTABLE_USE_DEFAULT
393 # define ptable_default_delete ptable_default_delete
395 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_delete) */
397 #endif /* PTABLE_NEED_DELETE */
399 #if PTABLE_NEED_CLEAR
401 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_clear)
402 static void PTABLE_PREFIX(_clear)(pPTBL_ ptable *t) {
404 register ptable_ent **array = t->ary;
408 ptable_ent *entry = array[idx];
410 ptable_ent *nentry = entry->next;
411 #ifdef PTABLE_VAL_FREE
412 PTABLE_VAL_FREE(entry->val);
414 PerlMemShared_free(entry);
423 # if PTABLE_USE_DEFAULT
424 # define ptable_default_clear ptable_default_clear
426 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_clear) */
428 #endif /* PTABLE_NEED_CLEAR */
430 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_free)
431 static void PTABLE_PREFIX(_free)(pPTBL_ ptable *t) {
434 PTABLE_PREFIX(_clear)(aPTBL_ t);
435 PerlMemShared_free(t->ary);
436 PerlMemShared_free(t);
438 # if PTABLE_USE_DEFAULT
439 # define ptable_default_free ptable_default_free
441 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_free) */
443 /* --- Cleanup ------------------------------------------------------------- */
445 #undef PTABLE_WAS_DEFAULT
446 #if PTABLE_USE_DEFAULT
447 # define PTABLE_WAS_DEFAULT 1
449 # define PTABLE_WAS_DEFAULT 0
453 #undef PTABLE_VAL_ALLOC
454 #undef PTABLE_VAL_FREE
455 #undef PTABLE_VAL_NEED_CONTEXT
456 #undef PTABLE_USE_DEFAULT
458 #undef PTABLE_NEED_SPLICE
459 #undef PTABLE_NEED_WALK
460 #undef PTABLE_NEED_STORE
461 #undef PTABLE_NEED_VIVIFY
462 #undef PTABLE_NEED_DELETE
463 #undef PTABLE_NEED_CLEAR
465 #undef PTABLE_NEED_ENT_VIVIFY
466 #undef PTABLE_NEED_ENT_DETACH