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