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//*****************************************************************************
5// Collections.cpp
6//
7
8//
9// This contains Collections C++ utility classes.
10//
11//*****************************************************************************
12
13#include "stdafx.h"
14#include "utilcode.h"
15#include "ex.h"
16
17//
18//
19// CHashTable
20//
21//
22
23#ifndef DACCESS_COMPILE
24
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//*****************************************************************************
30HRESULT CHashTable::NewInit( // Return status.
31 BYTE *pcEntries, // Array of structs we are managing.
32 ULONG iEntrySize) // Size of the entries.
33{
34 CONTRACTL
35 {
36 NOTHROW;
37 }
38 CONTRACTL_END;
39
40 _ASSERTE(iEntrySize >= sizeof(FREEHASHENTRY));
41
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));
46
47 // Save the array of structs we are managing.
48 m_pcEntries = (TADDR)pcEntries;
49 m_iEntrySize = iEntrySize;
50 return (S_OK);
51}
52
53//*****************************************************************************
54// Add the struct at the specified index in m_pcEntries to the hash chains.
55//*****************************************************************************
56BYTE *CHashTable::Add( // New entry.
57 ULONG iHash, // Hash value of entry to add.
58 ULONG iIndex) // Index of struct in m_pcEntries.
59{
60 CONTRACTL
61 {
62 NOTHROW;
63 }
64 CONTRACTL_END;
65
66 HASHENTRY *psEntry; // The struct we are adding.
67
68 // Get a pointer to the entry we are adding.
69 psEntry = EntryPtr(iIndex);
70
71 // Compute the hash value for the entry.
72 iHash %= m_iBuckets;
73
74 _ASSERTE(m_piBuckets[iHash] != iIndex &&
75 (m_piBuckets[iHash] == UINT32_MAX || EntryPtr(m_piBuckets[iHash])->iPrev != iIndex));
76
77 // Setup this entry.
78 psEntry->iPrev = UINT32_MAX;
79 psEntry->iNext = m_piBuckets[iHash];
80
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);
86}
87
88//*****************************************************************************
89// Delete the struct at the specified index in m_pcEntries from the hash chains.
90//*****************************************************************************
91void CHashTable::Delete(
92 ULONG iHash, // Hash value of entry to delete.
93 ULONG iIndex) // Index of struct in m_pcEntries.
94{
95 WRAPPER_NO_CONTRACT;
96
97 HASHENTRY *psEntry; // Struct to delete.
98
99 // Get a pointer to the entry we are deleting.
100 psEntry = EntryPtr(iIndex);
101 Delete(iHash, psEntry);
102}
103
104//*****************************************************************************
105// Delete the struct at the specified index in m_pcEntries from the hash chains.
106//*****************************************************************************
107void CHashTable::Delete(
108 ULONG iHash, // Hash value of entry to delete.
109 HASHENTRY *psEntry) // The struct to delete.
110{
111 CONTRACTL
112 {
113 NOTHROW;
114 }
115 CONTRACTL_END;
116
117 // Compute the hash value for the entry.
118 iHash %= m_iBuckets;
119
120 _ASSERTE(psEntry->iPrev != psEntry->iNext || psEntry->iPrev == UINT32_MAX);
121
122 // Fix the predecessor.
123 if (psEntry->iPrev == UINT32_MAX)
124 m_piBuckets[iHash] = psEntry->iNext;
125 else
126 EntryPtr(psEntry->iPrev)->iNext = psEntry->iNext;
127
128 // Fix the successor.
129 if (psEntry->iNext != UINT32_MAX)
130 EntryPtr(psEntry->iNext)->iPrev = psEntry->iPrev;
131}
132
133//*****************************************************************************
134// The item at the specified index has been moved, update the previous and
135// next item.
136//*****************************************************************************
137void CHashTable::Move(
138 ULONG iHash, // Hash value for the item.
139 ULONG iNew) // New location.
140{
141 CONTRACTL
142 {
143 NOTHROW;
144 }
145 CONTRACTL_END;
146
147 HASHENTRY *psEntry; // The struct we are deleting.
148
149 psEntry = EntryPtr(iNew);
150 _ASSERTE(psEntry->iPrev != iNew && psEntry->iNext != iNew);
151
152 if (psEntry->iPrev != UINT32_MAX)
153 EntryPtr(psEntry->iPrev)->iNext = iNew;
154 else
155 m_piBuckets[iHash % m_iBuckets] = iNew;
156 if (psEntry->iNext != UINT32_MAX)
157 EntryPtr(psEntry->iNext)->iPrev = iNew;
158}
159
160#endif // !DACCESS_COMPILE
161
162//*****************************************************************************
163// Search the hash table for an entry with the specified key value.
164//*****************************************************************************
165BYTE *CHashTable::Find( // Index of struct in m_pcEntries.
166 ULONG iHash, // Hash value of the item.
167 SIZE_T key) // The key to match.
168{
169 CONTRACTL
170 {
171 NOTHROW;
172 SO_TOLERANT;
173 GC_NOTRIGGER;
174 SUPPORTS_DAC;
175 }
176 CONTRACTL_END;
177
178 ULONG iNext; // Used to traverse the chains.
179 HASHENTRY *psEntry; // Used to traverse the chains.
180
181 // Start at the top of the chain.
182 iNext = m_piBuckets[iHash % m_iBuckets];
183
184 // Search until we hit the end.
185
186#ifdef _DEBUG
187 unsigned count = 0;
188#endif
189
190 while (iNext != UINT32_MAX)
191 {
192 // Compare the keys.
193 psEntry = EntryPtr(iNext);
194
195#ifdef _DEBUG
196 count++;
197#endif
198 if (!Cmp(key, psEntry))
199 {
200#ifdef _DEBUG
201 if (count > m_maxSearch)
202 m_maxSearch = count;
203#endif
204
205 return ((BYTE *) psEntry);
206 }
207
208 // Advance to the next item in the chain.
209 iNext = psEntry->iNext;
210 }
211
212 // We couldn't find it.
213 return (0);
214}
215
216//*****************************************************************************
217// Search the hash table for the next entry with the specified key value.
218//*****************************************************************************
219ULONG CHashTable::FindNext( // Index of struct in m_pcEntries.
220 SIZE_T key, // The key to match.
221 ULONG iIndex) // Index of previous match.
222{
223 CONTRACTL
224 {
225 NOTHROW;
226 }
227 CONTRACTL_END;
228
229 ULONG iNext; // Used to traverse the chains.
230 HASHENTRY *psEntry; // Used to traverse the chains.
231
232 // Start at the next entry in the chain.
233 iNext = EntryPtr(iIndex)->iNext;
234
235 // Search until we hit the end.
236 while (iNext != UINT32_MAX)
237 {
238 // Compare the keys.
239 psEntry = EntryPtr(iNext);
240 if (!Cmp(key, psEntry))
241 return (iNext);
242
243 // Advance to the next item in the chain.
244 iNext = psEntry->iNext;
245 }
246
247 // We couldn't find it.
248 return (UINT32_MAX);
249}
250
251//*****************************************************************************
252// Returns the next entry in the list.
253//*****************************************************************************
254BYTE *CHashTable::FindNextEntry( // The next entry, or0 for end of list.
255 HASHFIND *psSrch) // Search object.
256{
257 CONTRACTL
258 {
259 NOTHROW;
260 GC_NOTRIGGER;
261 SUPPORTS_DAC;
262 }
263 CONTRACTL_END;
264
265 HASHENTRY *psEntry; // Used to traverse the chains.
266
267 for (;;)
268 {
269 // See if we already have one to use and if so, use it.
270 if (psSrch->iNext != UINT32_MAX)
271 {
272 psEntry = EntryPtr(psSrch->iNext);
273 psSrch->iNext = psEntry->iNext;
274 return ((BYTE *) psEntry);
275 }
276
277 // Advance to the next bucket.
278 if (psSrch->iBucket < m_iBuckets)
279 psSrch->iNext = m_piBuckets[psSrch->iBucket++];
280 else
281 break;
282 }
283
284 // There were no more entries to be found.
285 return (0);
286}
287
288#ifdef DACCESS_COMPILE
289
290void
291CHashTable::EnumMemoryRegions(CLRDataEnumMemoryFlags flags,
292 ULONG numEntries)
293{
294 SUPPORTS_DAC;
295
296 // This class may be embedded so do not enum 'this'.
297 DacEnumMemoryRegion(m_pcEntries,
298 (ULONG)numEntries * m_iEntrySize);
299 DacEnumMemoryRegion(dac_cast<TADDR>(m_piBuckets),
300 (ULONG)m_iBuckets * sizeof(ULONG));
301}
302
303#endif // #ifdef DACCESS_COMPILE
304
305//
306//
307// CClosedHashBase
308//
309//
310
311//*****************************************************************************
312// Delete the given value. This will simply mark the entry as deleted (in
313// order to keep the collision chain intact). There is an optimization that
314// consecutive deleted entries leading up to a free entry are themselves freed
315// to reduce collisions later on.
316//*****************************************************************************
317void CClosedHashBase::Delete(
318 void *pData) // Key value to delete.
319{
320 CONTRACTL
321 {
322 NOTHROW;
323 }
324 CONTRACTL_END;
325
326 BYTE *ptr;
327
328 // Find the item to delete.
329 if ((ptr = Find(pData)) == 0)
330 {
331 // You deleted something that wasn't there, why?
332 _ASSERTE(0);
333 return;
334 }
335
336 // For a perfect system, there are no collisions so it is free.
337 if (m_bPerfect)
338 {
339 SetStatus(ptr, FREE);
340
341 // One less non free entry.
342 --m_iCount;
343
344 return;
345 }
346
347 // Mark this entry deleted.
348 SetStatus(ptr, DELETED);
349
350 // If the next item is free, then we can go backwards freeing
351 // deleted entries which are no longer part of a chain. This isn't
352 // 100% great, but it will reduce collisions.
353 BYTE *pnext;
354 if ((pnext = ptr + m_iEntrySize) > EntryPtr(m_iSize - 1))
355 pnext = &m_rgData[0];
356 if (Status(pnext) != FREE)
357 return;
358
359 // We can now free consecutive entries starting with the one
360 // we just deleted, up to the first non-deleted one.
361 while (Status(ptr) == DELETED)
362 {
363 // Free this entry.
364 SetStatus(ptr, FREE);
365
366 // One less non free entry.
367 --m_iCount;
368
369 // Check the one before it, handle wrap around.
370 if ((ptr -= m_iEntrySize) < &m_rgData[0])
371 ptr = EntryPtr(m_iSize - 1);
372 }
373}
374
375
376//*****************************************************************************
377// Iterates over all active values, passing each one to pDeleteLoopFunc.
378// If pDeleteLoopFunc returns TRUE, the entry is deleted. This is safer
379// and faster than using FindNext() and Delete().
380//*****************************************************************************
381void CClosedHashBase::DeleteLoop(
382 DELETELOOPFUNC pDeleteLoopFunc, // Decides whether to delete item
383 void *pCustomizer) // Extra value passed to deletefunc.
384{
385 CONTRACTL
386 {
387 NOTHROW;
388 }
389 CONTRACTL_END;
390
391 int i;
392
393 if (m_rgData == 0)
394 {
395 return;
396 }
397
398 for (i = 0; i < m_iSize; i++)
399 {
400 BYTE *pEntry = EntryPtr(i);
401 if (Status(pEntry) == USED)
402 {
403 if (pDeleteLoopFunc(pEntry, pCustomizer))
404 {
405 if (m_bPerfect)
406 {
407 SetStatus(pEntry, FREE);
408 // One less non free entry.
409 --m_iCount;
410 }
411 else
412 {
413 SetStatus(pEntry, DELETED);
414 }
415 }
416 }
417 }
418
419 if (!m_bPerfect)
420 {
421 // Now free DELETED entries that are no longer part of a chain.
422 for (i = 0; i < m_iSize; i++)
423 {
424 if (Status(EntryPtr(i)) == FREE)
425 {
426 break;
427 }
428 }
429 if (i != m_iSize)
430 {
431 int iFirstFree = i;
432
433 do
434 {
435 if (i-- == 0)
436 {
437 i = m_iSize - 1;
438 }
439 while (Status(EntryPtr(i)) == DELETED)
440 {
441 SetStatus(EntryPtr(i), FREE);
442
443
444 // One less non free entry.
445 --m_iCount;
446
447 if (i-- == 0)
448 {
449 i = m_iSize - 1;
450 }
451 }
452
453 while (Status(EntryPtr(i)) != FREE)
454 {
455 if (i-- == 0)
456 {
457 i = m_iSize - 1;
458 }
459 }
460
461 }
462 while (i != iFirstFree);
463 }
464 }
465
466}
467
468//*****************************************************************************
469// Lookup a key value and return a pointer to the element if found.
470//*****************************************************************************
471BYTE *CClosedHashBase::Find( // The item if found, 0 if not.
472 void *pData) // The key to lookup.
473{
474 CONTRACTL
475 {
476 NOTHROW;
477 }
478 CONTRACTL_END;
479
480 unsigned int iHash; // Hash value for this data.
481 int iBucket; // Which bucke to start at.
482 int i; // Loop control.
483
484 // Safety check.
485 if (!m_rgData || m_iCount == 0)
486 return (0);
487
488 // Hash to the bucket.
489 iHash = Hash(pData);
490 iBucket = iHash % m_iBuckets;
491
492 // For a perfect table, the bucket is the correct one.
493 if (m_bPerfect)
494 {
495 // If the value is there, it is the correct one.
496 if (Status(EntryPtr(iBucket)) != FREE)
497 return (EntryPtr(iBucket));
498 return (0);
499 }
500
501 // Walk the bucket list looking for the item.
502 for (i=iBucket; Status(EntryPtr(i)) != FREE; )
503 {
504 // Don't look at deleted items.
505 if (Status(EntryPtr(i)) == DELETED)
506 {
507 // Handle wrap around.
508 if (++i >= m_iSize)
509 i = 0;
510 continue;
511 }
512
513 // Check this one.
514 if (Compare(pData, EntryPtr(i)) == 0)
515 return (EntryPtr(i));
516
517 // If we never collided while adding items, then there is
518 // no point in scanning any further.
519 if (!m_iCollisions)
520 return (0);
521
522 // Handle wrap around.
523 if (++i >= m_iSize)
524 i = 0;
525 }
526 return (0);
527}
528
529
530
531//*****************************************************************************
532// Look for an item in the table. If it isn't found, then create a new one and
533// return that.
534//*****************************************************************************
535BYTE *CClosedHashBase::FindOrAdd( // The item if found, 0 if not.
536 void *pData, // The key to lookup.
537 bool &bNew) // true if created.
538{
539 CONTRACTL
540 {
541 NOTHROW;
542 }
543 CONTRACTL_END;
544
545 unsigned int iHash; // Hash value for this data.
546 int iBucket; // Which bucke to start at.
547 int i; // Loop control.
548
549 // If we haven't allocated any memory, or it is too small, fix it.
550 if (!m_rgData || ((m_iCount + 1) > (m_iSize * 3 / 4) && !m_bPerfect))
551 {
552 if (!ReHash())
553 return (0);
554 }
555
556 // Assume we find it.
557 bNew = false;
558
559 // Hash to the bucket.
560 iHash = Hash(pData);
561 iBucket = iHash % m_iBuckets;
562
563 // For a perfect table, the bucket is the correct one.
564 if (m_bPerfect)
565 {
566 // If the value is there, it is the correct one.
567 if (Status(EntryPtr(iBucket)) != FREE)
568 return (EntryPtr(iBucket));
569 i = iBucket;
570 }
571 else
572 {
573 // Walk the bucket list looking for the item.
574 for (i=iBucket; Status(EntryPtr(i)) != FREE; )
575 {
576 // Don't look at deleted items.
577 if (Status(EntryPtr(i)) == DELETED)
578 {
579 // Handle wrap around.
580 if (++i >= m_iSize)
581 i = 0;
582 continue;
583 }
584
585 // Check this one.
586 if (Compare(pData, EntryPtr(i)) == 0)
587 return (EntryPtr(i));
588
589 // One more to count.
590 ++m_iCollisions;
591
592 // Handle wrap around.
593 if (++i >= m_iSize)
594 i = 0;
595 }
596 }
597
598 // We've found an open slot, use it.
599 _ASSERTE(Status(EntryPtr(i)) == FREE);
600 bNew = true;
601 ++m_iCount;
602 return (EntryPtr(i));
603}
604
605//*****************************************************************************
606// This helper actually does the add for you.
607//*****************************************************************************
608BYTE *CClosedHashBase::DoAdd(void *pData, BYTE *rgData, int &iBuckets, int iSize,
609 int &iCollisions, int &iCount)
610{
611 CONTRACTL
612 {
613 NOTHROW;
614 }
615 CONTRACTL_END;
616
617 unsigned int iHash; // Hash value for this data.
618 int iBucket; // Which bucke to start at.
619 int i; // Loop control.
620
621 // Hash to the bucket.
622 iHash = Hash(pData);
623 iBucket = iHash % iBuckets;
624
625 // For a perfect table, the bucket is free.
626 if (m_bPerfect)
627 {
628 i = iBucket;
629 _ASSERTE(Status(EntryPtr(i, rgData)) == FREE);
630 }
631 // Need to scan.
632 else
633 {
634 // Walk the bucket list looking for a slot.
635 for (i=iBucket; Status(EntryPtr(i, rgData)) != FREE; )
636 {
637 // Handle wrap around.
638 if (++i >= iSize)
639 i = 0;
640
641 // If we made it this far, we collided.
642 ++iCollisions;
643 }
644 }
645
646 // One more item in list.
647 ++iCount;
648
649 // Return the new slot for the caller.
650 return (EntryPtr(i, rgData));
651}
652
653//*****************************************************************************
654// This function is called either to init the table in the first place, or
655// to rehash the table if we ran out of room.
656//*****************************************************************************
657bool CClosedHashBase::ReHash() // true if successful.
658{
659 CONTRACTL
660 {
661 NOTHROW;
662 }
663 CONTRACTL_END;
664
665 // Allocate memory if we don't have any.
666 if (!m_rgData)
667 {
668 if ((m_rgData = new (nothrow) BYTE [m_iSize * m_iEntrySize]) == 0)
669 return (false);
670 InitFree(&m_rgData[0], m_iSize);
671 return (true);
672 }
673
674 // We have entries already, allocate a new table.
675 BYTE *rgTemp, *p;
676 int iBuckets = m_iBuckets * 2 - 1;
677 int iSize = iBuckets + 7;
678 int iCollisions = 0;
679 int iCount = 0;
680
681 if ((rgTemp = new (nothrow) BYTE [iSize * m_iEntrySize]) == 0)
682 return (false);
683 InitFree(&rgTemp[0], iSize);
684 m_bPerfect = false;
685
686 // Rehash the data.
687 for (int i=0; i<m_iSize; i++)
688 {
689 // Only copy used entries.
690 if (Status(EntryPtr(i)) != USED)
691 continue;
692
693 // Add this entry to the list again.
694 VERIFY((p = DoAdd(GetKey(EntryPtr(i)), rgTemp, iBuckets,
695 iSize, iCollisions, iCount)));
696 memmove(p, EntryPtr(i), m_iEntrySize);
697 }
698
699 // Reset internals.
700 delete [] m_rgData;
701 m_rgData = rgTemp;
702 m_iBuckets = iBuckets;
703 m_iSize = iSize;
704 m_iCollisions = iCollisions;
705 m_iCount = iCount;
706 return (true);
707}
708
709
710//
711//
712// CStructArray
713//
714//
715
716
717//*****************************************************************************
718// Returns a pointer to the (iIndex)th element of the array, shifts the elements
719// in the array if the location is already full. The iIndex cannot exceed the count
720// of elements in the array.
721//*****************************************************************************
722void *CStructArray::InsertThrowing(
723 int iIndex)
724{
725 CONTRACTL
726 {
727 THROWS;
728 }
729 CONTRACTL_END;
730
731 _ASSERTE(iIndex >= 0);
732
733 // We can not insert an element further than the end of the array.
734 if (iIndex > m_iCount)
735 return (NULL);
736
737 // The array should grow, if we can't fit one more element into the array.
738 Grow(1);
739
740 // The pointer to be returned.
741 BYTE *pcList = m_pList + iIndex * m_iElemSize;
742
743 // See if we need to slide anything down.
744 if (iIndex < m_iCount)
745 memmove(pcList + m_iElemSize, pcList, (m_iCount - iIndex) * m_iElemSize);
746 ++m_iCount;
747 return(pcList);
748}
749
750//*****************************************************************************
751// Non-throwing variant
752//*****************************************************************************
753void *CStructArray::Insert(int iIndex)
754{
755 CONTRACTL
756 {
757 NOTHROW;
758 }
759 CONTRACTL_END;
760
761 void *result = NULL;
762 EX_TRY
763 {
764 result = InsertThrowing(iIndex);
765 }
766 EX_CATCH
767 {
768 }
769 EX_END_CATCH(SwallowAllExceptions);
770
771 return result;
772}
773
774
775//*****************************************************************************
776// Allocate a new element at the end of the dynamic array and return a pointer
777// to it.
778//*****************************************************************************
779void *CStructArray::AppendThrowing()
780{
781 CONTRACTL
782 {
783 THROWS;
784 }
785 CONTRACTL_END;
786
787 // The array should grow, if we can't fit one more element into the array.
788 Grow(1);
789
790 return (m_pList + m_iCount++ * m_iElemSize);
791}
792
793
794//*****************************************************************************
795// Non-throwing variant
796//*****************************************************************************
797void *CStructArray::Append()
798{
799 CONTRACTL
800 {
801 NOTHROW;
802 }
803 CONTRACTL_END;
804
805 void *result = NULL;
806 EX_TRY
807 {
808 result = AppendThrowing();
809 }
810 EX_CATCH
811 {
812 }
813 EX_END_CATCH(SwallowAllExceptions);
814
815 return result;
816}
817
818
819//*****************************************************************************
820// Allocate enough memory to have at least iCount items. This is a one shot
821// check for a block of items, instead of requiring singleton inserts. It also
822// avoids realloc headaches caused by growth, since you can do the whole block
823// in one piece of code. If the array is already large enough, this is a no-op.
824//*****************************************************************************
825void CStructArray::AllocateBlockThrowing(int iCount)
826{
827 CONTRACTL
828 {
829 THROWS;
830 }
831 CONTRACTL_END;
832
833 if (m_iSize < m_iCount+iCount)
834 Grow(iCount);
835 m_iCount += iCount;
836}
837
838//*****************************************************************************
839// Non-throwing variant
840//*****************************************************************************
841int CStructArray::AllocateBlock(int iCount)
842{
843 CONTRACTL
844 {
845 NOTHROW;
846 }
847 CONTRACTL_END;
848
849 int result = FALSE;
850 EX_TRY
851 {
852 AllocateBlockThrowing(iCount);
853 result = TRUE;
854 }
855 EX_CATCH
856 {
857 }
858 EX_END_CATCH(SwallowAllExceptions);
859
860 return result;
861}
862
863
864//*****************************************************************************
865// Deletes the specified element from the array.
866//*****************************************************************************
867void CStructArray::Delete(
868 int iIndex)
869{
870 CONTRACTL
871 {
872 NOTHROW;
873 }
874 CONTRACTL_END;
875
876 _ASSERTE(iIndex >= 0);
877
878 // See if we need to slide anything down.
879 if (iIndex < --m_iCount)
880 {
881 BYTE *pcList = m_pList + iIndex * m_iElemSize;
882 memmove(pcList, pcList + m_iElemSize, (m_iCount - iIndex) * m_iElemSize);
883 }
884}
885
886
887//*****************************************************************************
888// Grow the array if it is not possible to fit iCount number of new elements.
889//*****************************************************************************
890void CStructArray::Grow(
891 int iCount)
892{
893 CONTRACTL {
894 THROWS;
895 } CONTRACTL_END;
896
897 BYTE *pTemp; // temporary pointer used in realloc.
898 int iGrow;
899
900 if (m_iSize < m_iCount+iCount)
901 {
902 if (m_pList == NULL)
903 {
904 iGrow = max(m_iGrowInc, iCount);
905
906 //<TODO>@todo this is a workaround because I don't want to do resize right now.</TODO>
907 //check added to make PREFAST happy
908 S_SIZE_T newSize = S_SIZE_T(iGrow) * S_SIZE_T(m_iElemSize);
909 if(newSize.IsOverflow())
910 ThrowOutOfMemory();
911 else
912 {
913 m_pList = new BYTE[newSize.Value()];
914 m_iSize = iGrow;
915 m_bFree = true;
916 }
917 }
918 else
919 {
920 // Adjust grow size as a ratio to avoid too many reallocs.
921 if (m_iSize / m_iGrowInc >= 3)
922 { // Don't overflow and go negative.
923 int newinc = m_iGrowInc * 2;
924 if (newinc > m_iGrowInc)
925 m_iGrowInc = newinc;
926 }
927
928 iGrow = max(m_iGrowInc, iCount);
929
930 // try to allocate memory for reallocation.
931 S_SIZE_T allocSize = (S_SIZE_T(m_iSize) + S_SIZE_T(iGrow)) * S_SIZE_T(m_iElemSize);
932 S_SIZE_T copyBytes = S_SIZE_T(m_iSize) * S_SIZE_T(m_iElemSize);
933 if(allocSize.IsOverflow() || copyBytes.IsOverflow())
934 ThrowOutOfMemory();
935 if (m_bFree)
936 { // We already own memory.
937 pTemp = new BYTE[allocSize.Value()];
938 memcpy (pTemp, m_pList, copyBytes.Value());
939 delete [] m_pList;
940 }
941 else
942 { // We don't own memory; get our own.
943 pTemp = new BYTE[allocSize.Value()];
944 memcpy(pTemp, m_pList, copyBytes.Value());
945 m_bFree = true;
946 }
947 m_pList = pTemp;
948 m_iSize += iGrow;
949 }
950 }
951}
952
953
954//*****************************************************************************
955// Free the memory for this item.
956//*****************************************************************************
957void CStructArray::Clear()
958{
959 CONTRACTL
960 {
961 NOTHROW;
962 }
963 CONTRACTL_END;
964
965 // Free the chunk of memory.
966 if (m_bFree && m_pList != NULL)
967 delete [] m_pList;
968
969 m_pList = NULL;
970 m_iSize = 0;
971 m_iCount = 0;
972}
973