2 hash-table.hh -- declare Hash_table_entry, Hash_table
4 source file of the Flower Library
6 (c) 1999 Han-Wen Nienhuys <hanwen@cs.uu.nl>
13 unsigned int int_hash (int);
14 unsigned long prime_list (int idx);
20 return int_hash ((unsigned int) p);
23 template<class K, class V>
24 struct Hash_table_entry
33 Hash_table_entry (K s, V v)
42 A hash table of prime size.
44 We use quadratic probing.
46 template<class K, class V>
47 class Fixed_size_hash_table
50 Array<Hash_table_entry<K,V> > dict_arr_;
52 Fixed_size_hash_table (int size_idx)
55 int sz = prime_list(size_idx_);
56 dict_arr_.set_size (sz);
59 /// find #s#, or find first empty entry corresponding to #s#
60 int lookup (K s, unsigned int initial_hash)
62 int sz =dict_arr_.size ();
63 int i = initial_hash % sz;
66 if (dict_arr_[i].free_b_)
69 if (dict_arr_[i].key_ == s)
79 /// remove #s# from the hash table.
80 V remove (K s, unsigned int initial_hash)
82 int sz =dict_arr_.size ();
83 int i = initial_hash % sz;
88 duplicate with lookup, but we need value of j
91 while (j <= sz/2 && dict_arr_[i].key_ != s)
93 assert (!dict_arr_[i].free_b_);
100 int nexti = (i + j*j) % sz;
102 while (j <= sz/2 && !dict_arr_[i].free_b_)
104 dict_arr_[i] = dict_arr_[nexti];
107 nexti = (nexti + j*j)%sz;
115 Hash table with sliding sizes.
117 template<class K, class V>
120 Fixed_size_hash_table<K,V> * fixed_p_;
121 /// set size to next prime, and copy contents
124 Fixed_size_hash_table<K,V> *f = new Fixed_size_hash_table<K,V> (fixed_p_->size_idx_ +1);
126 for (int i=0; i < fixed_p_->dict_arr_.size(); i++)
128 if (fixed_p_->dict_arr_[i].free_b_)
131 K nm (fixed_p_->dict_arr_[i].key_);
132 unsigned int h = (*hash_func_)(nm);
133 int nl = f->lookup (nm, h);
135 f->dict_arr_[nl] = Hash_table_entry<K,V> (nm, fixed_p_->dict_arr_[i].value_);
144 fixed_p_ = new Fixed_size_hash_table<K,V> (0);
150 void operator = (Hash_table<K,V> const &src)
156 fixed_p_ = new Fixed_size_hash_table<K,V> (*src.fixed_p_);
157 hash_func_ = src.hash_func_;
159 Hash_table (Hash_table<K,V> const &src)
161 fixed_p_ = new Fixed_size_hash_table<K,V> (*src.fixed_p_);
162 hash_func_ = src.hash_func_;
167 int i= fixed_p_->size_idx_;
169 fixed_p_ = new Fixed_size_hash_table<K,V> (i);
171 bool elem_b (K s) const
173 int l = fixed_p_->lookup (s, (*hash_func_)(s));
175 return (l >= 0 && !fixed_p_->dict_arr_[l].free_b_) ;
179 Find and return element. If #s# is not in the table, create an entry in the table, and init
184 unsigned int h = (*hash_func_)(s);
185 while ((l= fixed_p_->lookup (s,h)) <0)
190 fixed_p_->dict_arr_[l].free_b_ = false;
191 fixed_p_->dict_arr_[l].key_ = s;
192 return fixed_p_->dict_arr_[l].value_;
196 return const_elem (s);
198 V const_elem (K k) const
202 retval = ((Hash_table<K,V>*)this)->elem (k);
210 V operator [] (K k) const
212 return const_elem (k);
217 return fixed_p_->remove (s, (*hash_func_)(s));
219 friend class Hash_table_iter<K,V>;
221 unsigned int (*hash_func_)(K);
225 #endif /* HASH_TABLE_HH */