Update XS helpers to 18554226
[perl/modules/indirect.git] / xsh / ptable.h
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 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  const size_t idx = ptable_bucket(t, key);
143
144  ent = t->ary[idx];
145  for (; ent; ent = ent->next) {
146   if (ent->key == key)
147    return ent;
148  }
149
150  return NULL;
151 }
152 #endif /* !ptable_ent_find */
153
154 #if PTABLE_NEED_ENT_VIVIFY
155
156 #ifndef ptable_split
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;
162  size_t       i;
163
164  XSH_SHARED_RECALLOC(ary, old_size, new_size, ptable_ent *);
165  t->max = --new_size;
166  t->ary = ary;
167
168  for (i = 0; i < old_size; i++, ary++) {
169   ptable_ent **curentp, **entp, *ent;
170
171   ent = *ary;
172   if (!ent)
173    continue;
174   entp    = ary;
175   curentp = ary + old_size;
176
177   do {
178    if ((new_size & PTABLE_HASH(ent->key)) != i) {
179     *entp     = ent->next;
180     ent->next = *curentp;
181     *curentp  = ent;
182    } else {
183     entp = &ent->next;
184    }
185    ent = *entp;
186   } while (ent);
187  }
188 }
189 #endif /* !ptable_split */
190
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))
194  ptable_ent  *ent;
195  const size_t idx = ptable_bucket(t, key);
196
197  ent = t->ary[idx];
198  for (; ent; ent = ent->next) {
199   if (ent->key == key)
200    return ent;
201  }
202
203  XSH_SHARED_ALLOC(ent, 1, ptable_ent);
204  ent->key    = key;
205  ent->val    = NULL;
206  ent->next   = t->ary[idx];
207  t->ary[idx] = ent;
208
209  t->items++;
210  if (ent->next && t->items > t->max)
211   ptable_split(t);
212
213  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 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);
226
227  prev = NULL;
228  ent  = t->ary[idx];
229  for (; ent; prev = ent, ent = ent->next) {
230   if (ent->key == key) {
231    if (prev)
232     prev->next  = ent->next;
233    else
234     t->ary[idx] = ent->next;
235    break;
236   }
237  }
238
239  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 static ptable *ptable_new(pPMS_ size_t init_buckets) {
251 #define ptable_new(B) ptable_new(aPMS_ (B))
252  ptable *t;
253
254  if (init_buckets < 4) {
255   init_buckets = 4;
256  } else {
257   init_buckets--;
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;
265   init_buckets++;
266  }
267
268  XSH_ASSERT(init_buckets >= 4 && ((init_buckets & (init_buckets - 1)) == 0));
269
270  XSH_SHARED_ALLOC(t, 1, ptable);
271  t->max   = init_buckets - 1;
272  t->items = 0;
273  XSH_SHARED_CALLOC(t->ary, t->max + 1, ptable_ent *);
274
275  return t;
276 }
277 #endif /* !ptable_new */
278
279 #ifndef ptable_fetch
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);
283
284  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 static void PTABLE_PREFIX(_store)(pPTBL_ ptable *t, const void *key, void *val){
340  ptable_ent *ent = ptable_ent_vivify(t, key);
341
342 #ifdef PTABLE_VAL_FREE
343  PTABLE_VAL_FREE(ent->val);
344 #endif
345
346  ent->val = val;
347
348  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 static void PTABLE_PREFIX(_delete)(pPTBL_ ptable *t, const void *key) {
380  ptable_ent *ent = ptable_ent_detach(t, key);
381
382 #ifdef PTABLE_VAL_FREE
383  if (ent) {
384   PTABLE_VAL_FREE(ent->val);
385  }
386 #endif
387
388  XSH_SHARED_FREE(ent, 1, ptable_ent);
389 }
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 static void PTABLE_PREFIX(_clear)(pPTBL_ ptable *t) {
401  if (t && t->items) {
402   register ptable_ent **array = t->ary;
403   size_t idx = t->max;
404
405   do {
406    ptable_ent *entry = array[idx];
407    while (entry) {
408     ptable_ent *nentry = entry->next;
409 #ifdef PTABLE_VAL_FREE
410     PTABLE_VAL_FREE(entry->val);
411 #endif
412     XSH_SHARED_FREE(entry, 1, ptable_ent);
413     entry = nentry;
414    }
415    array[idx] = NULL;
416   } while (idx--);
417
418   t->items = 0;
419  }
420 }
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 static void PTABLE_PREFIX(_free)(pPTBL_ ptable *t) {
430  if (!t)
431   return;
432  PTABLE_PREFIX(_clear)(aPTBL_ t);
433  XSH_SHARED_FREE(t->ary, t->max + 1, ptable_ent *);
434  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