ptable.h

   1 /* This file is part of the indirect Perl module.
   2  * See http://search.cpan.org/dist/indirect/ */
   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_JOIN
  56 # define PTABLE_PASTE(A, B) A ## B
  57 # define PTABLE_JOIN(A, B)  PTABLE_PASTE(A, B)
  58 #endif
  59
  60 #ifndef PTABLE_PREFIX
  61 # define PTABLE_PREFIX(X) PTABLE_JOIN(PTABLE_NAME, X)
  62 #endif
  63
  64 #ifndef PTABLE_NEED_DELETE
  65 # define PTABLE_NEED_DELETE 1
  66 #endif
  67
  68 #ifndef PTABLE_NEED_WALK
  69 # define PTABLE_NEED_WALK 1
  70 #endif
  71
  72 #ifndef ptable_ent
  73 typedef struct ptable_ent {
  74  struct ptable_ent *next;
  75  const void *       key;
  76  void *             val;
  77 } ptable_ent;
  78 #define ptable_ent ptable_ent
  79 #endif /* !ptable_ent */
  80
  81 #ifndef ptable
  82 typedef struct ptable {
  83  ptable_ent **ary;
  84  size_t       max;
  85  size_t       items;
  86 } ptable;
  87 #define ptable ptable
  88 #endif /* !ptable */
  89
  90 #ifndef ptable_new
  91 static ptable *ptable_new(pPTBLMS) {
  92 #define ptable_new() ptable_new(aPTBLMS)
  93  ptable *t = VOID2(ptable *, PerlMemShared_malloc(sizeof *t));
  94  t->max    = 15;
  95  t->items  = 0;
  96  t->ary    = VOID2(ptable_ent **,
  97                               PerlMemShared_calloc(t->max + 1, sizeof *t->ary));
  98  return t;
  99 }
 100 #endif /* !ptable_new */
 101
 102 #ifndef PTABLE_HASH
 103 # define PTABLE_HASH(ptr) \
 104      ((PTR2UV(ptr) >> 3) ^ (PTR2UV(ptr) >> (3 + 7)) ^ (PTR2UV(ptr) >> (3 + 17)))
 105 #endif
 106
 107 #ifndef ptable_find
 108 static ptable_ent *ptable_find(const ptable * const t, const void * const key) {
 109 #define ptable_find ptable_find
 110  ptable_ent *ent;
 111  const UV hash = PTABLE_HASH(key);
 112
 113  ent = t->ary[hash & t->max];
 114  for (; ent; ent = ent->next) {
 115   if (ent->key == key)
 116    return ent;
 117  }
 118
 119  return NULL;
 120 }
 121 #endif /* !ptable_find */
 122
 123 #ifndef ptable_fetch
 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);
 127
 128  return ent ? ent->val : NULL;
 129 }
 130 #endif /* !ptable_fetch */
 131
 132 #ifndef ptable_split
 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;
 138  size_t i;
 139
 140  ary = VOID2(ptable_ent **, PerlMemShared_realloc(ary, newsize * sizeof(*ary)));
 141  Zero(&ary[oldsize], newsize - oldsize, sizeof(*ary));
 142  t->max = --newsize;
 143  t->ary = ary;
 144
 145  for (i = 0; i < oldsize; i++, ary++) {
 146   ptable_ent **curentp, **entp, *ent;
 147   if (!*ary)
 148    continue;
 149   curentp = ary + oldsize;
 150   for (entp = ary, ent = *ary; ent; ent = *entp) {
 151    if ((newsize & PTABLE_HASH(ent->key)) != i) {
 152     *entp     = ent->next;
 153     ent->next = *curentp;
 154     *curentp  = ent;
 155     continue;
 156    } else
 157     entp = &ent->next;
 158   }
 159  }
 160 }
 161 #endif /* !ptable_split */
 162
 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);
 165
 166  if (ent) {
 167 #ifdef PTABLE_VAL_FREE
 168   void *oldval = ent->val;
 169   PTABLE_VAL_FREE(oldval);
 170 #endif
 171   ent->val = val;
 172  } else if (val) {
 173   const size_t i = PTABLE_HASH(key) & t->max;
 174   ent = VOID2(ptable_ent *, PerlMemShared_malloc(sizeof *ent));
 175   ent->key  = key;
 176   ent->val  = val;
 177   ent->next = t->ary[i];
 178   t->ary[i] = ent;
 179   t->items++;
 180   if (ent->next && t->items > t->max)
 181    ptable_split(t);
 182  }
 183 }
 184
 185 #if PTABLE_NEED_DELETE
 186
 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;
 190
 191  prev = NULL;
 192  ent  = t->ary[i];
 193  for (; ent; prev = ent, ent = ent->next) {
 194   if (ent->key == key)
 195    break;
 196  }
 197
 198  if (ent) {
 199   if (prev)
 200    prev->next = ent->next;
 201   else
 202    t->ary[i]  = ent->next;
 203 #ifdef PTABLE_VAL_FREE
 204   PTABLE_VAL_FREE(ent->val);
 205 #endif
 206   PerlMemShared_free(ent);
 207  }
 208 }
 209
 210 #endif /* PTABLE_NEED_DELETE */
 211
 212 #if PTABLE_NEED_WALK && !defined(ptable_walk)
 213
 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))
 216  if (t && t->items) {
 217   register ptable_ent ** const array = t->ary;
 218   size_t i = t->max;
 219   do {
 220    ptable_ent *entry;
 221    for (entry = array[i]; entry; entry = entry->next)
 222     if (entry->val)
 223      cb(aTHX_ entry, userdata);
 224   } while (i--);
 225  }
 226 }
 227
 228 #endif /* PTABLE_NEED_WALK && !defined(ptable_walk) */
 229
 230 static void PTABLE_PREFIX(_clear)(pPTBL_ ptable * const t) {
 231  if (t && t->items) {
 232   register ptable_ent ** const array = t->ary;
 233   size_t i = t->max;
 234
 235   do {
 236    ptable_ent *entry = array[i];
 237    while (entry) {
 238     ptable_ent * const nentry = entry->next;
 239 #ifdef PTABLE_VAL_FREE
 240     PTABLE_VAL_FREE(entry->val);
 241 #endif
 242     PerlMemShared_free(entry);
 243     entry = nentry;
 244    }
 245    array[i] = NULL;
 246   } while (i--);
 247
 248   t->items = 0;
 249  }
 250 }
 251
 252 static void PTABLE_PREFIX(_free)(pPTBL_ ptable * const t) {
 253  if (!t)
 254   return;
 255  PTABLE_PREFIX(_clear)(aPTBL_ t);
 256  PerlMemShared_free(t->ary);
 257  PerlMemShared_free(t);
 258 }
 259
 260 #undef pPTBL
 261 #undef pPTBL_
 262 #undef aPTBL
 263 #undef aPTBL_
 264
 265 #undef PTABLE_NAME
 266 #undef PTABLE_VAL_FREE
 267
 268 #undef PTABLE_NEED_DELETE
 269 #undef PTABLE_NEED_WALK