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 /* This class implements a simple hash table forward iterator. */
147 class PEGASUS_COMMON_LINKAGE _HashTableIteratorBase
148 {
149 public:
|
150 r.kieninger 1.18
|
151 kumpf 1.26 _HashTableIteratorBase(_BucketBase** first, _BucketBase** last);
|
152 mike 1.11
153 operator int() const { return _bucket != 0; }
154
155 _HashTableIteratorBase operator++(int);
156
157 _HashTableIteratorBase& operator++();
158
|
159 kumpf 1.26 protected:
|
160 kumpf 1.25
|
161 kumpf 1.26 // Note: The default copy constructor/assignment operator is used by the
162 // postfix increment operator. The member pointers may be safely copied
163 // because they refer to structures that must not change while the iterator
164 // is in scope.
|
165 mike 1.11
166 _BucketBase** _first;
167 _BucketBase** _last;
168 _BucketBase* _bucket;
169 };
170
171 // ATTN: reorganization not supported yet.
172
173 /*- The _HashTableRep class is the representation class used by HashTable.
174
175 This code is primarily an internal class used to implement the HashTable.
176 But there may be occasions to use it directly.
177
|
178 r.kieninger 1.18 _HashTableRep parcels out much of the large code so that that code is not
179 instantiated by the HashTable template class many times. This scheme helps
|
180 mike 1.11 reduce code bloat caused by templates. The HashTable template class below
181 acts as kind of a wrapper around this class.
182
183 _HashTableRep is implemented as an array of pointers to chains of hash
184 buckets. The table initially allocates some number of chains (which can
185 be controlled by the constructor) and then may increase the number of
186 chains later (resulting in a reorganization of the hash table).
187 */
188 class PEGASUS_COMMON_LINKAGE _HashTableRep
189 {
190 public:
191
192 /*- This constructor allocates an array of pointers to chains of buckets,
|
193 kumpf 1.23 which of course are all empty at this time. The numChains argument
194 If the numChains argument is less than eight, then eight chains will
195 be created.
196 @param numChains specifies the initial number of chains.
|
197 mike 1.11 */
198 _HashTableRep(Uint32 numChains);
199
200 /*- Copy constructor. */
201 _HashTableRep(const _HashTableRep& x);
202
203 /*- Destructor. */
204 ~_HashTableRep();
205
206 /*- Assignment operator. */
207 _HashTableRep& operator=(const _HashTableRep& x);
208
209 /*- Returns the size of this hash table (the number of entries). */
210 Uint32 size() const { return _size; }
211
212 /*- Clears the contents of this hash table. After this is called, the
|
213 kumpf 1.23 size() method returns zero.
|
214 mike 1.11 */
215 void clear();
216
217 /*- Inserts new key-value pair into hash table. Deletes the bucket on
|
218 kumpf 1.23 failure so caller need not.
219 @param hashCode hash code generated by caller's hash function.
220 @param bucket bucket to be inserted.
221 @param key pointer to key.
222 @return true if insertion successful; false if duplicate key.
|
223 mike 1.11 */
224 Boolean insert(Uint32 hashCode, _BucketBase* bucket, const void* key);
225
226 /*- Finds the bucket with the given key. This method uses the
|
227 kumpf 1.23 _BucketBase::equal() method to compare keys.
228 @param hashCode hash code generated by caller's hash function.
229 @param key void pointer to key.
230 @return pointer to bucket with that key or zero otherwise.
|
231 mike 1.11 */
|
232 mike 1.12 const _BucketBase* lookup(Uint32 hashCode, const void* key) const;
|
233 mike 1.11
234 /*- Removes the bucket with the given key. This method uses the
|
235 kumpf 1.23 _BucketBase::equal() method to compare keys.
236 @param hashCode hash code generated by caller's hash function.
237 @param key void pointer to key.
238 @return true if entry found and removed and false otherwise.
|
239 mike 1.11 */
240 Boolean remove(Uint32 hashCode, const void* key);
241
242 _BucketBase** getChains() const { return _chains; }
243
244 Uint32 getNumChains() const { return _numChains; }
245
246 protected:
247
248 Uint32 _size;
249 Uint32 _numChains;
250 _BucketBase** _chains;
251 };
252
253 /* The _Bucket class is used to implement the HashTable class.
254 */
255 template<class K, class V, class E>
256 class _Bucket : public _BucketBase
257 {
258 public:
259
260 mike 1.11 _Bucket(const K& key, const V& value) : _key(key), _value(value) { }
261
262 virtual ~_Bucket();
263
264 virtual Boolean equal(const void* key) const;
265
266 virtual _BucketBase* clone() const;
267
268 K& getKey() { return _key; }
269
270 V& getValue() { return _value; }
271
272 private:
273
274 K _key;
275 V _value;
276 };
277
278 template<class K, class V, class E>
279 Boolean _Bucket<K, V, E>::equal(const void* key) const
280 {
281 mike 1.11 return E::equal(*((K*)key), _key);
282 }
283
284 template<class K, class V, class E>
285 _Bucket<K, V, E>::~_Bucket()
286 {
287
288 }
289
290 template<class K, class V, class E>
291 _BucketBase* _Bucket<K, V, E>::clone() const
292 {
293 return new _Bucket<K, V, E>(_key, _value);
294 }
295
296 /* Iterator for HashTable class. */
297 template<class K, class V, class E>
298 class _HashTableIterator : public _HashTableIteratorBase
299 {
300 public:
301
302 mike 1.11 _HashTableIterator(_BucketBase** first, _BucketBase** last)
|
303 kumpf 1.23 : _HashTableIteratorBase(first, last) { }
|
304 mike 1.11
305 const K& key() const { return ((_Bucket<K, V, E>*)_bucket)->getKey(); }
306
307 const V& value() const { return ((_Bucket<K, V, E>*)_bucket)->getValue(); }
308 };
309
|
310 r.kieninger 1.18 /** The HashTable class provides a simple hash table implementation which
|
311 mike 1.11 associates key-value pairs.
312
313 This implementation minimizes template bloat considerably by factoring out
314 most of the code into a common non-template class (see _HashTableRep).
315 The HashTable class is mostly a wrapper to add proper type semantics to the
316 use of its representation class.
317
318 Hashing as always is O(1).
319
|
320 r.kieninger 1.18 HashTable uses the most popular hash table implementation which utilizes
|
321 mike 1.11 an array of pointers to bucket chains. This is organized as follows:
322
323 <pre>
|
324 r.kieninger 1.18 +---+
|
325 mike 1.11 | | +-----+-------+
326 0 | ----->| key | value |
327 | | +-----+-------+
328 +---+
329 | | +-----+-------+ +-----+-------+ +-----+-------+
330 1 | ----->| key | value |-->| key | value |-->| key | value |
331 | | +-----+-------+ +-----+-------+ +-----+-------+
332 +---+
333 .
334 .
335 .
336 +---+
337 | | +-----+-------+ +-----+-------+
338 N-1| ----->| key | value |-->| key | value |
339 | | +-----+-------+ +-----+-------+
340 +---+
341 </pre>
342
|
343 r.kieninger 1.18 To locate an item a hash function is applied to the key to produce an
344 integer value. Then the modulo of that integer is taken with N to select
|
345 mike 1.11 a chain (as shown above). Then the chain is searched for a bucket whose
346 key value is the same as the target key.
347
348 The number of chains default to DEFAULT_NUM_CHAINS but should be about
349 one-third the number of expected entries (so that the average chain
350 will be three long). Making the number of chains too large will waste
351 space causing the hash table to be very sparse. But for optimal efficiency,
352 one might set the number of chains to be the same as the expected number
353 of entries.
354
|
355 r.kieninger 1.18 This implementation does have NOT an adaptive growth algorithm yet which
|
356 mike 1.11 would allow it to increase the number of chains periodically based on some
357 statistic (e.g., when the number of entries is more than three times the
358 number of chains; this would keep the average chain length below three).
359
360 The following example shows how to instantiate a HashTable which associates
361 String keys with Uint32 values.
362
|
363 kumpf 1.23 <pre>
364 typedef HashTable<String, Uint32> HT;
365 HT ht;
366 </pre>
|
367 mike 1.11
|
368 r.kieninger 1.18 Some of the template arguments are defaulted in the above example (the
|
369 mike 1.11 third and forth). The instantiation is explicitly qualified like this
370 (which by the way has exactly the same effect).
371
|
372 kumpf 1.23 <pre>
373 typedef HashTable<String, Uint32,
374 EqualFunc<String>, HashFunc<String>> HT;
375 </pre>
|
376 mike 1.11
|
377 kumpf 1.23 The third and fourth arguments are described more in detail later.
|
378 mike 1.11
379 Then, entries may be inserted like this:
380
|
381 kumpf 1.23 <pre>
382 ht.insert("Red", 111);
383 ht.insert("Green", 222);
384 ht.insert("Blue", 222);
385 </pre>
|
386 mike 1.11
387 And entries may be looked up as follows:
388
|
389 kumpf 1.23 <pre>
390 Uint32 value;
391 ht.lookup("Red", value);
392 </pre>
|
393 mike 1.11
394 And entries may be removed like this:
395
|
396 kumpf 1.23 <pre>
397 h.remove("Red");
398 </pre>
|
399 mike 1.11
400 Iteration is done like this:
401
|
402 kumpf 1.23 <pre>
403 for (HT::Iterator i = ht.start(); i; i++)
404 {
405 // To access the key call i.key()!
406 // To access the value call i.value()!
407 }
408 </pre>
|
409 mike 1.11
|
410 r.kieninger 1.18 Note that only forward iteration is supported (no backwards iteration),
411 AND that the hashtable MUST NOT be modified during the iteration!!!
|
412 mike 1.11
413 Equality of keys is determined using the EqualFunc class which is
|
414 r.kieninger 1.18 the default third argument of the template argument list. A new function
415 object may be defined and passed to modify the behavior (for example, one
416 might define equality of strings to ignore whitespace). Here is how to
|
417 mike 1.11 define and use a new equality function object:
418
|
419 kumpf 1.23 <pre>
420 struct MyEqualFunc
421 {
422 static Boolean equal(const String& x, const String& y)
423 {
424 // do something here to test for equality!
425 }
426 };
|
427 mike 1.11
|
428 kumpf 1.23 ...
|
429 mike 1.11
|
430 kumpf 1.23 EqualFunc<String, Uint32, MyEqualFunc> ht;
431 </pre>
|
432 mike 1.11
|
433 r.kieninger 1.18 When the lookup(), insert(), and remove() methods are called, the
|
434 mike 1.11 MyEqualFunc::equal() method will be used to determine equality.
435
436 Hash functions are provided for common types (as part of the default
437 HashFunc class). For other types it is possible to define a custom function
438 object as follows:
439
|
440 kumpf 1.23 <pre>
441 struct MyHashFunc
442 {
443 static Uint32 hash(const String& x)
444 {
445 // Do some hashing here!
446 }
447 };
|
448 mike 1.11
|
449 kumpf 1.23 ...
|
450 mike 1.11
|
451 kumpf 1.23 EqualFunc<String, Uint32, MyEqualFunc, MyHashFunc> ht;
452 </pre>
|
453 mike 1.11
|
454 r.kieninger 1.18 As always, the hash function should provide a reasonably uniform
|
455 mike 1.11 distrubtion so that all of the entries don't get crowded into a few
456 chains. Note that a hash function which returns zero, would force
457 the pathalogical case in which all entries are placed in the first
458 chain.
459 */
460 template<class K, class V, class E , class H >
461 class HashTable
462 {
463 public:
464
465 typedef _HashTableIterator<K, V, E> Iterator;
466
467 /* By default, we create this many chains initially */
468 enum { DEFAULT_NUM_CHAINS = 32 };
469
470 /** Constructor.
|
471 kumpf 1.23 @param numChains number of chains to create.
|
472 mike 1.11 */
473 HashTable(Uint32 numChains = DEFAULT_NUM_CHAINS) : _rep(numChains)
474 {
475
476 }
477
478 /** Copy constructor. */
479 HashTable(const HashTable<K,V,E,H>& x) : _rep(x._rep)
480 {
481
482 }
483
484 /** Assignment operator. */
485 HashTable<K,V,E,H>& operator=(const HashTable<K,V,E,H>& x)
486 {
|
487 kumpf 1.23 if (this != &x)
488 _rep = x._rep;
489 return *this;
|
490 mike 1.11 }
491
492 /** Returns the size of this hash table (the number of entries). */
493 Uint32 size() const { return _rep.size(); }
494
495 /** Clears the contents of this hash table. After this is called, the
|
496 kumpf 1.23 size() method returns zero.
|
497 mike 1.11 */
498 void clear() { _rep.clear(); }
499
500 /** Inserts new key-value pair into hash table.
|
501 kumpf 1.23 @param key key component.
502 @param value value component.
503 @return true on success; false if duplicate key.
|
504 mike 1.11 */
505 Boolean insert(const K& key, const V& value)
506 {
|
507 kumpf 1.23 return _rep.insert(
508 H::hash(key), new _Bucket<K, V, E>(key, value), &key);
|
509 mike 1.11 }
510
511 /** Checks to see if hash table contains an entry with the given key.
|
512 kumpf 1.23 @param key key to be searched for
513 @return true if hash table contains an entry with the given key.
|
514 mike 1.11 */
|
515 mike 1.12 Boolean contains(const K& key) const
|
516 mike 1.11 {
|
517 kumpf 1.23 V value;
518 return lookup(key, value);
|
519 mike 1.11 }
520
521 /** Looks up the entry with the given key.
|
522 kumpf 1.23 @param key key of entry to be located.
523 @param value output value.
524 @return true if found; false otherwise.
|
525 mike 1.11 */
|
526 mike 1.12 Boolean lookup(const K& key, V& value) const;
|
527 mike 1.11
528 /** Removes the entry with the given key.
|
529 kumpf 1.23 @param key key of entry to be removed.
530 @return true on success; false otherwise.
|
531 mike 1.11 */
532 Boolean remove(const K& key)
533 {
|
534 kumpf 1.23 return _rep.remove(H::hash(key), &key);
|
535 mike 1.11 }
536
537 /** Obtains an iterator for this object. */
|
538 r.kieninger 1.18 Iterator start() const
|
539 mike 1.11 {
|
540 kumpf 1.23 return Iterator(
541 _rep.getChains(), _rep.getChains() + _rep.getNumChains());
|
542 mike 1.11 }
543
544 private:
545
546 _HashTableRep _rep;
547 };
548
549 template<class K, class V, class E, class H>
|
550 mike 1.12 inline Boolean HashTable<K, V, E, H>::lookup(const K& key, V& value) const
|
551 mike 1.11 {
|
552 r.kieninger 1.18 _Bucket<K, V, E>* bucket
|
553 kumpf 1.23 = (_Bucket<K, V, E>*)_rep.lookup(H::hash(key), &key);
|
554 mike 1.11
555 if (bucket)
556 {
|
557 kumpf 1.23 value = bucket->getValue();
558 return true;
|
559 mike 1.11 }
560
561 return false;
562 }
563
564 PEGASUS_NAMESPACE_END
565
566 #endif /* Pegasus_HashTable_h */
|
Return to
HashTable.h
CVS log
Up to [Pegasus] / pegasus / src / Pegasus / Common