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#ifndef _GCINFOARRAYLIST_H_
6#define _GCINFOARRAYLIST_H_
7
8// GCInfoArrayList is basically a more efficient linked list--it's useful for accumulating
9// lots of small fixed-size allocations into larger chunks which in a typical linked list
10// would incur an unnecessarily high amount of overhead.
11
12class GcInfoArrayListBase
13{
14private:
15 static const size_t GrowthFactor = 2;
16
17protected:
18 friend class IteratorBase;
19
20 struct ChunkBase
21 {
22 ChunkBase* m_next; // actually GcInfoArrayListChunk<ElementType>*
23 };
24
25 class IteratorBase
26 {
27 protected:
28 IteratorBase(GcInfoArrayListBase* list, size_t firstChunkCapacity);
29 ChunkBase* GetNextChunk(size_t& elementCount);
30
31 private:
32 GcInfoArrayListBase* m_list;
33 ChunkBase* m_currentChunk;
34 size_t m_currentChunkCount;
35 };
36
37 GcInfoArrayListBase(IAllocator* allocator);
38 virtual ~GcInfoArrayListBase();
39
40 void AppendNewChunk(size_t firstChunkCapacity, size_t elementSize, size_t chunkAlignment);
41
42public:
43 size_t Count()
44 {
45 return m_itemCount;
46 }
47
48protected:
49 IAllocator* m_allocator;
50 ChunkBase* m_firstChunk; // actually GcInfoArrayListChunk<ElementType>*
51 ChunkBase* m_lastChunk; // actually GcInfoArrayListChunk<ElementType>*
52 size_t m_lastChunkCount;
53 size_t m_lastChunkCapacity;
54 size_t m_itemCount;
55};
56
57template <typename ElementType, size_t FirstChunkCapacity>
58class GcInfoArrayList : public GcInfoArrayListBase
59{
60private:
61 struct Chunk : public ChunkBase
62 {
63 ElementType m_items[];
64 };
65
66public:
67 friend class Iterator;
68
69 struct Iterator : IteratorBase
70 {
71 Iterator(GcInfoArrayList* list)
72 : IteratorBase(list, FirstChunkCapacity)
73 {
74 }
75
76 ElementType* GetNext(size_t* elementCount)
77 {
78 Chunk* chunk = reinterpret_cast<Chunk*>(GetNextChunk(*elementCount));
79 return chunk == nullptr ? nullptr : &chunk->m_items[0];
80 }
81 };
82
83 GcInfoArrayList(IAllocator* allocator)
84 : GcInfoArrayListBase(allocator)
85 {
86 }
87
88 ElementType* Append()
89 {
90 if (m_lastChunk == nullptr || m_lastChunkCount == m_lastChunkCapacity)
91 {
92 AppendNewChunk(FirstChunkCapacity, sizeof(ElementType), __alignof(ElementType));
93 }
94
95 m_itemCount++;
96 m_lastChunkCount++;
97 return &reinterpret_cast<Chunk*>(m_lastChunk)->m_items[m_lastChunkCount - 1];
98 }
99
100 void CopyTo(ElementType* dest)
101 {
102 Iterator iter(this);
103 ElementType* source;
104 size_t elementCount;
105
106 while (source = iter.GetNext(&elementCount), source != nullptr)
107 {
108 memcpy(dest, source, elementCount * sizeof(ElementType));
109 dest += elementCount;
110 }
111 }
112};
113
114#endif
115