1 /************************************************************************/
2 /* */
3 /* Centre for Speech Technology Research */
4 /* University of Edinburgh, UK */
5 /* Copyright (c) 1996,1997 */
6 /* All Rights Reserved. */
7 /* */
8 /* Permission is hereby granted, free of charge, to use and distribute */
9 /* this software and its documentation without restriction, including */
10 /* without limitation the rights to use, copy, modify, merge, publish, */
11 /* distribute, sublicense, and/or sell copies of this work, and to */
12 /* permit persons to whom this work is furnished to do so, subject to */
13 /* the following conditions: */
14 /* 1. The code must retain the above copyright notice, this list of */
15 /* conditions and the following disclaimer. */
16 /* 2. Any modifications must be clearly marked as such. */
17 /* 3. Original authors' names are not deleted. */
18 /* 4. The authors' names are not used to endorse or promote products */
19 /* derived from this software without specific prior written */
20 /* permission. */
21 /* */
22 /* THE UNIVERSITY OF EDINBURGH AND THE CONTRIBUTORS TO THIS WORK */
23 /* DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING */
24 /* ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT */
25 /* SHALL THE UNIVERSITY OF EDINBURGH NOR THE CONTRIBUTORS BE LIABLE */
26 /* FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES */
27 /* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN */
28 /* AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, */
29 /* ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF */
30 /* THIS SOFTWARE. */
31 /* */
32 /************************************************************************/
33 /* Author: Richard Caley (rjc@cstr.ed.ac.uk) */
34 /* Date: Fri Apr 4 1997 */
35 /************************************************************************/
36 /* */
37 /* Simple Hash classes. */
38 /* */
39 /************************************************************************/
40
41
42 #include "EST_THash.h"
43
44 template<class K, class V>
EST_THash(int size,unsigned int (* hash_function)(const K & key,unsigned int size))45 EST_THash<K,V>::EST_THash(int size, unsigned int (*hash_function)(const K &key, unsigned int size))
46 {
47 p_num_entries =0;
48
49 p_num_buckets = size;
50
51 p_buckets = new EST_Hash_Pair<K,V> *[size];
52 for(int i=0; i<size;i++)
53 p_buckets[i] = NULL;
54
55 p_hash_function = hash_function;
56 }
57
58 template<class K, class V>
EST_THash(const EST_THash<K,V> & from)59 EST_THash<K,V>::EST_THash(const EST_THash<K,V> &from)
60 {
61 p_buckets=NULL;
62 copy(from);
63 }
64
65 template<class K, class V>
clear(void)66 void EST_THash<K,V>::clear(void)
67 {
68 if (p_buckets != NULL)
69 {
70 for(unsigned int i=0; i<p_num_buckets;i++)
71 {
72 EST_Hash_Pair<K,V> *p, *n;
73 for(p=p_buckets[i]; p != NULL; p=n)
74 {
75 n = p->next;
76 delete p;
77 }
78 p_buckets[i]=NULL;
79 }
80 }
81 p_num_entries=0;
82 }
83
84 template<class K, class V>
~EST_THash(void)85 EST_THash<K,V>::~EST_THash(void)
86 {
87 if (p_buckets)
88 {
89 clear();
90 delete[] p_buckets;
91 }
92 }
93
94
95 template<class K, class V>
present(const K & key) const96 int EST_THash<K,V>::present(const K &key) const
97 {
98 unsigned int b;
99 if (p_hash_function)
100 b = (*p_hash_function)(key, p_num_buckets);
101 else
102 b = DefaultHashFunction((void *)&key, sizeof(key), p_num_buckets);
103
104 EST_Hash_Pair<K,V> *p;
105
106 for(p=p_buckets[b]; p!=NULL; p=p->next)
107 if (p->k == key)
108 return TRUE;
109
110 return FALSE;
111 }
112
113 template<class K, class V>
val(const K & key,int & found) const114 V &EST_THash<K,V>::val(const K &key, int &found) const
115 {
116 unsigned int b;
117 if (p_hash_function)
118 b = (*p_hash_function)(key, p_num_buckets);
119 else
120 b = DefaultHashFunction((void *)&key, sizeof(key), p_num_buckets);
121
122 EST_Hash_Pair<K,V> *p;
123
124 for(p=p_buckets[b]; p!=NULL; p=p->next)
125 if (p->k == key)
126 {
127 found=1;
128 return p->v;
129 }
130
131 found=0;
132 return Dummy_Value;
133 }
134
135 template<class K, class V>
key(const V & val,int & found) const136 const K &EST_THash<K,V>::key(const V &val, int &found) const
137 {
138
139 for(unsigned int b=0; b<p_num_buckets; b++)
140 {
141 EST_Hash_Pair<K,V> *p;
142 for(p=p_buckets[b]; p!=NULL; p=p->next)
143 if (p->v == val)
144 {
145 found=1;
146 return p->k;
147 }
148 }
149 found=0;
150 return Dummy_Key;
151 }
152
153 template<class K, class V>
map(void (* func)(K &,V &))154 void EST_THash<K,V>::map(void (*func)(K&, V&))
155 {
156 for(unsigned int i=0; i<p_num_buckets; i++)
157 {
158 EST_Hash_Pair<K,V> *p;
159
160 for(p=p_buckets[i]; p!=NULL; p=p->next)
161 (*func)(p->k, p->v);
162 }
163
164 }
165
166 template<class K, class V>
add_item(const K & key,const V & value,int no_search)167 int EST_THash<K,V>::add_item(const K &key, const V &value, int no_search)
168 {
169 unsigned int b;
170 if (p_hash_function)
171 b = (*p_hash_function)(key, p_num_buckets);
172 else
173 b = DefaultHashFunction((void *)&key, sizeof(key), p_num_buckets);
174
175 EST_Hash_Pair<K,V> *p;
176
177 if (!no_search)
178 for(p=p_buckets[b]; p!=NULL; p=p->next)
179 if (p->k == key)
180 {
181 p->v = value;
182 return FALSE;
183 }
184
185 p = new EST_Hash_Pair<K,V>;
186 p->k = key;
187 p->v = value;
188 p->next = p_buckets[b];
189 p_buckets[b] = p;
190 p_num_entries++;
191 return TRUE;
192 }
193
194 template<class K, class V>
remove_item(const K & rkey,int quiet)195 int EST_THash<K,V>::remove_item(const K &rkey, int quiet)
196 {
197 unsigned int b;
198 if (p_hash_function)
199 b = (*p_hash_function)(rkey, p_num_buckets);
200 else
201 b = DefaultHashFunction((void *)&rkey, sizeof(rkey), p_num_buckets);
202
203 EST_Hash_Pair<K,V> **p;
204
205 for (p = &(p_buckets[b]); *p!=NULL; p=&((*p)->next))
206 if ( (*p)->k == rkey )
207 {
208 EST_Hash_Pair<K,V> *n = (*p)->next;
209 delete *p;
210 *p = n;
211 p_num_entries--;
212 return 0;
213 }
214
215 if (!quiet)
216 cerr << "THash: no item labelled \"" << rkey << "\"" << endl;
217 return -1;
218 }
219
220 template<class K, class V>
operator =(const EST_THash<K,V> & from)221 EST_THash<K,V> &EST_THash<K,V>::operator = (const EST_THash<K,V> &from)
222 {
223 copy(from);
224 return *this;
225 }
226
227 template<class K, class V>
dump(ostream & stream,int all)228 void EST_THash<K,V>::dump(ostream &stream, int all)
229 {
230 for(unsigned int i=0; i<p_num_buckets; i++)
231 if (all || p_buckets[i])
232 {
233 stream << i << ": ";
234 EST_Hash_Pair<K,V> *p;
235 for(p=p_buckets[i]; p!=NULL; p=p->next)
236 stream << "[" << p->k << "],(" << p->v << ") ";
237 stream << "\n";
238 }
239 }
240
241 template<class K, class V>
copy(const EST_THash<K,V> & from)242 void EST_THash<K,V>::copy(const EST_THash<K,V> &from)
243 {
244 clear();
245 p_num_entries = from.p_num_entries;
246 p_num_buckets = from.p_num_buckets;
247 p_hash_function = from.p_hash_function;
248
249 if (p_buckets != NULL)
250 delete [] p_buckets;
251
252 p_buckets = new EST_Hash_Pair<K,V> *[p_num_buckets];
253
254
255 for(unsigned int b=0; b<p_num_buckets; b++)
256 {
257 p_buckets[b]=NULL;
258 for(EST_Hash_Pair<K,V> *p=from.p_buckets[b]; p; p=p->next)
259 {
260 EST_Hash_Pair<K,V> *n = new EST_Hash_Pair<K,V>(*p);
261 n->next = p_buckets[b];
262 p_buckets[b]=n;
263 }
264 }
265 }
266
267
268
269
270
271