flower/include/hash-table.hh

   1 /*
   2   hash-table.hh -- declare Hash_table_entry, Hash_table
   3
   4   source file of the Flower Library
   5
   6   (c) 1999 Han-Wen Nienhuys <hanwen@cs.uu.nl>
   7
   8  */
   9
  10 #ifndef HASH_TABLE_HH
  11 #define HASH_TABLE_HH
  12
  13 unsigned int int_hash (int);
  14 unsigned long prime_list (int idx);
  15
  16 template<class K>
  17 unsigned int
  18 pointer_hash (K *p)
  19 {
  20   return int_hash ((unsigned int) p);
  21 }
  22
  23 template<class K, class V>
  24 struct Hash_table_entry
  25 {
  26   K key_;
  27   V value_;
  28   bool free_b_;
  29
  30   Hash_table_entry() {
  31     free_b_ = true;
  32   }
  33   Hash_table_entry (K s, V v)
  34     {
  35       key_ = s;
  36       value_ = v;
  37       free_b_ = false;
  38     }
  39 };
  40
  41 /**
  42    A hash table of prime size.
  43
  44    We use quadratic probing.
  45  */
  46 template<class K, class V>
  47 class Fixed_size_hash_table
  48 {
  49 public:
  50   Array<Hash_table_entry<K,V> > dict_arr_;
  51   int size_idx_;
  52   Fixed_size_hash_table (int size_idx)
  53     {
  54       size_idx_ = size_idx;
  55       int sz = prime_list(size_idx_);
  56       dict_arr_.set_size (sz);
  57     }
  58
  59   /// find #s#, or find first empty entry corresponding to #s#
  60   int lookup  (K s, unsigned int initial_hash)
  61     {
  62       int sz =dict_arr_.size ();
  63       int i = initial_hash % sz;
  64       int j = 0;
  65       while (j <= sz/2) {
  66         if (dict_arr_[i].free_b_)
  67           return i;
  68
  69         if (dict_arr_[i].key_ == s)
  70           return i;
  71
  72         j++;
  73         i = (i + j*j) % sz;
  74       }
  75
  76       return -1;
  77     }
  78
  79   /// remove #s# from the hash table.
  80   V remove (K s, unsigned int initial_hash)
  81     {
  82       int sz =dict_arr_.size ();
  83       int i = initial_hash % sz;
  84       int j = 0;
  85       V retval;
  86
  87       /*
  88         duplicate with lookup, but we need value of j
  89        */
  90
  91       while (j <= sz/2 && dict_arr_[i].key_ != s)
  92         {
  93           assert (!dict_arr_[i].free_b_);
  94
  95           j ++;
  96           i = (i + j*j) % sz;
  97         }
  98
  99       j++;
 100       int nexti = (i + j*j) % sz;
 101
 102       while (j <= sz/2 && !dict_arr_[i].free_b_)
 103         {
 104           dict_arr_[i] = dict_arr_[nexti];
 105           j++;
 106           i = nexti;
 107           nexti = (nexti + j*j)%sz;
 108         }
 109
 110       return retval;
 111     }
 112 };
 113
 114 /**
 115    Hash table with sliding sizes.
 116  */
 117 template<class K, class V>
 118 class Hash_table
 119 {
 120   Fixed_size_hash_table<K,V> * fixed_p_;
 121   /// set size to next prime, and copy contents
 122   void enlarge ()
 123     {
 124       Fixed_size_hash_table<K,V> *f = new Fixed_size_hash_table<K,V> (fixed_p_->size_idx_ +1);
 125
 126       for (int i=0; i < fixed_p_->dict_arr_.size(); i++)
 127         {
 128           if (fixed_p_->dict_arr_[i].free_b_)
 129             continue;
 130
 131           K nm (fixed_p_->dict_arr_[i].key_);
 132           unsigned int h = (*hash_func_)(nm);
 133           int nl = f->lookup (nm, h);
 134
 135           f->dict_arr_[nl] = Hash_table_entry<K,V> (nm, fixed_p_->dict_arr_[i].value_);
 136         }
 137       delete fixed_p_;
 138       fixed_p_ = f;
 139     }
 140 public:
 141   Hash_table ()
 142     {
 143       hash_func_ = 0;
 144       fixed_p_ = new Fixed_size_hash_table<K,V> (0);
 145     }
 146   ~Hash_table ()
 147     {
 148       delete fixed_p_;
 149     }
 150   void operator = (Hash_table<K,V> const &src)
 151     {
 152       if (&src == this)
 153         return;
 154
 155       delete fixed_p_;
 156       fixed_p_ = new Fixed_size_hash_table<K,V> (*src.fixed_p_);
 157       hash_func_ = src.hash_func_;
 158     }
 159   Hash_table (Hash_table<K,V> const &src)
 160     {
 161       fixed_p_ = new Fixed_size_hash_table<K,V> (*src.fixed_p_);
 162       hash_func_ = src.hash_func_;
 163     }
 164
 165   void clear ()
 166     {
 167       int i= fixed_p_->size_idx_;
 168       delete fixed_p_;
 169       fixed_p_ = new Fixed_size_hash_table<K,V> (i);
 170     }
 171   bool elem_b (K s) const
 172     {
 173       int l =  fixed_p_->lookup (s, (*hash_func_)(s));
 174
 175       return (l >= 0 && !fixed_p_->dict_arr_[l].free_b_) ;
 176     }
 177
 178   /**
 179      Find and return element.  If #s# is not in the table, create an entry in the table, and init
 180    */
 181   V& elem (K s)
 182     {
 183       int l;
 184       unsigned int h = (*hash_func_)(s);
 185       while ((l= fixed_p_->lookup (s,h)) <0)
 186         {
 187           enlarge ();
 188         }
 189
 190        fixed_p_->dict_arr_[l].free_b_ = false;
 191        fixed_p_->dict_arr_[l].key_ = s;
 192        return fixed_p_->dict_arr_[l].value_;
 193     }
 194   V elem (K s) const
 195     {
 196       return const_elem (s);
 197     }
 198   V const_elem (K k) const
 199   {
 200       V retval;
 201       assert (elem_b (k));
 202       retval = ((Hash_table<K,V>*)this)->elem (k);
 203       return retval;
 204   }
 205   V& operator [] (K k)
 206     {
 207       return elem (k);
 208     }
 209
 210   V operator [] (K k) const
 211     {
 212       return const_elem (k);
 213     }
 214
 215   V remove (K s)
 216     {
 217       return fixed_p_->remove (s, (*hash_func_)(s));
 218     }
 219   friend class Hash_table_iter<K,V>;
 220 public:
 221   unsigned int (*hash_func_)(K);
 222 };
 223
 224
 225 #endif /* HASH_TABLE_HH */
 226