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
23void 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
43PTR_VOID * ArrayListBase::GetPtr(DWORD index) const
44{
45 STATIC_CONTRACT_NOTHROW;
46 STATIC_CONTRACT_FORBID_FAULT;
47 STATIC_CONTRACT_SO_TOLERANT;
48 STATIC_CONTRACT_CANNOT_TAKE_LOCK;
49 SUPPORTS_DAC;
50
51 _ASSERTE(index < m_count);
52
53 ArrayListBlock *b = (ArrayListBlock*)&m_firstBlock;
54 while (index >= b->m_blockSize)
55 {
56 PREFIX_ASSUME(b->m_next != NULL);
57 index -= b->m_blockSize;
58 b = b->m_next;
59 }
60
61 return b->m_array + index;
62}
63
64#ifndef DACCESS_COMPILE
65
66HRESULT ArrayListBase::Append(void *element)
67{
68 CONTRACTL
69 {
70 NOTHROW;
71 INJECT_FAULT(return E_OUTOFMEMORY;);
72 }
73 CONTRACTL_END
74
75 ArrayListBlock *b = (ArrayListBlock*)&m_firstBlock;
76 DWORD count = m_count;
77
78 while (count >= b->m_blockSize)
79 {
80 count -= b->m_blockSize;
81
82 if (b->m_next == NULL)
83 {
84 _ASSERTE(count == 0);
85
86 DWORD nextSize = b->m_blockSize * 2;
87
88 ArrayListBlock *bNew = (ArrayListBlock *)
89 new (nothrow) BYTE [sizeof(ArrayListBlock) + nextSize * sizeof(void*)];
90
91 if (bNew == NULL)
92 return E_OUTOFMEMORY;
93
94 bNew->m_next = NULL;
95 bNew->m_blockSize = nextSize;
96
97 b->m_next = bNew;
98 }
99
100 b = b->m_next;
101 }
102
103 b->m_array[count] = element;
104
105 m_count++;
106
107 return S_OK;
108}
109
110#endif // #ifndef DACCESS_COMPILE
111
112DWORD ArrayListBase::FindElement(DWORD start, PTR_VOID element) const
113{
114 CONTRACTL
115 {
116 NOTHROW;
117 FORBID_FAULT;
118 }
119 CONTRACTL_END
120
121 DWORD index = start;
122
123 _ASSERTE(index <= m_count);
124
125 ArrayListBlock *b = (ArrayListBlock*)&m_firstBlock;
126
127 //
128 // Skip to the block containing start.
129 // index should be the index of start in the block.
130 //
131
132 while (b != NULL && index >= b->m_blockSize)
133 {
134 index -= b->m_blockSize;
135 b = b->m_next;
136 }
137
138 //
139 // Adjust start to be the index of the start of the block
140 //
141
142 start -= index;
143
144 //
145 // Compute max number of entries from the start of the block
146 //
147
148 DWORD max = m_count - start;
149
150 while (b != NULL)
151 {
152 //
153 // Compute end of search in this block - either end of the block
154 // or end of the array
155 //
156
157 DWORD blockMax;
158 if (max < b->m_blockSize)
159 blockMax = max;
160 else
161 blockMax = b->m_blockSize;
162
163 //
164 // Scan for element, until the end.
165 //
166
167 while (index < blockMax)
168 {
169 if (b->m_array[index] == element)
170 return start + index;
171 index++;
172 }
173
174 //
175 // Otherwise, increment block start index, decrement max count,
176 // reset index, and go to the next block (if any)
177 //
178
179 start += b->m_blockSize;
180 max -= b->m_blockSize;
181 index = 0;
182 b = b->m_next;
183 }
184
185 return (DWORD) NOT_FOUND;
186}
187
188BOOL ArrayListBase::Iterator::Next()
189{
190 LIMITED_METHOD_DAC_CONTRACT;
191
192 ++m_index;
193
194 if (m_index >= m_remaining)
195 return FALSE;
196
197 if (m_index >= m_block->m_blockSize)
198 {
199 m_remaining -= m_block->m_blockSize;
200 m_index -= m_block->m_blockSize;
201 m_total += m_block->m_blockSize;
202 m_block = m_block->m_next;
203 }
204
205 return TRUE;
206}
207
208#ifdef DACCESS_COMPILE
209
210void
211ArrayListBase::EnumMemoryRegions(CLRDataEnumMemoryFlags flags)
212{
213 SUPPORTS_DAC;
214
215 // Assume that 'this' is enumerated, either explicitly
216 // or because this class is embedded in another.
217
218 PTR_ArrayListBlock block = m_firstBlock.m_next;
219 while (block.IsValid())
220 {
221 block.EnumMem();
222 block = block->m_next;
223 }
224}
225
226#endif // #ifdef DACCESS_COMPILE
227