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