src/utilcode/collections.cpp

   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 //*****************************************************************************
  30 HRESULT 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 //*****************************************************************************
  56 BYTE *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 //*****************************************************************************
  91 void 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 //*****************************************************************************
 107 void 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 //*****************************************************************************
 137 void 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 //*****************************************************************************
 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.
 168 {
 169     CONTRACTL
 170     {
 171         NOTHROW;
 172         GC_NOTRIGGER;
 173         SUPPORTS_DAC;
 174     }
 175     CONTRACTL_END;
 176
 177     ULONG      iNext;                  // Used to traverse the chains.
 178     HASHENTRY   *psEntry;               // Used to traverse the chains.
 179
 180     // Start at the top of the chain.
 181     iNext = m_piBuckets[iHash % m_iBuckets];
 182
 183     // Search until we hit the end.
 184
 185 #ifdef _DEBUG
 186     unsigned count = 0;
 187 #endif
 188
 189     while (iNext != UINT32_MAX)
 190     {
 191         // Compare the keys.
 192         psEntry = EntryPtr(iNext);
 193
 194 #ifdef _DEBUG
 195         count++;
 196 #endif
 197         if (!Cmp(key, psEntry))
 198         {
 199 #ifdef _DEBUG
 200             if (count > m_maxSearch)
 201                 m_maxSearch = count;
 202 #endif
 203
 204             return ((BYTE *) psEntry);
 205         }
 206
 207         // Advance to the next item in the chain.
 208         iNext = psEntry->iNext;
 209     }
 210
 211     // We couldn't find it.
 212     return (0);
 213 }
 214
 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.
 221 {
 222     CONTRACTL
 223     {
 224         NOTHROW;
 225     }
 226     CONTRACTL_END;
 227
 228     ULONG      iNext;                  // Used to traverse the chains.
 229     HASHENTRY   *psEntry;               // Used to traverse the chains.
 230
 231     // Start at the next entry in the chain.
 232     iNext = EntryPtr(iIndex)->iNext;
 233
 234     // Search until we hit the end.
 235     while (iNext != UINT32_MAX)
 236     {
 237         // Compare the keys.
 238         psEntry = EntryPtr(iNext);
 239         if (!Cmp(key, psEntry))
 240             return (iNext);
 241
 242         // Advance to the next item in the chain.
 243         iNext = psEntry->iNext;
 244     }
 245
 246     // We couldn't find it.
 247     return (UINT32_MAX);
 248 }
 249
 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.
 255 {
 256     CONTRACTL
 257     {
 258         NOTHROW;
 259         GC_NOTRIGGER;
 260         SUPPORTS_DAC;
 261     }
 262     CONTRACTL_END;
 263
 264     HASHENTRY   *psEntry;               // Used to traverse the chains.
 265
 266     for (;;)
 267     {
 268         // See if we already have one to use and if so, use it.
 269         if (psSrch->iNext != UINT32_MAX)
 270         {
 271             psEntry = EntryPtr(psSrch->iNext);
 272             psSrch->iNext = psEntry->iNext;
 273             return ((BYTE *) psEntry);
 274         }
 275
 276         // Advance to the next bucket.
 277         if (psSrch->iBucket < m_iBuckets)
 278             psSrch->iNext = m_piBuckets[psSrch->iBucket++];
 279         else
 280             break;
 281     }
 282
 283     // There were no more entries to be found.
 284     return (0);
 285 }
 286
 287 #ifdef DACCESS_COMPILE
 288
 289 void
 290 CHashTable::EnumMemoryRegions(CLRDataEnumMemoryFlags flags,
 291                               ULONG numEntries)
 292 {
 293     SUPPORTS_DAC;
 294
 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));
 300 }
 301
 302 #endif // #ifdef DACCESS_COMPILE
 303
 304 //
 305 //
 306 // CClosedHashBase
 307 //
 308 //
 309
 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.
 318 {
 319     CONTRACTL
 320     {
 321         NOTHROW;
 322     }
 323     CONTRACTL_END;
 324
 325     BYTE        *ptr;
 326
 327     // Find the item to delete.
 328     if ((ptr = Find(pData)) == 0)
 329     {
 330         // You deleted something that wasn't there, why?
 331         _ASSERTE(0);
 332         return;
 333     }
 334
 335     // For a perfect system, there are no collisions so it is free.
 336     if (m_bPerfect)
 337     {
 338         SetStatus(ptr, FREE);
 339
 340         // One less non free entry.
 341         --m_iCount;
 342
 343         return;
 344     }
 345
 346     // Mark this entry deleted.
 347     SetStatus(ptr, DELETED);
 348
 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.
 352     BYTE        *pnext;
 353     if ((pnext = ptr + m_iEntrySize) > EntryPtr(m_iSize - 1))
 354         pnext = &m_rgData[0];
 355     if (Status(pnext) != FREE)
 356         return;
 357
 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)
 361     {
 362         // Free this entry.
 363         SetStatus(ptr, FREE);
 364
 365         // One less non free entry.
 366         --m_iCount;
 367
 368         // Check the one before it, handle wrap around.
 369         if ((ptr -= m_iEntrySize) < &m_rgData[0])
 370             ptr = EntryPtr(m_iSize - 1);
 371     }
 372 }
 373
 374
 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.
 383 {
 384     CONTRACTL
 385     {
 386         NOTHROW;
 387     }
 388     CONTRACTL_END;
 389
 390     int i;
 391
 392     if (m_rgData == 0)
 393     {
 394         return;
 395     }
 396
 397     for (i = 0; i < m_iSize; i++)
 398     {
 399         BYTE *pEntry = EntryPtr(i);
 400         if (Status(pEntry) == USED)
 401         {
 402             if (pDeleteLoopFunc(pEntry, pCustomizer))
 403             {
 404                 if (m_bPerfect)
 405                 {
 406                     SetStatus(pEntry, FREE);
 407                     // One less non free entry.
 408                     --m_iCount;
 409                 }
 410                 else
 411                 {
 412                     SetStatus(pEntry, DELETED);
 413                 }
 414             }
 415         }
 416     }
 417
 418     if (!m_bPerfect)
 419     {
 420         // Now free DELETED entries that are no longer part of a chain.
 421         for (i = 0; i < m_iSize; i++)
 422         {
 423             if (Status(EntryPtr(i)) == FREE)
 424             {
 425                 break;
 426             }
 427         }
 428         if (i != m_iSize)
 429         {
 430             int iFirstFree = i;
 431
 432             do
 433             {
 434                 if (i-- == 0)
 435                 {
 436                     i = m_iSize - 1;
 437                 }
 438                 while (Status(EntryPtr(i)) == DELETED)
 439                 {
 440                     SetStatus(EntryPtr(i), FREE);
 441
 442
 443                     // One less non free entry.
 444                     --m_iCount;
 445
 446                     if (i-- == 0)
 447                     {
 448                         i = m_iSize - 1;
 449                     }
 450                 }
 451
 452                 while (Status(EntryPtr(i)) != FREE)
 453                 {
 454                     if (i-- == 0)
 455                     {
 456                         i = m_iSize - 1;
 457                     }
 458                 }
 459
 460             }
 461             while (i != iFirstFree);
 462         }
 463     }
 464
 465 }
 466
 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.
 472 {
 473     CONTRACTL
 474     {
 475         NOTHROW;
 476     }
 477     CONTRACTL_END;
 478
 479     unsigned int iHash;                // Hash value for this data.
 480     int         iBucket;                // Which bucke to start at.
 481     int         i;                      // Loop control.
 482
 483     // Safety check.
 484     if (!m_rgData || m_iCount == 0)
 485         return (0);
 486
 487     // Hash to the bucket.
 488     iHash = Hash(pData);
 489     iBucket = iHash % m_iBuckets;
 490
 491     // For a perfect table, the bucket is the correct one.
 492     if (m_bPerfect)
 493     {
 494         // If the value is there, it is the correct one.
 495         if (Status(EntryPtr(iBucket)) != FREE)
 496             return (EntryPtr(iBucket));
 497         return (0);
 498     }
 499
 500     // Walk the bucket list looking for the item.
 501     for (i=iBucket;  Status(EntryPtr(i)) != FREE;  )
 502     {
 503         // Don't look at deleted items.
 504         if (Status(EntryPtr(i)) == DELETED)
 505         {
 506             // Handle wrap around.
 507             if (++i >= m_iSize)
 508                 i = 0;
 509             continue;
 510         }
 511
 512         // Check this one.
 513         if (Compare(pData, EntryPtr(i)) == 0)
 514             return (EntryPtr(i));
 515
 516         // If we never collided while adding items, then there is
 517         // no point in scanning any further.
 518         if (!m_iCollisions)
 519             return (0);
 520
 521         // Handle wrap around.
 522         if (++i >= m_iSize)
 523             i = 0;
 524     }
 525     return (0);
 526 }
 527
 528
 529
 530 //*****************************************************************************
 531 // Look for an item in the table.  If it isn't found, then create a new one and
 532 // return that.
 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.
 537 {
 538     CONTRACTL
 539     {
 540         NOTHROW;
 541     }
 542     CONTRACTL_END;
 543
 544     unsigned int iHash;                // Hash value for this data.
 545     int         iBucket;                // Which bucke to start at.
 546     int         i;                      // Loop control.
 547
 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))
 550     {
 551         if (!ReHash())
 552             return (0);
 553     }
 554
 555     // Assume we find it.
 556     bNew = false;
 557
 558     // Hash to the bucket.
 559     iHash = Hash(pData);
 560     iBucket = iHash % m_iBuckets;
 561
 562     // For a perfect table, the bucket is the correct one.
 563     if (m_bPerfect)
 564     {
 565         // If the value is there, it is the correct one.
 566         if (Status(EntryPtr(iBucket)) != FREE)
 567             return (EntryPtr(iBucket));
 568         i = iBucket;
 569     }
 570     else
 571     {
 572         // Walk the bucket list looking for the item.
 573         for (i=iBucket;  Status(EntryPtr(i)) != FREE;  )
 574         {
 575             // Don't look at deleted items.
 576             if (Status(EntryPtr(i)) == DELETED)
 577             {
 578                 // Handle wrap around.
 579                 if (++i >= m_iSize)
 580                     i = 0;
 581                 continue;
 582             }
 583
 584             // Check this one.
 585             if (Compare(pData, EntryPtr(i)) == 0)
 586                 return (EntryPtr(i));
 587
 588             // One more to count.
 589             ++m_iCollisions;
 590
 591             // Handle wrap around.
 592             if (++i >= m_iSize)
 593                 i = 0;
 594         }
 595     }
 596
 597     // We've found an open slot, use it.
 598     _ASSERTE(Status(EntryPtr(i)) == FREE);
 599     bNew = true;
 600     ++m_iCount;
 601     return (EntryPtr(i));
 602 }
 603
 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)
 609 {
 610     CONTRACTL
 611     {
 612         NOTHROW;
 613     }
 614     CONTRACTL_END;
 615
 616     unsigned int iHash;                // Hash value for this data.
 617     int         iBucket;                // Which bucke to start at.
 618     int         i;                      // Loop control.
 619
 620     // Hash to the bucket.
 621     iHash = Hash(pData);
 622     iBucket = iHash % iBuckets;
 623
 624     // For a perfect table, the bucket is free.
 625     if (m_bPerfect)
 626     {
 627         i = iBucket;
 628         _ASSERTE(Status(EntryPtr(i, rgData)) == FREE);
 629     }
 630     // Need to scan.
 631     else
 632     {
 633         // Walk the bucket list looking for a slot.
 634         for (i=iBucket;  Status(EntryPtr(i, rgData)) != FREE;  )
 635         {
 636             // Handle wrap around.
 637             if (++i >= iSize)
 638                 i = 0;
 639
 640             // If we made it this far, we collided.
 641             ++iCollisions;
 642         }
 643     }
 644
 645     // One more item in list.
 646     ++iCount;
 647
 648     // Return the new slot for the caller.
 649     return (EntryPtr(i, rgData));
 650 }
 651
 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.
 657 {
 658     CONTRACTL
 659     {
 660         NOTHROW;
 661     }
 662     CONTRACTL_END;
 663
 664     // Allocate memory if we don't have any.
 665     if (!m_rgData)
 666     {
 667         if ((m_rgData = new (nothrow) BYTE [m_iSize * m_iEntrySize]) == 0)
 668             return (false);
 669         InitFree(&m_rgData[0], m_iSize);
 670         return (true);
 671     }
 672
 673     // We have entries already, allocate a new table.
 674     BYTE        *rgTemp, *p;
 675     int         iBuckets = m_iBuckets * 2 - 1;
 676     int         iSize = iBuckets + 7;
 677     int         iCollisions = 0;
 678     int         iCount = 0;
 679
 680     if ((rgTemp = new (nothrow) BYTE [iSize * m_iEntrySize]) == 0)
 681         return (false);
 682     InitFree(&rgTemp[0], iSize);
 683     m_bPerfect = false;
 684
 685     // Rehash the data.
 686     for (int i=0;  i<m_iSize;  i++)
 687     {
 688         // Only copy used entries.
 689         if (Status(EntryPtr(i)) != USED)
 690             continue;
 691
 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);
 696     }
 697
 698     // Reset internals.
 699     delete [] m_rgData;
 700     m_rgData = rgTemp;
 701     m_iBuckets = iBuckets;
 702     m_iSize = iSize;
 703     m_iCollisions = iCollisions;
 704     m_iCount = iCount;
 705     return (true);
 706 }
 707
 708
 709 //
 710 //
 711 // CStructArray
 712 //
 713 //
 714
 715
 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(
 722     int         iIndex)
 723 {
 724     CONTRACTL
 725     {
 726         THROWS;
 727     }
 728     CONTRACTL_END;
 729
 730     _ASSERTE(iIndex >= 0);
 731
 732     // We can not insert an element further than the end of the array.
 733     if (iIndex > m_iCount)
 734         return (NULL);
 735
 736     // The array should grow, if we can't fit one more element into the array.
 737     Grow(1);
 738
 739     // The pointer to be returned.
 740     BYTE *pcList = m_pList + iIndex * m_iElemSize;
 741
 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);
 745     ++m_iCount;
 746     return(pcList);
 747 }
 748
 749 //*****************************************************************************
 750 // Non-throwing variant
 751 //*****************************************************************************
 752 void *CStructArray::Insert(int iIndex)
 753 {
 754     CONTRACTL
 755     {
 756         NOTHROW;
 757     }
 758     CONTRACTL_END;
 759
 760     void *result = NULL;
 761     EX_TRY
 762     {
 763         result = InsertThrowing(iIndex);
 764     }
 765     EX_CATCH
 766     {
 767     }
 768     EX_END_CATCH(SwallowAllExceptions);
 769
 770     return result;
 771 }
 772
 773
 774 //*****************************************************************************
 775 // Allocate a new element at the end of the dynamic array and return a pointer
 776 // to it.
 777 //*****************************************************************************
 778 void *CStructArray::AppendThrowing()
 779 {
 780     CONTRACTL
 781     {
 782         THROWS;
 783     }
 784     CONTRACTL_END;
 785
 786     // The array should grow, if we can't fit one more element into the array.
 787     Grow(1);
 788
 789     return (m_pList + m_iCount++ * m_iElemSize);
 790 }
 791
 792
 793 //*****************************************************************************
 794 // Non-throwing variant
 795 //*****************************************************************************
 796 void *CStructArray::Append()
 797 {
 798     CONTRACTL
 799     {
 800         NOTHROW;
 801     }
 802     CONTRACTL_END;
 803
 804     void *result = NULL;
 805     EX_TRY
 806     {
 807         result = AppendThrowing();
 808     }
 809     EX_CATCH
 810     {
 811     }
 812     EX_END_CATCH(SwallowAllExceptions);
 813
 814     return result;
 815 }
 816
 817
 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)
 825 {
 826     CONTRACTL
 827     {
 828         THROWS;
 829     }
 830     CONTRACTL_END;
 831
 832     if (m_iSize < m_iCount+iCount)
 833         Grow(iCount);
 834     m_iCount += iCount;
 835 }
 836
 837 //*****************************************************************************
 838 // Non-throwing variant
 839 //*****************************************************************************
 840 int CStructArray::AllocateBlock(int iCount)
 841 {
 842     CONTRACTL
 843     {
 844         NOTHROW;
 845     }
 846     CONTRACTL_END;
 847
 848     int result = FALSE;
 849     EX_TRY
 850     {
 851         AllocateBlockThrowing(iCount);
 852         result = TRUE;
 853     }
 854     EX_CATCH
 855     {
 856     }
 857     EX_END_CATCH(SwallowAllExceptions);
 858
 859     return result;
 860 }
 861
 862
 863 //*****************************************************************************
 864 // Deletes the specified element from the array.
 865 //*****************************************************************************
 866 void CStructArray::Delete(
 867     int         iIndex)
 868 {
 869     CONTRACTL
 870     {
 871         NOTHROW;
 872     }
 873     CONTRACTL_END;
 874
 875     _ASSERTE(iIndex >= 0);
 876
 877     // See if we need to slide anything down.
 878     if (iIndex < --m_iCount)
 879     {
 880         BYTE *pcList = m_pList + iIndex * m_iElemSize;
 881         memmove(pcList, pcList + m_iElemSize, (m_iCount - iIndex) * m_iElemSize);
 882     }
 883 }
 884
 885
 886 //*****************************************************************************
 887 // Grow the array if it is not possible to fit iCount number of new elements.
 888 //*****************************************************************************
 889 void CStructArray::Grow(
 890     int         iCount)
 891 {
 892     CONTRACTL {
 893         THROWS;
 894     } CONTRACTL_END;
 895
 896     BYTE        *pTemp;                 // temporary pointer used in realloc.
 897     int         iGrow;
 898
 899     if (m_iSize < m_iCount+iCount)
 900     {
 901         if (m_pList == NULL)
 902         {
 903             iGrow = max(m_iGrowInc, iCount);
 904
 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())
 909                 ThrowOutOfMemory();
 910             else
 911             {
 912                 m_pList = new BYTE[newSize.Value()];
 913                 m_iSize = iGrow;
 914                 m_bFree = true;
 915             }
 916         }
 917         else
 918         {
 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)
 924                     m_iGrowInc = newinc;
 925             }
 926
 927             iGrow = max(m_iGrowInc, iCount);
 928
 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())
 933                 ThrowOutOfMemory();
 934             if (m_bFree)
 935             {   // We already own memory.
 936                 pTemp = new BYTE[allocSize.Value()];
 937                 memcpy (pTemp, m_pList, copyBytes.Value());
 938                 delete [] m_pList;
 939             }
 940             else
 941             {   // We don't own memory; get our own.
 942                 pTemp = new BYTE[allocSize.Value()];
 943                 memcpy(pTemp, m_pList, copyBytes.Value());
 944                 m_bFree = true;
 945             }
 946             m_pList = pTemp;
 947             m_iSize += iGrow;
 948         }
 949     }
 950 }
 951
 952
 953 //*****************************************************************************
 954 // Free the memory for this item.
 955 //*****************************************************************************
 956 void CStructArray::Clear()
 957 {
 958     CONTRACTL
 959     {
 960         NOTHROW;
 961     }
 962     CONTRACTL_END;
 963
 964     // Free the chunk of memory.
 965     if (m_bFree && m_pList != NULL)
 966         delete [] m_pList;
 967
 968     m_pList = NULL;
 969     m_iSize = 0;
 970     m_iCount = 0;
 971 }