Edinburgh Speech Tools  2.1-release
EST_THash.cc
Go to the documentation of this file.
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>
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>
60 {
61  p_buckets=NULL;
62  copy(from);
63 }
64 
65 template<class K, class V>
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>
86 {
87  if (p_buckets)
88  {
89  clear();
90  delete[] p_buckets;
91  }
92 }
93 
94 
95 template<class K, class V>
96 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 
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>
114 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 
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>
136 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  {
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>
154 void EST_THash<K,V>::map(void (*func)(K&, V&))
155 {
156  for(unsigned int i=0; i<p_num_buckets; i++)
157  {
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>
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 
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>
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  std::cerr << "THash: no item labelled \"" << rkey << "\"" << std::endl;
217  return -1;
218 }
219 
220 template<class K, class V>
222 {
223  copy(from);
224  return *this;
225 }
226 
227 template<class K, class V>
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 << ": ";
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>
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  {
261  n->next = p_buckets[b];
262  p_buckets[b]=n;
263  }
264  }
265 }
266 
267 
268 
269 
270 
void clear(void)
Empty the table.
Definition: EST_THash.cc:66
EST_THash(int size, unsigned int(*hash_function)(const K &key, unsigned int size)=NULL)
Definition: EST_THash.cc:45
void copy(const EST_THash< K, V > &from)
Copy all entries.
Definition: EST_THash.cc:242
void map(void(*func)(K &, V &))
Apply func to each entry in the table.
Definition: EST_THash.cc:154
int remove_item(const K &rkey, int quiet=0)
Remove an entry from the table.
Definition: EST_THash.cc:195
~EST_THash(void)
Destroy the table.
Definition: EST_THash.cc:85
EST_THash< K, V > & operator=(const EST_THash< K, V > &from)
Assignment is a copy operation.
Definition: EST_THash.cc:221
V & val(const K &key, int &found) const
Definition: EST_THash.cc:114
V v
The value.
Definition: EST_THash.h:81
K k
The key.
Definition: EST_THash.h:79
int present(const K &key) const
Does the key have an entry?
Definition: EST_THash.cc:96
const K & key(const V &val, int &found) const
Definition: EST_THash.cc:136
#define FALSE
Definition: EST_bool.h:119
EST_TVector< T > & copy(EST_TVector< T > a, const EST_TList< T > &in)
NULL
Definition: EST_WFST.cc:55
int add_item(const K &key, const V &value, int no_search=0)
Add an entry to the table.
Definition: EST_THash.cc:167
An open hash table. The number of buckets should be set to allow enough space that there are relative...
Definition: EST_THash.h:69
void dump(ostream &stream, int all=0)
Print the table to stream in a human readable format.
Definition: EST_THash.cc:228
#define TRUE
Definition: EST_bool.h:118
This class is used in hash tables to hold a key value pair. Not much to say beyond that...
Definition: EST_THash.h:76