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    for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
 440       {
 441       if (m_apKeys[ iKey ] == NULL)
 442          break;
 443       }
 444    if (REALLOC (m_apKeys, m_cpKeys, 1+iKey, cREALLOC_KEYS))
 445       {
 446       m_apKeys[ iKey ] = new HASHLISTKEY (this, pszKeyName, fnCompareObjectData, fnHashObject, fnHashData, cTableSize);
 447       pKey = m_apKeys[ iKey ];
 448
 449       if (MIN_TABLE_SIZE(m_cObjectsMax) > pKey->m_cBuckets)
 450          {
 451          pKey->Resize();
 452          }
 453       else for (size_t iObject = 0; iObject < m_cObjectsMax; ++iObject)
 454          {
 455          LPHASHLISTENTRY pEntry;
 456          if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
 457             continue;
 458          if (pEntry->pObject != NULL)
 459             m_apKeys[ iKey ]->Add (iObject, pEntry->pObject);
 460          }
 461       }
 462
 463    Leave();
 464    return pKey;
 465 }
 466
 467
 468 LPHASHLISTKEY HASHLIST::FindKey (LPCTSTR pszKeyName)
 469 {
 470    LPHASHLISTKEY pKey = NULL;
 471    Enter();
 472
 473    for (size_t iKey = 0; !pKey && (iKey < m_cpKeys); ++iKey)
 474       {
 475       if (m_apKeys[ iKey ] == NULL)
 476          continue;
 477       if (!lstrcmpi (m_apKeys[ iKey ]->m_szKeyName, pszKeyName))
 478          pKey = m_apKeys[ iKey ];
 479       }
 480
 481    Leave();
 482    return pKey;
 483 }
 484
 485
 486 void HASHLIST::RemoveKey (LPHASHLISTKEY pKey)
 487 {
 488    Enter();
 489
 490    for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
 491       {
 492       if (m_apKeys[ iKey ] == pKey)
 493          {
 494          delete m_apKeys[ iKey ];
 495          m_apKeys[ iKey ] = NULL;
 496          break;
 497          }
 498       }
 499
 500    Leave();
 501 }
 502
 503
 504 LPENUM HASHLIST::FindFirst (void)
 505 {
 506    LPENUM pEnum = NULL;
 507    Enter();
 508
 509    if (m_iFirst != iINVALID)
 510       pEnum = New2 (ENUMERATION,(this, m_iFirst));
 511
 512    Leave();
 513    return pEnum;
 514 }
 515
 516
 517 LPENUM HASHLIST::FindLast (void)
 518 {
 519    LPENUM pEnum = NULL;
 520    Enter();
 521
 522    if (m_iLast != iINVALID)
 523       pEnum = New2 (ENUMERATION,(this, m_iLast));
 524
 525    Leave();
 526    return pEnum;
 527 }
 528
 529
 530 PVOID HASHLIST::GetFirstObject (void)
 531 {
 532    PVOID pObject = NULL;
 533    Enter();
 534
 535    if (m_iFirst != iINVALID)
 536       pObject = GetEntry(m_aObjects,m_iFirst)->pObject;
 537
 538    Leave();
 539    return pObject;
 540 }
 541
 542
 543 PVOID HASHLIST::GetLastObject (void)
 544 {
 545    PVOID pObject = NULL;
 546    Enter();
 547
 548    if (m_iLast != iINVALID)
 549       pObject = GetEntry(m_aObjects,m_iLast)->pObject;
 550
 551    Leave();
 552    return pObject;
 553 }
 554
 555
 556 size_t HASHLIST::GetCount (void)
 557 {
 558    return m_cObjects;
 559 }
 560
 561
 562 BOOL CALLBACK HASHLIST::KeyIndex_CompareObjectData (LPHASHLISTKEY pKey, PVOID pObject, PVOID pData)
 563 {
 564    size_t iIndex = (size_t)pObject -1;
 565    LPHASHLIST pList = pKey->GetHashList();
 566    return (GetEntry(pList->m_aObjects,iIndex)->pObject == pData) ? TRUE : FALSE;
 567 }
 568
 569
 570 HASHVALUE CALLBACK HASHLIST::KeyIndex_HashObject (LPHASHLISTKEY pKey, PVOID pObject)
 571 {
 572    size_t iIndex = (size_t)pObject -1;
 573    LPHASHLIST pList = pKey->GetHashList();
 574    return KeyIndex_HashData (pKey, GetEntry(pList->m_aObjects,iIndex)->pObject);
 575 }
 576
 577
 578 HASHVALUE CALLBACK HASHLIST::KeyIndex_HashData (LPHASHLISTKEY pKey, PVOID pData)
 579 {
 580    return ((DWORD)pData) >> 4;  // The "data" is the object's address.
 581 }
 582
 583
 584 /*
 585  * HASHLISTKEY CLASS _____________________________________________________________
 586  *
 587  */
 588
 589 HASHLISTKEY::HASHLISTKEY (LPHASHLIST pList, LPCTSTR pszKeyName, LPHASHFUNC_COMPAREOBJECTDATA fnCompareObjectData, LPHASHFUNC_HASHOBJECT fnHashObject, LPHASHFUNC_HASHDATA fnHashData, size_t cTableSize)
 590 {
 591    m_aObjects = new EXPANDARRAY (sizeof(HASHLISTENTRY), cREALLOC_OBJECTS);
 592
 593    m_cBuckets = (cTableSize == 0) ? cTABLESIZE_DEFAULT : cTableSize;
 594    m_aBuckets = (struct HASHBUCKET *)GlobalAlloc (GMEM_FIXED, m_cBuckets * sizeof(struct HASHBUCKET));
 595    for (size_t iBucket = 0; iBucket < m_cBuckets; ++iBucket)
 596       {
 597       m_aBuckets[ iBucket ].iFirst = iINVALID;
 598       m_aBuckets[ iBucket ].iLast = iINVALID;
 599       }
 600
 601    m_pList = pList;
 602    lstrcpy (m_szKeyName, pszKeyName);
 603    m_fnCompareObjectData = fnCompareObjectData;
 604    m_fnHashObject = fnHashObject;
 605    m_fnHashData = fnHashData;
 606 }
 607
 608
 609 HASHLISTKEY::~HASHLISTKEY (void)
 610 {
 611    m_pList->Enter();
 612
 613    for (size_t iObject = 0; iObject < m_pList->m_cObjectsMax; ++iObject)
 614       {
 615       if (!GetEntry(m_aObjects,iObject))
 616          continue;
 617       if (!GetEntry(m_aObjects,iObject)->pObject)
 618          continue;
 619       Remove (iObject);
 620       }
 621
 622    if (m_aObjects)
 623       delete m_aObjects;
 624    if (m_aBuckets)
 625       GlobalFree ((HGLOBAL)m_aBuckets);
 626
 627    m_pList->Leave();
 628 }
 629
 630
 631 LPHASHLIST HASHLISTKEY::GetHashList (void)
 632 {
 633    return m_pList;
 634 }
 635
 636
 637 BOOL HASHLISTKEY::CompareObjectData (PVOID pObject, PVOID pData)
 638 {
 639    return (*m_fnCompareObjectData)(this, pObject, pData);
 640 }
 641
 642 HASHVALUE HASHLISTKEY::HashObject (PVOID pObject)
 643 {
 644    return ((*m_fnHashObject)(this, pObject)) % m_cBuckets;
 645 }
 646
 647 HASHVALUE HASHLISTKEY::HashData (PVOID pData)
 648 {
 649    return ((*m_fnHashData)(this, pData)) % m_cBuckets;
 650 }
 651
 652
 653 LPENUM HASHLISTKEY::FindFirst (PVOID pData)
 654 {
 655    LPENUM pEnum = NULL;
 656    m_pList->Enter();
 657
 658    HASHVALUE hvSearch = HashData (pData);
 659
 660    size_t iObject;
 661    if ((iObject = m_aBuckets[ hvSearch ].iFirst) != iINVALID)
 662       {
 663       LPHASHLISTENTRY pEntry;
 664       do {
 665          if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
 666             break;
 667          if (CompareObjectData (pEntry->pObject, pData))
 668             {
 669             pEnum = New2 (ENUMERATION,(m_pList, iObject, this, pData));
 670             break;
 671             }
 672          } while ((iObject = pEntry->iNext) != iINVALID);
 673       }
 674
 675    m_pList->Leave();
 676    return pEnum;
 677 }
 678
 679
 680 LPENUM HASHLISTKEY::FindLast (PVOID pData)
 681 {
 682    LPENUM pEnum = NULL;
 683    m_pList->Enter();
 684
 685    HASHVALUE hvSearch = HashData (pData);
 686
 687    size_t iObject;
 688    if ((iObject = m_aBuckets[ hvSearch ].iLast) != iINVALID)
 689       {
 690       LPHASHLISTENTRY pEntry;
 691       do {
 692          if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
 693             break;
 694          if (CompareObjectData (pEntry->pObject, pData))
 695             {
 696             pEnum = New2 (ENUMERATION,(m_pList, iObject, this, pData));
 697             break;
 698             }
 699          } while ((iObject = pEntry->iPrevious) != iINVALID);
 700       }
 701
 702    m_pList->Leave();
 703    return pEnum;
 704 }
 705
 706
 707 PVOID HASHLISTKEY::GetFirstObject (PVOID pData)
 708 {
 709    PVOID pObject = NULL;
 710    m_pList->Enter();
 711
 712    HASHVALUE hvSearch = HashData (pData);
 713
 714    size_t iObject;
 715    if ((iObject = m_aBuckets[ hvSearch ].iFirst) != iINVALID)
 716       {
 717       LPHASHLISTENTRY pEntry;
 718       do {
 719          if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
 720             break;
 721          if (CompareObjectData (pEntry->pObject, pData))
 722             {
 723             pObject = pEntry->pObject;
 724             break;
 725             }
 726          } while ((iObject = pEntry->iNext) != iINVALID);
 727       }
 728
 729    m_pList->Leave();
 730    return pObject;
 731 }
 732
 733
 734 PVOID HASHLISTKEY::GetLastObject (PVOID pData)
 735 {
 736    PVOID pObject = NULL;
 737    m_pList->Enter();
 738
 739    HASHVALUE hvSearch = HashData (pData);
 740
 741    size_t iObject;
 742    if ((iObject = m_aBuckets[ hvSearch ].iLast) != iINVALID)
 743       {
 744       LPHASHLISTENTRY pEntry;
 745       do {
 746          if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
 747             break;
 748          if (CompareObjectData (pEntry->pObject, pData))
 749             {
 750             pObject = pEntry->pObject;
 751             break;
 752             }
 753          } while ((iObject = pEntry->iPrevious) != iINVALID);
 754       }
 755
 756    m_pList->Leave();
 757    return pObject;
 758 }
 759
 760
 761 BOOL HASHLISTKEY::fIsInList (PVOID pEntry)
 762 {
 763    PVOID pFind;
 764    if ((pFind = GetFirstObject (pEntry)) == NULL)
 765       return FALSE;
 766    return TRUE;
 767 }
 768
 769
 770 void HASHLISTKEY::Add (size_t iObject, PVOID pObject)
 771 {
 772    m_pList->Enter();
 773
 774    if ( ((this == m_pList->m_pKeyIndex) && (MIN_TABLE_SIZE_FOR_KEY(m_pList->m_cObjectsMax) > m_cBuckets)) ||
 775         ((this != m_pList->m_pKeyIndex) && (MIN_TABLE_SIZE(m_pList->m_cObjectsMax) > m_cBuckets)) )
 776       {
 777       Resize();
 778       }
 779    else
 780       {
 781       HASHVALUE hv = HashObject (pObject);
 782       struct HASHBUCKET *pBucket = &m_aBuckets[ hv ];
 783
 784       HASHLISTENTRY Entry;
 785       Entry.pObject = pObject;
 786       Entry.hv = hv;
 787       Entry.iNext = iINVALID;
 788       Entry.iPrevious = pBucket->iLast;
 789       m_aObjects->SetAt (iObject, &Entry);
 790
 791       pBucket->iLast = iObject;
 792
 793       if (Entry.iPrevious != iINVALID)
 794          {
 795          LPHASHLISTENTRY pPrevious;
 796          if ((pPrevious = GetEntry(m_aObjects,Entry.iPrevious)) != NULL)
 797             pPrevious->iNext = iObject;
 798          }
 799
 800       if (pBucket->iFirst == iINVALID)
 801          pBucket->iFirst = iObject;
 802       }
 803
 804    m_pList->Leave();
 805 }
 806
 807
 808 void HASHLISTKEY::Remove (size_t iObject)
 809 {
 810    m_pList->Enter();
 811
 812    LPHASHLISTENTRY pEntry;
 813    if ((pEntry = GetEntry(m_aObjects,iObject)) != NULL)
 814       {
 815       pEntry->pObject = NULL;
 816
 817       if (pEntry->iPrevious != iINVALID)
 818          {
 819          LPHASHLISTENTRY pPrevious;
 820          if ((pPrevious = GetEntry(m_aObjects,pEntry->iPrevious)) != NULL)
 821             pPrevious->iNext = pEntry->iNext;
 822          }
 823
 824       if (pEntry->iNext != iINVALID)
 825          {
 826          LPHASHLISTENTRY pNext;
 827          if ((pNext = GetEntry(m_aObjects,pEntry->iNext)) != NULL)
 828             pNext->iPrevious = pEntry->iPrevious;
 829          }
 830
 831       if (m_aBuckets[ pEntry->hv ].iLast == iObject)
 832          m_aBuckets[ pEntry->hv ].iLast = pEntry->iPrevious;
 833       if (m_aBuckets[ pEntry->hv ].iFirst == iObject)
 834          m_aBuckets[ pEntry->hv ].iFirst = pEntry->iNext;
 835       }
 836
 837    m_pList->Leave();
 838 }
 839
 840
 841 void HASHLISTKEY::Resize (void)
 842 {
 843    if (this == m_pList->m_pKeyIndex)
 844       {
 845       REALLOC (m_aBuckets, m_cBuckets, TARGET_TABLE_SIZE_FOR_KEY(m_pList->m_cObjectsMax), 1);
 846       }
 847    else
 848       {
 849       REALLOC (m_aBuckets, m_cBuckets, TARGET_TABLE_SIZE(m_pList->m_cObjectsMax), 1);
 850       }
 851
 852    for (size_t iBucket = 0; iBucket < m_cBuckets; ++iBucket)
 853       {
 854       m_aBuckets[ iBucket ].iFirst = iINVALID;
 855       m_aBuckets[ iBucket ].iLast = iINVALID;
 856       }
 857
 858    for (size_t iObject = 0; ; ++iObject)
 859       {
 860       LPHASHLISTENTRY pEntry;
 861       if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
 862          break;
 863       pEntry->pObject = NULL;
 864       }
 865
 866    // Re-add the objects to this key. One caveat: if this is the
 867    // hashlist's index key, then the format of the items is different--
 868    // retain that difference.
 869    //
 870    if (this == m_pList->m_pKeyIndex)
 871       {
 872       for (iObject = 0; ; ++iObject)
 873          {
 874          LPHASHLISTENTRY pEntry;
 875          if ((pEntry = GetEntry(m_pList->m_aObjects,iObject)) == NULL)
 876             break;
 877          if (pEntry->pObject != NULL)
 878             Add (iObject, (PVOID)(iObject+1));
 879          }
 880       }
 881    else // normal, user-defined key
 882       {
 883       for (iObject = 0; ; ++iObject)
 884          {
 885          LPHASHLISTENTRY pEntry;
 886          if ((pEntry = GetEntry(m_pList->m_aObjects,iObject)) == NULL)
 887             break;
 888          if (pEntry->pObject != NULL)
 889             Add (iObject, pEntry->pObject);
 890          }
 891       }
 892 }
 893
 894
 895 LPHASHLISTKEYDEBUGINFO HASHLISTKEY::GetDebugInfo (void)
 896 {
 897    m_pList->Enter();
 898
 899    LPHASHLISTKEYDEBUGINFO pInfo = new HASHLISTKEYDEBUGINFO;
 900    memset (pInfo, 0x00, sizeof(HASHLISTKEYDEBUGINFO));
 901
 902    // Find out how full each bucket is.
 903    //
 904    REALLOC (pInfo->aBuckets, pInfo->cBuckets, m_cBuckets, 1);
 905
 906    for (size_t iBucket = 0; iBucket < pInfo->cBuckets; ++iBucket)
 907       {
 908       for (size_t iObject = m_aBuckets[ iBucket ].iFirst;
 909            iObject != iINVALID;
 910            iObject = GetEntry(m_aObjects,iObject)->iNext)
 911          {
 912          (pInfo->aBuckets[ iBucket ])++;
 913          }
 914       }
 915
 916    // Calculate a "percent effectiveness". This is a pretty fuzzy
 917    // calculation; we want 100% if all buckets are the same size
 918    // (plus or minus one element), and 0% if all buckets except one are
 919    // empty but that one bucket has more than cBuckets elements. In
 920    // between, we'll try to create a roughly linear gradient. The
 921    // calculation is effectively the proportion of the number of
 922    // objects which are evenly distributed to the number of objects
 923    // overall.
 924    //
 925    if (pInfo->cBuckets == 0)
 926       {
 927       pInfo->perEffective = 100;
 928       }
 929    else
 930       {
 931       // We want an accurate count of objects, not the over-allocated
 932       // count given by m_cObjectsMax.
 933       //
 934       size_t cObjects = 0;
 935       for (iBucket = 0; iBucket < pInfo->cBuckets; ++iBucket)
 936          cObjects += pInfo->aBuckets[ iBucket ];
 937
 938       if (cObjects == 0)
 939          {
 940          pInfo->perEffective = 100;
 941          }
 942       else
 943          {
 944          // Determine what "even distribution" means--that's pretty easy.
 945          // We increase the count by one to indicate that slight unevenness
 946          // will occur unless the number of objects is a multiple of the
 947          // number of buckets.
 948          //
 949          size_t cPerfectLength = (cObjects / pInfo->cBuckets) + 1;
 950
 951          size_t cObjectsInPlace = 0;
 952          for (iBucket = 0; iBucket < pInfo->cBuckets; ++iBucket)
 953             cObjectsInPlace += min( pInfo->aBuckets[ iBucket ], cPerfectLength );
 954
 955          // Now calculating that percent effectiveness is easy. If everything
 956          // is evenly distributed, cObjectsInPlace will == cObjects--and
 957          // we want to call it 100%. If eveything is on one chain, then
 958          // cObjectsInPlace will be really small compared to cObjects.
 959          //
 960          pInfo->perEffective = (WORD)(cObjectsInPlace * 100 / cObjects);
 961          }
 962       }
 963
 964    m_pList->Leave();
 965    return pInfo;
 966 }
 967
 968
 969 void HASHLISTKEY::FreeDebugInfo (LPHASHLISTKEYDEBUGINFO pInfo)
 970 {
 971    if (pInfo->aBuckets)
 972       GlobalFree ((HGLOBAL)(pInfo->aBuckets));
 973 }
 974
 975
 976 /*
 977  * ENUMERATION CLASS _____________________________________________________________
 978  *
 979  */
 980
 981 ENUMERATION::ENUMERATION (LPHASHLIST pList, size_t iObject, LPHASHLISTKEY pKey, PVOID pData)
 982 {
 983    m_pList = pList;
 984    m_pKey = pKey;
 985    m_pData = pData;
 986    m_iObject = iObject;
 987
 988    PrepareWalk(); // finds m_iPrevious and m_iNext
 989
 990    m_pList->Enter();
 991 }
 992
 993
 994 ENUMERATION::~ENUMERATION (void)
 995 {
 996    m_pList->Leave();
 997 }
 998
 999
1000 PVOID ENUMERATION::GetObject (void)
1001 {
1002    return GetEntry(m_pList->m_aObjects,m_iObject)->pObject;
1003 }
1004
1005
1006 LPENUMERATION ENUMERATION::FindNext (void)
1007 {
1008    for (;;)
1009       {
1010       m_iObject = m_iNext;
1011       PrepareWalk();
1012
1013       if (m_iObject == iINVALID)
1014          break;
1015
1016       if (m_pKey == NULL)
1017          return this;
1018
1019       if (m_pKey->CompareObjectData (GetEntry(m_pList->m_aObjects,m_iObject)->pObject, m_pData))
1020          return this;
1021       }
1022
1023    Delete (this);
1024    return NULL;
1025 }
1026
1027
1028 LPENUMERATION ENUMERATION::FindPrevious (void)
1029 {
1030    for (;;)
1031       {
1032       m_iObject = m_iPrevious;
1033       PrepareWalk();
1034
1035       if (m_iObject == iINVALID)
1036          break;
1037
1038       if (m_pKey == NULL)
1039          return this;
1040
1041       if (m_pKey->CompareObjectData (GetEntry(m_pList->m_aObjects,m_iObject)->pObject, m_pData))
1042          return this;
1043       }
1044
1045    Delete (this);
1046    return NULL;
1047 }
1048
1049
1050 void ENUMERATION::PrepareWalk (void)
1051 {
1052    if (m_iObject == iINVALID)
1053       {
1054       m_iPrevious = iINVALID;
1055       m_iNext = iINVALID;
1056       }
1057    else if (m_pKey == NULL)
1058       {
1059       m_iPrevious = GetEntry(m_pList->m_aObjects,m_iObject)->iPrevious;
1060       m_iNext = GetEntry(m_pList->m_aObjects,m_iObject)->iNext;
1061       }
1062    else
1063       {
1064       m_iPrevious = GetEntry(m_pKey->m_aObjects,m_iObject)->iPrevious;
1065       m_iNext = GetEntry(m_pKey->m_aObjects,m_iObject)->iNext;
1066       }
1067 }
1068
1069
1070 /*
1071  * GENERAL-PURPOSE ____________________________________________________________
1072  *
1073  */
1074
1075 HASHVALUE HashString (LPCTSTR pszString)
1076 {
1077 #ifdef UNICODE
1078    return HashUnicodeString (pszString);
1079 #else
1080    return HashAnsiString (pszString);
1081 #endif
1082 }
1083
1084 HASHVALUE HashAnsiString (LPCSTR pszStringA)
1085 {
1086    HASHVALUE hv = 0;
1087
1088    for (size_t cch = lstrlenA(pszStringA); cch >= 4; pszStringA += 4, cch -= 4)
1089       hv += *(DWORD *)pszStringA;
1090
1091    for (; cch; pszStringA++, cch--)
1092       hv += *pszStringA;
1093
1094    return hv;
1095 }
1096
1097 HASHVALUE HashUnicodeString (LPWSTR pszStringW)
1098 {
1099    HASHVALUE hv = 0;
1100
1101    for (size_t cch = lstrlenW(pszStringW); cch >= 2; pszStringW += 2, cch -= 2)
1102       {
1103       hv += *(DWORD *)pszStringW;   // since HIBYTE(*psz) is usually zero,
1104       hv = (hv >> 24) | (hv << 8);  // rotate {hv} high-ward by 8 bits
1105       }
1106
1107    for (; cch; pszStringW++, cch--)
1108       hv += *pszStringW;
1109
1110    return hv;
1111 }
1112