src/WINNT/afsapplib/hashlist.cpp

   1 extern "C" {
   2 #include <afs/param.h>
   3 #include <afs/stds.h>
   4 }
   5
   6 #include <WINNT/TaLocale.h>
   7
   8
   9 /*
  10  * HashList - super-quick list manager
  11  *
  12  */
  13
  14 #include <windows.h>
  15 #include <WINNT/hashlist.h>
  16
  17
  18 /*
  19  * DEFINITIONS ________________________________________________________________
  20  *
  21  */
  22
  23 #define iINVALID             ((size_t)-1)
  24
  25         // We over-allocate the m_aObjects[] arrays whenever one fills up,
  26         // in order to perform fewer allocations. The allocation size
  27         // is defined by the macro below:
  28         //
  29 #define cREALLOC_OBJECTS       8192
  30
  31         // We also over-allocate the m_aKeys[] array in a hashlist, but
  32         // nothing so dramatic here. It's simply always allocated to a
  33         // multiple of 4.
  34         //
  35 #define cREALLOC_KEYS            4
  36
  37         // The hashtables within each HASHLISTKEY also automatically resize
  38         // themselves whenever they're too small for the number of objects
  39         // they're supporting. There are two algorithms: a slow progression
  40         // for user-defined keys, and a rapid progression for the index key.
  41         // The difference is utilized because the index key (the key used
  42         // internally by each hashlist to provide object-address-to-index
  43         // lookups for fast Remove() calls) responds well to huge hash table
  44         // sizes (because it hashes on addresses, which are evenly
  45         // distributed). User-defined keys don't always use hashing indexes
  46         // that respond so well to additional hashtable size, so they generally
  47         // end up with smaller hash tables (so as not to waste memory).
  48         // The algorithms below cause the following progression (presuming
  49         // the default starting size of 1000 buckets):
  50         //
  51         // Buckets in normal keys:             Buckets in index key:
  52         //    1000 (up to  30000 objects)         1000 (up to   23000 objects)
  53         //    3000 (up to  90000 objects)         4600 (up to  105800 objects)
  54         //    9000 (up to 270000 objects)        21160 (up to  486680 objects)
  55         //   27000 (up to 810000 objects)        97336 (up to 2238728 objects)
  56         //
  57 #define MIN_TABLE_SIZE(_cObjects)     ((_cObjects) / 30)
  58 #define TARGET_TABLE_SIZE(_cObjects)  ((_cObjects) / 10)
  59
  60 #define MIN_TABLE_SIZE_FOR_KEY(_cObjects)     ((_cObjects) / 23)
  61 #define TARGET_TABLE_SIZE_FOR_KEY(_cObjects)  ((_cObjects) /  5)
  62
  63
  64 /*
  65  * REALLOC ____________________________________________________________________
  66  *
  67  */
  68
  69 #ifdef REALLOC
  70 #undef REALLOC
  71 #endif
  72 #define REALLOC(_a,_c,_r,_i) HashList_ReallocFunction ((LPVOID*)&_a,sizeof(*_a),&_c,_r,_i)
  73 BOOL HashList_ReallocFunction (LPVOID *ppTarget, size_t cbElement, size_t *pcTarget, size_t cReq, size_t cInc)
  74 {
  75    LPVOID pNew;
  76    size_t cNew;
  77
  78    if (cReq <= *pcTarget)
  79       return TRUE;
  80
  81    if ((cNew = cInc * ((cReq + cInc-1) / cInc)) <= 0)
  82       return FALSE;
  83
  84    if ((pNew = (LPVOID)GlobalAlloc (GMEM_FIXED, cbElement * cNew)) == NULL)
  85       return FALSE;
  86
  87    if (*pcTarget == 0)
  88       memset (pNew, 0x00, cbElement * cNew);
  89    else
  90       {
  91       memcpy (pNew, *ppTarget, cbElement * (*pcTarget));
  92       memset (&((char*)pNew)[ cbElement * (*pcTarget) ], 0x00, cbElement * (cNew - *pcTarget));
  93       GlobalFree ((HGLOBAL)*ppTarget);
  94       }
  95
  96    *ppTarget = pNew;
  97    *pcTarget = cNew;
  98    return TRUE;
  99 }
 100
 101
 102 /*
 103  * EXPANDARRAY CLASS __________________________________________________________
 104  *
 105  */
 106
 107 #define cEXPANDARRAYHEAPELEMENTS  1024
 108 #define cREALLOC_EXPANDARRAYHEAPS   16
 109
 110 EXPANDARRAY::EXPANDARRAY (size_t cbElement, size_t cElementsPerHeap)
 111 {
 112    if ((m_cbElement = cbElement) == 0)
 113       m_cbElement = sizeof(DWORD);
 114    if ((m_cElementsPerHeap = cElementsPerHeap) == 0)
 115       m_cElementsPerHeap = cEXPANDARRAYHEAPELEMENTS;
 116
 117    m_cHeaps = 0;
 118    m_aHeaps = 0;
 119 }
 120
 121 EXPANDARRAY::~EXPANDARRAY (void)
 122 {
 123    if (m_aHeaps)
 124       {
 125       for (size_t ii = 0; ii < m_cHeaps; ++ii)
 126          {
 127          if (m_aHeaps[ ii ])
 128             GlobalFree ((HGLOBAL)(m_aHeaps[ ii ]));
 129          }
 130       GlobalFree ((HGLOBAL)m_aHeaps);
 131       }
 132 }
 133
 134 PVOID EXPANDARRAY::GetAt (size_t iElement)
 135 {
 136    size_t iHeap = iElement / m_cElementsPerHeap;
 137    size_t iIndex = iElement % m_cElementsPerHeap;
 138    if ((iHeap >= m_cHeaps) || (!m_aHeaps[iHeap]))
 139       return NULL;
 140
 141    PVOID pElement;
 142    pElement = &((PBYTE)m_aHeaps[ iHeap ]->aElements)[ iIndex * m_cbElement ];
 143    return pElement;
 144 }
 145
 146 PVOID EXPANDARRAY::SetAt (size_t iElement, PVOID pData)
 147 {
 148    size_t iHeap = iElement / m_cElementsPerHeap;
 149    size_t iIndex = iElement % m_cElementsPerHeap;
 150
 151    if (!REALLOC (m_aHeaps, m_cHeaps, 1+iHeap, cREALLOC_EXPANDARRAYHEAPS))
 152       return NULL;
 153
 154    if (!m_aHeaps[ iHeap ])
 155       {
 156       size_t cbHeap = sizeof(EXPANDARRAYHEAP) + (m_cElementsPerHeap * m_cbElement);
 157       if ((m_aHeaps[ iHeap ] = (LPEXPANDARRAYHEAP)GlobalAlloc (GMEM_FIXED, cbHeap)) == NULL)
 158          return NULL;
 159       memset (m_aHeaps[ iHeap ], 0x00, cbHeap);
 160       m_aHeaps[ iHeap ]->aElements = ((PBYTE)m_aHeaps[ iHeap ]) + sizeof(EXPANDARRAYHEAP);
 161       }
 162
 163    PVOID pElement;
 164    pElement = &((PBYTE)m_aHeaps[ iHeap ]->aElements)[ iIndex * m_cbElement ];
 165    if (pData)
 166       memcpy (pElement, pData, m_cbElement);
 167    return pElement;
 168 }
 169
 170
 171 /*
 172  * HASHLIST CLASS _____________________________________________________________
 173  *
 174  */
 175
 176 #define GetEntry(_pArray,_iEntry)  ((LPHASHLISTENTRY)((_pArray)->GetAt(_iEntry)))
 177
 178 HASHLIST::HASHLIST (void)
 179 {
 180    InitializeCriticalSection (&m_cs);
 181    m_pcs = &m_cs;
 182    Enter();
 183
 184    m_iFirst = iINVALID;
 185    m_iLast = iINVALID;
 186    m_iNextFree = 0;
 187    m_aObjects = new EXPANDARRAY (sizeof(HASHLISTENTRY), cREALLOC_OBJECTS);
 188    m_cObjects = 0;
 189    m_cObjectsMax = 0;
 190    m_apKeys = NULL;
 191    m_cpKeys = 0;
 192
 193    m_pKeyIndex = new HASHLISTKEY (this, TEXT("Index"), HASHLIST::KeyIndex_CompareObjectData, HASHLIST::KeyIndex_HashObject, HASHLIST::KeyIndex_HashData, cTABLESIZE_DEFAULT);
 194
 195    Leave();
 196 }
 197
 198
 199 HASHLIST::~HASHLIST (void)
 200 {
 201    Enter();
 202
 203    if (m_apKeys != NULL)
 204       {
 205       for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
 206          {
 207          if (m_apKeys[ iKey ] != NULL)
 208             delete m_apKeys[ iKey ];
 209          }
 210       GlobalFree ((HGLOBAL)m_apKeys);
 211       }
 212
 213    if (m_pKeyIndex)
 214       {
 215       delete m_pKeyIndex;
 216       }
 217
 218    if (m_aObjects != NULL)
 219       {
 220       delete m_aObjects;
 221       }
 222
 223    Leave();
 224    DeleteCriticalSection (&m_cs);
 225 }
 226
 227
 228 void HASHLIST::Enter (void)
 229 {
 230    EnterCriticalSection (m_pcs);
 231 }
 232
 233
 234 void HASHLIST::Leave (void)
 235 {
 236    LeaveCriticalSection (m_pcs);
 237 }
 238
 239
 240 void HASHLIST::SetCriticalSection (CRITICAL_SECTION *pcs)
 241 {
 242    m_pcs = (pcs == NULL) ? &m_cs : pcs;
 243 }
 244
 245
 246 BOOL HASHLIST::AddUnique (PVOID pEntryToAdd, LPHASHLISTKEY pKey)
 247 {
 248    if ( ((pKey == NULL) && (fIsInList (pEntryToAdd))) ||
 249         ((pKey != NULL) && (pKey->fIsInList (pEntryToAdd))) )
 250       {
 251       return TRUE;
 252       }
 253
 254    return Add (pEntryToAdd);
 255 }
 256
 257
 258 BOOL HASHLIST::Add (PVOID pEntryToAdd)
 259 {
 260    BOOL rc = FALSE;
 261    Enter();
 262
 263    if (pEntryToAdd)
 264       {
 265       size_t iObject = m_iNextFree;
 266
 267       if ((GetEntry(m_aObjects,iObject) && (GetEntry(m_aObjects,iObject)->pObject)))
 268          {
 269          for (iObject = 0; iObject < m_cObjectsMax; ++iObject)
 270             {
 271             if ( (!GetEntry(m_aObjects,iObject)) || (!GetEntry(m_aObjects,iObject)->pObject) )
 272                break;
 273             }
 274          }
 275
 276       m_iNextFree = 1+iObject;
 277
 278       HASHLISTENTRY Entry;
 279       Entry.pObject = pEntryToAdd;
 280       Entry.iNext = iINVALID;
 281       Entry.iPrevious = m_iLast;
 282       m_aObjects->SetAt (iObject, &Entry);
 283
 284       if (m_iLast != iINVALID)
 285          {
 286          LPHASHLISTENTRY pEntry;
 287          if ((pEntry = GetEntry(m_aObjects,m_iLast)) != NULL)
 288             pEntry->iNext = iObject;
 289          }
 290
 291       m_iLast = iObject;
 292       if (m_iFirst == iINVALID)
 293          m_iFirst = iObject;
 294
 295       m_pKeyIndex->Add (iObject, (PVOID)(iObject+1));
 296
 297       for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
 298          {
 299          if (m_apKeys[ iKey ] == NULL)
 300             continue;
 301          m_apKeys[ iKey ]->Add (iObject, pEntryToAdd);
 302          }
 303
 304       ++m_cObjects;
 305       m_cObjectsMax = max (m_cObjectsMax, m_cObjects);
 306       rc = TRUE;
 307       }
 308
 309    Leave();
 310    return rc;
 311 }
 312
 313
 314 void HASHLIST::Remove (PVOID pEntryToRemove)
 315 {
 316    Enter();
 317
 318    if (pEntryToRemove)
 319       {
 320       // The first step is to find which m_aObjects entry corresponds
 321       // with this object. Ordinarily that'd be a brute-force search;
 322       // however, to speed things up, we have a special key placed on
 323       // the address of the object for determining its index. It lets
 324       // us replace this code:
 325       //
 326       // for (size_t iObject = 0; iObject < m_cObjectsMax; ++iObject)
 327       //   {
 328       //   if (m_aObjects[ iObject ].pObject == pEntryToRemove)
 329       //      break;
 330       //   }
 331       //
 332       // Because this index key uses a hashtable that's resized very
 333       // aggressively, performance tests of up to 100,000 objects
 334       // indicate that removing an object now clocks in as O(1), rather
 335       // than the O(N) that it would be if we used the brute-force approach.
 336       // At 100,000 objects it does use up some 70k of memory, but wow
 337       // is it fast...
 338       //
 339       size_t iObject = iINVALID;
 340
 341       PVOID pFind;
 342       if ((pFind = m_pKeyIndex->GetFirstObject (pEntryToRemove)) != NULL)
 343          iObject = *(size_t *)&pFind -1;
 344
 345       // Now remove the object.
 346       //
 347       if (iObject != iINVALID)
 348          {
 349          LPHASHLISTENTRY pEntry;
 350          if ((pEntry = GetEntry(m_aObjects,iObject)) != NULL)
 351             {
 352             pEntry->pObject = NULL;
 353
 354             if (pEntry->iPrevious != iINVALID)
 355                {
 356                LPHASHLISTENTRY pPrevious;
 357                if ((pPrevious = GetEntry(m_aObjects,pEntry->iPrevious)) != NULL)
 358                   pPrevious->iNext = pEntry->iNext;
 359                }
 360             if (pEntry->iNext != iINVALID)
 361                {
 362                LPHASHLISTENTRY pNext;
 363                if ((pNext = GetEntry(m_aObjects,pEntry->iNext)) != NULL)
 364                   pNext->iPrevious = pEntry->iPrevious;
 365                }
 366
 367             if (m_iLast == iObject)
 368                m_iLast = pEntry->iPrevious;
 369             if (m_iFirst == iObject)
 370                m_iFirst = pEntry->iNext;
 371
 372             for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
 373                {
 374                if (m_apKeys[ iKey ] == NULL)
 375                   continue;
 376                m_apKeys[ iKey ]->Remove (iObject);
 377                }
 378
 379             m_pKeyIndex->Remove (iObject);
 380             --m_cObjects;
 381             }
 382          }
 383       }
 384
 385    Leave();
 386 }
 387
 388
 389 BOOL HASHLIST::Update (PVOID pEntryToUpdate)
 390 {
 391    BOOL rc = TRUE;
 392    Enter();
 393
 394    PVOID pFind;
 395    if ((pFind = m_pKeyIndex->GetFirstObject (pEntryToUpdate)) == NULL)
 396       rc = FALSE;
 397    else
 398       {
 399       size_t iObject = *(size_t *)&pFind -1;
 400
 401       for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
 402          {
 403          if (m_apKeys[ iKey ] == NULL)
 404             continue;
 405
 406          m_apKeys[ iKey ]->Remove (iObject);
 407          m_apKeys[ iKey ]->Add (iObject, pEntryToUpdate);
 408          }
 409       }
 410
 411    Leave();
 412    return rc;
 413 }
 414
 415
 416 BOOL HASHLIST::fIsInList (PVOID pEntry)
 417 {
 418    PVOID pFind;
 419    if ((pFind = m_pKeyIndex->GetFirstObject (pEntry)) == NULL)
 420       return FALSE;
 421    return TRUE;
 422 }
 423
 424
 425 LPHASHLISTKEY HASHLIST::CreateKey (LPCTSTR pszKeyName, LPHASHFUNC_COMPAREOBJECTDATA fnCompareObjectData, LPHASHFUNC_HASHOBJECT fnHashObject, LPHASHFUNC_HASHDATA fnHashData, size_t cTableSize)
 426 {
 427    LPHASHLISTKEY pKey = NULL;
 428    Enter();
 429
 430    for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
 431       {
 432       if (m_apKeys[ iKey ] == NULL)
 433          break;
 434       }
 435    if (REALLOC (m_apKeys, m_cpKeys, 1+iKey, cREALLOC_KEYS))
 436       {
 437       m_apKeys[ iKey ] = new HASHLISTKEY (this, pszKeyName, fnCompareObjectData, fnHashObject, fnHashData, cTableSize);
 438       pKey = m_apKeys[ iKey ];
 439
 440       if (MIN_TABLE_SIZE(m_cObjectsMax) > pKey->m_cBuckets)
 441          {
 442          pKey->Resize();
 443          }
 444       else for (size_t iObject = 0; iObject < m_cObjectsMax; ++iObject)
 445          {
 446          LPHASHLISTENTRY pEntry;
 447          if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
 448             continue;
 449          if (pEntry->pObject != NULL)
 450             m_apKeys[ iKey ]->Add (iObject, pEntry->pObject);
 451          }
 452       }
 453
 454    Leave();
 455    return pKey;
 456 }
 457
 458
 459 LPHASHLISTKEY HASHLIST::FindKey (LPCTSTR pszKeyName)
 460 {
 461    LPHASHLISTKEY pKey = NULL;
 462    Enter();
 463
 464    for (size_t iKey = 0; !pKey && (iKey < m_cpKeys); ++iKey)
 465       {
 466       if (m_apKeys[ iKey ] == NULL)
 467          continue;
 468       if (!lstrcmpi (m_apKeys[ iKey ]->m_szKeyName, pszKeyName))
 469          pKey = m_apKeys[ iKey ];
 470       }
 471
 472    Leave();
 473    return pKey;
 474 }
 475
 476
 477 void HASHLIST::RemoveKey (LPHASHLISTKEY pKey)
 478 {
 479    Enter();
 480
 481    for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
 482       {
 483       if (m_apKeys[ iKey ] == pKey)
 484          {
 485          delete m_apKeys[ iKey ];
 486          m_apKeys[ iKey ] = NULL;
 487          break;
 488          }
 489       }
 490
 491    Leave();
 492 }
 493
 494
 495 LPENUM HASHLIST::FindFirst (void)
 496 {
 497    LPENUM pEnum = NULL;
 498    Enter();
 499
 500    if (m_iFirst != iINVALID)
 501       pEnum = New2 (ENUMERATION,(this, m_iFirst));
 502
 503    Leave();
 504    return pEnum;
 505 }
 506
 507
 508 LPENUM HASHLIST::FindLast (void)
 509 {
 510    LPENUM pEnum = NULL;
 511    Enter();
 512
 513    if (m_iLast != iINVALID)
 514       pEnum = New2 (ENUMERATION,(this, m_iLast));
 515
 516    Leave();
 517    return pEnum;
 518 }
 519
 520
 521 PVOID HASHLIST::GetFirstObject (void)
 522 {
 523    PVOID pObject = NULL;
 524    Enter();
 525
 526    if (m_iFirst != iINVALID)
 527       pObject = GetEntry(m_aObjects,m_iFirst)->pObject;
 528
 529    Leave();
 530    return pObject;
 531 }
 532
 533
 534 PVOID HASHLIST::GetLastObject (void)
 535 {
 536    PVOID pObject = NULL;
 537    Enter();
 538
 539    if (m_iLast != iINVALID)
 540       pObject = GetEntry(m_aObjects,m_iLast)->pObject;
 541
 542    Leave();
 543    return pObject;
 544 }
 545
 546
 547 size_t HASHLIST::GetCount (void)
 548 {
 549    return m_cObjects;
 550 }
 551
 552
 553 BOOL CALLBACK HASHLIST::KeyIndex_CompareObjectData (LPHASHLISTKEY pKey, PVOID pObject, PVOID pData)
 554 {
 555    size_t iIndex = (size_t)pObject -1;
 556    LPHASHLIST pList = pKey->GetHashList();
 557    return (GetEntry(pList->m_aObjects,iIndex)->pObject == pData) ? TRUE : FALSE;
 558 }
 559
 560
 561 HASHVALUE CALLBACK HASHLIST::KeyIndex_HashObject (LPHASHLISTKEY pKey, PVOID pObject)
 562 {
 563    size_t iIndex = (size_t)pObject -1;
 564    LPHASHLIST pList = pKey->GetHashList();
 565    return KeyIndex_HashData (pKey, GetEntry(pList->m_aObjects,iIndex)->pObject);
 566 }
 567
 568
 569 HASHVALUE CALLBACK HASHLIST::KeyIndex_HashData (LPHASHLISTKEY pKey, PVOID pData)
 570 {
 571    return ((DWORD)pData) >> 4;  // The "data" is the object's address.
 572 }
 573
 574
 575 /*
 576  * HASHLISTKEY CLASS _____________________________________________________________
 577  *
 578  */
 579
 580 HASHLISTKEY::HASHLISTKEY (LPHASHLIST pList, LPCTSTR pszKeyName, LPHASHFUNC_COMPAREOBJECTDATA fnCompareObjectData, LPHASHFUNC_HASHOBJECT fnHashObject, LPHASHFUNC_HASHDATA fnHashData, size_t cTableSize)
 581 {
 582    m_aObjects = new EXPANDARRAY (sizeof(HASHLISTENTRY), cREALLOC_OBJECTS);
 583
 584    m_cBuckets = (cTableSize == 0) ? cTABLESIZE_DEFAULT : cTableSize;
 585    m_aBuckets = (struct HASHBUCKET *)GlobalAlloc (GMEM_FIXED, m_cBuckets * sizeof(struct HASHBUCKET));
 586    for (size_t iBucket = 0; iBucket < m_cBuckets; ++iBucket)
 587       {
 588       m_aBuckets[ iBucket ].iFirst = iINVALID;
 589       m_aBuckets[ iBucket ].iLast = iINVALID;
 590       }
 591
 592    m_pList = pList;
 593    lstrcpy (m_szKeyName, pszKeyName);
 594    m_fnCompareObjectData = fnCompareObjectData;
 595    m_fnHashObject = fnHashObject;
 596    m_fnHashData = fnHashData;
 597 }
 598
 599
 600 HASHLISTKEY::~HASHLISTKEY (void)
 601 {
 602    m_pList->Enter();
 603
 604    for (size_t iObject = 0; iObject < m_pList->m_cObjectsMax; ++iObject)
 605       {
 606       if (!GetEntry(m_aObjects,iObject))
 607          continue;
 608       if (!GetEntry(m_aObjects,iObject)->pObject)
 609          continue;
 610       Remove (iObject);
 611       }
 612
 613    if (m_aObjects)
 614       delete m_aObjects;
 615    if (m_aBuckets)
 616       GlobalFree ((HGLOBAL)m_aBuckets);
 617
 618    m_pList->Leave();
 619 }
 620
 621
 622 LPHASHLIST HASHLISTKEY::GetHashList (void)
 623 {
 624    return m_pList;
 625 }
 626
 627
 628 BOOL HASHLISTKEY::CompareObjectData (PVOID pObject, PVOID pData)
 629 {
 630    return (*m_fnCompareObjectData)(this, pObject, pData);
 631 }
 632
 633 HASHVALUE HASHLISTKEY::HashObject (PVOID pObject)
 634 {
 635    return ((*m_fnHashObject)(this, pObject)) % m_cBuckets;
 636 }
 637
 638 HASHVALUE HASHLISTKEY::HashData (PVOID pData)
 639 {
 640    return ((*m_fnHashData)(this, pData)) % m_cBuckets;
 641 }
 642
 643
 644 LPENUM HASHLISTKEY::FindFirst (PVOID pData)
 645 {
 646    LPENUM pEnum = NULL;
 647    m_pList->Enter();
 648
 649    HASHVALUE hvSearch = HashData (pData);
 650
 651    size_t iObject;
 652    if ((iObject = m_aBuckets[ hvSearch ].iFirst) != iINVALID)
 653       {
 654       LPHASHLISTENTRY pEntry;
 655       do {
 656          if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
 657             break;
 658          if (CompareObjectData (pEntry->pObject, pData))
 659             {
 660             pEnum = New2 (ENUMERATION,(m_pList, iObject, this, pData));
 661             break;
 662             }
 663          } while ((iObject = pEntry->iNext) != iINVALID);
 664       }
 665
 666    m_pList->Leave();
 667    return pEnum;
 668 }
 669
 670
 671 LPENUM HASHLISTKEY::FindLast (PVOID pData)
 672 {
 673    LPENUM pEnum = NULL;
 674    m_pList->Enter();
 675
 676    HASHVALUE hvSearch = HashData (pData);
 677
 678    size_t iObject;
 679    if ((iObject = m_aBuckets[ hvSearch ].iLast) != iINVALID)
 680       {
 681       LPHASHLISTENTRY pEntry;
 682       do {
 683          if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
 684             break;
 685          if (CompareObjectData (pEntry->pObject, pData))
 686             {
 687             pEnum = New2 (ENUMERATION,(m_pList, iObject, this, pData));
 688             break;
 689             }
 690          } while ((iObject = pEntry->iPrevious) != iINVALID);
 691       }
 692
 693    m_pList->Leave();
 694    return pEnum;
 695 }
 696
 697
 698 PVOID HASHLISTKEY::GetFirstObject (PVOID pData)
 699 {
 700    PVOID pObject = NULL;
 701    m_pList->Enter();
 702
 703    HASHVALUE hvSearch = HashData (pData);
 704
 705    size_t iObject;
 706    if ((iObject = m_aBuckets[ hvSearch ].iFirst) != iINVALID)
 707       {
 708       LPHASHLISTENTRY pEntry;
 709       do {
 710          if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
 711             break;
 712          if (CompareObjectData (pEntry->pObject, pData))
 713             {
 714             pObject = pEntry->pObject;
 715             break;
 716             }
 717          } while ((iObject = pEntry->iNext) != iINVALID);
 718       }
 719
 720    m_pList->Leave();
 721    return pObject;
 722 }
 723
 724
 725 PVOID HASHLISTKEY::GetLastObject (PVOID pData)
 726 {
 727    PVOID pObject = NULL;
 728    m_pList->Enter();
 729
 730    HASHVALUE hvSearch = HashData (pData);
 731
 732    size_t iObject;
 733    if ((iObject = m_aBuckets[ hvSearch ].iLast) != iINVALID)
 734       {
 735       LPHASHLISTENTRY pEntry;
 736       do {
 737          if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
 738             break;
 739          if (CompareObjectData (pEntry->pObject, pData))
 740             {
 741             pObject = pEntry->pObject;
 742             break;
 743             }
 744          } while ((iObject = pEntry->iPrevious) != iINVALID);
 745       }
 746
 747    m_pList->Leave();
 748    return pObject;
 749 }
 750
 751
 752 BOOL HASHLISTKEY::fIsInList (PVOID pEntry)
 753 {
 754    PVOID pFind;
 755    if ((pFind = GetFirstObject (pEntry)) == NULL)
 756       return FALSE;
 757    return TRUE;
 758 }
 759
 760
 761 void HASHLISTKEY::Add (size_t iObject, PVOID pObject)
 762 {
 763    m_pList->Enter();
 764
 765    if ( ((this == m_pList->m_pKeyIndex) && (MIN_TABLE_SIZE_FOR_KEY(m_pList->m_cObjectsMax) > m_cBuckets)) ||
 766         ((this != m_pList->m_pKeyIndex) && (MIN_TABLE_SIZE(m_pList->m_cObjectsMax) > m_cBuckets)) )
 767       {
 768       Resize();
 769       }
 770    else
 771       {
 772       HASHVALUE hv = HashObject (pObject);
 773       struct HASHBUCKET *pBucket = &m_aBuckets[ hv ];
 774
 775       HASHLISTENTRY Entry;
 776       Entry.pObject = pObject;
 777       Entry.hv = hv;
 778       Entry.iNext = iINVALID;
 779       Entry.iPrevious = pBucket->iLast;
 780       m_aObjects->SetAt (iObject, &Entry);
 781
 782       pBucket->iLast = iObject;
 783
 784       if (Entry.iPrevious != iINVALID)
 785          {
 786          LPHASHLISTENTRY pPrevious;
 787          if ((pPrevious = GetEntry(m_aObjects,Entry.iPrevious)) != NULL)
 788             pPrevious->iNext = iObject;
 789          }
 790
 791       if (pBucket->iFirst == iINVALID)
 792          pBucket->iFirst = iObject;
 793       }
 794
 795    m_pList->Leave();
 796 }
 797
 798
 799 void HASHLISTKEY::Remove (size_t iObject)
 800 {
 801    m_pList->Enter();
 802
 803    LPHASHLISTENTRY pEntry;
 804    if ((pEntry = GetEntry(m_aObjects,iObject)) != NULL)
 805       {
 806       pEntry->pObject = NULL;
 807
 808       if (pEntry->iPrevious != iINVALID)
 809          {
 810          LPHASHLISTENTRY pPrevious;
 811          if ((pPrevious = GetEntry(m_aObjects,pEntry->iPrevious)) != NULL)
 812             pPrevious->iNext = pEntry->iNext;
 813          }
 814
 815       if (pEntry->iNext != iINVALID)
 816          {
 817          LPHASHLISTENTRY pNext;
 818          if ((pNext = GetEntry(m_aObjects,pEntry->iNext)) != NULL)
 819             pNext->iPrevious = pEntry->iPrevious;
 820          }
 821
 822       if (m_aBuckets[ pEntry->hv ].iLast == iObject)
 823          m_aBuckets[ pEntry->hv ].iLast = pEntry->iPrevious;
 824       if (m_aBuckets[ pEntry->hv ].iFirst == iObject)
 825          m_aBuckets[ pEntry->hv ].iFirst = pEntry->iNext;
 826       }
 827
 828    m_pList->Leave();
 829 }
 830
 831
 832 void HASHLISTKEY::Resize (void)
 833 {
 834    if (this == m_pList->m_pKeyIndex)
 835       {
 836       REALLOC (m_aBuckets, m_cBuckets, TARGET_TABLE_SIZE_FOR_KEY(m_pList->m_cObjectsMax), 1);
 837       }
 838    else
 839       {
 840       REALLOC (m_aBuckets, m_cBuckets, TARGET_TABLE_SIZE(m_pList->m_cObjectsMax), 1);
 841       }
 842
 843    for (size_t iBucket = 0; iBucket < m_cBuckets; ++iBucket)
 844       {
 845       m_aBuckets[ iBucket ].iFirst = iINVALID;
 846       m_aBuckets[ iBucket ].iLast = iINVALID;
 847       }
 848
 849    for (size_t iObject = 0; ; ++iObject)
 850       {
 851       LPHASHLISTENTRY pEntry;
 852       if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
 853          break;
 854       pEntry->pObject = NULL;
 855       }
 856
 857    // Re-add the objects to this key. One caveat: if this is the
 858    // hashlist's index key, then the format of the items is different--
 859    // retain that difference.
 860    //
 861    if (this == m_pList->m_pKeyIndex)
 862       {
 863       for (iObject = 0; ; ++iObject)
 864          {
 865          LPHASHLISTENTRY pEntry;
 866          if ((pEntry = GetEntry(m_pList->m_aObjects,iObject)) == NULL)
 867             break;
 868          if (pEntry->pObject != NULL)
 869             Add (iObject, (PVOID)(iObject+1));
 870          }
 871       }
 872    else // normal, user-defined key
 873       {
 874       for (iObject = 0; ; ++iObject)
 875          {
 876          LPHASHLISTENTRY pEntry;
 877          if ((pEntry = GetEntry(m_pList->m_aObjects,iObject)) == NULL)
 878             break;
 879          if (pEntry->pObject != NULL)
 880             Add (iObject, pEntry->pObject);
 881          }
 882       }
 883 }
 884
 885
 886 LPHASHLISTKEYDEBUGINFO HASHLISTKEY::GetDebugInfo (void)
 887 {
 888    m_pList->Enter();
 889
 890    LPHASHLISTKEYDEBUGINFO pInfo = new HASHLISTKEYDEBUGINFO;
 891    memset (pInfo, 0x00, sizeof(HASHLISTKEYDEBUGINFO));
 892
 893    // Find out how full each bucket is.
 894    //
 895    REALLOC (pInfo->aBuckets, pInfo->cBuckets, m_cBuckets, 1);
 896
 897    for (size_t iBucket = 0; iBucket < pInfo->cBuckets; ++iBucket)
 898       {
 899       for (size_t iObject = m_aBuckets[ iBucket ].iFirst;
 900            iObject != iINVALID;
 901            iObject = GetEntry(m_aObjects,iObject)->iNext)
 902          {
 903          (pInfo->aBuckets[ iBucket ])++;
 904          }
 905       }
 906
 907    // Calculate a "percent effectiveness". This is a pretty fuzzy
 908    // calculation; we want 100% if all buckets are the same size
 909    // (plus or minus one element), and 0% if all buckets except one are
 910    // empty but that one bucket has more than cBuckets elements. In
 911    // between, we'll try to create a roughly linear gradient. The
 912    // calculation is effectively the proportion of the number of
 913    // objects which are evenly distributed to the number of objects
 914    // overall.
 915    //
 916    if (pInfo->cBuckets == 0)
 917       {
 918       pInfo->perEffective = 100;
 919       }
 920    else
 921       {
 922       // We want an accurate count of objects, not the over-allocated
 923       // count given by m_cObjectsMax.
 924       //
 925       size_t cObjects = 0;
 926       for (iBucket = 0; iBucket < pInfo->cBuckets; ++iBucket)
 927          cObjects += pInfo->aBuckets[ iBucket ];
 928
 929       if (cObjects == 0)
 930          {
 931          pInfo->perEffective = 100;
 932          }
 933       else
 934          {
 935          // Determine what "even distribution" means--that's pretty easy.
 936          // We increase the count by one to indicate that slight unevenness
 937          // will occur unless the number of objects is a multiple of the
 938          // number of buckets.
 939          //
 940          size_t cPerfectLength = (cObjects / pInfo->cBuckets) + 1;
 941
 942          size_t cObjectsInPlace = 0;
 943          for (iBucket = 0; iBucket < pInfo->cBuckets; ++iBucket)
 944             cObjectsInPlace += min( pInfo->aBuckets[ iBucket ], cPerfectLength );
 945
 946          // Now calculating that percent effectiveness is easy. If everything
 947          // is evenly distributed, cObjectsInPlace will == cObjects--and
 948          // we want to call it 100%. If eveything is on one chain, then
 949          // cObjectsInPlace will be really small compared to cObjects.
 950          //
 951          pInfo->perEffective = (WORD)(cObjectsInPlace * 100 / cObjects);
 952          }
 953       }
 954
 955    m_pList->Leave();
 956    return pInfo;
 957 }
 958
 959
 960 void HASHLISTKEY::FreeDebugInfo (LPHASHLISTKEYDEBUGINFO pInfo)
 961 {
 962    if (pInfo->aBuckets)
 963       GlobalFree ((HGLOBAL)(pInfo->aBuckets));
 964 }
 965
 966
 967 /*
 968  * ENUMERATION CLASS _____________________________________________________________
 969  *
 970  */
 971
 972 ENUMERATION::ENUMERATION (LPHASHLIST pList, size_t iObject, LPHASHLISTKEY pKey, PVOID pData)
 973 {
 974    m_pList = pList;
 975    m_pKey = pKey;
 976    m_pData = pData;
 977    m_iObject = iObject;
 978
 979    PrepareWalk(); // finds m_iPrevious and m_iNext
 980
 981    m_pList->Enter();
 982 }
 983
 984
 985 ENUMERATION::~ENUMERATION (void)
 986 {
 987    m_pList->Leave();
 988 }
 989
 990
 991 PVOID ENUMERATION::GetObject (void)
 992 {
 993    return GetEntry(m_pList->m_aObjects,m_iObject)->pObject;
 994 }
 995
 996
 997 LPENUMERATION ENUMERATION::FindNext (void)
 998 {
 999    for (;;)
1000       {
1001       m_iObject = m_iNext;
1002       PrepareWalk();
1003
1004       if (m_iObject == iINVALID)
1005          break;
1006
1007       if (m_pKey == NULL)
1008          return this;
1009
1010       if (m_pKey->CompareObjectData (GetEntry(m_pList->m_aObjects,m_iObject)->pObject, m_pData))
1011          return this;
1012       }
1013
1014    Delete (this);
1015    return NULL;
1016 }
1017
1018
1019 LPENUMERATION ENUMERATION::FindPrevious (void)
1020 {
1021    for (;;)
1022       {
1023       m_iObject = m_iPrevious;
1024       PrepareWalk();
1025
1026       if (m_iObject == iINVALID)
1027          break;
1028
1029       if (m_pKey == NULL)
1030          return this;
1031
1032       if (m_pKey->CompareObjectData (GetEntry(m_pList->m_aObjects,m_iObject)->pObject, m_pData))
1033          return this;
1034       }
1035
1036    Delete (this);
1037    return NULL;
1038 }
1039
1040
1041 void ENUMERATION::PrepareWalk (void)
1042 {
1043    if (m_iObject == iINVALID)
1044       {
1045       m_iPrevious = iINVALID;
1046       m_iNext = iINVALID;
1047       }
1048    else if (m_pKey == NULL)
1049       {
1050       m_iPrevious = GetEntry(m_pList->m_aObjects,m_iObject)->iPrevious;
1051       m_iNext = GetEntry(m_pList->m_aObjects,m_iObject)->iNext;
1052       }
1053    else
1054       {
1055       m_iPrevious = GetEntry(m_pKey->m_aObjects,m_iObject)->iPrevious;
1056       m_iNext = GetEntry(m_pKey->m_aObjects,m_iObject)->iNext;
1057       }
1058 }
1059
1060
1061 /*
1062  * GENERAL-PURPOSE ____________________________________________________________
1063  *
1064  */
1065
1066 HASHVALUE HashString (LPCTSTR pszString)
1067 {
1068 #ifdef UNICODE
1069    return HashUnicodeString (pszString);
1070 #else
1071    return HashAnsiString (pszString);
1072 #endif
1073 }
1074
1075 HASHVALUE HashAnsiString (LPCSTR pszStringA)
1076 {
1077    HASHVALUE hv = 0;
1078
1079    for (size_t cch = lstrlenA(pszStringA); cch >= 4; pszStringA += 4, cch -= 4)
1080       hv += *(DWORD *)pszStringA;
1081
1082    for (; cch; pszStringA++, cch--)
1083       hv += *pszStringA;
1084
1085    return hv;
1086 }
1087
1088 HASHVALUE HashUnicodeString (LPWSTR pszStringW)
1089 {
1090    HASHVALUE hv = 0;
1091
1092    for (size_t cch = lstrlenW(pszStringW); cch >= 2; pszStringW += 2, cch -= 2)
1093       {
1094       hv += *(DWORD *)pszStringW;   // since HIBYTE(*psz) is usually zero,
1095       hv = (hv >> 24) | (hv << 8);  // rotate {hv} high-ward by 8 bits
1096       }
1097
1098    for (; cch; pszStringW++, cch--)
1099       hv += *pszStringW;
1100
1101    return hv;
1102 }
1103