]> git.vpit.fr Git - perl/modules/re-engine-Plugin.git/blob - xsh/ptable.h
The Big Boilerplate Factorization
[perl/modules/re-engine-Plugin.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" /* VOID2(), XSH_ASSERT(), xPMS */
10
11 /* --- Configuration ------------------------------------------------------- */
12
13 #ifndef PTABLE_USE_DEFAULT
14 # define PTABLE_USE_DEFAULT 0
15 #endif
16
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
20 # endif
21 # undef  PTABLE_NAME
22 # define PTABLE_NAME ptable_default
23 # undef  PTABLE_VAL_NEED_CONTEXT
24 # define PTABLE_VAL_NEED_CONTEXT 0
25 #else
26 # ifndef PTABLE_NAME
27 #  error PTABLE_NAME must be defined
28 # endif
29 # ifndef PTABLE_VAL_NEED_CONTEXT
30 #  define PTABLE_VAL_NEED_CONTEXT 1
31 # endif
32 #endif
33
34 #ifndef PTABLE_JOIN
35 # define PTABLE_PASTE(A, B) A ## B
36 # define PTABLE_JOIN(A, B)  PTABLE_PASTE(A, B)
37 #endif
38
39 #ifndef PTABLE_PREFIX
40 # define PTABLE_PREFIX(X) PTABLE_JOIN(PTABLE_NAME, X)
41 #endif
42
43 #ifndef PTABLE_NEED_SPLICE
44 # define PTABLE_NEED_SPLICE 0
45 #endif
46
47 #ifndef PTABLE_NEED_WALK
48 # define PTABLE_NEED_WALK 0
49 #endif
50
51 #ifndef PTABLE_NEED_STORE
52 # define PTABLE_NEED_STORE 1
53 #endif
54
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()
61 # endif
62 # define PTABLE_NEED_VIVIFY 1
63 #endif
64
65 #ifndef PTABLE_NEED_DELETE
66 # define PTABLE_NEED_DELETE 1
67 #endif
68
69 #ifndef PTABLE_NEED_CLEAR
70 # define PTABLE_NEED_CLEAR 1
71 #endif
72
73 #undef PTABLE_NEED_ENT_VIVIFY
74 #if PTABLE_NEED_SPLICE || PTABLE_NEED_STORE || PTABLE_NEED_VIVIFY
75 # define PTABLE_NEED_ENT_VIVIFY 1
76 #else
77 # define PTABLE_NEED_ENT_VIVIFY 0
78 #endif
79
80 #undef PTABLE_NEED_ENT_DETACH
81 #if PTABLE_NEED_SPLICE || PTABLE_NEED_DELETE
82 # define PTABLE_NEED_ENT_DETACH 1
83 #else
84 # define PTABLE_NEED_ENT_DETACH 0
85 #endif
86
87 /* ... Context for ptable_*() functions calling PTABLE_VAL_ALLOC/FREE() .... */
88
89 #undef pPTBL
90 #undef pPTBL_
91 #undef aPTBL
92 #undef aPTBL_
93
94 #if PTABLE_VAL_NEED_CONTEXT
95 # define pPTBL  pTHX
96 # define pPTBL_ pTHX_
97 # define aPTBL  aTHX
98 # define aPTBL_ aTHX_
99 #else
100 # define pPTBL  pPMS
101 # define pPTBL_ pPMS_
102 # define aPTBL  aPMS
103 # define aPTBL_ aPMS_
104 #endif
105
106 /* --- <ptable> struct ----------------------------------------------------- */
107
108 #ifndef ptable_ent
109 typedef struct ptable_ent {
110  struct ptable_ent *next;
111  const void *       key;
112  void *             val;
113 } ptable_ent;
114 #define ptable_ent ptable_ent
115 #endif /* !ptable_ent */
116
117 #ifndef ptable
118 typedef struct ptable {
119  ptable_ent **ary;
120  size_t       max;
121  size_t       items;
122 } ptable;
123 #define ptable ptable
124 #endif /* !ptable */
125
126 /* --- Private interface --------------------------------------------------- */
127
128 #ifndef PTABLE_HASH
129 # define PTABLE_HASH(ptr) \
130      ((PTR2UV(ptr) >> 3) ^ (PTR2UV(ptr) >> (3 + 7)) ^ (PTR2UV(ptr) >> (3 + 17)))
131 #endif
132
133 #ifndef ptable_bucket
134 # define ptable_bucket(T, K) (PTABLE_HASH(K) & (T)->max)
135 #endif
136
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
140  ptable_ent  *ent;
141  const size_t idx = ptable_bucket(t, key);
142
143  ent = t->ary[idx];
144  for (; ent; ent = ent->next) {
145   if (ent->key == key)
146    return ent;
147  }
148
149  return NULL;
150 }
151 #endif /* !ptable_ent_find */
152
153 #if PTABLE_NEED_ENT_VIVIFY
154
155 #ifndef ptable_split
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;
161  size_t       i;
162
163  ary = VOID2(ptable_ent **,
164              PerlMemShared_realloc(ary, new_size * sizeof *ary));
165  Zero(ary + old_size, new_size - old_size, sizeof *ary);
166  t->max = --new_size;
167  t->ary = ary;
168
169  for (i = 0; i < old_size; i++, ary++) {
170   ptable_ent **curentp, **entp, *ent;
171
172   ent = *ary;
173   if (!ent)
174    continue;
175   entp    = ary;
176   curentp = ary + old_size;
177
178   do {
179    if ((new_size & PTABLE_HASH(ent->key)) != i) {
180     *entp     = ent->next;
181     ent->next = *curentp;
182     *curentp  = ent;
183    } else {
184     entp = &ent->next;
185    }
186    ent = *entp;
187   } while (ent);
188  }
189 }
190 #endif /* !ptable_split */
191
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))
195  ptable_ent  *ent;
196  const size_t idx = ptable_bucket(t, key);
197
198  ent = t->ary[idx];
199  for (; ent; ent = ent->next) {
200   if (ent->key == key)
201    return ent;
202  }
203
204  ent = VOID2(ptable_ent *, PerlMemShared_malloc(sizeof *ent));
205
206  ent->key    = key;
207  ent->val    = NULL;
208  ent->next   = t->ary[idx];
209  t->ary[idx] = ent;
210
211  t->items++;
212  if (ent->next && t->items > t->max)
213   ptable_split(t);
214
215  return ent;
216 }
217 #endif /* !ptable_ent_vivify */
218
219 #endif /* PTABLE_NEED_ENT_VIVIFY */
220
221 #if PTABLE_NEED_ENT_DETACH
222
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);
228
229  prev = NULL;
230  ent  = t->ary[idx];
231  for (; ent; prev = ent, ent = ent->next) {
232   if (ent->key == key) {
233    if (prev)
234     prev->next  = ent->next;
235    else
236     t->ary[idx] = ent->next;
237    break;
238   }
239  }
240
241  return ent;
242 }
243 #endif /* !ptable_ent_detach */
244
245 #endif /* PTABLE_NEED_ENT_DETACH */
246
247 /* --- Public interface ---------------------------------------------------- */
248
249 /* ... Common symbols ...................................................... */
250
251 #ifndef ptable_new
252 static ptable *ptable_new(pPMS_ size_t init_buckets) {
253 #define ptable_new(B) ptable_new(aPMS_ (B))
254  ptable *t;
255
256  if (init_buckets < 4) {
257   init_buckets = 4;
258  } else {
259   init_buckets--;
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;
267   init_buckets++;
268  }
269
270  XSH_ASSERT(init_buckets >= 4 && ((init_buckets & (init_buckets - 1)) == 0));
271
272  t        = VOID2(ptable *, PerlMemShared_malloc(sizeof *t));
273  t->max   = init_buckets - 1;
274  t->items = 0;
275  t->ary   = VOID2(ptable_ent **,
276                               PerlMemShared_calloc(t->max + 1, sizeof *t->ary));
277  return t;
278 }
279 #endif /* !ptable_new */
280
281 #ifndef ptable_fetch
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);
285
286  return ent ? ent->val : NULL;
287 }
288 #endif /* !ptable_fetch */
289
290 #if PTABLE_NEED_SPLICE
291
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))
295  ptable_ent *ent;
296  void       *old_val = NULL;
297
298  if (new_val) {
299   ent      = ptable_ent_vivify(t, key);
300   old_val  = ent->val;
301   ent->val = new_val;
302  } else {
303   ent = ptable_ent_detach(t, key);
304   if (ent) {
305    old_val = ent->val;
306    PerlMemShared_free(ent);
307   }
308  }
309
310  return old_val;
311 }
312 #endif /* !ptable_splice */
313
314 #endif /* PTABLE_NEED_SPLICE */
315
316 #if PTABLE_NEED_WALK
317
318 #ifndef ptable_walk
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))
321  if (t && t->items) {
322   register ptable_ent **array = t->ary;
323   size_t i = t->max;
324   do {
325    ptable_ent *entry;
326    for (entry = array[i]; entry; entry = entry->next)
327     if (entry->val)
328      cb(aTHX_ entry, userdata);
329   } while (i--);
330  }
331 }
332 #endif /* !ptable_walk */
333
334 #endif /* PTABLE_NEED_WALK */
335
336 /* ... Specialized symbols ................................................. */
337
338 #if PTABLE_NEED_STORE
339
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);
343
344 #ifdef PTABLE_VAL_FREE
345  PTABLE_VAL_FREE(ent->val);
346 #endif
347
348  ent->val = val;
349
350  return;
351 }
352 # if PTABLE_USE_DEFAULT
353 #  define ptable_default_store ptable_default_store
354 # endif
355 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_store) */
356
357 #endif /* PTABLE_NEED_STORE */
358
359 #if PTABLE_NEED_VIVIFY
360
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);
364
365  if (!ent->val) {
366   PTABLE_VAL_ALLOC(ent->val);
367  }
368
369  return ent->val;
370 }
371 # if PTABLE_USE_DEFAULT
372 #  define ptable_default_vivify ptable_default_vivify
373 # endif
374 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_vivify) */
375
376 #endif /* PTABLE_NEED_VIVIFY */
377
378 #if PTABLE_NEED_DELETE
379
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);
383
384 #ifdef PTABLE_VAL_FREE
385  if (ent) {
386   PTABLE_VAL_FREE(ent->val);
387  }
388 #endif
389
390  PerlMemShared_free(ent);
391 }
392 # if PTABLE_USE_DEFAULT
393 #  define ptable_default_delete ptable_default_delete
394 # endif
395 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_delete) */
396
397 #endif /* PTABLE_NEED_DELETE */
398
399 #if PTABLE_NEED_CLEAR
400
401 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_clear)
402 static void PTABLE_PREFIX(_clear)(pPTBL_ ptable *t) {
403  if (t && t->items) {
404   register ptable_ent **array = t->ary;
405   size_t idx = t->max;
406
407   do {
408    ptable_ent *entry = array[idx];
409    while (entry) {
410     ptable_ent *nentry = entry->next;
411 #ifdef PTABLE_VAL_FREE
412     PTABLE_VAL_FREE(entry->val);
413 #endif
414     PerlMemShared_free(entry);
415     entry = nentry;
416    }
417    array[idx] = NULL;
418   } while (idx--);
419
420   t->items = 0;
421  }
422 }
423 # if PTABLE_USE_DEFAULT
424 #  define ptable_default_clear ptable_default_clear
425 # endif
426 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_clear) */
427
428 #endif /* PTABLE_NEED_CLEAR */
429
430 #if !PTABLE_USE_DEFAULT || !defined(ptable_default_free)
431 static void PTABLE_PREFIX(_free)(pPTBL_ ptable *t) {
432  if (!t)
433   return;
434  PTABLE_PREFIX(_clear)(aPTBL_ t);
435  PerlMemShared_free(t->ary);
436  PerlMemShared_free(t);
437 }
438 # if PTABLE_USE_DEFAULT
439 #  define ptable_default_free ptable_default_free
440 # endif
441 #endif /* !PTABLE_USE_DEFAULT || !defined(ptable_default_free) */
442
443 /* --- Cleanup ------------------------------------------------------------- */
444
445 #undef PTABLE_WAS_DEFAULT
446 #if PTABLE_USE_DEFAULT
447 # define PTABLE_WAS_DEFAULT 1
448 #else
449 # define PTABLE_WAS_DEFAULT 0
450 #endif
451
452 #undef PTABLE_NAME
453 #undef PTABLE_VAL_ALLOC
454 #undef PTABLE_VAL_FREE
455 #undef PTABLE_VAL_NEED_CONTEXT
456 #undef PTABLE_USE_DEFAULT
457
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
464
465 #undef PTABLE_NEED_ENT_VIVIFY
466 #undef PTABLE_NEED_ENT_DETACH