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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
#ifndef SLANG_CORE_FREE_LIST_H
#define SLANG_CORE_FREE_LIST_H
#include "slang-common.h"
#include "slang.h"
#include <stdlib.h>
#include <string.h>
namespace Slang
{
#if SLANG_DEBUG
#define SLANG_FREE_LIST_INIT_MEM
#endif
#ifdef SLANG_FREE_LIST_INIT_MEM
#define SLANG_FREE_LIST_INIT_ALLOCATE(ptr) _initAllocate(ptr);
#define SLANG_FREE_LIST_INIT_DEALLOCATE(ptr) _initDeallocate(ptr);
#else
#define SLANG_FREE_LIST_INIT_ALLOCATE(ptr)
#define SLANG_FREE_LIST_INIT_DEALLOCATE(ptr)
#endif
/*! \brief A freelist is a simple and fast memory allocator that can allocate and free in any order
identically sized blocks.
\details A free list is a memory allocation system that performs allocations/deallocations very
quickly for elements which are all the same size. In a freelist all elements are the same size, and
elements can be allocated and freed in any order, as long as every deallocation matches every
allocation. Both allocation and deallocation are O(1), and generally just a few instructions. The
underlying memory allocator will allocate in large blocks, with multiple elements amortizing a more
costly large allocation against lots of fast small element allocations. */
class FreeList
{
public:
typedef FreeList ThisType;
enum
{
DEFAULT_ALIGNMENT = sizeof(void*)
};
/// Free elements are held in a singly linked list. The minimum size of an element is therefore
/// a pointer
struct Element
{
Element* m_next;
};
struct Block
{
Block* m_next; ///< The next block
uint8_t* m_data; ///< The list of the elements each m_elementSize in size
};
/// Allocate a single element
SLANG_FORCE_INLINE void* allocate();
/// Deallocate a block that was previously allocated with allocate
SLANG_FORCE_INLINE void deallocate(void* data);
/// Returns true if this is from a valid allocation
bool isValidAllocation(const void* dataIn) const;
/// Get the element size
SLANG_FORCE_INLINE size_t getElementSize() const { return m_elementSize; }
/// Get the total size of each individual block allocation in bytes
SLANG_FORCE_INLINE size_t getBlockSize() const { return m_blockSize; }
/// Deallocates all elements
void deallocateAll();
/// Deallocates all, and frees any backing memory (put in initial state)
void reset();
/// Initialize. If called on an already initialized heap, the heap will be deallocated.
void init(size_t elementSize, size_t alignment, size_t elemsPerBlock);
/// Swap this with rhs
void swapWith(ThisType& rhs);
/// Default Ctor
FreeList() { _init(); }
/// Ctor
FreeList(size_t elementSize, size_t alignment, size_t elemsPerBlock)
{
_init(elementSize, alignment, elemsPerBlock);
}
/// Dtor
~FreeList();
protected:
/// Initializes assuming freelist is not constructed
void _init(size_t elementSize, size_t alignment, size_t elemsPerBlock);
void* _allocate();
void _deallocateBlocks(Block* block);
/// Initializes setting everything to empty (doesn't free anything if already allocated)
void _init();
SLANG_FORCE_INLINE static size_t _calcAlignedBlockSize(size_t align)
{
return (sizeof(Block) + align - 1) & ~(align - 1);
}
void _initAllocate(void* mem);
void _initDeallocate(void* mem);
uint8_t* m_top; ///< The top position of the current block
uint8_t* m_end; ///< The end of the current block
Block* m_activeBlocks; ///< The blocks there are potentially allocations from
Block* m_freeBlocks; ///< Blocks that there are no allocations in
Element* m_freeElements; ///< A singly linked list of elements available
size_t m_elementSize;
size_t m_alignment;
size_t m_blockSize;
size_t m_blockAllocationSize; ///< The actual allocation size. Maybe bigger than m_blockSize if
///< alignment requires it.
};
// --------------------------------------------------------------------------
SLANG_FORCE_INLINE void* FreeList::allocate()
{
// First see if there are any freeElements ready to go
{
Element* element = m_freeElements;
if (element)
{
m_freeElements = element->m_next;
SLANG_FREE_LIST_INIT_ALLOCATE(element)
return element;
}
}
if (m_top >= m_end)
{
return _allocate();
}
void* data = (void*)m_top;
SLANG_FREE_LIST_INIT_ALLOCATE(data)
m_top += m_elementSize;
return data;
}
// --------------------------------------------------------------------------
SLANG_FORCE_INLINE void FreeList::deallocate(void* data)
{
assert(isValidAllocation(data));
SLANG_FREE_LIST_INIT_DEALLOCATE(data)
// Put onto the singly linked free element list
Element* ele = (Element*)data;
ele->m_next = m_freeElements;
m_freeElements = ele;
}
} // namespace Slang
#endif // SLANG_FREE_LIST_H
|
