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