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);
15 template<class K, class V>
16 struct Hash_table_entry
25 Hash_table_entry (K s, V v)
34 A hash table of prime size.
36 We use quadratic probing.
38 template<class K, class V>
39 class Fixed_size_hash_table
42 Array<Hash_table_entry<K,V> > dict_arr_;
44 Fixed_size_hash_table (int size_idx)
47 int sz = prime_list(size_idx_);
48 dict_arr_.set_size (sz);
51 /// find #s#, or find first empty entry corresponding to #s#
52 int lookup (K s, unsigned int initial_hash)
54 int sz =dict_arr_.size ();
55 int i = initial_hash % sz;
58 if (dict_arr_[i].free_b_)
61 if (dict_arr_[i].key_ == s)
71 /// remove #s# from the hash table.
72 V remove (K s, unsigned int initial_hash)
74 assert (false); // Untested routine.
75 int sz =dict_arr_.size ();
76 int i = initial_hash % sz;
79 while (j <= sz/2 && dict_arr_[i].key_ != s)
81 assert (!dict_arr_[i].free_b_);
89 int nexti = (i + j*j) % sz;
91 while (j <= sz/2 && !dict_arr_[i].free_b_)
93 dict_arr_[i] = dict_arr_[nexti];
96 nexti = (nexti + j*j)%sz;
104 Hash table with sliding sizes.
106 template<class K, class V>
109 Fixed_size_hash_table<K,V> * fixed_p_;
110 /// set size to next prime, and copy contents
113 Fixed_size_hash_table<K,V> *f = new Fixed_size_hash_table<K,V> (fixed_p_->size_idx_ +1);
115 for (int i=0; i < fixed_p_->dict_arr_.size(); i++)
117 if (fixed_p_->dict_arr_[i].free_b_)
120 K nm (fixed_p_->dict_arr_[i].key_);
121 unsigned int h = (*hash_func_)(nm);
122 int nl = f->lookup (nm, h);
124 f->dict_arr_[nl] = Hash_table_entry<K,V> (nm, fixed_p_->dict_arr_[i].value_);
133 fixed_p_ = new Fixed_size_hash_table<K,V> (0);
139 void operator = (Hash_table<K,V> const &src)
145 fixed_p_ = new Fixed_size_hash_table<K,V> (*src.fixed_p_);
146 hash_func_ = src.hash_func_;
148 Hash_table (Hash_table<K,V> const &src)
150 fixed_p_ = new Fixed_size_hash_table<K,V> (*src.fixed_p_);
151 hash_func_ = src.hash_func_;
156 int i= fixed_p_->size_idx_;
158 fixed_p_ = new Fixed_size_hash_table<K,V> (i);
160 bool elem_b (K s) const
162 int l = fixed_p_->lookup (s, (*hash_func_)(s));
164 return (l >= 0 && !fixed_p_->dict_arr_[l].free_b_) ;
168 Find and return element. If #s# is not in the table, create an entry in the table, and init
173 unsigned int h = (*hash_func_)(s);
174 while ((l= fixed_p_->lookup (s,h)) <0)
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_;
185 return const_elem (s);
187 V const_elem (K k) const
191 retval = ((Hash_table<K,V>*)this)->elem (k);
199 V operator [] (K k) const
201 return const_elem (k);
206 return fixed_p_->remove (s, (*hash_func_)(s));
208 friend class Hash_table_iter<K,V>;
210 unsigned int (*hash_func_)(K);
214 #endif /* HASH_TABLE_HH */