ptable.h

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