Edinburgh Speech Tools  2.1-release
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
EST_THash.h
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  /************************************************************************/
35 
36 #ifndef __EST_THASH_H__
37 #define __EST_THASH_H__
38 
39 #include <iostream>
40 
41 using namespace std;
42 
43 #include "EST_String.h"
44 #include "EST_system.h"
45 #include "EST_bool.h"
46 #include "EST_TIterator.h"
47 
48 #include "instantiate/EST_THashI.h"
49 #include "instantiate/EST_TStringHashI.h"
50 
51 /**@defgroup HashTables Hash Tables
52  * @ingroup containerclasses
53  *
54  * @author Richard Caley <rjc@cstr.ed.ac.uk>
55  * @version $Id: EST_THash.h,v 1.6 2004/09/29 08:24:17 robert Exp $
56  */
57 ///@{
58 
59 /** \class EST_HashFunctions
60  * \brief This is just a convenient place to put some useful hash functions.
61  */
63 public:
64  /// A generally useful hash function.
65  static unsigned int DefaultHash(const void *data, size_t size, unsigned int n);
66 
67  /// A hash function for strings.
68  static unsigned int StringHash(const EST_String &key, unsigned int size);
69 };
70 
71 template<class K, class V> class EST_THash;
72 
73 /** \class EST_Hash_Pair
74  * \brief This class is used in hash tables to hold a key value pair.
75  * Not much to say beyond that.
76  */
77 template<class K, class V>
79 public:
80  /// The key
81  K k;
82  /// The value
83  V v;
84 
85 private:
86  /// Pointer used to chain entries into buckets.
87  EST_Hash_Pair<K,V> *next;
88 
89  /// The hash table must be a friend so it can see the pointer.
90  friend class EST_THash<K, V>;
91 };
92 
93 /** \class EST_THash
94  * \brief An open hash table. The number of buckets should be set to allow
95  * enough space that there are relatively few entries per bucket on
96  * average.
97  */
98 template<class K, class V>
99 class EST_THash : protected EST_HashFunctions {
100 
101 private:
102  /// Something to return when there is no entry in the table.
103  static V Dummy_Value;
104  static K Dummy_Key;
105 
106  /// Total number of entries.
107  unsigned int p_num_entries;
108 
109  /// Number of buckets.
110  unsigned int p_num_buckets;
111 
112  /// Pointer to an array of <variable>p_num_buckets</variable>buckets.
113  EST_Hash_Pair<K,V> **p_buckets;
114 
115  /// The hash function to use on this table.
116  unsigned int (*p_hash_function)(const K &key, unsigned int size);
117 
118 public:
119  /** Create a table with the given number of buckets. Optionally setting
120  * a custom hash function.
121  */
122  EST_THash(int size,
123  unsigned int (*hash_function)(const K &key, unsigned int size)= NULL);
124 
125  /// Create a copy
126  EST_THash(const EST_THash<K,V> &from);
127 
128  /// Destroy the table.
129  ~EST_THash(void);
130 
131  /// Empty the table.
132  void clear(void);
133 
134  /// Return the total number of entries in the table.
135  unsigned int num_entries(void) const
136  { return p_num_entries; };
137 
138  /// Does the key have an entry?
139  int present(const K &key) const;
140 
141  /** Return the value associated with the key.
142  * `found` is set to whether such an entry was found.
143  */
144  V &val(const K &key, int &found) const;
145 
146  /// Return the value associated with the key.
147  V &val(const K &key) const {int x; return val(key, x); }
148 
149  const K &key(const V &val, int &found) const;
150  const K &key(const V &val) const {int x; return key(val, x); }
151 
152  /// Copy all entries
153  void copy(const EST_THash<K,V> &from);
154 
155  /// Apply `func` to each entry in the table.
156  void map(void (*func)(K&, V&));
157 
158  /// Add an entry to the table.
159  int add_item(const K &key, const V &value, int no_search = 0);
160 
161  /// Remove an entry from the table.
162  int remove_item(const K &rkey, int quiet = 0);
163 
164  /// Assignment is a copy operation
165  EST_THash<K,V> &operator = (const EST_THash<K,V> &from);
166 
167  /// Print the table to `stream` in a human readable format.
168  void dump(ostream &stream, int all=0);
169 
170  /**@name Pair Iteration
171  *
172  * This iterator steps through the table returning key-value pairs.
173  */
174  ///@{
175 protected:
176  /** A position in the table is given by a bucket number and a
177  * pointer into the bucket.
178  */
179  // struct IPointer{ unsigned int b; EST_Hash_Pair<K, V> *p; };
180  struct IPointer_s{ unsigned int b; EST_Hash_Pair<K, V> *p; };
181 
182  typedef struct IPointer_s IPointer;
183 
184  /// Shift to point at something.
185  void skip_blank(IPointer &ip) const
186  {
187  while (ip.p==NULL && ip.b<p_num_buckets)
188  {ip.b++; ip.p = ip.b<p_num_buckets?p_buckets[ip.b]:0; }
189  }
190 
191  /// Go to start of the table.
192  void point_to_first(IPointer &ip) const
193  { ip.b=0; ip.p = ip.b<p_num_buckets?p_buckets[ip.b]:0;
194  skip_blank(ip);}
195 
196  /// Move pointer forwards, at the end of the bucket, move down.
197  void move_pointer_forwards(IPointer &ip) const
198  {
199  ip.p = ip.p->next;
200  skip_blank(ip);
201  }
202 
203  /// We are at the end if the pointer ever becomes NULL
204  bool points_to_something(const IPointer &ip) const { return ip.b<p_num_buckets; }
205 
206  /// Return the contents of this entry.
207  EST_Hash_Pair<K, V> &points_at(const IPointer &ip) { return *(ip.p); }
208 
209  /// The iterator must be a friend to access this private interface.
210  friend class EST_TStructIterator< EST_THash<K, V>, IPointer, EST_Hash_Pair<K, V> >;
211  friend class EST_TRwStructIterator< EST_THash<K, V>, IPointer, EST_Hash_Pair<K, V> >;
212  friend class EST_TIterator< EST_THash<K, V>, IPointer, EST_Hash_Pair<K, V> >;
213  friend class EST_TRwIterator< EST_THash<K, V>, IPointer, EST_Hash_Pair<K, V> >;
214 
215 public:
216  /// An entry returned by the iterator is a key value pair.
218 
219  /// Give the iterator a sensible name.
222  ///@}
223 
224  /**@name Key Iteration
225  *
226  * This iterator steps through the table returning just keys.
227  */
228  ///@{
229 protected:
230  /** A position in the table is given by a bucket number and a
231  * pointer into the bucket.
232  */
233  struct IPointer_k_s { unsigned int b; EST_Hash_Pair<K, V> *p; };
234 
235  typedef struct IPointer_k_s IPointer_k;
236 
237  /// Shift to point at something.
238  void skip_blank(IPointer_k &ip) const
239  {
240  while (ip.p==NULL && ip.b<p_num_buckets)
241  {ip.b++; ip.p = ip.b<p_num_buckets?p_buckets[ip.b]:0; }
242  }
243 
244  /// Go to start of the table.
245  void point_to_first(IPointer_k &ip) const
246  { ip.b=0; ip.p = ip.b<p_num_buckets?p_buckets[ip.b]:0;
247  skip_blank(ip);}
248 
249  /// Move pointer forwards, at the end of the bucket, move down.
250  void move_pointer_forwards(IPointer_k &ip) const
251  {
252  ip.p = ip.p->next;
253  skip_blank(ip);
254  }
255 
256  /// We are at the end if the pointer ever becomes NULL
257  bool points_to_something(const IPointer_k &ip) const { return ip.b<p_num_buckets; }
258 
259  /// Return the key of this entry.
260  K &points_at(const IPointer_k &ip) { return (ip.p)->k; }
261 
262  /// The iterator must be a friend to access this private interface.
263  friend class EST_TIterator< EST_THash<K, V>, IPointer_k, K >;
264  friend class EST_TRwIterator< EST_THash<K, V>, IPointer_k, K >;
265 
266 public:
267  /// An entry returned by this iterator is just a key.
268  typedef K KeyEntry;
269 
270  /// Give the iterator a sensible name.
271  typedef EST_TIterator< EST_THash<K, V>, IPointer_k, K > KeyEntries;
272  typedef EST_TRwIterator< EST_THash<K, V>, IPointer_k, K > KeyRwEntries;
273  ///@}
274 
275 };
276 
277 /** \class EST_TStringHash
278  * \brief A specialised hash table for when the key is an EST_String.
279  *
280  * This is just a version of EST_THash which
281  * has a different default hash function.
282  */
283 template<class V>
284 class EST_TStringHash : public EST_THash<EST_String, V> {
285 public:
286 
287  /// Create a string hash table of `size` buckets.
288  EST_TStringHash(int size) : EST_THash<EST_String, V>(size, EST_HashFunctions::StringHash) {};
289 
290  /// An entry returned by the iterator is a key value pair.
291  typedef EST_Hash_Pair<EST_String, V> Entry;
292 
293 /* struct IPointer_s{ unsigned int b; Entry *p; };
294  typedef struct IPointer_s IPointer; */
295 
296  // Convince GCC that the IPointer we're going to use is a typename
297  typedef typename EST_THash<EST_String, V>::IPointer TN_IPointer;
298 
299  /// Give the iterator a sensible name.
302 
303  typedef EST_TRwStructIterator< EST_THash<EST_String, V>, typename EST_THash<EST_String, V>::IPointer,
305 
306  typedef EST_String KeyEntry;
307 
308 /* struct IPointer_k_s { unsigned int b; EST_Hash_Pair<EST_String, V> *p; };
309  typedef struct IPointer_k_s IPointer_k; */
310 
311  /// Give the iterator a sensible name.
312 
313  // Convince GCC that the IPointer_k we're going to use is a typename
315 
318  typedef EST_TRwIterator< EST_THash<EST_String, V>, typename EST_THash<EST_String, V>::IPointer_k,
320 };
321 
322  ///@}
323 
324 /** \brief The default hash function used by EST_THash
325  */
326 inline static unsigned int DefaultHashFunction(const void *data, size_t size, unsigned int n)
327 {
328  unsigned int x=0;
329  const char *p = (const char *)data;
330  for(; size>0 ; p++, size--)
331  x = ((x+*p)*33) % n;
332  return x;
333 }
334 
335 #endif
EST_TStructIterator< EST_THash< K, V >, IPointer, EST_Hash_Pair< K, V > > Entries
Give the iterator a sensible name.
Definition: EST_THash.h:220
An open hash table. The number of buckets should be set to allow enough space that there are relative...
Definition: EST_THash.h:71
void skip_blank(IPointer &ip) const
Shift to point at something.
Definition: EST_THash.h:185
EST_TStructIterator< EST_THash< EST_String, V >, typename EST_THash< EST_String, V >::IPointer, EST_Hash_Pair< EST_String, V > > Entries
Give the iterator a sensible name.
Definition: EST_THash.h:301
A specialised hash table for when the key is an EST_String.
Definition: EST_THash.h:284
bool points_to_something(const IPointer &ip) const
We are at the end if the pointer ever becomes NULL.
Definition: EST_THash.h:204
void point_to_first(IPointer_k &ip) const
Go to start of the table.
Definition: EST_THash.h:245
EST_TIterator< EST_THash< K, V >, IPointer_k, K > KeyEntries
Give the iterator a sensible name.
Definition: EST_THash.h:271
K & points_at(const IPointer_k &ip)
Return the key of this entry.
Definition: EST_THash.h:260
EST_TStringHash(int size)
Create a string hash table of size buckets.
Definition: EST_THash.h:288
void skip_blank(IPointer_k &ip) const
Shift to point at something.
Definition: EST_THash.h:238
void point_to_first(IPointer &ip) const
Go to start of the table.
Definition: EST_THash.h:192
EST_THash< EST_String, V >::IPointer_k TN_IPointer_k
Give the iterator a sensible name.
Definition: EST_THash.h:314
EST_Hash_Pair< K, V > Entry
An entry returned by the iterator is a key value pair.
Definition: EST_THash.h:217
V v
The value.
Definition: EST_THash.h:83
K k
The key.
Definition: EST_THash.h:81
V & val(const K &key) const
Return the value associated with the key.
Definition: EST_THash.h:147
unsigned int num_entries(void) const
Return the total number of entries in the table.
Definition: EST_THash.h:135
This is just a convenient place to put some useful hash functions.
Definition: EST_THash.h:62
EST_Hash_Pair< K, V > & points_at(const IPointer &ip)
Return the contents of this entry.
Definition: EST_THash.h:207
void move_pointer_forwards(IPointer_k &ip) const
Move pointer forwards, at the end of the bucket, move down.
Definition: EST_THash.h:250
void move_pointer_forwards(IPointer &ip) const
Move pointer forwards, at the end of the bucket, move down.
Definition: EST_THash.h:197
This class is used in hash tables to hold a key value pair. Not much to say beyond that...
Definition: EST_THash.h:78
bool points_to_something(const IPointer_k &ip) const
We are at the end if the pointer ever becomes NULL.
Definition: EST_THash.h:257
K KeyEntry
An entry returned by this iterator is just a key.
Definition: EST_THash.h:268