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