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 #include <winnt/osi_malloc.h>
  17
  18
  19 /*
  20  * HashList - super-quick list manager
  21  *
  22  */
  23
  24 #include <windows.h>
  25 #include <WINNT/hashlist.h>
  26
  27
  28 /*
  29  * DEFINITIONS ________________________________________________________________
  30  *
  31  */
  32
  33 #define iINVALID             ((size_t)-1)
  34
  35         // We over-allocate the m_aObjects[] arrays whenever one fills up,
  36         // in order to perform fewer allocations. The allocation size
  37         // is defined by the macro below:
  38         //
  39 #define cREALLOC_OBJECTS       8192
  40
  41         // We also over-allocate the m_aKeys[] array in a hashlist, but
  42         // nothing so dramatic here. It's simply always allocated to a
  43         // multiple of 4.
  44         //
  45 #define cREALLOC_KEYS            4
  46
  47         // The hashtables within each HASHLISTKEY also automatically resize
  48         // themselves whenever they're too small for the number of objects
  49         // they're supporting. There are two algorithms: a slow progression
  50         // for user-defined keys, and a rapid progression for the index key.
  51         // The difference is utilized because the index key (the key used
  52         // internally by each hashlist to provide object-address-to-index
  53         // lookups for fast Remove() calls) responds well to huge hash table
  54         // sizes (because it hashes on addresses, which are evenly
  55         // distributed). User-defined keys don't always use hashing indexes
  56         // that respond so well to additional hashtable size, so they generally
  57         // end up with smaller hash tables (so as not to waste memory).
  58         // The algorithms below cause the following progression (presuming
  59         // the default starting size of 1000 buckets):
  60         //
  61         // Buckets in normal keys:             Buckets in index key:
  62         //    1000 (up to  30000 objects)         1000 (up to   23000 objects)
  63         //    3000 (up to  90000 objects)         4600 (up to  105800 objects)
  64         //    9000 (up to 270000 objects)        21160 (up to  486680 objects)
  65         //   27000 (up to 810000 objects)        97336 (up to 2238728 objects)
  66         //
  67 #define MIN_TABLE_SIZE(_cObjects)     ((_cObjects) / 30)
  68 #define TARGET_TABLE_SIZE(_cObjects)  ((_cObjects) / 10)
  69
  70 #define MIN_TABLE_SIZE_FOR_KEY(_cObjects)     ((_cObjects) / 23)
  71 #define TARGET_TABLE_SIZE_FOR_KEY(_cObjects)  ((_cObjects) /  5)
  72
  73
  74 /*
  75  * REALLOC ____________________________________________________________________
  76  *
  77  */
  78
  79 #ifdef REALLOC
  80 #undef REALLOC
  81 #endif
  82 #define REALLOC(_a,_c,_r,_i) HashList_ReallocFunction ((LPVOID*)&_a,sizeof(*_a),&_c,_r,_i)
  83 BOOL HashList_ReallocFunction (LPVOID *ppTarget, size_t cbElement, size_t *pcTarget, size_t cReq, size_t cInc)
  84 {
  85    LPVOID pNew;
  86    size_t cNew;
  87
  88    if (cReq <= *pcTarget)
  89       return TRUE;
  90
  91    if ((cNew = cInc * ((cReq + cInc-1) / cInc)) <= 0)
  92       return FALSE;
  93
  94    if ((pNew = (LPVOID)GlobalAlloc (GMEM_FIXED, cbElement * cNew)) == NULL)
  95       return FALSE;
  96
  97    if (*pcTarget == 0)
  98       memset (pNew, 0x00, cbElement * cNew);
  99    else
 100       {
 101       memcpy (pNew, *ppTarget, cbElement * (*pcTarget));
 102       memset (&((char*)pNew)[ cbElement * (*pcTarget) ], 0x00, cbElement * (cNew - *pcTarget));
 103       GlobalFree ((HGLOBAL)*ppTarget);
 104       }
 105
 106    *ppTarget = pNew;
 107    *pcTarget = cNew;
 108    return TRUE;
 109 }
 110
 111
 112 /*
 113  * EXPANDARRAY CLASS __________________________________________________________
 114  *
 115  */
 116
 117 #define cEXPANDARRAYHEAPELEMENTS  1024
 118 #define cREALLOC_EXPANDARRAYHEAPS   16
 119
 120 EXPANDARRAY::EXPANDARRAY (size_t cbElement, size_t cElementsPerHeap)
 121 {
 122    if ((m_cbElement = cbElement) == 0)
 123       m_cbElement = sizeof(DWORD);
 124    if ((m_cElementsPerHeap = cElementsPerHeap) == 0)
 125       m_cElementsPerHeap = cEXPANDARRAYHEAPELEMENTS;
 126
 127    m_cHeaps = 0;
 128    m_aHeaps = 0;
 129 }
 130
 131 EXPANDARRAY::~EXPANDARRAY (void)
 132 {
 133    if (m_aHeaps)
 134       {
 135       for (size_t ii = 0; ii < m_cHeaps; ++ii)
 136          {
 137          if (m_aHeaps[ ii ])
 138             GlobalFree ((HGLOBAL)(m_aHeaps[ ii ]));
 139          }
 140       GlobalFree ((HGLOBAL)m_aHeaps);
 141       }
 142 }
 143
 144 PVOID EXPANDARRAY::GetAt (size_t iElement)
 145 {
 146    size_t iHeap = iElement / m_cElementsPerHeap;
 147    size_t iIndex = iElement % m_cElementsPerHeap;
 148    if ((iHeap >= m_cHeaps) || (!m_aHeaps[iHeap]))
 149       return NULL;
 150
 151    PVOID pElement;
 152    pElement = &((PBYTE)m_aHeaps[ iHeap ]->aElements)[ iIndex * m_cbElement ];
 153    return pElement;
 154 }
 155
 156 PVOID EXPANDARRAY::SetAt (size_t iElement, PVOID pData)
 157 {
 158    size_t iHeap = iElement / m_cElementsPerHeap;
 159    size_t iIndex = iElement % m_cElementsPerHeap;
 160
 161    if (!REALLOC (m_aHeaps, m_cHeaps, 1+iHeap, cREALLOC_EXPANDARRAYHEAPS))
 162       return NULL;
 163
 164    if (!m_aHeaps[ iHeap ])
 165       {
 166       size_t cbHeap = sizeof(EXPANDARRAYHEAP) + (m_cElementsPerHeap * m_cbElement);
 167       if ((m_aHeaps[ iHeap ] = (LPEXPANDARRAYHEAP)GlobalAlloc (GMEM_FIXED, cbHeap)) == NULL)
 168          return NULL;
 169       memset (m_aHeaps[ iHeap ], 0x00, cbHeap);
 170       m_aHeaps[ iHeap ]->aElements = ((PBYTE)m_aHeaps[ iHeap ]) + sizeof(EXPANDARRAYHEAP);
 171       }
 172
 173    PVOID pElement;
 174    pElement = &((PBYTE)m_aHeaps[ iHeap ]->aElements)[ iIndex * m_cbElement ];
 175    if (pData)
 176       memcpy (pElement, pData, m_cbElement);
 177    return pElement;
 178 }
 179
 180
 181 /*
 182  * HASHLIST CLASS _____________________________________________________________
 183  *
 184  */
 185
 186 #define GetEntry(_pArray,_iEntry)  ((LPHASHLISTENTRY)((_pArray)->GetAt(_iEntry)))
 187
 188 HASHLIST::HASHLIST (void)
 189 {
 190    InitializeCriticalSection (&m_cs);
 191    m_pcs = &m_cs;
 192    Enter();
 193
 194    m_iFirst = iINVALID;
 195    m_iLast = iINVALID;
 196    m_iNextFree = 0;
 197    m_aObjects = new EXPANDARRAY (sizeof(HASHLISTENTRY), cREALLOC_OBJECTS);
 198    m_cObjects = 0;
 199    m_cObjectsMax = 0;
 200    m_apKeys = NULL;
 201    m_cpKeys = 0;
 202
 203    m_pKeyIndex = new HASHLISTKEY (this, TEXT("Index"), HASHLIST::KeyIndex_CompareObjectData, HASHLIST::KeyIndex_HashObject, HASHLIST::KeyIndex_HashData, cTABLESIZE_DEFAULT);
 204
 205    Leave();
 206 }
 207
 208
 209 HASHLIST::~HASHLIST (void)
 210 {
 211    Enter();
 212
 213    if (m_apKeys != NULL)
 214       {
 215       for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
 216          {
 217          if (m_apKeys[ iKey ] != NULL)
 218             delete m_apKeys[ iKey ];
 219          }
 220       GlobalFree ((HGLOBAL)m_apKeys);
 221       }
 222
 223    if (m_pKeyIndex)
 224       {
 225       delete m_pKeyIndex;
 226       }
 227
 228    if (m_aObjects != NULL)
 229       {
 230       delete m_aObjects;
 231       }
 232
 233    Leave();
 234    DeleteCriticalSection (&m_cs);
 235 }
 236
 237
 238 void HASHLIST::Enter (void)
 239 {
 240    EnterCriticalSection (m_pcs);
 241 }
 242
 243
 244 void HASHLIST::Leave (void)
 245 {
 246    LeaveCriticalSection (m_pcs);
 247 }
 248
 249
 250 void HASHLIST::SetCriticalSection (CRITICAL_SECTION *pcs)
 251 {
 252    m_pcs = (pcs == NULL) ? &m_cs : pcs;
 253 }
 254
 255
 256 BOOL HASHLIST::AddUnique (PVOID pEntryToAdd, LPHASHLISTKEY pKey)
 257 {
 258    if ( ((pKey == NULL) && (fIsInList (pEntryToAdd))) ||
 259         ((pKey != NULL) && (pKey->fIsInList (pEntryToAdd))) )
 260       {
 261       return TRUE;
 262       }
 263
 264    return Add (pEntryToAdd);
 265 }
 266
 267
 268 BOOL HASHLIST::Add (PVOID pEntryToAdd)
 269 {
 270    BOOL rc = FALSE;
 271    Enter();
 272
 273    if (pEntryToAdd)
 274       {
 275       size_t iObject = m_iNextFree;
 276
 277       if ((GetEntry(m_aObjects,iObject) && (GetEntry(m_aObjects,iObject)->pObject)))
 278          {
 279          for (iObject = 0; iObject < m_cObjectsMax; ++iObject)
 280             {
 281             if ( (!GetEntry(m_aObjects,iObject)) || (!GetEntry(m_aObjects,iObject)->pObject) )
 282                break;
 283             }
 284          }
 285
 286       m_iNextFree = 1+iObject;
 287
 288       HASHLISTENTRY Entry;
 289       Entry.pObject = pEntryToAdd;
 290       Entry.iNext = iINVALID;
 291       Entry.iPrevious = m_iLast;
 292       m_aObjects->SetAt (iObject, &Entry);
 293
 294       if (m_iLast != iINVALID)
 295          {
 296          LPHASHLISTENTRY pEntry;
 297          if ((pEntry = GetEntry(m_aObjects,m_iLast)) != NULL)
 298             pEntry->iNext = iObject;
 299          }
 300
 301       m_iLast = iObject;
 302       if (m_iFirst == iINVALID)
 303          m_iFirst = iObject;
 304
 305       m_pKeyIndex->Add (iObject, (PVOID)(iObject+1));
 306
 307       for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
 308          {
 309          if (m_apKeys[ iKey ] == NULL)
 310             continue;
 311          m_apKeys[ iKey ]->Add (iObject, pEntryToAdd);
 312          }
 313
 314       ++m_cObjects;
 315       m_cObjectsMax = max (m_cObjectsMax, m_cObjects);
 316       rc = TRUE;
 317       }
 318
 319    Leave();
 320    return rc;
 321 }
 322
 323
 324 void HASHLIST::Remove (PVOID pEntryToRemove)
 325 {
 326    Enter();
 327
 328    if (pEntryToRemove)
 329       {
 330       // The first step is to find which m_aObjects entry corresponds
 331       // with this object. Ordinarily that'd be a brute-force search;
 332       // however, to speed things up, we have a special key placed on
 333       // the address of the object for determining its index. It lets
 334       // us replace this code:
 335       //
 336       // for (size_t iObject = 0; iObject < m_cObjectsMax; ++iObject)
 337       //   {
 338       //   if (m_aObjects[ iObject ].pObject == pEntryToRemove)
 339       //      break;
 340       //   }
 341       //
 342       // Because this index key uses a hashtable that's resized very
 343       // aggressively, performance tests of up to 100,000 objects
 344       // indicate that removing an object now clocks in as O(1), rather
 345       // than the O(N) that it would be if we used the brute-force approach.
 346       // At 100,000 objects it does use up some 70k of memory, but wow
 347       // is it fast...
 348       //
 349       size_t iObject = iINVALID;
 350
 351       PVOID pFind;
 352       if ((pFind = m_pKeyIndex->GetFirstObject (pEntryToRemove)) != NULL)
 353          iObject = *(size_t *)&pFind -1;
 354
 355       // Now remove the object.
 356       //
 357       if (iObject != iINVALID)
 358          {
 359          LPHASHLISTENTRY pEntry;
 360          if ((pEntry = GetEntry(m_aObjects,iObject)) != NULL)
 361             {
 362             pEntry->pObject = NULL;
 363
 364             if (pEntry->iPrevious != iINVALID)
 365                {
 366                LPHASHLISTENTRY pPrevious;
 367                if ((pPrevious = GetEntry(m_aObjects,pEntry->iPrevious)) != NULL)
 368                   pPrevious->iNext = pEntry->iNext;
 369                }
 370             if (pEntry->iNext != iINVALID)
 371                {
 372                LPHASHLISTENTRY pNext;
 373                if ((pNext = GetEntry(m_aObjects,pEntry->iNext)) != NULL)
 374                   pNext->iPrevious = pEntry->iPrevious;
 375                }
 376
 377             if (m_iLast == iObject)
 378                m_iLast = pEntry->iPrevious;
 379             if (m_iFirst == iObject)
 380                m_iFirst = pEntry->iNext;
 381
 382             for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
 383                {
 384                if (m_apKeys[ iKey ] == NULL)
 385                   continue;
 386                m_apKeys[ iKey ]->Remove (iObject);
 387                }
 388
 389             m_pKeyIndex->Remove (iObject);
 390             --m_cObjects;
 391             }
 392          }
 393       }
 394
 395    Leave();
 396 }
 397
 398
 399 BOOL HASHLIST::Update (PVOID pEntryToUpdate)
 400 {
 401    BOOL rc = TRUE;
 402    Enter();
 403
 404    PVOID pFind;
 405    if ((pFind = m_pKeyIndex->GetFirstObject (pEntryToUpdate)) == NULL)
 406       rc = FALSE;
 407    else
 408       {
 409       size_t iObject = *(size_t *)&pFind -1;
 410
 411       for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
 412          {
 413          if (m_apKeys[ iKey ] == NULL)
 414             continue;
 415
 416          m_apKeys[ iKey ]->Remove (iObject);
 417          m_apKeys[ iKey ]->Add (iObject, pEntryToUpdate);
 418          }
 419       }
 420
 421    Leave();
 422    return rc;
 423 }
 424
 425
 426 BOOL HASHLIST::fIsInList (PVOID pEntry)
 427 {
 428    PVOID pFind;
 429    if ((pFind = m_pKeyIndex->GetFirstObject (pEntry)) == NULL)
 430       return FALSE;
 431    return TRUE;
 432 }
 433
 434
 435 LPHASHLISTKEY HASHLIST::CreateKey (LPCTSTR pszKeyName, LPHASHFUNC_COMPAREOBJECTDATA fnCompareObjectData, LPHASHFUNC_HASHOBJECT fnHashObject, LPHASHFUNC_HASHDATA fnHashData, size_t cTableSize)
 436 {
 437    LPHASHLISTKEY pKey = NULL;
 438    Enter();
 439
 440    for (size_t 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    for (size_t iObject = 0; ; ++iObject)
 860       {
 861       LPHASHLISTENTRY pEntry;
 862       if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
 863          break;
 864       pEntry->pObject = NULL;
 865       }
 866
 867    // Re-add the objects to this key. One caveat: if this is the
 868    // hashlist's index key, then the format of the items is different--
 869    // retain that difference.
 870    //
 871    if (this == m_pList->m_pKeyIndex)
 872       {
 873       for (iObject = 0; ; ++iObject)
 874          {
 875          LPHASHLISTENTRY pEntry;
 876          if ((pEntry = GetEntry(m_pList->m_aObjects,iObject)) == NULL)
 877             break;
 878          if (pEntry->pObject != NULL)
 879             Add (iObject, (PVOID)(iObject+1));
 880          }
 881       }
 882    else // normal, user-defined key
 883       {
 884       for (iObject = 0; ; ++iObject)
 885          {
 886          LPHASHLISTENTRY pEntry;
 887          if ((pEntry = GetEntry(m_pList->m_aObjects,iObject)) == NULL)
 888             break;
 889          if (pEntry->pObject != NULL)
 890             Add (iObject, pEntry->pObject);
 891          }
 892       }
 893 }
 894
 895
 896 LPHASHLISTKEYDEBUGINFO HASHLISTKEY::GetDebugInfo (void)
 897 {
 898    m_pList->Enter();
 899
 900    LPHASHLISTKEYDEBUGINFO pInfo = new HASHLISTKEYDEBUGINFO;
 901    memset (pInfo, 0x00, sizeof(HASHLISTKEYDEBUGINFO));
 902
 903    // Find out how full each bucket is.
 904    //
 905    REALLOC (pInfo->aBuckets, pInfo->cBuckets, m_cBuckets, 1);
 906
 907    for (size_t iBucket = 0; iBucket < pInfo->cBuckets; ++iBucket)
 908       {
 909       for (size_t iObject = m_aBuckets[ iBucket ].iFirst;
 910            iObject != iINVALID;
 911            iObject = GetEntry(m_aObjects,iObject)->iNext)
 912          {
 913          (pInfo->aBuckets[ iBucket ])++;
 914          }
 915       }
 916
 917    // Calculate a "percent effectiveness". This is a pretty fuzzy
 918    // calculation; we want 100% if all buckets are the same size
 919    // (plus or minus one element), and 0% if all buckets except one are
 920    // empty but that one bucket has more than cBuckets elements. In
 921    // between, we'll try to create a roughly linear gradient. The
 922    // calculation is effectively the proportion of the number of
 923    // objects which are evenly distributed to the number of objects
 924    // overall.
 925    //
 926    if (pInfo->cBuckets == 0)
 927       {
 928       pInfo->perEffective = 100;
 929       }
 930    else
 931       {
 932       // We want an accurate count of objects, not the over-allocated
 933       // count given by m_cObjectsMax.
 934       //
 935       size_t cObjects = 0;
 936       for (iBucket = 0; iBucket < pInfo->cBuckets; ++iBucket)
 937          cObjects += pInfo->aBuckets[ iBucket ];
 938
 939       if (cObjects == 0)
 940          {
 941          pInfo->perEffective = 100;
 942          }
 943       else
 944          {
 945          // Determine what "even distribution" means--that's pretty easy.
 946          // We increase the count by one to indicate that slight unevenness
 947          // will occur unless the number of objects is a multiple of the
 948          // number of buckets.
 949          //
 950          size_t cPerfectLength = (cObjects / pInfo->cBuckets) + 1;
 951
 952          size_t cObjectsInPlace = 0;
 953          for (iBucket = 0; iBucket < pInfo->cBuckets; ++iBucket)
 954             cObjectsInPlace += min( pInfo->aBuckets[ iBucket ], cPerfectLength );
 955
 956          // Now calculating that percent effectiveness is easy. If everything
 957          // is evenly distributed, cObjectsInPlace will == cObjects--and
 958          // we want to call it 100%. If eveything is on one chain, then
 959          // cObjectsInPlace will be really small compared to cObjects.
 960          //
 961          pInfo->perEffective = (WORD)(cObjectsInPlace * 100 / cObjects);
 962          }
 963       }
 964
 965    m_pList->Leave();
 966    return pInfo;
 967 }
 968
 969
 970 void HASHLISTKEY::FreeDebugInfo (LPHASHLISTKEYDEBUGINFO pInfo)
 971 {
 972    if (pInfo->aBuckets)
 973       GlobalFree ((HGLOBAL)(pInfo->aBuckets));
 974 }
 975
 976
 977 /*
 978  * ENUMERATION CLASS _____________________________________________________________
 979  *
 980  */
 981
 982 ENUMERATION::ENUMERATION (LPHASHLIST pList, size_t iObject, LPHASHLISTKEY pKey, PVOID pData)
 983 {
 984    m_pList = pList;
 985    m_pKey = pKey;
 986    m_pData = pData;
 987    m_iObject = iObject;
 988
 989    PrepareWalk(); // finds m_iPrevious and m_iNext
 990
 991    m_pList->Enter();
 992 }
 993
 994
 995 ENUMERATION::~ENUMERATION (void)
 996 {
 997    m_pList->Leave();
 998 }
 999
1000
1001 PVOID ENUMERATION::GetObject (void)
1002 {
1003    return GetEntry(m_pList->m_aObjects,m_iObject)->pObject;
1004 }
1005
1006
1007 LPENUMERATION ENUMERATION::FindNext (void)
1008 {
1009    for (;;)
1010       {
1011       m_iObject = m_iNext;
1012       PrepareWalk();
1013
1014       if (m_iObject == iINVALID)
1015          break;
1016
1017       if (m_pKey == NULL)
1018          return this;
1019
1020       if (m_pKey->CompareObjectData (GetEntry(m_pList->m_aObjects,m_iObject)->pObject, m_pData))
1021          return this;
1022       }
1023
1024    Delete (this);
1025    return NULL;
1026 }
1027
1028
1029 LPENUMERATION ENUMERATION::FindPrevious (void)
1030 {
1031    for (;;)
1032       {
1033       m_iObject = m_iPrevious;
1034       PrepareWalk();
1035
1036       if (m_iObject == iINVALID)
1037          break;
1038
1039       if (m_pKey == NULL)
1040          return this;
1041
1042       if (m_pKey->CompareObjectData (GetEntry(m_pList->m_aObjects,m_iObject)->pObject, m_pData))
1043          return this;
1044       }
1045
1046    Delete (this);
1047    return NULL;
1048 }
1049
1050
1051 void ENUMERATION::PrepareWalk (void)
1052 {
1053    if (m_iObject == iINVALID)
1054       {
1055       m_iPrevious = iINVALID;
1056       m_iNext = iINVALID;
1057       }
1058    else if (m_pKey == NULL)
1059       {
1060       m_iPrevious = GetEntry(m_pList->m_aObjects,m_iObject)->iPrevious;
1061       m_iNext = GetEntry(m_pList->m_aObjects,m_iObject)->iNext;
1062       }
1063    else
1064       {
1065       m_iPrevious = GetEntry(m_pKey->m_aObjects,m_iObject)->iPrevious;
1066       m_iNext = GetEntry(m_pKey->m_aObjects,m_iObject)->iNext;
1067       }
1068 }
1069
1070
1071 /*
1072  * GENERAL-PURPOSE ____________________________________________________________
1073  *
1074  */
1075
1076 HASHVALUE HashString (LPCTSTR pszString)
1077 {
1078 #ifdef UNICODE
1079    return HashUnicodeString (pszString);
1080 #else
1081    return HashAnsiString (pszString);
1082 #endif
1083 }
1084
1085 HASHVALUE HashAnsiString (LPCSTR pszStringA)
1086 {
1087    HASHVALUE hv = 0;
1088
1089    for (size_t cch = lstrlenA(pszStringA); cch >= 4; pszStringA += 4, cch -= 4)
1090       hv += *(DWORD *)pszStringA;
1091
1092    for (; cch; pszStringA++, cch--)
1093       hv += *pszStringA;
1094
1095    return hv;
1096 }
1097
1098 HASHVALUE HashUnicodeString (LPWSTR pszStringW)
1099 {
1100    HASHVALUE hv = 0;
1101
1102    for (size_t cch = lstrlenW(pszStringW); cch >= 2; pszStringW += 2, cch -= 2)
1103       {
1104       hv += *(DWORD *)pszStringW;   // since HIBYTE(*psz) is usually zero,
1105       hv = (hv >> 24) | (hv << 8);  // rotate {hv} high-ward by 8 bits
1106       }
1107
1108    for (; cch; pszStringW++, cch--)
1109       hv += *pszStringW;
1110
1111    return hv;
1112 }
1113