1/* This file is part of the Variable::Magic Perl module. 2 * See http://search.cpan.org/dist/Variable-Magic/ */ 3 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. */ 8 9/* This header is designed to be included several times with different 10 * definitions for PTABLE_NAME and PTABLE_VAL_FREE(). */ 11 12#undef VOID2 13#ifdef __cplusplus 14# define VOID2(T, P) static_cast<T>(P) 15#else 16# define VOID2(T, P) (P) 17#endif 18 19#undef pPTBLMS 20#undef pPTBLMS_ 21#undef aPTBLMS 22#undef aPTBLMS_ 23 24/* Context for PerlMemShared_* functions */ 25 26#ifdef PERL_IMPLICIT_SYS 27# define pPTBLMS pTHX 28# define pPTBLMS_ pTHX_ 29# define aPTBLMS aTHX 30# define aPTBLMS_ aTHX_ 31#else 32# define pPTBLMS void 33# define pPTBLMS_ 34# define aPTBLMS 35# define aPTBLMS_ 36#endif 37 38#ifndef pPTBL 39# define pPTBL pPTBLMS 40#endif 41#ifndef pPTBL_ 42# define pPTBL_ pPTBLMS_ 43#endif 44#ifndef aPTBL 45# define aPTBL aPTBLMS 46#endif 47#ifndef aPTBL_ 48# define aPTBL_ aPTBLMS_ 49#endif 50 51#ifndef PTABLE_NAME 52# define PTABLE_NAME ptable 53#endif 54 55#ifndef PTABLE_VAL_FREE 56# define PTABLE_VAL_FREE(V) 57#endif 58 59#ifndef PTABLE_JOIN 60# define PTABLE_PASTE(A, B) A ## B 61# define PTABLE_JOIN(A, B) PTABLE_PASTE(A, B) 62#endif 63 64#ifndef PTABLE_PREFIX 65# define PTABLE_PREFIX(X) PTABLE_JOIN(PTABLE_NAME, X) 66#endif 67 68#ifndef ptable_ent 69typedef struct ptable_ent { 70 struct ptable_ent *next; 71 const void * key; 72 void * val; 73} ptable_ent; 74#define ptable_ent ptable_ent 75#endif /* !ptable_ent */ 76 77#ifndef ptable 78typedef struct ptable { 79 ptable_ent **ary; 80 size_t max; 81 size_t items; 82} ptable; 83#define ptable ptable 84#endif /* !ptable */ 85 86#ifndef ptable_new 87STATIC ptable *ptable_new(pPTBLMS) { 88#define ptable_new() ptable_new(aPTBLMS) 89 ptable *t = VOID2(ptable *, PerlMemShared_malloc(sizeof *t)); 90 t->max = 15; 91 t->items = 0; 92 t->ary = VOID2(ptable_ent **, 93 PerlMemShared_calloc(t->max + 1, sizeof *t->ary)); 94 return t; 95} 96#endif /* !ptable_new */ 97 98#ifndef PTABLE_HASH 99# define PTABLE_HASH(ptr) \ 100 ((PTR2UV(ptr) >> 3) ^ (PTR2UV(ptr) >> (3 + 7)) ^ (PTR2UV(ptr) >> (3 + 17))) 101#endif 102 103#ifndef ptable_find 104STATIC ptable_ent *ptable_find(const ptable * const t, const void * const key) { 105#define ptable_find ptable_find 106 ptable_ent *ent; 107 const UV hash = PTABLE_HASH(key); 108 109 ent = t->ary[hash & t->max]; 110 for (; ent; ent = ent->next) { 111 if (ent->key == key) 112 return ent; 113 } 114 115 return NULL; 116} 117#endif /* !ptable_find */ 118 119#ifndef ptable_fetch 120STATIC void *ptable_fetch(const ptable * const t, const void * const key) { 121#define ptable_fetch ptable_fetch 122 const ptable_ent *const ent = ptable_find(t, key); 123 124 return ent ? ent->val : NULL; 125} 126#endif /* !ptable_fetch */ 127 128#ifndef ptable_split 129STATIC void ptable_split(pPTBLMS_ ptable * const t) { 130#define ptable_split(T) ptable_split(aPTBLMS_ (T)) 131 ptable_ent **ary = t->ary; 132 const size_t oldsize = t->max + 1; 133 size_t newsize = oldsize * 2; 134 size_t i; 135 136 ary = VOID2(ptable_ent **, PerlMemShared_realloc(ary, newsize * sizeof(*ary))); 137 Zero(&ary[oldsize], newsize - oldsize, sizeof(*ary)); 138 t->max = --newsize; 139 t->ary = ary; 140 141 for (i = 0; i < oldsize; i++, ary++) { 142 ptable_ent **curentp, **entp, *ent; 143 if (!*ary) 144 continue; 145 curentp = ary + oldsize; 146 for (entp = ary, ent = *ary; ent; ent = *entp) { 147 if ((newsize & PTABLE_HASH(ent->key)) != i) { 148 *entp = ent->next; 149 ent->next = *curentp; 150 *curentp = ent; 151 continue; 152 } else 153 entp = &ent->next; 154 } 155 } 156} 157#endif /* !ptable_split */ 158 159STATIC void PTABLE_PREFIX(_store)(pPTBL_ ptable * const t, const void * const key, void * const val) { 160 ptable_ent *ent = ptable_find(t, key); 161 162 if (ent) { 163 void *oldval = ent->val; 164 PTABLE_VAL_FREE(oldval); 165 ent->val = val; 166 } else if (val) { 167 const size_t i = PTABLE_HASH(key) & t->max; 168 ent = VOID2(ptable_ent *, PerlMemShared_malloc(sizeof *ent)); 169 ent->key = key; 170 ent->val = val; 171 ent->next = t->ary[i]; 172 t->ary[i] = ent; 173 t->items++; 174 if (ent->next && t->items > t->max) 175 ptable_split(t); 176 } 177} 178 179#ifndef ptable_walk 180STATIC void ptable_walk(pTHX_ ptable * const t, void (*cb)(pTHX_ ptable_ent *ent, void *userdata), void *userdata) { 181#define ptable_walk(T, CB, UD) ptable_walk(aTHX_ (T), (CB), (UD)) 182 if (t && t->items) { 183 register ptable_ent ** const array = t->ary; 184 size_t i = t->max; 185 do { 186 ptable_ent *entry; 187 for (entry = array[i]; entry; entry = entry->next) 188 cb(aTHX_ entry, userdata); 189 } while (i--); 190 } 191} 192#endif /* !ptable_walk */ 193 194STATIC void PTABLE_PREFIX(_clear)(pPTBL_ ptable * const t) { 195 if (t && t->items) { 196 register ptable_ent ** const array = t->ary; 197 size_t i = t->max; 198 199 do { 200 ptable_ent *entry = array[i]; 201 while (entry) { 202 ptable_ent * const oentry = entry; 203 void *val = oentry->val; 204 entry = entry->next; 205 PTABLE_VAL_FREE(val); 206 PerlMemShared_free(oentry); 207 } 208 array[i] = NULL; 209 } while (i--); 210 211 t->items = 0; 212 } 213} 214 215STATIC void PTABLE_PREFIX(_free)(pPTBL_ ptable * const t) { 216 if (!t) 217 return; 218 PTABLE_PREFIX(_clear)(aPTBL_ t); 219 PerlMemShared_free(t->ary); 220 PerlMemShared_free(t); 221} 222 223#undef pPTBL 224#undef pPTBL_ 225#undef aPTBL 226#undef aPTBL_ 227 228#undef PTABLE_NAME 229#undef PTABLE_VAL_FREE 230