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