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