1 /* This file is part of the indirect Perl module.
2 * See http://search.cpan.org/dist/indirect/ */
4 /* This is a pointer table implementation essentially copied from the ptr_table
5 * implementation in perl's sv.c, except that it has been modified to use memory
6 * shared across threads.
7 * Copyright goes to the original authors, bug reports to me. */
9 /* This header is designed to be included several times with different
10 * definitions for PTABLE_NAME and PTABLE_VAL_FREE(). */
14 # define VOID2(T, P) static_cast<T>(P)
16 # define VOID2(T, P) (P)
24 /* Context for PerlMemShared_* functions */
26 #ifdef PERL_IMPLICIT_SYS
28 # define pPTBLMS_ pTHX_
30 # define aPTBLMS_ aTHX_
39 # define pPTBL pPTBLMS
42 # define pPTBL_ pPTBLMS_
45 # define aPTBL aPTBLMS
48 # define aPTBL_ aPTBLMS_
52 # define PTABLE_NAME ptable
56 # define PTABLE_PASTE(A, B) A ## B
57 # define PTABLE_JOIN(A, B) PTABLE_PASTE(A, B)
61 # define PTABLE_PREFIX(X) PTABLE_JOIN(PTABLE_NAME, X)
64 #ifndef PTABLE_NEED_DELETE
65 # define PTABLE_NEED_DELETE 1
68 #ifndef PTABLE_NEED_WALK
69 # define PTABLE_NEED_WALK 1
73 typedef struct ptable_ent {
74 struct ptable_ent *next;
78 #define ptable_ent ptable_ent
79 #endif /* !ptable_ent */
82 typedef struct ptable {
91 static ptable *ptable_new(pPTBLMS) {
92 #define ptable_new() ptable_new(aPTBLMS)
93 ptable *t = VOID2(ptable *, PerlMemShared_malloc(sizeof *t));
96 t->ary = VOID2(ptable_ent **,
97 PerlMemShared_calloc(t->max + 1, sizeof *t->ary));
100 #endif /* !ptable_new */
103 # define PTABLE_HASH(ptr) \
104 ((PTR2UV(ptr) >> 3) ^ (PTR2UV(ptr) >> (3 + 7)) ^ (PTR2UV(ptr) >> (3 + 17)))
108 static ptable_ent *ptable_find(const ptable * const t, const void * const key) {
109 #define ptable_find ptable_find
111 const UV hash = PTABLE_HASH(key);
113 ent = t->ary[hash & t->max];
114 for (; ent; ent = ent->next) {
121 #endif /* !ptable_find */
124 static void *ptable_fetch(const ptable * const t, const void * const key) {
125 #define ptable_fetch ptable_fetch
126 const ptable_ent *const ent = ptable_find(t, key);
128 return ent ? ent->val : NULL;
130 #endif /* !ptable_fetch */
133 static void ptable_split(pPTBLMS_ ptable * const t) {
134 #define ptable_split(T) ptable_split(aPTBLMS_ (T))
135 ptable_ent **ary = t->ary;
136 const size_t oldsize = t->max + 1;
137 size_t newsize = oldsize * 2;
140 ary = VOID2(ptable_ent **, PerlMemShared_realloc(ary, newsize * sizeof(*ary)));
141 Zero(&ary[oldsize], newsize - oldsize, sizeof(*ary));
145 for (i = 0; i < oldsize; i++, ary++) {
146 ptable_ent **curentp, **entp, *ent;
149 curentp = ary + oldsize;
150 for (entp = ary, ent = *ary; ent; ent = *entp) {
151 if ((newsize & PTABLE_HASH(ent->key)) != i) {
153 ent->next = *curentp;
161 #endif /* !ptable_split */
163 static void PTABLE_PREFIX(_store)(pPTBL_ ptable * const t, const void * const key, void * const val) {
164 ptable_ent *ent = ptable_find(t, key);
167 #ifdef PTABLE_VAL_FREE
168 void *oldval = ent->val;
169 PTABLE_VAL_FREE(oldval);
173 const size_t i = PTABLE_HASH(key) & t->max;
174 ent = VOID2(ptable_ent *, PerlMemShared_malloc(sizeof *ent));
177 ent->next = t->ary[i];
180 if (ent->next && t->items > t->max)
185 #if PTABLE_NEED_DELETE
187 static void PTABLE_PREFIX(_delete)(pPTBL_ ptable * const t, const void * const key) {
188 ptable_ent *prev, *ent;
189 const size_t i = PTABLE_HASH(key) & t->max;
193 for (; ent; prev = ent, ent = ent->next) {
200 prev->next = ent->next;
202 t->ary[i] = ent->next;
203 #ifdef PTABLE_VAL_FREE
204 PTABLE_VAL_FREE(ent->val);
206 PerlMemShared_free(ent);
210 #endif /* PTABLE_NEED_DELETE */
212 #if PTABLE_NEED_WALK && !defined(ptable_walk)
214 static void ptable_walk(pTHX_ ptable * const t, void (*cb)(pTHX_ ptable_ent *ent, void *userdata), void *userdata) {
215 #define ptable_walk(T, CB, UD) ptable_walk(aTHX_ (T), (CB), (UD))
217 register ptable_ent ** const array = t->ary;
221 for (entry = array[i]; entry; entry = entry->next)
223 cb(aTHX_ entry, userdata);
228 #endif /* PTABLE_NEED_WALK && !defined(ptable_walk) */
230 static void PTABLE_PREFIX(_clear)(pPTBL_ ptable * const t) {
232 register ptable_ent ** const array = t->ary;
236 ptable_ent *entry = array[i];
238 ptable_ent * const nentry = entry->next;
239 #ifdef PTABLE_VAL_FREE
240 PTABLE_VAL_FREE(entry->val);
242 PerlMemShared_free(entry);
252 static void PTABLE_PREFIX(_free)(pPTBL_ ptable * const t) {
255 PTABLE_PREFIX(_clear)(aPTBL_ t);
256 PerlMemShared_free(t->ary);
257 PerlMemShared_free(t);
266 #undef PTABLE_VAL_FREE
268 #undef PTABLE_NEED_DELETE
269 #undef PTABLE_NEED_WALK