1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
3 // See the LICENSE file in the project root for more information.
4 //*****************************************************************************
9 // This contains Collections C++ utility classes.
11 //*****************************************************************************
23 #ifndef DACCESS_COMPILE
25 //*****************************************************************************
26 // This is the second part of construction where we do all of the work that
27 // can fail. We also take the array of structs here because the calling class
28 // presumably needs to allocate it in its NewInit.
29 //*****************************************************************************
30 HRESULT CHashTable::NewInit( // Return status.
31 BYTE *pcEntries, // Array of structs we are managing.
32 ULONG iEntrySize) // Size of the entries.
40 _ASSERTE(iEntrySize >= sizeof(FREEHASHENTRY));
42 // Allocate the bucket chain array and init it.
43 if ((m_piBuckets = new (nothrow) ULONG [m_iBuckets]) == NULL)
44 return (OutOfMemory());
45 memset(m_piBuckets, 0xff, m_iBuckets * sizeof(ULONG));
47 // Save the array of structs we are managing.
48 m_pcEntries = (TADDR)pcEntries;
49 m_iEntrySize = iEntrySize;
53 //*****************************************************************************
54 // Add the struct at the specified index in m_pcEntries to the hash chains.
55 //*****************************************************************************
56 BYTE *CHashTable::Add( // New entry.
57 ULONG iHash, // Hash value of entry to add.
58 ULONG iIndex) // Index of struct in m_pcEntries.
66 HASHENTRY *psEntry; // The struct we are adding.
68 // Get a pointer to the entry we are adding.
69 psEntry = EntryPtr(iIndex);
71 // Compute the hash value for the entry.
74 _ASSERTE(m_piBuckets[iHash] != iIndex &&
75 (m_piBuckets[iHash] == UINT32_MAX || EntryPtr(m_piBuckets[iHash])->iPrev != iIndex));
78 psEntry->iPrev = UINT32_MAX;
79 psEntry->iNext = m_piBuckets[iHash];
81 // Link it into the hash chain.
82 if (m_piBuckets[iHash] != UINT32_MAX)
83 EntryPtr(m_piBuckets[iHash])->iPrev = iIndex;
84 m_piBuckets[iHash] = iIndex;
85 return ((BYTE *) psEntry);
88 //*****************************************************************************
89 // Delete the struct at the specified index in m_pcEntries from the hash chains.
90 //*****************************************************************************
91 void CHashTable::Delete(
92 ULONG iHash, // Hash value of entry to delete.
93 ULONG iIndex) // Index of struct in m_pcEntries.
97 HASHENTRY *psEntry; // Struct to delete.
99 // Get a pointer to the entry we are deleting.
100 psEntry = EntryPtr(iIndex);
101 Delete(iHash, psEntry);
104 //*****************************************************************************
105 // Delete the struct at the specified index in m_pcEntries from the hash chains.
106 //*****************************************************************************
107 void CHashTable::Delete(
108 ULONG iHash, // Hash value of entry to delete.
109 HASHENTRY *psEntry) // The struct to delete.
117 // Compute the hash value for the entry.
120 _ASSERTE(psEntry->iPrev != psEntry->iNext || psEntry->iPrev == UINT32_MAX);
122 // Fix the predecessor.
123 if (psEntry->iPrev == UINT32_MAX)
124 m_piBuckets[iHash] = psEntry->iNext;
126 EntryPtr(psEntry->iPrev)->iNext = psEntry->iNext;
128 // Fix the successor.
129 if (psEntry->iNext != UINT32_MAX)
130 EntryPtr(psEntry->iNext)->iPrev = psEntry->iPrev;
133 //*****************************************************************************
134 // The item at the specified index has been moved, update the previous and
136 //*****************************************************************************
137 void CHashTable::Move(
138 ULONG iHash, // Hash value for the item.
139 ULONG iNew) // New location.
147 HASHENTRY *psEntry; // The struct we are deleting.
149 psEntry = EntryPtr(iNew);
150 _ASSERTE(psEntry->iPrev != iNew && psEntry->iNext != iNew);
152 if (psEntry->iPrev != UINT32_MAX)
153 EntryPtr(psEntry->iPrev)->iNext = iNew;
155 m_piBuckets[iHash % m_iBuckets] = iNew;
156 if (psEntry->iNext != UINT32_MAX)
157 EntryPtr(psEntry->iNext)->iPrev = iNew;
160 #endif // !DACCESS_COMPILE
162 //*****************************************************************************
163 // Search the hash table for an entry with the specified key value.
164 //*****************************************************************************
165 BYTE *CHashTable::Find( // Index of struct in m_pcEntries.
166 ULONG iHash, // Hash value of the item.
167 SIZE_T key) // The key to match.
177 ULONG iNext; // Used to traverse the chains.
178 HASHENTRY *psEntry; // Used to traverse the chains.
180 // Start at the top of the chain.
181 iNext = m_piBuckets[iHash % m_iBuckets];
183 // Search until we hit the end.
189 while (iNext != UINT32_MAX)
192 psEntry = EntryPtr(iNext);
197 if (!Cmp(key, psEntry))
200 if (count > m_maxSearch)
204 return ((BYTE *) psEntry);
207 // Advance to the next item in the chain.
208 iNext = psEntry->iNext;
211 // We couldn't find it.
215 //*****************************************************************************
216 // Search the hash table for the next entry with the specified key value.
217 //*****************************************************************************
218 ULONG CHashTable::FindNext( // Index of struct in m_pcEntries.
219 SIZE_T key, // The key to match.
220 ULONG iIndex) // Index of previous match.
228 ULONG iNext; // Used to traverse the chains.
229 HASHENTRY *psEntry; // Used to traverse the chains.
231 // Start at the next entry in the chain.
232 iNext = EntryPtr(iIndex)->iNext;
234 // Search until we hit the end.
235 while (iNext != UINT32_MAX)
238 psEntry = EntryPtr(iNext);
239 if (!Cmp(key, psEntry))
242 // Advance to the next item in the chain.
243 iNext = psEntry->iNext;
246 // We couldn't find it.
250 //*****************************************************************************
251 // Returns the next entry in the list.
252 //*****************************************************************************
253 BYTE *CHashTable::FindNextEntry( // The next entry, or0 for end of list.
254 HASHFIND *psSrch) // Search object.
264 HASHENTRY *psEntry; // Used to traverse the chains.
268 // See if we already have one to use and if so, use it.
269 if (psSrch->iNext != UINT32_MAX)
271 psEntry = EntryPtr(psSrch->iNext);
272 psSrch->iNext = psEntry->iNext;
273 return ((BYTE *) psEntry);
276 // Advance to the next bucket.
277 if (psSrch->iBucket < m_iBuckets)
278 psSrch->iNext = m_piBuckets[psSrch->iBucket++];
283 // There were no more entries to be found.
287 #ifdef DACCESS_COMPILE
290 CHashTable::EnumMemoryRegions(CLRDataEnumMemoryFlags flags,
295 // This class may be embedded so do not enum 'this'.
296 DacEnumMemoryRegion(m_pcEntries,
297 (ULONG)numEntries * m_iEntrySize);
298 DacEnumMemoryRegion(dac_cast<TADDR>(m_piBuckets),
299 (ULONG)m_iBuckets * sizeof(ULONG));
302 #endif // #ifdef DACCESS_COMPILE
310 //*****************************************************************************
311 // Delete the given value. This will simply mark the entry as deleted (in
312 // order to keep the collision chain intact). There is an optimization that
313 // consecutive deleted entries leading up to a free entry are themselves freed
314 // to reduce collisions later on.
315 //*****************************************************************************
316 void CClosedHashBase::Delete(
317 void *pData) // Key value to delete.
327 // Find the item to delete.
328 if ((ptr = Find(pData)) == 0)
330 // You deleted something that wasn't there, why?
335 // For a perfect system, there are no collisions so it is free.
338 SetStatus(ptr, FREE);
340 // One less non free entry.
346 // Mark this entry deleted.
347 SetStatus(ptr, DELETED);
349 // If the next item is free, then we can go backwards freeing
350 // deleted entries which are no longer part of a chain. This isn't
351 // 100% great, but it will reduce collisions.
353 if ((pnext = ptr + m_iEntrySize) > EntryPtr(m_iSize - 1))
354 pnext = &m_rgData[0];
355 if (Status(pnext) != FREE)
358 // We can now free consecutive entries starting with the one
359 // we just deleted, up to the first non-deleted one.
360 while (Status(ptr) == DELETED)
363 SetStatus(ptr, FREE);
365 // One less non free entry.
368 // Check the one before it, handle wrap around.
369 if ((ptr -= m_iEntrySize) < &m_rgData[0])
370 ptr = EntryPtr(m_iSize - 1);
375 //*****************************************************************************
376 // Iterates over all active values, passing each one to pDeleteLoopFunc.
377 // If pDeleteLoopFunc returns TRUE, the entry is deleted. This is safer
378 // and faster than using FindNext() and Delete().
379 //*****************************************************************************
380 void CClosedHashBase::DeleteLoop(
381 DELETELOOPFUNC pDeleteLoopFunc, // Decides whether to delete item
382 void *pCustomizer) // Extra value passed to deletefunc.
397 for (i = 0; i < m_iSize; i++)
399 BYTE *pEntry = EntryPtr(i);
400 if (Status(pEntry) == USED)
402 if (pDeleteLoopFunc(pEntry, pCustomizer))
406 SetStatus(pEntry, FREE);
407 // One less non free entry.
412 SetStatus(pEntry, DELETED);
420 // Now free DELETED entries that are no longer part of a chain.
421 for (i = 0; i < m_iSize; i++)
423 if (Status(EntryPtr(i)) == FREE)
438 while (Status(EntryPtr(i)) == DELETED)
440 SetStatus(EntryPtr(i), FREE);
443 // One less non free entry.
452 while (Status(EntryPtr(i)) != FREE)
461 while (i != iFirstFree);
467 //*****************************************************************************
468 // Lookup a key value and return a pointer to the element if found.
469 //*****************************************************************************
470 BYTE *CClosedHashBase::Find( // The item if found, 0 if not.
471 void *pData) // The key to lookup.
479 unsigned int iHash; // Hash value for this data.
480 int iBucket; // Which bucke to start at.
481 int i; // Loop control.
484 if (!m_rgData || m_iCount == 0)
487 // Hash to the bucket.
489 iBucket = iHash % m_iBuckets;
491 // For a perfect table, the bucket is the correct one.
494 // If the value is there, it is the correct one.
495 if (Status(EntryPtr(iBucket)) != FREE)
496 return (EntryPtr(iBucket));
500 // Walk the bucket list looking for the item.
501 for (i=iBucket; Status(EntryPtr(i)) != FREE; )
503 // Don't look at deleted items.
504 if (Status(EntryPtr(i)) == DELETED)
506 // Handle wrap around.
513 if (Compare(pData, EntryPtr(i)) == 0)
514 return (EntryPtr(i));
516 // If we never collided while adding items, then there is
517 // no point in scanning any further.
521 // Handle wrap around.
530 //*****************************************************************************
531 // Look for an item in the table. If it isn't found, then create a new one and
533 //*****************************************************************************
534 BYTE *CClosedHashBase::FindOrAdd( // The item if found, 0 if not.
535 void *pData, // The key to lookup.
536 bool &bNew) // true if created.
544 unsigned int iHash; // Hash value for this data.
545 int iBucket; // Which bucke to start at.
546 int i; // Loop control.
548 // If we haven't allocated any memory, or it is too small, fix it.
549 if (!m_rgData || ((m_iCount + 1) > (m_iSize * 3 / 4) && !m_bPerfect))
555 // Assume we find it.
558 // Hash to the bucket.
560 iBucket = iHash % m_iBuckets;
562 // For a perfect table, the bucket is the correct one.
565 // If the value is there, it is the correct one.
566 if (Status(EntryPtr(iBucket)) != FREE)
567 return (EntryPtr(iBucket));
572 // Walk the bucket list looking for the item.
573 for (i=iBucket; Status(EntryPtr(i)) != FREE; )
575 // Don't look at deleted items.
576 if (Status(EntryPtr(i)) == DELETED)
578 // Handle wrap around.
585 if (Compare(pData, EntryPtr(i)) == 0)
586 return (EntryPtr(i));
588 // One more to count.
591 // Handle wrap around.
597 // We've found an open slot, use it.
598 _ASSERTE(Status(EntryPtr(i)) == FREE);
601 return (EntryPtr(i));
604 //*****************************************************************************
605 // This helper actually does the add for you.
606 //*****************************************************************************
607 BYTE *CClosedHashBase::DoAdd(void *pData, BYTE *rgData, int &iBuckets, int iSize,
608 int &iCollisions, int &iCount)
616 unsigned int iHash; // Hash value for this data.
617 int iBucket; // Which bucke to start at.
618 int i; // Loop control.
620 // Hash to the bucket.
622 iBucket = iHash % iBuckets;
624 // For a perfect table, the bucket is free.
628 _ASSERTE(Status(EntryPtr(i, rgData)) == FREE);
633 // Walk the bucket list looking for a slot.
634 for (i=iBucket; Status(EntryPtr(i, rgData)) != FREE; )
636 // Handle wrap around.
640 // If we made it this far, we collided.
645 // One more item in list.
648 // Return the new slot for the caller.
649 return (EntryPtr(i, rgData));
652 //*****************************************************************************
653 // This function is called either to init the table in the first place, or
654 // to rehash the table if we ran out of room.
655 //*****************************************************************************
656 bool CClosedHashBase::ReHash() // true if successful.
664 // Allocate memory if we don't have any.
667 if ((m_rgData = new (nothrow) BYTE [m_iSize * m_iEntrySize]) == 0)
669 InitFree(&m_rgData[0], m_iSize);
673 // We have entries already, allocate a new table.
675 int iBuckets = m_iBuckets * 2 - 1;
676 int iSize = iBuckets + 7;
680 if ((rgTemp = new (nothrow) BYTE [iSize * m_iEntrySize]) == 0)
682 InitFree(&rgTemp[0], iSize);
686 for (int i=0; i<m_iSize; i++)
688 // Only copy used entries.
689 if (Status(EntryPtr(i)) != USED)
692 // Add this entry to the list again.
693 VERIFY((p = DoAdd(GetKey(EntryPtr(i)), rgTemp, iBuckets,
694 iSize, iCollisions, iCount)));
695 memmove(p, EntryPtr(i), m_iEntrySize);
701 m_iBuckets = iBuckets;
703 m_iCollisions = iCollisions;
716 //*****************************************************************************
717 // Returns a pointer to the (iIndex)th element of the array, shifts the elements
718 // in the array if the location is already full. The iIndex cannot exceed the count
719 // of elements in the array.
720 //*****************************************************************************
721 void *CStructArray::InsertThrowing(
730 _ASSERTE(iIndex >= 0);
732 // We can not insert an element further than the end of the array.
733 if (iIndex > m_iCount)
736 // The array should grow, if we can't fit one more element into the array.
739 // The pointer to be returned.
740 BYTE *pcList = m_pList + iIndex * m_iElemSize;
742 // See if we need to slide anything down.
743 if (iIndex < m_iCount)
744 memmove(pcList + m_iElemSize, pcList, (m_iCount - iIndex) * m_iElemSize);
749 //*****************************************************************************
750 // Non-throwing variant
751 //*****************************************************************************
752 void *CStructArray::Insert(int iIndex)
763 result = InsertThrowing(iIndex);
768 EX_END_CATCH(SwallowAllExceptions);
774 //*****************************************************************************
775 // Allocate a new element at the end of the dynamic array and return a pointer
777 //*****************************************************************************
778 void *CStructArray::AppendThrowing()
786 // The array should grow, if we can't fit one more element into the array.
789 return (m_pList + m_iCount++ * m_iElemSize);
793 //*****************************************************************************
794 // Non-throwing variant
795 //*****************************************************************************
796 void *CStructArray::Append()
807 result = AppendThrowing();
812 EX_END_CATCH(SwallowAllExceptions);
818 //*****************************************************************************
819 // Allocate enough memory to have at least iCount items. This is a one shot
820 // check for a block of items, instead of requiring singleton inserts. It also
821 // avoids realloc headaches caused by growth, since you can do the whole block
822 // in one piece of code. If the array is already large enough, this is a no-op.
823 //*****************************************************************************
824 void CStructArray::AllocateBlockThrowing(int iCount)
832 if (m_iSize < m_iCount+iCount)
837 //*****************************************************************************
838 // Non-throwing variant
839 //*****************************************************************************
840 int CStructArray::AllocateBlock(int iCount)
851 AllocateBlockThrowing(iCount);
857 EX_END_CATCH(SwallowAllExceptions);
863 //*****************************************************************************
864 // Deletes the specified element from the array.
865 //*****************************************************************************
866 void CStructArray::Delete(
875 _ASSERTE(iIndex >= 0);
877 // See if we need to slide anything down.
878 if (iIndex < --m_iCount)
880 BYTE *pcList = m_pList + iIndex * m_iElemSize;
881 memmove(pcList, pcList + m_iElemSize, (m_iCount - iIndex) * m_iElemSize);
886 //*****************************************************************************
887 // Grow the array if it is not possible to fit iCount number of new elements.
888 //*****************************************************************************
889 void CStructArray::Grow(
896 BYTE *pTemp; // temporary pointer used in realloc.
899 if (m_iSize < m_iCount+iCount)
903 iGrow = max(m_iGrowInc, iCount);
905 //<TODO>@todo this is a workaround because I don't want to do resize right now.</TODO>
906 //check added to make PREFAST happy
907 S_SIZE_T newSize = S_SIZE_T(iGrow) * S_SIZE_T(m_iElemSize);
908 if(newSize.IsOverflow())
912 m_pList = new BYTE[newSize.Value()];
919 // Adjust grow size as a ratio to avoid too many reallocs.
920 if (m_iSize / m_iGrowInc >= 3)
921 { // Don't overflow and go negative.
922 int newinc = m_iGrowInc * 2;
923 if (newinc > m_iGrowInc)
927 iGrow = max(m_iGrowInc, iCount);
929 // try to allocate memory for reallocation.
930 S_SIZE_T allocSize = (S_SIZE_T(m_iSize) + S_SIZE_T(iGrow)) * S_SIZE_T(m_iElemSize);
931 S_SIZE_T copyBytes = S_SIZE_T(m_iSize) * S_SIZE_T(m_iElemSize);
932 if(allocSize.IsOverflow() || copyBytes.IsOverflow())
935 { // We already own memory.
936 pTemp = new BYTE[allocSize.Value()];
937 memcpy (pTemp, m_pList, copyBytes.Value());
941 { // We don't own memory; get our own.
942 pTemp = new BYTE[allocSize.Value()];
943 memcpy(pTemp, m_pList, copyBytes.Value());
953 //*****************************************************************************
954 // Free the memory for this item.
955 //*****************************************************************************
956 void CStructArray::Clear()
964 // Free the chunk of memory.
965 if (m_bFree && m_pList != NULL)