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
6#ifndef ARRAYLIST_H_
7#define ARRAYLIST_H_
8
9#include <daccess.h>
10#include <contract.h>
11#include <stddef.h> // offsetof
12
13//
14// ArrayList is a simple class which is used to contain a growable
15// list of pointers, stored in chunks. Modification is by appending
16// only currently. Access is by index (efficient if the number of
17// elements stays small) and iteration (efficient in all cases).
18//
19// An important property of an ArrayList is that the list remains
20// coherent while it is being modified. This means that readers
21// never need to lock when accessing it.
22//
23
24#ifdef _MSC_VER
25#pragma warning(push)
26#pragma warning(disable : 4200) // Disable zero-sized array warning
27#endif
28
29class ArrayListBase
30{
31 public:
32
33 enum
34 {
35 ARRAY_BLOCK_SIZE_START = 5,
36 };
37
38 private:
39
40 struct ArrayListBlock
41 {
42 SPTR(ArrayListBlock) m_next;
43 DWORD m_blockSize;
44#ifdef _WIN64
45 DWORD m_padding;
46#endif
47 PTR_VOID m_array[0];
48
49#ifdef DACCESS_COMPILE
50 static ULONG32 DacSize(TADDR addr)
51 {
52 LIMITED_METHOD_CONTRACT;
53 return offsetof(ArrayListBlock, m_array) +
54 (*PTR_DWORD(addr + offsetof(ArrayListBlock, m_blockSize)) * sizeof(void*));
55 }
56#endif
57 };
58 typedef SPTR(ArrayListBlock) PTR_ArrayListBlock;
59
60 struct FirstArrayListBlock
61 {
62 PTR_ArrayListBlock m_next;
63 DWORD m_blockSize;
64#ifdef _WIN64
65 DWORD m_padding;
66#endif
67 void * m_array[ARRAY_BLOCK_SIZE_START];
68 };
69
70 typedef DPTR(FirstArrayListBlock) PTR_FirstArrayListBlock;
71
72 DWORD m_count;
73 FirstArrayListBlock m_firstBlock;
74
75 public:
76
77 PTR_VOID *GetPtr(DWORD index) const;
78 PTR_VOID Get(DWORD index) const
79 {
80 WRAPPER_NO_CONTRACT;
81 SUPPORTS_DAC;
82
83 return *GetPtr(index);
84 }
85
86 void Set(DWORD index, PTR_VOID element)
87 {
88 WRAPPER_NO_CONTRACT;
89 STATIC_CONTRACT_SO_INTOLERANT;
90 *GetPtr(index) = element;
91 }
92
93 DWORD GetCount() const { LIMITED_METHOD_DAC_CONTRACT; return m_count; }
94
95 HRESULT Append(void *element);
96
97 enum { NOT_FOUND = -1 };
98 DWORD FindElement(DWORD start, PTR_VOID element) const;
99
100 void Clear();
101
102 void Init()
103 {
104 LIMITED_METHOD_CONTRACT;
105 STATIC_CONTRACT_SO_INTOLERANT;
106
107 m_count = 0;
108 m_firstBlock.m_next = NULL;
109 m_firstBlock.m_blockSize = ARRAY_BLOCK_SIZE_START;
110 }
111
112 void Destroy()
113 {
114 WRAPPER_NO_CONTRACT;
115 STATIC_CONTRACT_SO_INTOLERANT;
116 Clear();
117 }
118
119#ifdef DACCESS_COMPILE
120 void EnumMemoryRegions(CLRDataEnumMemoryFlags flags);
121#endif
122
123 class ConstIterator;
124
125 class Iterator
126 {
127 friend class ArrayListBase;
128 friend class ConstIterator;
129
130 public:
131 BOOL Next();
132
133 void SetEmpty()
134 {
135 LIMITED_METHOD_CONTRACT;
136
137 m_block = NULL;
138 m_index = (DWORD)-1;
139 m_remaining = 0;
140 m_total = 0;
141 }
142
143 PTR_VOID GetElement() {LIMITED_METHOD_DAC_CONTRACT; return m_block->m_array[m_index]; }
144 PTR_VOID * GetElementPtr() {LIMITED_METHOD_CONTRACT; return m_block->m_array + m_index; }
145 DWORD GetIndex() {LIMITED_METHOD_CONTRACT; return m_index + m_total; }
146 void *GetBlock() { return m_block; }
147
148 private:
149 ArrayListBlock* m_block;
150 DWORD m_index;
151 DWORD m_remaining;
152 DWORD m_total;
153 static Iterator Create(ArrayListBlock* block, DWORD remaining)
154 {
155 LIMITED_METHOD_DAC_CONTRACT;
156 STATIC_CONTRACT_SO_INTOLERANT;
157 Iterator i;
158 i.m_block = block;
159 i.m_index = (DWORD) -1;
160 i.m_remaining = remaining;
161 i.m_total = 0;
162 return i;
163 }
164 };
165
166 class ConstIterator
167 {
168 public:
169 ConstIterator(ArrayListBlock *pBlock, DWORD dwRemaining) : m_iterator(Iterator::Create(pBlock, dwRemaining))
170 {
171 }
172
173 BOOL Next()
174 {
175 WRAPPER_NO_CONTRACT;
176 return m_iterator.Next();
177 }
178
179 PTR_VOID GetElement()
180 {
181 WRAPPER_NO_CONTRACT;
182 return m_iterator.GetElement();
183 }
184
185 private:
186 Iterator m_iterator;
187 };
188
189 Iterator Iterate()
190 {
191 STATIC_CONTRACT_SO_INTOLERANT;
192 WRAPPER_NO_CONTRACT;
193 return Iterator::Create((ArrayListBlock*)&m_firstBlock, m_count);
194 }
195
196 ConstIterator Iterate() const
197 {
198 STATIC_CONTRACT_SO_INTOLERANT;
199
200 // Const cast is safe because ConstIterator does not expose any way to modify the block
201 ArrayListBlock *pFirstBlock = const_cast<ArrayListBlock *>(reinterpret_cast<const ArrayListBlock *>(&m_firstBlock));
202 return ConstIterator(pFirstBlock, m_count);
203 }
204
205 // BlockIterator is used for only memory walking, such as prejit save/fixup.
206 // It is not appropriate for other more typical ArrayList use.
207 class BlockIterator
208 {
209 private:
210
211 ArrayListBlock *m_block;
212 DWORD m_remaining;
213
214 friend class ArrayListBase;
215 BlockIterator(ArrayListBlock *block, DWORD remaining)
216 : m_block(block), m_remaining(remaining)
217 {
218 }
219
220 public:
221
222 BOOL Next()
223 {
224 if (m_block != NULL)
225 {
226 // Prevent m_remaining from underflowing - we can have completely empty block at the end.
227 if (m_remaining > m_block->m_blockSize)
228 m_remaining -= m_block->m_blockSize;
229 else
230 m_remaining = 0;
231
232 m_block = m_block->m_next;
233 }
234 return m_block != NULL;
235 }
236
237 void ClearUnusedMemory()
238 {
239 if (m_remaining < m_block->m_blockSize)
240 ZeroMemory(&(m_block->m_array[m_remaining]), (m_block->m_blockSize - m_remaining) * sizeof(void*));
241#ifdef _WIN64
242 m_block->m_padding = 0;
243#endif
244 }
245
246 void **GetNextPtr()
247 {
248 return (void **) &m_block->m_next;
249 }
250
251 void *GetBlock()
252 {
253 return m_block;
254 }
255
256 SIZE_T GetBlockSize()
257 {
258 return offsetof(ArrayListBlock, m_array) + (m_block->m_blockSize * sizeof(void*));
259 }
260 };
261
262 void **GetInitialNextPtr()
263 {
264 return (void **) &m_firstBlock.m_next;
265 }
266
267 BlockIterator IterateBlocks()
268 {
269 return BlockIterator((ArrayListBlock *) &m_firstBlock, m_count);
270 }
271
272};
273
274class ArrayList : public ArrayListBase
275{
276public:
277#ifndef DACCESS_COMPILE
278 ArrayList()
279 {
280 STATIC_CONTRACT_SO_INTOLERANT;
281 WRAPPER_NO_CONTRACT;
282 Init();
283 }
284
285 ~ArrayList()
286 {
287 STATIC_CONTRACT_SO_INTOLERANT;
288 WRAPPER_NO_CONTRACT;
289 Destroy();
290 }
291#endif
292};
293
294/* to be used as static variable - no constructor/destructor, assumes zero
295 initialized memory */
296class ArrayListStatic : public ArrayListBase
297{
298};
299
300typedef DPTR(ArrayListStatic) PTR_ArrayListStatic;
301#ifdef _MSC_VER
302#pragma warning(pop)
303#endif
304
305#endif
306