src/WINNT/afsapplib/hashlist.cpp

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