1 martin 1.29 //%LICENSE////////////////////////////////////////////////////////////////
2 //
3 // Licensed to The Open Group (TOG) under one or more contributor license
4 // agreements. Refer to the OpenPegasusNOTICE.txt file distributed with
5 // this work for additional information regarding copyright ownership.
6 // Each contributor licenses this file to you under the OpenPegasus Open
7 // Source License; you may not use this file except in compliance with the
8 // License.
9 //
10 // Permission is hereby granted, free of charge, to any person obtaining a
11 // copy of this software and associated documentation files (the "Software"),
12 // to deal in the Software without restriction, including without limitation
13 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
14 // and/or sell copies of the Software, and to permit persons to whom the
15 // Software is furnished to do so, subject to the following conditions:
16 //
17 // The above copyright notice and this permission notice shall be included
18 // in all copies or substantial portions of the Software.
19 //
20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
21 // OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
22 martin 1.29 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
23 // IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
24 // CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
25 // TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
26 // SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
|
27 karl 1.19 //
|
28 martin 1.29 //////////////////////////////////////////////////////////////////////////
|
29 mike 1.11 //
30 //%/////////////////////////////////////////////////////////////////////////////
31
32 #ifndef Pegasus_HashTable_h
33 #define Pegasus_HashTable_h
34
35 #include <Pegasus/Common/Config.h>
36 #include <Pegasus/Common/String.h>
|
37 carolann.graves 1.20 #include <Pegasus/Common/CIMObjectPath.h>
|
38 kumpf 1.14 #include <Pegasus/Common/Linkage.h>
|
39 mike 1.11
40 PEGASUS_NAMESPACE_BEGIN
41
42 /* This is the default hash function object used by the HashTable template.
43 Specializations are provided for common types.
44 */
45 template<class K>
46 struct HashFunc
47 {
48 };
49
50 PEGASUS_TEMPLATE_SPECIALIZATION struct PEGASUS_COMMON_LINKAGE HashFunc<String>
51 {
52 static Uint32 hash(const String& str);
53 };
54
55 PEGASUS_TEMPLATE_SPECIALIZATION struct HashFunc<Uint32>
56 {
57 static Uint32 hash(Uint32 x) { return x + 13; }
58 };
59
|
60 carolann.graves 1.20 PEGASUS_TEMPLATE_SPECIALIZATION struct HashFunc <CIMObjectPath>
61 {
62 static Uint32 hash (const CIMObjectPath & path)
63 {
64 return path.makeHashCode ();
65 }
66 };
67
|
68 mike 1.21 //
69 // Computes a hash code for a string without regard to case. For example, it
70 // yields the same hash code for "AB", "ab", "Ab", and "aB".
71 //
72 struct PEGASUS_COMMON_LINKAGE HashLowerCaseFunc
|
73 kumpf 1.16 {
|
74 mike 1.21 static Uint32 hash(const String& str);
|
75 kumpf 1.16 };
76
|
77 mike 1.11 /* This is a function object used by the HashTable to compare keys. This is
|
78 r.kieninger 1.18 the default implementation. Others may be defined and passed in the
|
79 mike 1.11 template argument list to perform other kinds of comparisons.
80 */
81 template<class K>
82 struct EqualFunc
83 {
84 static Boolean equal(const K& x, const K& y)
85 {
|
86 kumpf 1.23 return x == y;
|
87 kumpf 1.16 }
88 };
89
|
90 carolann.graves 1.20 PEGASUS_TEMPLATE_SPECIALIZATION struct EqualFunc <CIMObjectPath>
91 {
92 static Boolean equal (const CIMObjectPath & x, const CIMObjectPath & y)
93 {
94 return x.identical (y);
95 }
96 };
97
|
98 kumpf 1.16 /*
|
99 r.kieninger 1.18 Equal function object that can be used by HashTable to compare keys that
100 should be treated as case insensitive.
|
101 kumpf 1.16
102 This function can be used for hash table keys constructed from strings that
|
103 r.kieninger 1.18 should be treated as case insensitive (e.g. class names, namespace names,
|
104 kumpf 1.16 system names).
105
106 Note: this function compares Strings based on the process locale.
107 */
108 struct EqualNoCaseFunc
109 {
110 static Boolean equal (const String & x, const String & y)
111 {
112 return (0 == String::compareNoCase (x, y));
|
113 mike 1.11 }
114 };
115
116 /* Representation for a bucket. The HashTable class derives from this
117 bucket to append a key and value. This base class just defines
118 the pointer to the next bucket in the chain.
119 */
120 class PEGASUS_COMMON_LINKAGE _BucketBase
121 {
122 public:
123
124 /* Default constructor. */
125 _BucketBase() : next(0) { }
126
|
127 r.kieninger 1.18 /* Virtual destructor to ensure destruction of derived class
|
128 kumpf 1.23 elements.
|
129 mike 1.11 */
130 virtual ~_BucketBase();
131
132 /* returns true if the key pointed to by the key argument is equal
|
133 kumpf 1.23 to the internal key of this bucket. This method must be overridden
134 by the derived class.
|
135 mike 1.11 */
136 virtual Boolean equal(const void* key) const = 0;
137
138 /* Clone this bucket. */
139 virtual _BucketBase* clone() const = 0;
140
141 _BucketBase* next;
142 };
143
144 /* This class implements a simple hash table forward iterator. */
145 class PEGASUS_COMMON_LINKAGE _HashTableIteratorBase
146 {
147 public:
|
148 r.kieninger 1.18
|
149 kumpf 1.26 _HashTableIteratorBase(_BucketBase** first, _BucketBase** last);
|
150 mike 1.11
151 operator int() const { return _bucket != 0; }
152
|
153 mike 1.28 void operator++();
|
154 mike 1.11
|
155 mike 1.28 void operator++(int)
156 {
157 operator++();
158 }
|
159 mike 1.11
|
160 kumpf 1.26 protected:
|
161 kumpf 1.25
|
162 kumpf 1.26 // Note: The default copy constructor/assignment operator is used by the
163 // postfix increment operator. The member pointers may be safely copied
164 // because they refer to structures that must not change while the iterator
165 // is in scope.
|
166 mike 1.11
167 _BucketBase** _first;
168 _BucketBase** _last;
169 _BucketBase* _bucket;
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 yi.zhou 1.27 /** Looks up the entry with the given key and returns a pointer to the
530 value. Note that this pointer may become invalid when the HashTable
531 is updated.
532 @param key key of entry to be located.
533 @param value Output pointer to the value.
534 @return true if found; false otherwise.
535 */
536 Boolean lookupReference(const K& key, V*& value);
537
|
538 mike 1.11 /** Removes the entry with the given key.
|
539 kumpf 1.23 @param key key of entry to be removed.
540 @return true on success; false otherwise.
|
541 mike 1.11 */
542 Boolean remove(const K& key)
543 {
|
544 kumpf 1.23 return _rep.remove(H::hash(key), &key);
|
545 mike 1.11 }
546
547 /** Obtains an iterator for this object. */
|
548 r.kieninger 1.18 Iterator start() const
|
549 mike 1.11 {
|
550 kumpf 1.23 return Iterator(
551 _rep.getChains(), _rep.getChains() + _rep.getNumChains());
|
552 mike 1.11 }
553
554 private:
555
556 _HashTableRep _rep;
557 };
558
559 template<class K, class V, class E, class H>
|
560 mike 1.12 inline Boolean HashTable<K, V, E, H>::lookup(const K& key, V& value) const
|
561 mike 1.11 {
|
562 r.kieninger 1.18 _Bucket<K, V, E>* bucket
|
563 kumpf 1.23 = (_Bucket<K, V, E>*)_rep.lookup(H::hash(key), &key);
|
564 mike 1.11
565 if (bucket)
566 {
|
567 kumpf 1.23 value = bucket->getValue();
568 return true;
|
569 mike 1.11 }
570
571 return false;
572 }
573
|
574 yi.zhou 1.27 template<class K, class V, class E, class H>
575 inline Boolean HashTable<K, V, E, H>::lookupReference(const K& key, V*& value)
576 {
577 _Bucket<K, V, E>* bucket =
578 (_Bucket<K, V, E>*)_rep.lookup(H::hash(key), &key);
579
580 if (bucket)
581 {
582 value = &bucket->getValue();
583 return true;
584 }
585
586 return false;
587 }
588
|
589 mike 1.11 PEGASUS_NAMESPACE_END
590
591 #endif /* Pegasus_HashTable_h */
|
Return to
HashTable.h
CVS log
Up to [Pegasus] / pegasus / src / Pegasus / Common