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