flower/include/dictionary.hh

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