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