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>
19 * HashList - super-quick list manager
24 #include <WINNT/hashlist.h>
28 * DEFINITIONS ________________________________________________________________
32 #define iINVALID ((size_t)-1)
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:
38 #define cREALLOC_OBJECTS 8192
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
44 #define cREALLOC_KEYS 4
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):
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)
66 #define MIN_TABLE_SIZE(_cObjects) ((_cObjects) / 30)
67 #define TARGET_TABLE_SIZE(_cObjects) ((_cObjects) / 10)
69 #define MIN_TABLE_SIZE_FOR_KEY(_cObjects) ((_cObjects) / 23)
70 #define TARGET_TABLE_SIZE_FOR_KEY(_cObjects) ((_cObjects) / 5)
74 * REALLOC ____________________________________________________________________
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)
87 if (cReq <= *pcTarget)
90 if ((cNew = cInc * ((cReq + cInc-1) / cInc)) <= 0)
93 if ((pNew = (LPVOID)GlobalAlloc (GMEM_FIXED, cbElement * cNew)) == NULL)
97 memset (pNew, 0x00, cbElement * cNew);
100 memcpy (pNew, *ppTarget, cbElement * (*pcTarget));
101 memset (&((char*)pNew)[ cbElement * (*pcTarget) ], 0x00, cbElement * (cNew - *pcTarget));
102 GlobalFree ((HGLOBAL)*ppTarget);
112 * EXPANDARRAY CLASS __________________________________________________________
116 #define cEXPANDARRAYHEAPELEMENTS 1024
117 #define cREALLOC_EXPANDARRAYHEAPS 16
119 EXPANDARRAY::EXPANDARRAY (size_t cbElement, size_t cElementsPerHeap)
121 if ((m_cbElement = cbElement) == 0)
122 m_cbElement = sizeof(DWORD);
123 if ((m_cElementsPerHeap = cElementsPerHeap) == 0)
124 m_cElementsPerHeap = cEXPANDARRAYHEAPELEMENTS;
130 EXPANDARRAY::~EXPANDARRAY (void)
134 for (size_t ii = 0; ii < m_cHeaps; ++ii)
137 GlobalFree ((HGLOBAL)(m_aHeaps[ ii ]));
139 GlobalFree ((HGLOBAL)m_aHeaps);
143 PVOID EXPANDARRAY::GetAt (size_t iElement)
145 size_t iHeap = iElement / m_cElementsPerHeap;
146 size_t iIndex = iElement % m_cElementsPerHeap;
147 if ((iHeap >= m_cHeaps) || (!m_aHeaps[iHeap]))
151 pElement = &((PBYTE)m_aHeaps[ iHeap ]->aElements)[ iIndex * m_cbElement ];
155 PVOID EXPANDARRAY::SetAt (size_t iElement, PVOID pData)
157 size_t iHeap = iElement / m_cElementsPerHeap;
158 size_t iIndex = iElement % m_cElementsPerHeap;
160 if (!REALLOC (m_aHeaps, m_cHeaps, 1+iHeap, cREALLOC_EXPANDARRAYHEAPS))
163 if (!m_aHeaps[ iHeap ])
165 size_t cbHeap = sizeof(EXPANDARRAYHEAP) + (m_cElementsPerHeap * m_cbElement);
166 if ((m_aHeaps[ iHeap ] = (LPEXPANDARRAYHEAP)GlobalAlloc (GMEM_FIXED, cbHeap)) == NULL)
168 memset (m_aHeaps[ iHeap ], 0x00, cbHeap);
169 m_aHeaps[ iHeap ]->aElements = ((PBYTE)m_aHeaps[ iHeap ]) + sizeof(EXPANDARRAYHEAP);
173 pElement = &((PBYTE)m_aHeaps[ iHeap ]->aElements)[ iIndex * m_cbElement ];
175 memcpy (pElement, pData, m_cbElement);
181 * HASHLIST CLASS _____________________________________________________________
185 #define GetEntry(_pArray,_iEntry) ((LPHASHLISTENTRY)((_pArray)->GetAt(_iEntry)))
187 HASHLIST::HASHLIST (void)
189 InitializeCriticalSection (&m_cs);
196 m_aObjects = new EXPANDARRAY (sizeof(HASHLISTENTRY), cREALLOC_OBJECTS);
202 m_pKeyIndex = new HASHLISTKEY (this, TEXT("Index"), HASHLIST::KeyIndex_CompareObjectData, HASHLIST::KeyIndex_HashObject, HASHLIST::KeyIndex_HashData, cTABLESIZE_DEFAULT);
208 HASHLIST::~HASHLIST (void)
212 if (m_apKeys != NULL)
214 for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
216 if (m_apKeys[ iKey ] != NULL)
217 delete m_apKeys[ iKey ];
219 GlobalFree ((HGLOBAL)m_apKeys);
227 if (m_aObjects != NULL)
233 DeleteCriticalSection (&m_cs);
237 void HASHLIST::Enter (void)
239 EnterCriticalSection (m_pcs);
243 void HASHLIST::Leave (void)
245 LeaveCriticalSection (m_pcs);
249 void HASHLIST::SetCriticalSection (CRITICAL_SECTION *pcs)
251 m_pcs = (pcs == NULL) ? &m_cs : pcs;
255 BOOL HASHLIST::AddUnique (PVOID pEntryToAdd, LPHASHLISTKEY pKey)
257 if ( ((pKey == NULL) && (fIsInList (pEntryToAdd))) ||
258 ((pKey != NULL) && (pKey->fIsInList (pEntryToAdd))) )
263 return Add (pEntryToAdd);
267 BOOL HASHLIST::Add (PVOID pEntryToAdd)
274 size_t iObject = m_iNextFree;
276 if ((GetEntry(m_aObjects,iObject) && (GetEntry(m_aObjects,iObject)->pObject)))
278 for (iObject = 0; iObject < m_cObjectsMax; ++iObject)
280 if ( (!GetEntry(m_aObjects,iObject)) || (!GetEntry(m_aObjects,iObject)->pObject) )
285 m_iNextFree = 1+iObject;
288 Entry.pObject = pEntryToAdd;
289 Entry.iNext = iINVALID;
290 Entry.iPrevious = m_iLast;
291 m_aObjects->SetAt (iObject, &Entry);
293 if (m_iLast != iINVALID)
295 LPHASHLISTENTRY pEntry;
296 if ((pEntry = GetEntry(m_aObjects,m_iLast)) != NULL)
297 pEntry->iNext = iObject;
301 if (m_iFirst == iINVALID)
304 m_pKeyIndex->Add (iObject, (PVOID)(iObject+1));
306 for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
308 if (m_apKeys[ iKey ] == NULL)
310 m_apKeys[ iKey ]->Add (iObject, pEntryToAdd);
314 m_cObjectsMax = max (m_cObjectsMax, m_cObjects);
323 void HASHLIST::Remove (PVOID pEntryToRemove)
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:
335 // for (size_t iObject = 0; iObject < m_cObjectsMax; ++iObject)
337 // if (m_aObjects[ iObject ].pObject == pEntryToRemove)
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
348 size_t iObject = iINVALID;
351 if ((pFind = m_pKeyIndex->GetFirstObject (pEntryToRemove)) != NULL)
352 iObject = *(size_t *)&pFind -1;
354 // Now remove the object.
356 if (iObject != iINVALID)
358 LPHASHLISTENTRY pEntry;
359 if ((pEntry = GetEntry(m_aObjects,iObject)) != NULL)
361 pEntry->pObject = NULL;
363 if (pEntry->iPrevious != iINVALID)
365 LPHASHLISTENTRY pPrevious;
366 if ((pPrevious = GetEntry(m_aObjects,pEntry->iPrevious)) != NULL)
367 pPrevious->iNext = pEntry->iNext;
369 if (pEntry->iNext != iINVALID)
371 LPHASHLISTENTRY pNext;
372 if ((pNext = GetEntry(m_aObjects,pEntry->iNext)) != NULL)
373 pNext->iPrevious = pEntry->iPrevious;
376 if (m_iLast == iObject)
377 m_iLast = pEntry->iPrevious;
378 if (m_iFirst == iObject)
379 m_iFirst = pEntry->iNext;
381 for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
383 if (m_apKeys[ iKey ] == NULL)
385 m_apKeys[ iKey ]->Remove (iObject);
388 m_pKeyIndex->Remove (iObject);
398 BOOL HASHLIST::Update (PVOID pEntryToUpdate)
404 if ((pFind = m_pKeyIndex->GetFirstObject (pEntryToUpdate)) == NULL)
408 size_t iObject = *(size_t *)&pFind -1;
410 for (size_t iKey = 0; iKey < m_cpKeys; ++iKey)
412 if (m_apKeys[ iKey ] == NULL)
415 m_apKeys[ iKey ]->Remove (iObject);
416 m_apKeys[ iKey ]->Add (iObject, pEntryToUpdate);
425 BOOL HASHLIST::fIsInList (PVOID pEntry)
428 if ((pFind = m_pKeyIndex->GetFirstObject (pEntry)) == NULL)
434 LPHASHLISTKEY HASHLIST::CreateKey (LPCTSTR pszKeyName, LPHASHFUNC_COMPAREOBJECTDATA fnCompareObjectData, LPHASHFUNC_HASHOBJECT fnHashObject, LPHASHFUNC_HASHDATA fnHashData, size_t cTableSize)
436 LPHASHLISTKEY pKey = NULL;
440 for (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;
860 for (iObject = 0; ; ++iObject)
862 LPHASHLISTENTRY pEntry;
863 if ((pEntry = GetEntry(m_aObjects,iObject)) == NULL)
865 pEntry->pObject = NULL;
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.
872 if (this == m_pList->m_pKeyIndex)
874 for (iObject = 0; ; ++iObject)
876 LPHASHLISTENTRY pEntry;
877 if ((pEntry = GetEntry(m_pList->m_aObjects,iObject)) == NULL)
879 if (pEntry->pObject != NULL)
880 Add (iObject, (PVOID)(iObject+1));
883 else // normal, user-defined key
885 for (iObject = 0; ; ++iObject)
887 LPHASHLISTENTRY pEntry;
888 if ((pEntry = GetEntry(m_pList->m_aObjects,iObject)) == NULL)
890 if (pEntry->pObject != NULL)
891 Add (iObject, pEntry->pObject);
897 LPHASHLISTKEYDEBUGINFO HASHLISTKEY::GetDebugInfo (void)
901 LPHASHLISTKEYDEBUGINFO pInfo = new HASHLISTKEYDEBUGINFO;
902 memset (pInfo, 0x00, sizeof(HASHLISTKEYDEBUGINFO));
904 // Find out how full each bucket is.
906 REALLOC (pInfo->aBuckets, pInfo->cBuckets, m_cBuckets, 1);
909 for (iBucket = 0; iBucket < pInfo->cBuckets; ++iBucket)
911 for (size_t iObject = m_aBuckets[ iBucket ].iFirst;
913 iObject = GetEntry(m_aObjects,iObject)->iNext)
915 (pInfo->aBuckets[ iBucket ])++;
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
928 if (pInfo->cBuckets == 0)
930 pInfo->perEffective = 100;
934 // We want an accurate count of objects, not the over-allocated
935 // count given by m_cObjectsMax.
938 for (iBucket = 0; iBucket < pInfo->cBuckets; ++iBucket)
939 cObjects += pInfo->aBuckets[ iBucket ];
943 pInfo->perEffective = 100;
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.
952 size_t cPerfectLength = (cObjects / pInfo->cBuckets) + 1;
954 size_t cObjectsInPlace = 0;
955 for (iBucket = 0; iBucket < pInfo->cBuckets; ++iBucket)
956 cObjectsInPlace += min( pInfo->aBuckets[ iBucket ], cPerfectLength );
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.
963 pInfo->perEffective = (WORD)(cObjectsInPlace * 100 / cObjects);
972 void HASHLISTKEY::FreeDebugInfo (LPHASHLISTKEYDEBUGINFO pInfo)
975 GlobalFree ((HGLOBAL)(pInfo->aBuckets));
980 * ENUMERATION CLASS _____________________________________________________________
984 ENUMERATION::ENUMERATION (LPHASHLIST pList, size_t iObject, LPHASHLISTKEY pKey, PVOID pData)
991 PrepareWalk(); // finds m_iPrevious and m_iNext
997 ENUMERATION::~ENUMERATION (void)
1003 PVOID ENUMERATION::GetObject (void)
1005 return GetEntry(m_pList->m_aObjects,m_iObject)->pObject;
1009 LPENUMERATION ENUMERATION::FindNext (void)
1013 m_iObject = m_iNext;
1016 if (m_iObject == iINVALID)
1022 if (m_pKey->CompareObjectData (GetEntry(m_pList->m_aObjects,m_iObject)->pObject, m_pData))
1031 LPENUMERATION ENUMERATION::FindPrevious (void)
1035 m_iObject = m_iPrevious;
1038 if (m_iObject == iINVALID)
1044 if (m_pKey->CompareObjectData (GetEntry(m_pList->m_aObjects,m_iObject)->pObject, m_pData))
1053 void ENUMERATION::PrepareWalk (void)
1055 if (m_iObject == iINVALID)
1057 m_iPrevious = iINVALID;
1060 else if (m_pKey == NULL)
1062 m_iPrevious = GetEntry(m_pList->m_aObjects,m_iObject)->iPrevious;
1063 m_iNext = GetEntry(m_pList->m_aObjects,m_iObject)->iNext;
1067 m_iPrevious = GetEntry(m_pKey->m_aObjects,m_iObject)->iPrevious;
1068 m_iNext = GetEntry(m_pKey->m_aObjects,m_iObject)->iNext;
1074 * GENERAL-PURPOSE ____________________________________________________________
1078 HASHVALUE HashString (LPCTSTR pszString)
1081 return HashUnicodeString (pszString);
1083 return HashAnsiString (pszString);
1087 HASHVALUE HashAnsiString (LPCSTR pszStringA)
1092 for (cch = lstrlenA(pszStringA); cch >= 4; pszStringA += 4, cch -= 4)
1093 hv += *(DWORD *)pszStringA;
1095 for (; cch; pszStringA++, cch--)
1101 HASHVALUE HashUnicodeString (LPWSTR pszStringW)
1106 for (cch = lstrlenW(pszStringW); cch >= 2; pszStringW += 2, cch -= 2)
1108 hv += *(DWORD *)pszStringW; // since HIBYTE(*psz) is usually zero,
1109 hv = (hv >> 24) | (hv << 8); // rotate {hv} high-ward by 8 bits
1112 for (; cch; pszStringW++, cch--)