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