headers/private/shared/OpenHashTable.h

   1 /*
   2 Open Tracker License
   3
   4 Terms and Conditions
   5
   6 Copyright (c) 1991-2000, Be Incorporated. All rights reserved.
   7
   8 Permission is hereby granted, free of charge, to any person obtaining a copy of
   9 this software and associated documentation files (the "Software"), to deal in
  10 the Software without restriction, including without limitation the rights to
  11 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
  12 of the Software, and to permit persons to whom the Software is furnished to do
  13 so, subject to the following conditions:
  14
  15 The above copyright notice and this permission notice applies to all licensees
  16 and shall be included in all copies or substantial portions of the Software.
  17
  18 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  19 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF TITLE, MERCHANTABILITY,
  20 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  21 BE INCORPORATED BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  22 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF, OR IN CONNECTION
  23 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  24
  25 Except as contained in this notice, the name of Be Incorporated shall not be
  26 used in advertising or otherwise to promote the sale, use or other dealings in
  27 this Software without prior written authorization from Be Incorporated.
  28
  29 Tracker(TM), Be(R), BeOS(R), and BeIA(TM) are trademarks or registered trademarks
  30 of Be Incorporated in the United States and other countries. Other brand product
  31 names are registered trademarks or trademarks of their respective holders.
  32 All rights reserved.
  33 */
  34
  35 // bonefish:
  36 // * removed need for exceptions
  37 // * fixed warnings
  38 // * implemented rehashing
  39 // * added RemoveAll()
  40 // TODO:
  41 // * shrinking of element vectors
  42
  43 // Hash table with open addresssing
  44
  45 #ifndef __OPEN_HASH_TABLE__
  46 #define __OPEN_HASH_TABLE__
  47
  48 #include <stdlib.h>
  49 #include <new>
  50
  51 // don't include <Debug.h>
  52 #ifndef _OPEN_HASH_TABLE_ASSERT
  53 #       define _OPEN_HASH_TABLE_ASSERT(E)       (void)0
  54 #endif
  55 #ifndef _OPEN_HASH_TABLE_TRESPASS
  56 #       define _OPEN_HASH_TABLE_TRESPASS()      (void)0
  57 #endif
  58
  59 namespace BPrivate {
  60
  61 template <class Element>
  62 class ElementVector {
  63         // element vector for OpenHashTable needs to implement this
  64         // interface
  65 public:
  66         Element &At(int32 index);
  67         Element *Add();
  68         int32 IndexOf(const Element &) const;
  69         void Remove(int32 index);
  70 };
  71
  72 class OpenHashElement {
  73 public:
  74         uint32 Hash() const;
  75         bool operator==(const OpenHashElement &) const;
  76         void Adopt(OpenHashElement &);
  77                 // low overhead copy, original element is in undefined state
  78                 // after call (calls Adopt on BString members, etc.)
  79         int32 fNext;
  80 };
  81
  82 const uint32 kPrimes [] = {
  83         509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071, 262139,
  84         524287, 1048573, 2097143, 4194301, 8388593, 16777213, 33554393, 67108859,
  85         134217689, 268435399, 536870909, 1073741789, 2147483647, 0
  86 };
  87
  88 template <class Element, class ElementVec = ElementVector<Element> >
  89 class OpenHashTable {
  90 public:
  91         OpenHashTable(int32 minSize, ElementVec *elementVector = 0,
  92                                   float maxLoadFactor = 0.8);
  93                 // it is up to the subclass of OpenHashTable to supply
  94                 // elementVector
  95         ~OpenHashTable();
  96
  97         bool InitCheck() const;
  98
  99         void SetElementVector(ElementVec *elementVector);
 100
 101         Element *FindFirst(uint32 elementHash) const;
 102         Element *Add(uint32 elementHash);
 103
 104         void Remove(Element *element, bool dontRehash = false);
 105         void RemoveAll();
 106
 107         // when calling Add, any outstanding element pointer may become
 108         // invalid; to deal with this, get the element index and restore
 109         // it after the add
 110         int32 ElementIndex(const Element *) const;
 111         Element *ElementAt(int32 index) const;
 112
 113         int32 ArraySize() const;
 114         int32 VectorSize() const;
 115         int32 CountElements() const;
 116
 117 protected:
 118         static int32 OptimalSize(int32 minSize);
 119
 120 private:
 121         bool _RehashIfNeeded();
 122         bool _Rehash();
 123
 124         int32 fArraySize;
 125         int32 fInitialSize;
 126         int32 fElementCount;
 127         int32 *fHashArray;
 128         ElementVec *fElementVector;
 129         float fMaxLoadFactor;
 130 };
 131
 132 template <class Element>
 133 class OpenHashElementArray : public ElementVector<Element> {
 134         // this is a straightforward implementation of an element vector
 135         // deleting is handled by linking deleted elements into a free list
 136         // the vector never shrinks
 137 public:
 138         OpenHashElementArray(int32 initialSize);
 139         ~OpenHashElementArray();
 140
 141         bool InitCheck() const;
 142
 143         Element &At(int32 index);
 144         const Element &At(int32 index) const;
 145         Element *Add(const Element &);
 146         Element *Add();
 147         void Remove(int32 index);
 148         int32 IndexOf(const Element &) const;
 149         int32 Size() const;
 150
 151 private:
 152         Element *fData;
 153         int32 fSize;
 154         int32 fNextFree;
 155         int32 fNextDeleted;
 156 };
 157
 158
 159 //-----------------------------------
 160
 161 template<class Element, class ElementVec>
 162 OpenHashTable<Element, ElementVec>::OpenHashTable(int32 minSize,
 163         ElementVec *elementVector, float maxLoadFactor)
 164         :       fArraySize(OptimalSize(minSize)),
 165                 fInitialSize(fArraySize),
 166                 fElementCount(0),
 167                 fElementVector(elementVector),
 168                 fMaxLoadFactor(maxLoadFactor)
 169 {
 170         // sanity check the maximal load factor
 171         if (fMaxLoadFactor < 0.5)
 172                 fMaxLoadFactor = 0.5;
 173         // allocate and init the array
 174         fHashArray = (int32*)calloc(fArraySize, sizeof(int32));
 175         if (fHashArray) {
 176                 for (int32 index = 0; index < fArraySize; index++)
 177                         fHashArray[index] = -1;
 178         }
 179 }
 180
 181 template<class Element, class ElementVec>
 182 OpenHashTable<Element, ElementVec>::~OpenHashTable()
 183 {
 184         RemoveAll();
 185         free(fHashArray);
 186 }
 187
 188 template<class Element, class ElementVec>
 189 bool
 190 OpenHashTable<Element, ElementVec>::InitCheck() const
 191 {
 192         return (fHashArray && fElementVector);
 193 }
 194
 195 template<class Element, class ElementVec>
 196 int32
 197 OpenHashTable<Element, ElementVec>::OptimalSize(int32 minSize)
 198 {
 199         for (int32 index = 0; ; index++)
 200                 if (!kPrimes[index] || kPrimes[index] >= (uint32)minSize)
 201                         return (int32)kPrimes[index];
 202
 203         return 0;
 204 }
 205
 206 template<class Element, class ElementVec>
 207 Element *
 208 OpenHashTable<Element, ElementVec>::FindFirst(uint32 hash) const
 209 {
 210         _OPEN_HASH_TABLE_ASSERT(fElementVector);
 211         hash %= fArraySize;
 212         if (fHashArray[hash] < 0)
 213                 return 0;
 214
 215         return &fElementVector->At(fHashArray[hash]);
 216 }
 217
 218 template<class Element, class ElementVec>
 219 int32
 220 OpenHashTable<Element, ElementVec>::ElementIndex(const Element *element) const
 221 {
 222         return fElementVector->IndexOf(*element);
 223 }
 224
 225 template<class Element, class ElementVec>
 226 Element *
 227 OpenHashTable<Element, ElementVec>::ElementAt(int32 index) const
 228 {
 229         return &fElementVector->At(index);
 230 }
 231
 232 template<class Element, class ElementVec>
 233 int32
 234 OpenHashTable<Element, ElementVec>::ArraySize() const
 235 {
 236         return fArraySize;
 237 }
 238
 239 template<class Element, class ElementVec>
 240 int32
 241 OpenHashTable<Element, ElementVec>::VectorSize() const
 242 {
 243         return fElementVector->Size();
 244 }
 245
 246 template<class Element, class ElementVec>
 247 int32
 248 OpenHashTable<Element, ElementVec>::CountElements() const
 249 {
 250         return fElementCount;
 251 }
 252
 253
 254 template<class Element, class ElementVec>
 255 Element *
 256 OpenHashTable<Element, ElementVec>::Add(uint32 hash)
 257 {
 258         _OPEN_HASH_TABLE_ASSERT(fElementVector);
 259         _RehashIfNeeded();
 260         hash %= fArraySize;
 261         Element *result = fElementVector->Add();
 262         if (result) {
 263                 result->fNext = fHashArray[hash];
 264                 fHashArray[hash] = fElementVector->IndexOf(*result);
 265                 fElementCount++;
 266         }
 267         return result;
 268 }
 269
 270 template<class Element, class ElementVec>
 271 void
 272 OpenHashTable<Element, ElementVec>::Remove(Element *element, bool dontRehash)
 273 {
 274         if (!dontRehash)
 275                 _RehashIfNeeded();
 276         uint32 hash = element->Hash() % fArraySize;
 277         int32 next = fHashArray[hash];
 278         _OPEN_HASH_TABLE_ASSERT(next >= 0);
 279
 280         if (&fElementVector->At(next) == element) {
 281                 fHashArray[hash] = element->fNext;
 282                 fElementVector->Remove(next);
 283                 fElementCount--;
 284                 return;
 285         }
 286
 287         for (int32 index = next; index >= 0; ) {
 288                 // look for an existing match in table
 289                 next = fElementVector->At(index).fNext;
 290                 if (next < 0) {
 291                         _OPEN_HASH_TABLE_TRESPASS();
 292                         return;
 293                 }
 294
 295                 if (&fElementVector->At(next) == element) {
 296                         fElementVector->At(index).fNext = element->fNext;
 297                         fElementVector->Remove(next);
 298                         fElementCount--;
 299                         return;
 300                 }
 301                 index = next;
 302         }
 303 }
 304
 305 template<class Element, class ElementVec>
 306 void
 307 OpenHashTable<Element, ElementVec>::RemoveAll()
 308 {
 309         for (int32 i = 0; fElementCount > 0 && i < fArraySize; i++) {
 310                 int32 index = fHashArray[i];
 311                 while (index >= 0) {
 312                         Element* element = &fElementVector->At(index);
 313                         int32 next = element->fNext;
 314                         fElementVector->Remove(index);
 315                         fElementCount--;
 316                         index = next;
 317                 }
 318                 fHashArray[i] = -1;
 319         }
 320         _RehashIfNeeded();
 321 }
 322
 323 template<class Element, class ElementVec>
 324 void
 325 OpenHashTable<Element, ElementVec>::SetElementVector(ElementVec *elementVector)
 326 {
 327         fElementVector = elementVector;
 328 }
 329
 330 // _RehashIfNeeded
 331 template<class Element, class ElementVec>
 332 bool
 333 OpenHashTable<Element, ElementVec>::_RehashIfNeeded()
 334 {
 335         // The load factor range [fMaxLoadFactor / 3, fMaxLoadFactor] is fine,
 336         // I think. After rehashing the load factor will be about
 337         // fMaxLoadFactor * 2 / 3, respectively fMaxLoadFactor / 2.
 338         float loadFactor = (float)fElementCount / (float)fArraySize;
 339         if (loadFactor > fMaxLoadFactor
 340                 || (fArraySize > fInitialSize && loadFactor < fMaxLoadFactor / 3)) {
 341                 return _Rehash();
 342         }
 343         return true;
 344 }
 345
 346 // _Rehash
 347 template<class Element, class ElementVec>
 348 bool
 349 OpenHashTable<Element, ElementVec>::_Rehash()
 350 {
 351         bool result = true;
 352         int32 newSize = int32(fElementCount * 1.73 * fMaxLoadFactor);
 353         newSize = (fInitialSize > newSize ? fInitialSize : newSize);
 354         if (newSize != fArraySize) {
 355                 // allocate a new array
 356                 int32 *newHashArray = (int32*)calloc(newSize, sizeof(int32));
 357                 if (newHashArray) {
 358                         // init the new hash array
 359                         for (int32 index = 0; index < newSize; index++)
 360                                 newHashArray[index] = -1;
 361                         // iterate through all elements and put them into the new
 362                         // hash array
 363                         for (int i = 0; i < fArraySize; i++) {
 364                                 int32 index = fHashArray[i];
 365                                 while (index >= 0) {
 366                                         // insert the element in the new array
 367                                         Element &element = fElementVector->At(index);
 368                                         int32 next = element.fNext;
 369                                         uint32 hash = (element.Hash() % newSize);
 370                                         element.fNext = newHashArray[hash];
 371                                         newHashArray[hash] = index;
 372                                         // next element in old list
 373                                         index = next;
 374                                 }
 375                         }
 376                         // delete the old array and set the new one
 377                         free(fHashArray);
 378                         fHashArray = newHashArray;
 379                         fArraySize = newSize;
 380                 } else
 381                         result = false;
 382         }
 383         return result;
 384 }
 385
 386
 387 template<class Element>
 388 OpenHashElementArray<Element>::OpenHashElementArray(int32 initialSize)
 389         :       fSize(initialSize),
 390                 fNextFree(0),
 391                 fNextDeleted(-1)
 392 {
 393         fData = (Element*)calloc((size_t)initialSize, sizeof(Element));
 394 }
 395
 396 template<class Element>
 397 OpenHashElementArray<Element>::~OpenHashElementArray()
 398 {
 399         free(fData);
 400 }
 401
 402 template<class Element>
 403 bool
 404 OpenHashElementArray<Element>::InitCheck() const
 405 {
 406         return fData;
 407 }
 408
 409 template<class Element>
 410 Element &
 411 OpenHashElementArray<Element>::At(int32 index)
 412 {
 413         _OPEN_HASH_TABLE_ASSERT(index < fSize);
 414         return fData[index];
 415 }
 416
 417 template<class Element>
 418 const Element &
 419 OpenHashElementArray<Element>::At(int32 index) const
 420 {
 421         _OPEN_HASH_TABLE_ASSERT(index < fSize);
 422         return fData[index];
 423 }
 424
 425 template<class Element>
 426 int32
 427 OpenHashElementArray<Element>::IndexOf(const Element &element) const
 428 {
 429         int32 result = &element - fData;
 430         if (result < 0 || result > fSize)
 431                 return -1;
 432
 433         return result;
 434 }
 435
 436 template<class Element>
 437 int32
 438 OpenHashElementArray<Element>::Size() const
 439 {
 440         return fSize;
 441 }
 442
 443
 444 template<class Element>
 445 Element *
 446 OpenHashElementArray<Element>::Add(const Element &newElement)
 447 {
 448         Element *element = Add();
 449         if (element)
 450                 element->Adopt(newElement);
 451         return element;
 452 }
 453
 454 #if DEBUG
 455 const int32 kGrowChunk = 10;
 456 #else
 457 const int32 kGrowChunk = 1024;
 458 #endif
 459
 460 template<class Element>
 461 Element *
 462 OpenHashElementArray<Element>::Add()
 463 {
 464         int32 index = fNextFree;
 465         if (fNextDeleted >= 0) {
 466                 index = fNextDeleted;
 467                 fNextDeleted = At(index).fNext;
 468         } else if (fNextFree >= fSize - 1) {
 469                 int32 newSize = fSize + kGrowChunk;
 470 /*
 471                 Element *newData = (Element *)calloc((size_t)newSize , sizeof(Element));
 472                 if (!newData)
 473                         return NULL;
 474                 memcpy(newData, fData, fSize * sizeof(Element));
 475                 free(fData);
 476 */
 477                 Element *newData = (Element*)realloc(fData,
 478                         (size_t)newSize * sizeof(Element));
 479                 if (!newData)
 480                         return NULL;
 481
 482                 fData = newData;
 483                 fSize = newSize;
 484                 index = fNextFree;
 485                 fNextFree++;
 486         } else
 487                 fNextFree++;
 488
 489         new (&At(index)) Element;
 490                 // call placement new to initialize the element properly
 491         _OPEN_HASH_TABLE_ASSERT(At(index).fNext == -1);
 492
 493         return &At(index);
 494 }
 495
 496 template<class Element>
 497 void
 498 OpenHashElementArray<Element>::Remove(int32 index)
 499 {
 500         // delete by chaining empty elements in a single linked
 501         // list, reusing the next field
 502         _OPEN_HASH_TABLE_ASSERT(index < fSize);
 503         At(index).~Element();
 504                 // call the destructor explicitly to destroy the element
 505                 // properly
 506         At(index).fNext = fNextDeleted;
 507         fNextDeleted = index;
 508 }
 509
 510 } // namespace BPrivate
 511
 512 using BPrivate::OpenHashTable;
 513
 514 #endif // __OPEN_HASH_TABLE__