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