1 karl 1.19 //%2005////////////////////////////////////////////////////////////////////////
|
2 mike 1.11 //
|
3 karl 1.17 // Copyright (c) 2000, 2001, 2002 BMC Software; Hewlett-Packard Development
4 // Company, L.P.; IBM Corp.; The Open Group; Tivoli Systems.
5 // Copyright (c) 2003 BMC Software; Hewlett-Packard Development Company, L.P.;
|
6 karl 1.15 // IBM Corp.; EMC Corporation, The Open Group.
|
7 karl 1.17 // Copyright (c) 2004 BMC Software; Hewlett-Packard Development Company, L.P.;
8 // IBM Corp.; EMC Corporation; VERITAS Software Corporation; The Open Group.
|
9 karl 1.19 // Copyright (c) 2005 Hewlett-Packard Development Company, L.P.; IBM Corp.;
10 // EMC Corporation; VERITAS Software Corporation; The Open Group.
|
11 mike 1.11 //
12 // Permission is hereby granted, free of charge, to any person obtaining a copy
|
13 kumpf 1.13 // of this software and associated documentation files (the "Software"), to
14 // deal in the Software without restriction, including without limitation the
15 // rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
|
16 mike 1.11 // sell copies of the Software, and to permit persons to whom the Software is
17 // furnished to do so, subject to the following conditions:
|
18 karl 1.19 //
|
19 kumpf 1.13 // THE ABOVE COPYRIGHT NOTICE AND THIS PERMISSION NOTICE SHALL BE INCLUDED IN
|
20 mike 1.11 // ALL COPIES OR SUBSTANTIAL PORTIONS OF THE SOFTWARE. THE SOFTWARE IS PROVIDED
21 // "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT
|
22 kumpf 1.13 // LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
23 // PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
24 // HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
|
25 mike 1.11 // ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
27 //
28 //==============================================================================
29 //
30 // Author: Mike Brasher (mbrasher@bmc.com)
31 //
|
32 r.kieninger 1.18 // Modified By: Carol Ann Krug Graves, Hewlett-Packard Company
|
33 kumpf 1.16 // (carolann_graves@hp.com)
|
34 mike 1.11 //
35 //%/////////////////////////////////////////////////////////////////////////////
36
37 #ifndef Pegasus_HashTable_h
38 #define Pegasus_HashTable_h
39
40 #include <Pegasus/Common/Config.h>
41 #include <Pegasus/Common/String.h>
|
42 kumpf 1.14 #include <Pegasus/Common/Linkage.h>
|
43 mike 1.11
44 PEGASUS_NAMESPACE_BEGIN
45
46 /* This is the default hash function object used by the HashTable template.
47 Specializations are provided for common types.
48 */
49 template<class K>
50 struct HashFunc
51 {
52 };
53
54 PEGASUS_TEMPLATE_SPECIALIZATION struct PEGASUS_COMMON_LINKAGE HashFunc<String>
55 {
56 static Uint32 hash(const String& str);
57 };
58
59 PEGASUS_TEMPLATE_SPECIALIZATION struct HashFunc<Uint32>
60 {
61 static Uint32 hash(Uint32 x) { return x + 13; }
62 };
63
|
64 kumpf 1.16 /*
|
65 r.kieninger 1.18 Hash function object that converts to lowercase.
|
66 kumpf 1.16
67 This function can be used for hash table keys constructed from strings that
|
68 r.kieninger 1.18 should be treated as case insensitive (e.g. class names, namespace names,
69 system names).
|
70 kumpf 1.16
71 Note: this function converts to lower case based on the process locale.
72 */
73 struct HashLowerCaseFunc
74 {
75 static Uint32 hash (const String & str)
76 {
77 String cpy (str);
78 cpy.toLower ();
79 Uint32 h = 0;
80 for (Uint32 i = 0, n = cpy.size (); i < n; i++)
81 h = 5 * h + cpy [i];
82 return h;
83 }
84 };
85
|
86 mike 1.11 /* This is a function object used by the HashTable to compare keys. This is
|
87 r.kieninger 1.18 the default implementation. Others may be defined and passed in the
|
88 mike 1.11 template argument list to perform other kinds of comparisons.
89 */
90 template<class K>
91 struct EqualFunc
92 {
93 static Boolean equal(const K& x, const K& y)
94 {
95 return x == y;
|
96 kumpf 1.16 }
97 };
98
99 /*
|
100 r.kieninger 1.18 Equal function object that can be used by HashTable to compare keys that
101 should be treated as case insensitive.
|
102 kumpf 1.16
103 This function can be used for hash table keys constructed from strings that
|
104 r.kieninger 1.18 should be treated as case insensitive (e.g. class names, namespace names,
|
105 kumpf 1.16 system names).
106
107 Note: this function compares Strings based on the process locale.
108 */
109 struct EqualNoCaseFunc
110 {
111 static Boolean equal (const String & x, const String & y)
112 {
113 return (0 == String::compareNoCase (x, y));
|
114 mike 1.11 }
115 };
116
117 /* Representation for a bucket. The HashTable class derives from this
118 bucket to append a key and value. This base class just defines
119 the pointer to the next bucket in the chain.
120 */
121 class PEGASUS_COMMON_LINKAGE _BucketBase
122 {
123 public:
124
125 /* Default constructor. */
126 _BucketBase() : next(0) { }
127
|
128 r.kieninger 1.18 /* Virtual destructor to ensure destruction of derived class
|
129 mike 1.11 elements.
130 */
131 virtual ~_BucketBase();
132
133 /* returns true if the key pointed to by the key argument is equal
134 to the internal key of this bucket. This method must be overridden
135 by the derived class.
136 */
137 virtual Boolean equal(const void* key) const = 0;
138
139 /* Clone this bucket. */
140 virtual _BucketBase* clone() const = 0;
141
142 _BucketBase* next;
143 };
144
145 class _HashTableRep;
146
147 /* This class implements a simple hash table forward iterator. */
148 class PEGASUS_COMMON_LINKAGE _HashTableIteratorBase
149 {
150 mike 1.11 public:
|
151 r.kieninger 1.18
|
152 mike 1.11 _HashTableIteratorBase() : _first(0), _last(0), _bucket(0) { }
153
154 operator int() const { return _bucket != 0; }
155
156 _HashTableIteratorBase operator++(int);
157
158 _HashTableIteratorBase& operator++();
159
160 _HashTableIteratorBase(_BucketBase** first, _BucketBase** last);
161
162 protected:
163
164 _BucketBase** _first;
165 _BucketBase** _last;
166 _BucketBase* _bucket;
167 friend class _HashTableRep;
168 };
169
170 // ATTN: reorganization not supported yet.
171
172 /*- The _HashTableRep class is the representation class used by HashTable.
173 mike 1.11
174 This code is primarily an internal class used to implement the HashTable.
175 But there may be occasions to use it directly.
176
|
177 r.kieninger 1.18 _HashTableRep parcels out much of the large code so that that code is not
178 instantiated by the HashTable template class many times. This scheme helps
|
179 mike 1.11 reduce code bloat caused by templates. The HashTable template class below
180 acts as kind of a wrapper around this class.
181
182 _HashTableRep is implemented as an array of pointers to chains of hash
183 buckets. The table initially allocates some number of chains (which can
184 be controlled by the constructor) and then may increase the number of
185 chains later (resulting in a reorganization of the hash table).
186 */
187 class PEGASUS_COMMON_LINKAGE _HashTableRep
188 {
189 public:
190
191 /*- This constructor allocates an array of pointers to chains of buckets,
192 which of course are all empty at this time. The numChains argument
193 If the numChains argument is less than eight, then eight chains will
194 be created.
195 @param numChains specifies the initial number of chains.
196 */
197 _HashTableRep(Uint32 numChains);
198
199 /*- Copy constructor. */
200 mike 1.11 _HashTableRep(const _HashTableRep& x);
201
202 /*- Destructor. */
203 ~_HashTableRep();
204
205 /*- Assignment operator. */
206 _HashTableRep& operator=(const _HashTableRep& x);
207
208 /*- Returns the size of this hash table (the number of entries). */
209 Uint32 size() const { return _size; }
210
211 /*- Clears the contents of this hash table. After this is called, the
212 size() method returns zero.
213 */
214 void clear();
215
216 /*- Inserts new key-value pair into hash table. Deletes the bucket on
217 failure so caller need not.
218 @param hashCode hash code generated by caller's hash function.
219 @param bucket bucket to be inserted.
220 @param key pointer to key.
221 mike 1.11 @return true if insertion successful; false if duplicate key.
222 */
223 Boolean insert(Uint32 hashCode, _BucketBase* bucket, const void* key);
224
225 /*- Finds the bucket with the given key. This method uses the
226 _BucketBase::equal() method to compare keys.
227 @param hashCode hash code generated by caller's hash function.
228 @param key void pointer to key.
229 @return pointer to bucket with that key or zero otherwise.
230 */
|
231 mike 1.12 const _BucketBase* lookup(Uint32 hashCode, const void* key) const;
|
232 mike 1.11
233 /*- Removes the bucket with the given key. This method uses the
234 _BucketBase::equal() method to compare keys.
235 @param hashCode hash code generated by caller's hash function.
236 @param key void pointer to key.
237 @return true if entry found and removed and false otherwise.
238 */
239 Boolean remove(Uint32 hashCode, const void* key);
240
241 _BucketBase** getChains() const { return _chains; }
242
243 Uint32 getNumChains() const { return _numChains; }
244
245 protected:
246
247 Uint32 _size;
248 Uint32 _numChains;
249 _BucketBase** _chains;
250 };
251
252 /* The _Bucket class is used to implement the HashTable class.
253 mike 1.11 */
254 template<class K, class V, class E>
255 class _Bucket : public _BucketBase
256 {
257 public:
258
259 _Bucket(const K& key, const V& value) : _key(key), _value(value) { }
260
261 virtual ~_Bucket();
262
263 virtual Boolean equal(const void* key) const;
264
265 virtual _BucketBase* clone() const;
266
267 K& getKey() { return _key; }
268
269 V& getValue() { return _value; }
270
271 private:
272
273 K _key;
274 mike 1.11 V _value;
275 };
276
277 template<class K, class V, class E>
278 Boolean _Bucket<K, V, E>::equal(const void* key) const
279 {
280 return E::equal(*((K*)key), _key);
281 }
282
283 template<class K, class V, class E>
284 _Bucket<K, V, E>::~_Bucket()
285 {
286
287 }
288
289 template<class K, class V, class E>
290 _BucketBase* _Bucket<K, V, E>::clone() const
291 {
292 return new _Bucket<K, V, E>(_key, _value);
293 }
294
295 mike 1.11 /* Iterator for HashTable class. */
296 template<class K, class V, class E>
297 class _HashTableIterator : public _HashTableIteratorBase
298 {
299 public:
300
|
301 r.kieninger 1.18 _HashTableIterator()
|
302 mike 1.11 : _HashTableIteratorBase() { }
303
304 _HashTableIterator(_BucketBase** first, _BucketBase** last)
305 : _HashTableIteratorBase(first, last) { }
306
307 const K& key() const { return ((_Bucket<K, V, E>*)_bucket)->getKey(); }
308
309 const V& value() const { return ((_Bucket<K, V, E>*)_bucket)->getValue(); }
310 };
311
|
312 r.kieninger 1.18 /** The HashTable class provides a simple hash table implementation which
|
313 mike 1.11 associates key-value pairs.
314
315 This implementation minimizes template bloat considerably by factoring out
316 most of the code into a common non-template class (see _HashTableRep).
317 The HashTable class is mostly a wrapper to add proper type semantics to the
318 use of its representation class.
319
320 Hashing as always is O(1).
321
|
322 r.kieninger 1.18 HashTable uses the most popular hash table implementation which utilizes
|
323 mike 1.11 an array of pointers to bucket chains. This is organized as follows:
324
325 <pre>
|
326 r.kieninger 1.18 +---+
|
327 mike 1.11 | | +-----+-------+
328 0 | ----->| key | value |
329 | | +-----+-------+
330 +---+
331 | | +-----+-------+ +-----+-------+ +-----+-------+
332 1 | ----->| key | value |-->| key | value |-->| key | value |
333 | | +-----+-------+ +-----+-------+ +-----+-------+
334 +---+
335 .
336 .
337 .
338 +---+
339 | | +-----+-------+ +-----+-------+
340 N-1| ----->| key | value |-->| key | value |
341 | | +-----+-------+ +-----+-------+
342 +---+
343 </pre>
344
|
345 r.kieninger 1.18 To locate an item a hash function is applied to the key to produce an
346 integer value. Then the modulo of that integer is taken with N to select
|
347 mike 1.11 a chain (as shown above). Then the chain is searched for a bucket whose
348 key value is the same as the target key.
349
350 The number of chains default to DEFAULT_NUM_CHAINS but should be about
351 one-third the number of expected entries (so that the average chain
352 will be three long). Making the number of chains too large will waste
353 space causing the hash table to be very sparse. But for optimal efficiency,
354 one might set the number of chains to be the same as the expected number
355 of entries.
356
|
357 r.kieninger 1.18 This implementation does have NOT an adaptive growth algorithm yet which
|
358 mike 1.11 would allow it to increase the number of chains periodically based on some
359 statistic (e.g., when the number of entries is more than three times the
360 number of chains; this would keep the average chain length below three).
361
362 The following example shows how to instantiate a HashTable which associates
363 String keys with Uint32 values.
364
365 <pre>
366 typedef HashTable<String, Uint32> HT;
367 HT ht;
368 </pre>
369
|
370 r.kieninger 1.18 Some of the template arguments are defaulted in the above example (the
|
371 mike 1.11 third and forth). The instantiation is explicitly qualified like this
372 (which by the way has exactly the same effect).
373
374 <pre>
375 typedef HashTable<String, Uint32, EqualFunc<String>, HashFunc<String>> HT;
376 </pre>
377
378 The third and forth arguments are described more in detail later.
379
380 Then, entries may be inserted like this:
381
382 <pre>
383 ht.insert("Red", 111);
384 ht.insert("Green", 222);
385 ht.insert("Blue", 222);
386 </pre>
387
388 And entries may be looked up as follows:
389
390 <pre>
391 Uint32 value;
392 mike 1.11 ht.lookup("Red", value);
393 </pre>
394
395 And entries may be removed like this:
396
397 <pre>
398 h.remove("Red");
399 </pre>
400
401 Iteration is done like this:
402
403 <pre>
404 for (HT::Iterator i = ht.start(); i; i++)
405 {
406 // To access the key call i.key()!
407 // To access the value call i.value()!
408 }
409 </pre>
410
|
411 r.kieninger 1.18 Note that only forward iteration is supported (no backwards iteration),
412 AND that the hashtable MUST NOT be modified during the iteration!!!
|
413 mike 1.11
414 Equality of keys is determined using the EqualFunc class which is
|
415 r.kieninger 1.18 the default third argument of the template argument list. A new function
416 object may be defined and passed to modify the behavior (for example, one
417 might define equality of strings to ignore whitespace). Here is how to
|
418 mike 1.11 define and use a new equality function object:
419
420 <pre>
421 struct MyEqualFunc
422 {
423 static Boolean equal(const String& x, const String& y)
424 {
425 // do something here to test for equality!
426 }
427 };
428
429 ...
430
431 EqualFunc<String, Uint32, MyEqualFunc> ht;
432 </pre>
433
|
434 r.kieninger 1.18 When the lookup(), insert(), and remove() methods are called, the
|
435 mike 1.11 MyEqualFunc::equal() method will be used to determine equality.
436
437 Hash functions are provided for common types (as part of the default
438 HashFunc class). For other types it is possible to define a custom function
439 object as follows:
440
441 <pre>
442 struct MyHashFunc
443 {
444 static Uint32 hash(const String& x)
445 {
446 // Do some hashing here!
447 }
448 };
449
450 ...
451
452 EqualFunc<String, Uint32, MyEqualFunc, MyHashFunc> ht;
453 </pre>
454
|
455 r.kieninger 1.18 As always, the hash function should provide a reasonably uniform
|
456 mike 1.11 distrubtion so that all of the entries don't get crowded into a few
457 chains. Note that a hash function which returns zero, would force
458 the pathalogical case in which all entries are placed in the first
459 chain.
460 */
461 template<class K, class V, class E , class H >
462 class HashTable
463 {
464 public:
465
466 typedef _HashTableIterator<K, V, E> Iterator;
467
468 /* By default, we create this many chains initially */
469 enum { DEFAULT_NUM_CHAINS = 32 };
470
471 /** Constructor.
472 @param numChains number of chains to create.
473 */
474 HashTable(Uint32 numChains = DEFAULT_NUM_CHAINS) : _rep(numChains)
475 {
476
477 mike 1.11 }
478
479 /** Copy constructor. */
480 HashTable(const HashTable<K,V,E,H>& x) : _rep(x._rep)
481 {
482
483 }
484
485 /** Assignment operator. */
486 HashTable<K,V,E,H>& operator=(const HashTable<K,V,E,H>& x)
487 {
488 if (this != &x)
489 _rep = x._rep;
490 return *this;
491 }
492
493 /** Returns the size of this hash table (the number of entries). */
494 Uint32 size() const { return _rep.size(); }
495
496 /** Clears the contents of this hash table. After this is called, the
497 size() method returns zero.
498 mike 1.11 */
499 void clear() { _rep.clear(); }
500
501 /** Inserts new key-value pair into hash table.
502 @param key key component.
503 @param value value component.
504 @return true on success; false if duplicate key.
505 */
506 Boolean insert(const K& key, const V& value)
507 {
508 return _rep.insert(
509 H::hash(key), new _Bucket<K, V, E>(key, value), &key);
510 }
511
512 /** Checks to see if hash table contains an entry with the given key.
513 @param key key to be searched for
514 @return true if hash table contains an entry with the given key.
515 */
|
516 mike 1.12 Boolean contains(const K& key) const
|
517 mike 1.11 {
518 V value;
519 return lookup(key, value);
520 }
521
522 /** Looks up the entry with the given key.
523 @param key key of entry to be located.
524 @param value output value.
525 @return true if found; false otherwise.
526 */
|
527 mike 1.12 Boolean lookup(const K& key, V& value) const;
|
528 mike 1.11
529 /** Removes the entry with the given key.
530 @param key key of entry to be removed.
531 @return true on success; false otherwise.
532 */
533 Boolean remove(const K& key)
534 {
535 return _rep.remove(H::hash(key), &key);
536 }
537
538 /** Obtains an iterator for this object. */
|
539 r.kieninger 1.18 Iterator start() const
|
540 mike 1.11 {
541 return Iterator(
542 _rep.getChains(), _rep.getChains() + _rep.getNumChains());
543 }
544
545 private:
546
547 _HashTableRep _rep;
548 };
549
550 template<class K, class V, class E, class H>
|
551 mike 1.12 inline Boolean HashTable<K, V, E, H>::lookup(const K& key, V& value) const
|
552 mike 1.11 {
|
553 r.kieninger 1.18 _Bucket<K, V, E>* bucket
|
554 mike 1.11 = (_Bucket<K, V, E>*)_rep.lookup(H::hash(key), &key);
555
556 if (bucket)
557 {
558 value = bucket->getValue();
559 return true;
560 }
561
562 return false;
563 }
564
565 PEGASUS_NAMESPACE_END
566
567 #endif /* Pegasus_HashTable_h */
|
Return to
HashTable.h
CVS log
Up to [Pegasus] / pegasus / src / Pegasus / Common