src/utilcode/arraylist.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 #include "stdafx.h"
   6
   7 #include "arraylist.h"
   8 #include "utilcode.h"
   9 #include "ex.h"
  10
  11 //
  12 // ArrayList is a simple class which is used to contain a growable
  13 // list of pointers, stored in chunks.  Modification is by appending
  14 // only currently.  Access is by index (efficient if the number of
  15 // elements stays small) and iteration (efficient in all cases).
  16 //
  17 // An important property of an ArrayList is that the list remains
  18 // coherent while it is being modified (appended to). This means that readers
  19 // never need to lock when accessing it. (Locking is necessary among multiple
  20 // writers, however.)
  21 //
  22
  23 void ArrayListBase::Clear()
  24 {
  25     CONTRACTL
  26     {
  27         NOTHROW;
  28         FORBID_FAULT;
  29     }
  30     CONTRACTL_END
  31
  32     ArrayListBlock *block = m_firstBlock.m_next;
  33     while (block != NULL)
  34     {
  35         ArrayListBlock *next = block->m_next;
  36         delete [] block;
  37         block = next;
  38     }
  39     m_firstBlock.m_next = 0;
  40     m_count = 0;
  41 }
  42
  43 PTR_VOID * ArrayListBase::GetPtr(DWORD index) const
  44 {
  45     STATIC_CONTRACT_NOTHROW;
  46     STATIC_CONTRACT_FORBID_FAULT;
  47     STATIC_CONTRACT_CANNOT_TAKE_LOCK;
  48     SUPPORTS_DAC;
  49
  50     _ASSERTE(index < m_count);
  51
  52     ArrayListBlock *b = (ArrayListBlock*)&m_firstBlock;
  53     while (index >= b->m_blockSize)
  54     {
  55         PREFIX_ASSUME(b->m_next != NULL);
  56         index -= b->m_blockSize;
  57         b = b->m_next;
  58     }
  59
  60     return b->m_array + index;
  61 }
  62
  63 #ifndef DACCESS_COMPILE
  64
  65 HRESULT ArrayListBase::Append(void *element)
  66 {
  67     CONTRACTL
  68     {
  69         NOTHROW;
  70         INJECT_FAULT(return E_OUTOFMEMORY;);
  71     }
  72     CONTRACTL_END
  73
  74     ArrayListBlock *b = (ArrayListBlock*)&m_firstBlock;
  75     DWORD           count = m_count;
  76
  77     while (count >= b->m_blockSize)
  78     {
  79         count -= b->m_blockSize;
  80
  81         if (b->m_next == NULL)
  82         {
  83             _ASSERTE(count == 0);
  84
  85             DWORD nextSize = b->m_blockSize * 2;
  86
  87             ArrayListBlock *bNew = (ArrayListBlock *)
  88               new (nothrow) BYTE [sizeof(ArrayListBlock) + nextSize * sizeof(void*)];
  89
  90             if (bNew == NULL)
  91                 return E_OUTOFMEMORY;
  92
  93             bNew->m_next = NULL;
  94             bNew->m_blockSize = nextSize;
  95
  96             b->m_next = bNew;
  97         }
  98
  99         b = b->m_next;
 100     }
 101
 102     b->m_array[count] = element;
 103
 104     m_count++;
 105
 106     return S_OK;
 107 }
 108
 109 #endif // #ifndef DACCESS_COMPILE
 110
 111 DWORD ArrayListBase::FindElement(DWORD start, PTR_VOID element) const
 112 {
 113     CONTRACTL
 114     {
 115         NOTHROW;
 116         FORBID_FAULT;
 117     }
 118     CONTRACTL_END
 119
 120     DWORD index = start;
 121
 122     _ASSERTE(index <= m_count);
 123
 124     ArrayListBlock *b = (ArrayListBlock*)&m_firstBlock;
 125
 126     //
 127     // Skip to the block containing start.
 128     // index should be the index of start in the block.
 129     //
 130
 131     while (b != NULL && index >= b->m_blockSize)
 132     {
 133         index -= b->m_blockSize;
 134         b = b->m_next;
 135     }
 136
 137     //
 138     // Adjust start to be the index of the start of the block
 139     //
 140
 141     start -= index;
 142
 143     //
 144     // Compute max number of entries from the start of the block
 145     //
 146
 147     DWORD max = m_count - start;
 148
 149     while (b != NULL)
 150     {
 151         //
 152         // Compute end of search in this block - either end of the block
 153         // or end of the array
 154         //
 155
 156         DWORD blockMax;
 157         if (max < b->m_blockSize)
 158             blockMax = max;
 159         else
 160             blockMax = b->m_blockSize;
 161
 162         //
 163         // Scan for element, until the end.
 164         //
 165
 166         while (index < blockMax)
 167         {
 168             if (b->m_array[index] == element)
 169                 return start + index;
 170             index++;
 171         }
 172
 173         //
 174         // Otherwise, increment block start index, decrement max count,
 175         // reset index, and go to the next block (if any)
 176         //
 177
 178         start += b->m_blockSize;
 179         max -= b->m_blockSize;
 180         index = 0;
 181         b = b->m_next;
 182     }
 183
 184     return (DWORD) NOT_FOUND;
 185 }
 186
 187 BOOL ArrayListBase::Iterator::Next()
 188 {
 189     LIMITED_METHOD_DAC_CONTRACT;
 190
 191     ++m_index;
 192
 193     if (m_index >= m_remaining)
 194         return FALSE;
 195
 196     if (m_index >= m_block->m_blockSize)
 197     {
 198         m_remaining -= m_block->m_blockSize;
 199         m_index -= m_block->m_blockSize;
 200         m_total += m_block->m_blockSize;
 201         m_block = m_block->m_next;
 202     }
 203
 204     return TRUE;
 205 }
 206
 207 #ifdef DACCESS_COMPILE
 208
 209 void
 210 ArrayListBase::EnumMemoryRegions(CLRDataEnumMemoryFlags flags)
 211 {
 212     SUPPORTS_DAC;
 213
 214     // Assume that 'this' is enumerated, either explicitly
 215     // or because this class is embedded in another.
 216
 217     PTR_ArrayListBlock block = m_firstBlock.m_next;
 218     while (block.IsValid())
 219     {
 220         block.EnumMem();
 221         block = block->m_next;
 222     }
 223 }
 224
 225 #endif // #ifdef DACCESS_COMPILE