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> struct Hash_table_iter;
21 return int_hash ((unsigned int) p);
24 template<class K, class V>
25 struct Hash_table_entry
34 Hash_table_entry (K s, V v)
43 A hash table of prime size.
45 We use quadratic probing.
47 DEPRECATED. Use either SCM (preferred) or STL
49 template<class K, class V>
50 class Fixed_size_hash_table
53 Array<Hash_table_entry<K,V> > dict_arr_;
55 Fixed_size_hash_table (int size_idx)
58 int sz = prime_list(size_idx_);
59 dict_arr_.set_size (sz);
62 /// find #s#, or find first empty entry corresponding to #s#
63 int lookup (K s, unsigned int initial_hash)
65 int sz =dict_arr_.size ();
66 initial_hash = initial_hash % sz;
70 i = (initial_hash + j*j) % sz;
72 if (dict_arr_[i].free_b_)
75 if (dict_arr_[i].key_ == s)
85 /// remove #s# from the hash table.
86 V remove (K s, unsigned int initial_hash)
94 Hash table with sliding sizes.
96 template<class K, class V>
99 Fixed_size_hash_table<K,V> * fixed_p_;
100 /// set size to next prime, and copy contents
103 Fixed_size_hash_table<K,V> *f = new Fixed_size_hash_table<K,V> (fixed_p_->size_idx_ +1);
105 for (int i=0; i < fixed_p_->dict_arr_.size(); i++)
107 if (fixed_p_->dict_arr_[i].free_b_)
110 K nm (fixed_p_->dict_arr_[i].key_);
111 unsigned int h = (*hash_func_)(nm);
112 int nl = f->lookup (nm, h);
114 f->dict_arr_[nl] = Hash_table_entry<K,V> (nm, fixed_p_->dict_arr_[i].value_);
123 fixed_p_ = new Fixed_size_hash_table<K,V> (0);
129 void operator = (Hash_table<K,V> const &src)
135 fixed_p_ = new Fixed_size_hash_table<K,V> (*src.fixed_p_);
136 hash_func_ = src.hash_func_;
138 Hash_table (Hash_table<K,V> const &src)
140 fixed_p_ = new Fixed_size_hash_table<K,V> (*src.fixed_p_);
141 hash_func_ = src.hash_func_;
146 int i= fixed_p_->size_idx_;
148 fixed_p_ = new Fixed_size_hash_table<K,V> (i);
150 bool elem_b (K s) const
152 int l = fixed_p_->lookup (s, (*hash_func_)(s));
154 return (l >= 0 && !fixed_p_->dict_arr_[l].free_b_) ;
158 Find and return element. If #s# is not in the table, create an
159 entry in the table, and init */
163 unsigned int h = (*hash_func_)(s);
164 while ((l= fixed_p_->lookup (s,h)) <0)
169 fixed_p_->dict_arr_[l].free_b_ = false;
170 fixed_p_->dict_arr_[l].key_ = s;
171 return fixed_p_->dict_arr_[l].value_;
173 bool try_retrieve (K k, V *v)
175 int l = fixed_p_->lookup (k, (*hash_func_)(k));
176 if (l < 0 || fixed_p_->dict_arr_[l].free_b_)
180 *v = fixed_p_->dict_arr_[l].value_;
186 return const_elem (s);
188 V const_elem (K k) const
192 retval = ((Hash_table<K,V>*)this)->elem (k);
200 V operator [] (K k) const
202 return const_elem (k);
207 return fixed_p_->remove (s, (*hash_func_)(s));
209 friend class Hash_table_iter<K,V>;
211 unsigned int (*hash_func_)(K);
215 #endif /* HASH_TABLE_HH */