src/Pegasus/Common/HashTable.h

   1 //%2005////////////////////////////////////////////////////////////////////////
   2 //
   3 // 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 // IBM Corp.; EMC Corporation, The Open Group.
   7 // Copyright (c) 2004 BMC Software; Hewlett-Packard Development Company, L.P.;
   8 // IBM Corp.; EMC Corporation; VERITAS Software Corporation; The Open Group.
   9 // Copyright (c) 2005 Hewlett-Packard Development Company, L.P.; IBM Corp.;
  10 // EMC Corporation; VERITAS Software Corporation; The Open Group.
  11 //
  12 // Permission is hereby granted, free of charge, to any person obtaining a copy
  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 // 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 //
  19 // THE ABOVE COPYRIGHT NOTICE AND THIS PERMISSION NOTICE SHALL BE INCLUDED IN
  20 // 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 // 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 // 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 // Modified By: Carol Ann Krug Graves, Hewlett-Packard Company
  33 //                  (carolann_graves@hp.com)
  34 //
  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 #include <Pegasus/Common/CIMObjectPath.h>
  43 #include <Pegasus/Common/Linkage.h>
  44
  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 PEGASUS_TEMPLATE_SPECIALIZATION struct HashFunc <CIMObjectPath>
  66 {
  67     static Uint32 hash (const CIMObjectPath & path)
  68     {
  69         return path.makeHashCode ();
  70     }
  71 };
  72
  73 /*
  74     Hash function object that converts to lowercase.
  75
  76     This function can be used for hash table keys constructed from strings that
  77     should be treated as case insensitive (e.g. class names, namespace names,
  78     system names).
  79
  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 /*  This is a function object used by the HashTable to compare keys. This is
  96     the default implementation. Others may be defined and passed in the
  97     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     }
 106 };
 107
 108 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 /*
 117     Equal function object that can be used by HashTable to compare keys that
 118     should be treated as case insensitive.
 119
 120     This function can be used for hash table keys constructed from strings that
 121     should be treated as case insensitive (e.g. class names, namespace names,
 122     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     }
 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     /* Virtual destructor to ensure destruction of derived class
 146         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 public:
 168
 169     _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
 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     _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     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     _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         @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     const _BucketBase* lookup(Uint32 hashCode, const void* key) const;
 249
 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 */
 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     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 /* Iterator for HashTable class. */
 313 template<class K, class V, class E>
 314 class _HashTableIterator : public _HashTableIteratorBase
 315 {
 316 public:
 317
 318     _HashTableIterator()
 319         : _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 /** The HashTable class provides a simple hash table implementation which
 330     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     HashTable uses the most popular hash table implementation which utilizes
 340     an array of pointers to bucket chains. This is organized as follows:
 341
 342         <pre>
 343            +---+
 344            |   |   +-----+-------+
 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     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     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     This implementation does have NOT an adaptive growth algorithm yet which
 375     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&lt;String, Uint32&gt; HT;
 384         HT ht;
 385         </pre>
 386
 387     Some of the template arguments are defaulted in the above example (the
 388     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&lt;String, Uint32, EqualFunc&lt;String&gt;, HashFunc&lt;String&gt;&gt; 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         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     Note that only forward iteration is supported (no backwards iteration),
 429     AND that the hashtable MUST NOT be modified during the iteration!!!
 430
 431     Equality of keys is determined using the EqualFunc class which is
 432     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     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&lt;String, Uint32, MyEqualFunc&gt; ht;
 449         </pre>
 450
 451     When the lookup(), insert(), and remove() methods are called, the
 452     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&lt;String, Uint32, MyEqualFunc, MyHashFunc&gt; ht;
 470         </pre>
 471
 472     As always, the hash function should provide a reasonably uniform
 473     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     }
 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     */
 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     Boolean contains(const K& key) const
 534     {
 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     Boolean lookup(const K& key, V& value) const;
 545
 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     Iterator start() const
 557     {
 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 inline Boolean HashTable<K, V, E, H>::lookup(const K& key, V& value) const
 569 {
 570     _Bucket<K, V, E>* bucket
 571         = (_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 */