ptable.h

   1 /* This file is part of the Lexical-Types Perl module.
   2  * See http://search.cpan.org/dist/Lexical-Types/ */
   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 typedef struct ptable_ent {
  10  struct ptable_ent *next;
  11  const void *       key;
  12  void *             val;
  13 } ptable_ent;
  14
  15 typedef struct ptable {
  16  ptable_ent **ary;
  17  UV           max;
  18  UV           items;
  19 } ptable;
  20
  21 #ifndef PTABLE_VAL_FREE
  22 # define PTABLE_VAL_FREE(V)
  23 #endif
  24
  25 STATIC ptable *ptable_new(void) {
  26  ptable *t = PerlMemShared_malloc(sizeof *t);
  27  t->max   = 127;
  28  t->items = 0;
  29  t->ary   = PerlMemShared_calloc(t->max + 1, sizeof *t->ary);
  30  return t;
  31 }
  32
  33 #define PTABLE_HASH(ptr) \
  34   ((PTR2UV(ptr) >> 3) ^ (PTR2UV(ptr) >> (3 + 7)) ^ (PTR2UV(ptr) >> (3 + 17)))
  35
  36 STATIC ptable_ent *ptable_find(const ptable * const t, const void * const key) {
  37  ptable_ent *ent;
  38  const UV hash = PTABLE_HASH(key);
  39
  40  ent = t->ary[hash & t->max];
  41  for (; ent; ent = ent->next) {
  42   if (ent->key == key)
  43    return ent;
  44  }
  45
  46  return NULL;
  47 }
  48
  49 STATIC void *ptable_fetch(const ptable * const t, const void * const key) {
  50  const ptable_ent *const ent = ptable_find(t, key);
  51
  52  return ent ? ent->val : NULL;
  53 }
  54
  55 STATIC void ptable_split(ptable * const t) {
  56  ptable_ent **ary = t->ary;
  57  const UV oldsize = t->max + 1;
  58  UV newsize = oldsize * 2;
  59  UV i;
  60
  61  ary = PerlMemShared_realloc(ary, newsize * sizeof(*ary));
  62  Zero(&ary[oldsize], newsize - oldsize, sizeof(*ary));
  63  t->max = --newsize;
  64  t->ary = ary;
  65
  66  for (i = 0; i < oldsize; i++, ary++) {
  67   ptable_ent **curentp, **entp, *ent;
  68   if (!*ary)
  69    continue;
  70   curentp = ary + oldsize;
  71   for (entp = ary, ent = *ary; ent; ent = *entp) {
  72    if ((newsize & PTABLE_HASH(ent->key)) != i) {
  73     *entp     = ent->next;
  74     ent->next = *curentp;
  75     *curentp  = ent;
  76     continue;
  77    } else
  78     entp = &ent->next;
  79   }
  80  }
  81 }
  82
  83 STATIC void ptable_store(ptable * const t, const void * const key, void * const val) {
  84  ptable_ent *ent = ptable_find(t, key);
  85
  86  if (ent) {
  87   void *oldval = ent->val;
  88   PTABLE_VAL_FREE(oldval);
  89   ent->val = val;
  90  } else {
  91   const UV i = PTABLE_HASH(key) & t->max;
  92   ent = PerlMemShared_malloc(sizeof *ent);
  93   ent->key  = key;
  94   ent->val  = val;
  95   ent->next = t->ary[i];
  96   t->ary[i] = ent;
  97   t->items++;
  98   if (ent->next && t->items > t->max)
  99    ptable_split(t);
 100  }
 101 }
 102
 103 #if 0
 104
 105 STATIC void ptable_clear(ptable * const t) {
 106  if (t && t->items) {
 107   register ptable_ent ** const array = t->ary;
 108   UV i = t->max;
 109
 110   do {
 111    ptable_ent *entry = array[i];
 112    while (entry) {
 113     ptable_ent * const oentry = entry;
 114     void *val = oentry->val;
 115     entry = entry->next;
 116     PTABLE_VAL_FREE(val);
 117     PerlMemShared_free(entry);
 118    }
 119    array[i] = NULL;
 120   } while (i--);
 121
 122   t->items = 0;
 123  }
 124 }
 125
 126 STATIC void ptable_free(ptable * const t) {
 127  if (!t)
 128   return;
 129  ptable_clear(t);
 130  PerlMemShared_free(t->ary);
 131  PerlMemShared_free(t);
 132 }
 133
 134 #endif