2 * Copyright 2000, International Business Machines Corporation and others.
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
11 #include <afs/param.h>
15 #include <WINNT/TaLocale.h>
16 #include <winnt/osi_malloc.h>
20 * HashList - super-quick list manager
25 #include <WINNT/hashlist.h>
29 * DEFINITIONS ________________________________________________________________
33 #define iINVALID ((size_t)-1)
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:
39 #define cREALLOC_OBJECTS 8192
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
45 #define cREALLOC_KEYS 4
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):
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)
67 #define MIN_TABLE_SIZE(_cObjects) ((_cObjects) / 30)
68 #define TARGET_TABLE_SIZE(_cObjects) ((_cObjects) / 10)
70 #define MIN_TABLE_SIZE_FOR_KEY(_cObjects) ((_cObjects) / 23)
71 #define TARGET_TABLE_SIZE_FOR_KEY(_cObjects) ((_cObjects) / 5)
75 * REALLOC ____________________________________________________________________
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)
88 if (cReq <= *pcTarget)
91 if ((cNew = cInc * ((cReq + cInc-1) / cInc)) <= 0)
94 if ((pNew = (LPVOID)GlobalAlloc (GMEM_FIXED, cbElement * cNew)) == NULL)
98 memset (pNew, 0x00, cbElement * cNew);
101 memcpy (pNew, *ppTarget, cbElement * (*pcTarget));
102 memset (&((char*)pNew)[ cbElement * (*pcTarget) ], 0x00, cbElement * (cNew - *pcTarget));
103 GlobalFree ((HGLOBAL)*ppTarget);
113 * EXPANDARRAY CLASS __________________________________________________________
117 #define cEXPANDARRAYHEAPELEMENTS 1024
118 #define cREALLOC_EXPANDARRAYHEAPS 16
120 EXPANDARRAY::EXPANDARRAY (size_t cbElement, size_t cElementsPerHeap)
122 if ((m_cbElement = cbElement) == 0)
123 m_cbElement = sizeof(DWORD);
124 if ((m_cElementsPerHeap = cElementsPerHeap) == 0)
125 m_cElementsPerHeap = cEXPANDARRAYHEAPELEMENTS;
131 EXPANDARRAY::~EXPANDARRAY (void)
135 for (size_t ii = 0; ii < m_cHeaps; ++ii)
138 GlobalFree ((HGLOBAL)(m_aHeaps[ ii ]));
140 GlobalFree ((HGLOBAL)m_aHeaps);
144 PVOID EXPANDARRAY::GetAt (size_t iElement)
146 size_t iHeap = iElement / m_cElementsPerHeap;
147 size_t iIndex = iElement % m_cElementsPerHeap;
148 if ((iHeap >= m_cHeaps) || (!m_aHeaps[iHeap]))
152 pElement = &((PBYTE)m_aHeaps[ iHeap ]->aElements)[ iIndex * m_cbElement ];
156 PVOID EXPANDARRAY::SetAt (size_t iElement, PVOID pData)
158 size_t iHeap = iElement / m_cElementsPerHeap;
159 size_t iIndex = iElement % m_cElementsPerHeap;
161 if (!REALLOC (m_aHeaps, m_cHeaps, 1+iHeap, cREALLOC_EXPANDARRAYHEAPS))
164 if (!m_aHeaps[ iHeap ])
166 size_t cbHeap = sizeof(EXPANDARRAYHEAP) + (m_cElementsPerHeap * m_cbElement);
167 if ((m_aHeaps[ iHeap ] = (LPEXPANDARRAYHEAP)GlobalAlloc (GMEM_FIXED, cbHeap)) == NULL)
169 memset (m_aHeaps[ iHeap ], 0x00, cbHeap);
170 m_aHeaps[ iHeap ]->aElements = ((PBYTE)m_aHeaps[ iHeap ]) + sizeof(EXPANDARRAYHEAP);
174 pElement = &((PBYTE)m_aHeaps[ iHeap ]->aElements)[ iIndex * m_cbElement ];
176 memcpy (pElement, pData, m_cbElement);
182 * HASHLIST CLASS _____________________________________________________________
186 #define GetEntry(_pArray,_iEntry) ((LPHASHLISTENTRY)((_pArray)->GetAt(_iEntry)))
188 HASHLIST::HASHLIST (void)
190 InitializeCriticalSection (&m_cs);
197 m_aObjects = new EXPANDARRAY (sizeof(HASHLISTENTRY), cREALLOC_OBJECTS);
203 m_pKeyIndex = new HASHLISTKEY (this, TEXT("Index"), HASHLIST::KeyIndex_CompareObjectData, HASHLIST::KeyIndex_HashObject, HASHLIST::KeyIndex_HashData, cTABLESIZE_DEFAULT);
209 HASHLIST::~HASHLIST (void)
213 if (m_apKeys != NULL)
215 for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
217 if (m_apKeys[ iKey ] != NULL)
218 delete m_apKeys[ iKey ];
220 GlobalFree ((HGLOBAL)m_apKeys);
228 if (m_aObjects != NULL)
234 DeleteCriticalSection (&m_cs);
238 void HASHLIST::Enter (void)
240 EnterCriticalSection (m_pcs);
244 void HASHLIST::Leave (void)
246 LeaveCriticalSection (m_pcs);
250 void HASHLIST::SetCriticalSection (CRITICAL_SECTION *pcs)
252 m_pcs = (pcs == NULL) ? &m_cs : pcs;
256 BOOL HASHLIST::AddUnique (PVOID pEntryToAdd, LPHASHLISTKEY pKey)
258 if ( ((pKey == NULL) && (fIsInList (pEntryToAdd))) ||
259 ((pKey != NULL) && (pKey->fIsInList (pEntryToAdd))) )
264 return Add (pEntryToAdd);
268 BOOL HASHLIST::Add (PVOID pEntryToAdd)
275 size_t iObject = m_iNextFree;
277 if ((GetEntry(m_aObjects,iObject) && (GetEntry(m_aObjects,iObject)->pObject)))
279 for (iObject = 0; iObject < m_cObjectsMax; ++iObject)
281 if ( (!GetEntry(m_aObjects,iObject)) || (!GetEntry(m_aObjects,iObject)->pObject) )
286 m_iNextFree = 1+iObject;
289 Entry.pObject = pEntryToAdd;
290 Entry.iNext = iINVALID;
291 Entry.iPrevious = m_iLast;
292 m_aObjects->SetAt (iObject, &Entry);
294 if (m_iLast != iINVALID)
296 LPHASHLISTENTRY pEntry;
297 if ((pEntry = GetEntry(m_aObjects,m_iLast)) != NULL)
298 pEntry->iNext = iObject;
302 if (m_iFirst == iINVALID)
305 m_pKeyIndex->Add (iObject, (PVOID)(iObject+1));
307 for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
309 if (m_apKeys[ iKey ] == NULL)
311 m_apKeys[ iKey ]->Add (iObject, pEntryToAdd);
315 m_cObjectsMax = max (m_cObjectsMax, m_cObjects);
324 void HASHLIST::Remove (PVOID pEntryToRemove)
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:
336 // for (size_t iObject = 0; iObject < m_cObjectsMax; ++iObject)
338 // if (m_aObjects[ iObject ].pObject == pEntryToRemove)
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
349 size_t iObject = iINVALID;
352 if ((pFind = m_pKeyIndex->GetFirstObject (pEntryToRemove)) != NULL)
353 iObject = *(size_t *)&pFind -1;
355 // Now remove the object.
357 if (iObject != iINVALID)
359 LPHASHLISTENTRY pEntry;
360 if ((pEntry = GetEntry(m_aObjects,iObject)) != NULL)
362 pEntry->pObject = NULL;
364 if (pEntry->iPrevious != iINVALID)
366 LPHASHLISTENTRY pPrevious;
367 if ((pPrevious = GetEntry(m_aObjects,pEntry->iPrevious)) != NULL)
368 pPrevious->iNext = pEntry->iNext;
370 if (pEntry->iNext != iINVALID)
372 LPHASHLISTENTRY pNext;
373 if ((pNext = GetEntry(m_aObjects,pEntry->iNext)) != NULL)
374 pNext->iPrevious = pEntry->iPrevious;
377 if (m_iLast == iObject)
378 m_iLast = pEntry->iPrevious;
379 if (m_iFirst == iObject)
380 m_iFirst = pEntry->iNext;
382 for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
384 if (m_apKeys[ iKey ] == NULL)
386 m_apKeys[ iKey ]->Remove (iObject);
389 m_pKeyIndex->Remove (iObject);
399 BOOL HASHLIST::Update (PVOID pEntryToUpdate)
405 if ((pFind = m_pKeyIndex->GetFirstObject (pEntryToUpdate)) == NULL)
409 size_t iObject = *(size_t *)&pFind -1;
411 for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
413 if (m_apKeys[ iKey ] == NULL)
416 m_apKeys[ iKey ]->Remove (iObject);
417 m_apKeys[ iKey ]->Add (iObject, pEntryToUpdate);
426 BOOL HASHLIST::fIsInList (PVOID pEntry)
429 if ((pFind = m_pKeyIndex->GetFirstObject (pEntry)) == NULL)
435 LPHASHLISTKEY HASHLIST::CreateKey (LPCTSTR pszKeyName, LPHASHFUNC_COMPAREOBJECTDATA fnCompareObjectData, LPHASHFUNC_HASHOBJECT fnHashObject, LPHASHFUNC_HASHDATA fnHashData, size_t cTableSize)
437 LPHASHLISTKEY pKey = NULL;
440 for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
442 if (m_apKeys[ iKey ] == NULL)
445 if (REALLOC (m_apKeys, m_cpKeys, 1+iKey, cREALLOC_KEYS))
447 m_apKeys[ iKey ] = new HASHLISTKEY (this, pszKeyName, fnCompareObjectData, fnHashObject, fnHashData, cTableSize);
448 pKey = m_apKeys[ iKey ];
450 if (MIN_TABLE_SIZE(m_cObjectsMax) > pKey->m_cBuckets)
454 else for (size_t iObject = 0; iObject < m_cObjectsMax; ++iObject)
456 LPHASHLISTENTRY pEntry;
457 if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
459 if (pEntry->pObject != NULL)
460 m_apKeys[ iKey ]->Add (iObject, pEntry->pObject);
469 LPHASHLISTKEY HASHLIST::FindKey (LPCTSTR pszKeyName)
471 LPHASHLISTKEY pKey = NULL;
474 for (size_t iKey = 0; !pKey && (iKey < m_cpKeys); ++iKey)
476 if (m_apKeys[ iKey ] == NULL)
478 if (!lstrcmpi (m_apKeys[ iKey ]->m_szKeyName, pszKeyName))
479 pKey = m_apKeys[ iKey ];
487 void HASHLIST::RemoveKey (LPHASHLISTKEY pKey)
491 for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
493 if (m_apKeys[ iKey ] == pKey)
495 delete m_apKeys[ iKey ];
496 m_apKeys[ iKey ] = NULL;
505 LPENUM HASHLIST::FindFirst (void)
510 if (m_iFirst != iINVALID)
511 pEnum = New2 (ENUMERATION,(this, m_iFirst));
518 LPENUM HASHLIST::FindLast (void)
523 if (m_iLast != iINVALID)
524 pEnum = New2 (ENUMERATION,(this, m_iLast));
531 PVOID HASHLIST::GetFirstObject (void)
533 PVOID pObject = NULL;
536 if (m_iFirst != iINVALID)
537 pObject = GetEntry(m_aObjects,m_iFirst)->pObject;
544 PVOID HASHLIST::GetLastObject (void)
546 PVOID pObject = NULL;
549 if (m_iLast != iINVALID)
550 pObject = GetEntry(m_aObjects,m_iLast)->pObject;
557 size_t HASHLIST::GetCount (void)
563 BOOL CALLBACK HASHLIST::KeyIndex_CompareObjectData (LPHASHLISTKEY pKey, PVOID pObject, PVOID pData)
565 size_t iIndex = (size_t)pObject -1;
566 LPHASHLIST pList = pKey->GetHashList();
567 return (GetEntry(pList->m_aObjects,iIndex)->pObject == pData) ? TRUE : FALSE;
571 HASHVALUE CALLBACK HASHLIST::KeyIndex_HashObject (LPHASHLISTKEY pKey, PVOID pObject)
573 size_t iIndex = (size_t)pObject -1;
574 LPHASHLIST pList = pKey->GetHashList();
575 return KeyIndex_HashData (pKey, GetEntry(pList->m_aObjects,iIndex)->pObject);
579 HASHVALUE CALLBACK HASHLIST::KeyIndex_HashData (LPHASHLISTKEY pKey, PVOID pData)
581 return ((DWORD)pData) >> 4; // The "data" is the object's address.
586 * HASHLISTKEY CLASS _____________________________________________________________
590 HASHLISTKEY::HASHLISTKEY (LPHASHLIST pList, LPCTSTR pszKeyName, LPHASHFUNC_COMPAREOBJECTDATA fnCompareObjectData, LPHASHFUNC_HASHOBJECT fnHashObject, LPHASHFUNC_HASHDATA fnHashData, size_t cTableSize)
592 m_aObjects = new EXPANDARRAY (sizeof(HASHLISTENTRY), cREALLOC_OBJECTS);
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)
598 m_aBuckets[ iBucket ].iFirst = iINVALID;
599 m_aBuckets[ iBucket ].iLast = iINVALID;
603 lstrcpy (m_szKeyName, pszKeyName);
604 m_fnCompareObjectData = fnCompareObjectData;
605 m_fnHashObject = fnHashObject;
606 m_fnHashData = fnHashData;
610 HASHLISTKEY::~HASHLISTKEY (void)
614 for (size_t iObject = 0; iObject < m_pList->m_cObjectsMax; ++iObject)
616 if (!GetEntry(m_aObjects,iObject))
618 if (!GetEntry(m_aObjects,iObject)->pObject)
626 GlobalFree ((HGLOBAL)m_aBuckets);
632 LPHASHLIST HASHLISTKEY::GetHashList (void)
638 BOOL HASHLISTKEY::CompareObjectData (PVOID pObject, PVOID pData)
640 return (*m_fnCompareObjectData)(this, pObject, pData);
643 HASHVALUE HASHLISTKEY::HashObject (PVOID pObject)
645 return ((*m_fnHashObject)(this, pObject)) % m_cBuckets;
648 HASHVALUE HASHLISTKEY::HashData (PVOID pData)
650 return ((*m_fnHashData)(this, pData)) % m_cBuckets;
654 LPENUM HASHLISTKEY::FindFirst (PVOID pData)
659 HASHVALUE hvSearch = HashData (pData);
662 if ((iObject = m_aBuckets[ hvSearch ].iFirst) != iINVALID)
664 LPHASHLISTENTRY pEntry;
666 if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
668 if (CompareObjectData (pEntry->pObject, pData))
670 pEnum = New2 (ENUMERATION,(m_pList, iObject, this, pData));
673 } while ((iObject = pEntry->iNext) != iINVALID);
681 LPENUM HASHLISTKEY::FindLast (PVOID pData)
686 HASHVALUE hvSearch = HashData (pData);
689 if ((iObject = m_aBuckets[ hvSearch ].iLast) != iINVALID)
691 LPHASHLISTENTRY pEntry;
693 if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
695 if (CompareObjectData (pEntry->pObject, pData))
697 pEnum = New2 (ENUMERATION,(m_pList, iObject, this, pData));
700 } while ((iObject = pEntry->iPrevious) != iINVALID);
708 PVOID HASHLISTKEY::GetFirstObject (PVOID pData)
710 PVOID pObject = NULL;
713 HASHVALUE hvSearch = HashData (pData);
716 if ((iObject = m_aBuckets[ hvSearch ].iFirst) != iINVALID)
718 LPHASHLISTENTRY pEntry;
720 if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
722 if (CompareObjectData (pEntry->pObject, pData))
724 pObject = pEntry->pObject;
727 } while ((iObject = pEntry->iNext) != iINVALID);
735 PVOID HASHLISTKEY::GetLastObject (PVOID pData)
737 PVOID pObject = NULL;
740 HASHVALUE hvSearch = HashData (pData);
743 if ((iObject = m_aBuckets[ hvSearch ].iLast) != iINVALID)
745 LPHASHLISTENTRY pEntry;
747 if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
749 if (CompareObjectData (pEntry->pObject, pData))
751 pObject = pEntry->pObject;
754 } while ((iObject = pEntry->iPrevious) != iINVALID);
762 BOOL HASHLISTKEY::fIsInList (PVOID pEntry)
765 if ((pFind = GetFirstObject (pEntry)) == NULL)
771 void HASHLISTKEY::Add (size_t iObject, PVOID pObject)
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)) )
782 HASHVALUE hv = HashObject (pObject);
783 struct HASHBUCKET *pBucket = &m_aBuckets[ hv ];
786 Entry.pObject = pObject;
788 Entry.iNext = iINVALID;
789 Entry.iPrevious = pBucket->iLast;
790 m_aObjects->SetAt (iObject, &Entry);
792 pBucket->iLast = iObject;
794 if (Entry.iPrevious != iINVALID)
796 LPHASHLISTENTRY pPrevious;
797 if ((pPrevious = GetEntry(m_aObjects,Entry.iPrevious)) != NULL)
798 pPrevious->iNext = iObject;
801 if (pBucket->iFirst == iINVALID)
802 pBucket->iFirst = iObject;
809 void HASHLISTKEY::Remove (size_t iObject)
813 LPHASHLISTENTRY pEntry;
814 if ((pEntry = GetEntry(m_aObjects,iObject)) != NULL)
816 pEntry->pObject = NULL;
818 if (pEntry->iPrevious != iINVALID)
820 LPHASHLISTENTRY pPrevious;
821 if ((pPrevious = GetEntry(m_aObjects,pEntry->iPrevious)) != NULL)
822 pPrevious->iNext = pEntry->iNext;
825 if (pEntry->iNext != iINVALID)
827 LPHASHLISTENTRY pNext;
828 if ((pNext = GetEntry(m_aObjects,pEntry->iNext)) != NULL)
829 pNext->iPrevious = pEntry->iPrevious;
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;
842 void HASHLISTKEY::Resize (void)
844 if (this == m_pList->m_pKeyIndex)
846 REALLOC (m_aBuckets, m_cBuckets, TARGET_TABLE_SIZE_FOR_KEY(m_pList->m_cObjectsMax), 1);
850 REALLOC (m_aBuckets, m_cBuckets, TARGET_TABLE_SIZE(m_pList->m_cObjectsMax), 1);
853 for (size_t iBucket = 0; iBucket < m_cBuckets; ++iBucket)
855 m_aBuckets[ iBucket ].iFirst = iINVALID;
856 m_aBuckets[ iBucket ].iLast = iINVALID;
859 for (size_t iObject = 0; ; ++iObject)
861 LPHASHLISTENTRY pEntry;
862 if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
864 pEntry->pObject = NULL;
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.
871 if (this == m_pList->m_pKeyIndex)
873 for (iObject = 0; ; ++iObject)
875 LPHASHLISTENTRY pEntry;
876 if ((pEntry = GetEntry(m_pList->m_aObjects,iObject)) == NULL)
878 if (pEntry->pObject != NULL)
879 Add (iObject, (PVOID)(iObject+1));
882 else // normal, user-defined key
884 for (iObject = 0; ; ++iObject)
886 LPHASHLISTENTRY pEntry;
887 if ((pEntry = GetEntry(m_pList->m_aObjects,iObject)) == NULL)
889 if (pEntry->pObject != NULL)
890 Add (iObject, pEntry->pObject);
896 LPHASHLISTKEYDEBUGINFO HASHLISTKEY::GetDebugInfo (void)
900 LPHASHLISTKEYDEBUGINFO pInfo = new HASHLISTKEYDEBUGINFO;
901 memset (pInfo, 0x00, sizeof(HASHLISTKEYDEBUGINFO));
903 // Find out how full each bucket is.
905 REALLOC (pInfo->aBuckets, pInfo->cBuckets, m_cBuckets, 1);
907 for (size_t iBucket = 0; iBucket < pInfo->cBuckets; ++iBucket)
909 for (size_t iObject = m_aBuckets[ iBucket ].iFirst;
911 iObject = GetEntry(m_aObjects,iObject)->iNext)
913 (pInfo->aBuckets[ iBucket ])++;
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
926 if (pInfo->cBuckets == 0)
928 pInfo->perEffective = 100;
932 // We want an accurate count of objects, not the over-allocated
933 // count given by m_cObjectsMax.
936 for (iBucket = 0; iBucket < pInfo->cBuckets; ++iBucket)
937 cObjects += pInfo->aBuckets[ iBucket ];
941 pInfo->perEffective = 100;
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.
950 size_t cPerfectLength = (cObjects / pInfo->cBuckets) + 1;
952 size_t cObjectsInPlace = 0;
953 for (iBucket = 0; iBucket < pInfo->cBuckets; ++iBucket)
954 cObjectsInPlace += min( pInfo->aBuckets[ iBucket ], cPerfectLength );
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.
961 pInfo->perEffective = (WORD)(cObjectsInPlace * 100 / cObjects);
970 void HASHLISTKEY::FreeDebugInfo (LPHASHLISTKEYDEBUGINFO pInfo)
973 GlobalFree ((HGLOBAL)(pInfo->aBuckets));
978 * ENUMERATION CLASS _____________________________________________________________
982 ENUMERATION::ENUMERATION (LPHASHLIST pList, size_t iObject, LPHASHLISTKEY pKey, PVOID pData)
989 PrepareWalk(); // finds m_iPrevious and m_iNext
995 ENUMERATION::~ENUMERATION (void)
1001 PVOID ENUMERATION::GetObject (void)
1003 return GetEntry(m_pList->m_aObjects,m_iObject)->pObject;
1007 LPENUMERATION ENUMERATION::FindNext (void)
1011 m_iObject = m_iNext;
1014 if (m_iObject == iINVALID)
1020 if (m_pKey->CompareObjectData (GetEntry(m_pList->m_aObjects,m_iObject)->pObject, m_pData))
1029 LPENUMERATION ENUMERATION::FindPrevious (void)
1033 m_iObject = m_iPrevious;
1036 if (m_iObject == iINVALID)
1042 if (m_pKey->CompareObjectData (GetEntry(m_pList->m_aObjects,m_iObject)->pObject, m_pData))
1051 void ENUMERATION::PrepareWalk (void)
1053 if (m_iObject == iINVALID)
1055 m_iPrevious = iINVALID;
1058 else if (m_pKey == NULL)
1060 m_iPrevious = GetEntry(m_pList->m_aObjects,m_iObject)->iPrevious;
1061 m_iNext = GetEntry(m_pList->m_aObjects,m_iObject)->iNext;
1065 m_iPrevious = GetEntry(m_pKey->m_aObjects,m_iObject)->iPrevious;
1066 m_iNext = GetEntry(m_pKey->m_aObjects,m_iObject)->iNext;
1072 * GENERAL-PURPOSE ____________________________________________________________
1076 HASHVALUE HashString (LPCTSTR pszString)
1079 return HashUnicodeString (pszString);
1081 return HashAnsiString (pszString);
1085 HASHVALUE HashAnsiString (LPCSTR pszStringA)
1089 for (size_t cch = lstrlenA(pszStringA); cch >= 4; pszStringA += 4, cch -= 4)
1090 hv += *(DWORD *)pszStringA;
1092 for (; cch; pszStringA++, cch--)
1098 HASHVALUE HashUnicodeString (LPWSTR pszStringW)
1102 for (size_t cch = lstrlenW(pszStringW); cch >= 2; pszStringW += 2, cch -= 2)
1104 hv += *(DWORD *)pszStringW; // since HIBYTE(*psz) is usually zero,
1105 hv = (hv >> 24) | (hv << 8); // rotate {hv} high-ward by 8 bits
1108 for (; cch; pszStringW++, cch--)