text: /*
   * This is a customized version of the pointer table implementation in sv.c
   */
  
  #include "ppport.h"
  
  #if PTRSIZE == 8
      /*
       * This is one of Thomas Wang's hash functions for 64-bit integers from:
       * https://gist.github.com/badboy/6267743
       */
      U32 ptr_hash(PTRV u) {
          u = (~u) + (u << 18);
          u = u ^ (u >> 31);
          u = u * 21;
          u = u ^ (u >> 11);
          u = u + (u << 6);
          u = u ^ (u >> 22);
          return (U32)u;
      }
  #else
      /*
       * This is one of Bob Jenkins' hash functions for 32-bit integers
       * from: https://burtleburtle.net/bob/hash/integer.html
       */
      U32 ptr_hash(PTRV u) {
          u = (u + 0x7ed55d16) + (u << 12);
          u = (u ^ 0xc761c23c) ^ (u >> 19);
          u = (u + 0x165667b1) + (u << 5);
          u = (u + 0xd3a2646c) ^ (u << 9);
          u = (u + 0xfd7046c5) + (u << 3);
          u = (u ^ 0xb55a4f09) ^ (u >> 16);
          return u;
      }
  #endif
  
  #define PTABLE_HASH(ptr) ptr_hash(PTR2nat(ptr))
  
  struct PTABLE_entry {
      struct PTABLE_entry     *next;
      void                    *key;
      void                    *value;
  };
  
  struct PTABLE {
      struct PTABLE_entry     **tbl_ary;
      UV                      tbl_max;
      UV                      tbl_items;
  };
  
  typedef struct PTABLE_entry PTABLE_ENTRY_t;
  typedef struct PTABLE            PTABLE_t;
  
  static PTABLE_t * PTABLE_new(void);
  static PTABLE_ENTRY_t * PTABLE_find(PTABLE_t *tbl, const void *key);
  static void * PTABLE_fetch(PTABLE_t *tbl, const void *key);
  static void PTABLE_store(PTABLE_t *tbl, void *key, void *value);
  static void PTABLE_grow(PTABLE_t *tbl);
  static void PTABLE_clear(PTABLE_t *tbl);
  static void PTABLE_free(PTABLE_t *tbl);
  
  /* create a new pointer => pointer table */
  
  static PTABLE_t *
  PTABLE_new(void)
  {
      PTABLE_t *tbl;
      Newxz(tbl, 1, PTABLE_t);
      tbl->tbl_max = 511;
      tbl->tbl_items = 0;
      Newxz(tbl->tbl_ary, tbl->tbl_max + 1, PTABLE_ENTRY_t*);
      return tbl;
  }
  
  /* map an existing pointer using a table */
  
  static PTABLE_ENTRY_t *
  PTABLE_find(PTABLE_t *tbl, const void *key) {
      PTABLE_ENTRY_t *tblent;
      const UV hash = PTABLE_HASH(key);
      tblent = tbl->tbl_ary[hash & tbl->tbl_max];
      for (; tblent; tblent = tblent->next) {
          if (tblent->key == key)
              return tblent;
      }
      return NULL;
  }
  
  static void *
  PTABLE_fetch(PTABLE_t *tbl, const void *key)
  {
      PTABLE_ENTRY_t const *const tblent = PTABLE_find(tbl, key);
      return tblent ? tblent->value : NULL;
  }
  
  /* add a new entry to a pointer => pointer table */
  
  static void
  PTABLE_store(PTABLE_t *tbl, void *key, void *value)
  {
      PTABLE_ENTRY_t *tblent = PTABLE_find(tbl, key);
  
      if (tblent) {
          tblent->value = value;
      } else {
          const UV entry = PTABLE_HASH(key) & tbl->tbl_max;
          Newx(tblent, 1, PTABLE_ENTRY_t);
  
          tblent->key = key;
          tblent->value = value;
          tblent->next = tbl->tbl_ary[entry];
          tbl->tbl_ary[entry] = tblent;
          tbl->tbl_items++;
          if (tblent->next && (tbl->tbl_items > tbl->tbl_max))
              PTABLE_grow(tbl);
      }
  }
  
  /* double the hash bucket size of an existing ptr table */
  
  static void
  PTABLE_grow(PTABLE_t *tbl)
  {
      PTABLE_ENTRY_t **ary = tbl->tbl_ary;
      const UV oldsize = tbl->tbl_max + 1;
      UV newsize = oldsize * 2;
      UV i;
  
      Renew(ary, newsize, PTABLE_ENTRY_t*);
      Zero(&ary[oldsize], newsize - oldsize, PTABLE_ENTRY_t*);
      tbl->tbl_max = --newsize;
      tbl->tbl_ary = ary;
  
      for (i = 0; i < oldsize; i++, ary++) {
          PTABLE_ENTRY_t **curentp, **entp, *ent;
          if (!*ary)
              continue;
          curentp = ary + oldsize;
          for (entp = ary, ent = *ary; ent; ent = *entp) {
              if ((newsize & PTABLE_HASH(ent->key)) != i) {
                  *entp = ent->next;
                  ent->next = *curentp;
                  *curentp = ent;
                  continue;
              } else {
                  entp = &ent->next;
              }
          }
      }
  }
  
  /* remove all the entries from a ptr table */
  
  static void
  PTABLE_clear(PTABLE_t *tbl)
  {
      if (tbl && tbl->tbl_items) {
          register PTABLE_ENTRY_t * * const array = tbl->tbl_ary;
          UV riter = tbl->tbl_max;
  
          do {
              PTABLE_ENTRY_t *entry = array[riter];
  
              while (entry) {
                  PTABLE_ENTRY_t * const oentry = entry;
                  entry = entry->next;
                  Safefree(oentry);
              }
  
              /* chocolateboy 2008-01-08
               *
               * make sure we clear the array entry, so that subsequent probes fail
               */
  
              array[riter] = NULL;
          } while (riter--);
  
          tbl->tbl_items = 0;
      }
  }
  
  /* clear and free a ptr table */
  
  static void
  PTABLE_free(PTABLE_t *tbl)
  {
      if (!tbl) {
          return;
      }
      PTABLE_clear(tbl);
      Safefree(tbl->tbl_ary);
      Safefree(tbl);
  }
  