prop-src/hashtab.cc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 //  Hash Tables
   3 ///////////////////////////////////////////////////////////////////////////////
   4 #include <string.h>
   5 #include <AD/generic/ordering.h>
   6 #include "hashtab.h"
   7
   8 ///////////////////////////////////////////////////////////////////////////////
   9 //  Import some type definitions
  10 ///////////////////////////////////////////////////////////////////////////////
  11 typedef HashTable::Key          Key;
  12 typedef HashTable::Value        Value;
  13 typedef HashTable::Entry        Entry;
  14 typedef HashTable::HashFunction HashFunction;
  15 typedef HashTable::Equality     Equality;
  16
  17 ///////////////////////////////////////////////////////////////////////////////
  18 //  Constructor and destructor
  19 ///////////////////////////////////////////////////////////////////////////////
  20 HashTable:: HashTable(HashFunction h, Equality e, int n)
  21   : hash(h), eq(e), count(0), table(0), capacity(0), growth_limit(0)
  22     { grow(n); }
  23 HashTable::~HashTable() { delete [] table; }
  24
  25 ///////////////////////////////////////////////////////////////////////////////
  26 //  Check if a key is in the table.
  27 ///////////////////////////////////////////////////////////////////////////////
  28 Bool HashTable::contains (Key key) const { return lookup(key) != 0; }
  29
  30 ///////////////////////////////////////////////////////////////////////////////
  31 //  Empties the table.
  32 ///////////////////////////////////////////////////////////////////////////////
  33 void HashTable::clear()
  34 {  for (Entry * p = table, * q = p + capacity; p < q; p++) p->hash_val = -1;
  35    count = 0;
  36 }
  37
  38 ///////////////////////////////////////////////////////////////////////////////
  39 //  Increase the size of a table.
  40 ///////////////////////////////////////////////////////////////////////////////
  41 void HashTable::grow(int n)
  42 {  if (n < capacity) return;
  43    Entry * new_table = new Entry [n];
  44    int i;
  45    for (i = 0; i < n; i++) new_table[i].hash_val = -1;
  46    if (count > 0) {
  47       for (i = 0; i < capacity; i++)
  48       {  if (table[i].hash_val >= 0) {
  49             unsigned int j, h = (*hash)(table[i].k) % n;
  50             for (j = h;;)
  51             {  if (new_table[j].hash_val < 0)
  52                {  new_table[j].k        = table[i].k;
  53                   new_table[j].v        = table[i].v;
  54                   new_table[j].hash_val = h;
  55                   break;
  56                }
  57                if (++j >= n) j = 0;
  58             }
  59          }
  60       }
  61    }
  62    if (table) delete [] table;
  63    table = new_table;
  64    capacity = n;
  65    growth_limit = n * 6 / 10;
  66 }
  67
  68 ///////////////////////////////////////////////////////////////////////////////
  69 //  Lookup a key from the table.  Use linear probing.  I'm lazy.
  70 ///////////////////////////////////////////////////////////////////////////////
  71 const Entry * HashTable::private_lookup (unsigned int h, Key k) const
  72 {
  73    register unsigned int i = h;
  74
  75    for (;;)
  76    {  if (table[i].hash_val < 0 ||
  77           table[i].hash_val == h && (*eq)(table[i].k,k))
  78             return table + i;
  79       if (++i >= capacity) i = 0;
  80    }
  81 }
  82
  83 ///////////////////////////////////////////////////////////////////////////////
  84 //  Lookup an entry from a key
  85 ///////////////////////////////////////////////////////////////////////////////
  86 Entry * HashTable::lookup (Key k) const
  87 {  unsigned int h = (*hash)(k) % capacity;
  88    Entry * e = (Entry *)private_lookup(h,k);
  89    return e->hash_val >= 0 ? e : 0;
  90 }
  91
  92 ///////////////////////////////////////////////////////////////////////////////
  93 //  Insert a new element into the table.
  94 ///////////////////////////////////////////////////////////////////////////////
  95 void HashTable::insert (Key k, Value v)
  96 {  if (count >= growth_limit) grow(capacity * 7 / 4 + 32);
  97    unsigned int h = (*hash)(k) % capacity;
  98    Entry * e = (Entry*)private_lookup(h,k);
  99    if (e->hash_val >= 0) e->v = v;
 100    else { e->k = k; e->v = v; e->hash_val = h; count++; }
 101 }
 102
 103 ///////////////////////////////////////////////////////////////////////////////
 104 //  Returns the first element of the table.
 105 ///////////////////////////////////////////////////////////////////////////////
 106 Entry * HashTable::first() const
 107 {  if (count == 0) return 0;
 108    register const Entry * p, * q;
 109    for (p = table, q = table + capacity; p < q; p++)
 110       if (p->hash_val >= 0) return (Entry*)p;
 111    return 0;
 112 }
 113
 114 ///////////////////////////////////////////////////////////////////////////////
 115 //  Returns the next element from the table.
 116 ///////////////////////////////////////////////////////////////////////////////
 117 Entry * HashTable::next(Entry * p) const
 118 {  register const Entry * q;
 119    for (q = table + capacity, p++; p < q; p++)
 120       if (p->hash_val >= 0) return (Entry*)p;
 121    return 0;
 122 }
 123
 124 ///////////////////////////////////////////////////////////////////////////////
 125 //  Hashing and equality functions
 126 ///////////////////////////////////////////////////////////////////////////////
 127 unsigned int string_hash(Key k) {  return hash((const char *)k); }
 128 Bool         string_equal(Key a, Key b)
 129    { return strcmp((const char *)a, (const char *)b) == 0; }
 130 unsigned int integer_hash(Key k)         { return (unsigned int)k; }
 131 Bool         integer_equal(Key a, Key b) { return a == b; }