yum-mirror/slang

Making it easier to work with shaders

git clone https://git.yummers.dev/yum-mirror/slang

Ellie Hermaszewskaformatf65d756bf

master
branchesmasterall refs →
4.8 KiB159 linesraw
1#ifndef SLANG_CORE_FREE_LIST_H
2#define SLANG_CORE_FREE_LIST_H
3
4#include "slang-common.h"
5#include "slang.h"
6
7#include <stdlib.h>
8#include <string.h>
9
10namespace Slang
11{
12
13#if SLANG_DEBUG
14#define SLANG_FREE_LIST_INIT_MEM
15#endif
16
17#ifdef SLANG_FREE_LIST_INIT_MEM
18#define SLANG_FREE_LIST_INIT_ALLOCATE(ptr) _initAllocate(ptr);
19#define SLANG_FREE_LIST_INIT_DEALLOCATE(ptr) _initDeallocate(ptr);
20#else
21#define SLANG_FREE_LIST_INIT_ALLOCATE(ptr)
22#define SLANG_FREE_LIST_INIT_DEALLOCATE(ptr)
23#endif
24
25/*! \brief A freelist is a simple and fast memory allocator that can allocate and free in any order
26identically sized blocks.
27
28\details A free list is a memory allocation system that performs allocations/deallocations very
29quickly for elements which are all the same size. In a freelist all elements are the same size, and
30elements can be allocated and freed in any order, as long as every deallocation matches every
31allocation. Both allocation and deallocation are O(1), and generally just a few instructions. The
32underlying memory allocator will allocate in large blocks, with multiple elements amortizing a more
33costly large allocation against lots of fast small element allocations. */
34class FreeList
35{
36public:
37    typedef FreeList ThisType;
38
39    enum
40    {
41        DEFAULT_ALIGNMENT = sizeof(void*)
42    };
43
44    /// Free elements are held in a singly linked list. The minimum size of an element is therefore
45    /// a pointer
46    struct Element
47    {
48        Element* m_next;
49    };
50    struct Block
51    {
52        Block* m_next;   ///< The next block
53        uint8_t* m_data; ///< The list of the elements each m_elementSize in size
54    };
55
56    /// Allocate a single element
57    SLANG_FORCE_INLINE void* allocate();
58    /// Deallocate a block that was previously allocated with allocate
59    SLANG_FORCE_INLINE void deallocate(void* data);
60
61    /// Returns true if this is from a valid allocation
62    bool isValidAllocation(const void* dataIn) const;
63
64    /// Get the element size
65    SLANG_FORCE_INLINE size_t getElementSize() const { return m_elementSize; }
66    /// Get the total size of each individual block allocation in bytes
67    SLANG_FORCE_INLINE size_t getBlockSize() const { return m_blockSize; }
68
69    /// Deallocates all elements
70    void deallocateAll();
71    /// Deallocates all, and frees any backing memory (put in initial state)
72    void reset();
73
74    /// Initialize. If called on an already initialized heap, the heap will be deallocated.
75    void init(size_t elementSize, size_t alignment, size_t elemsPerBlock);
76
77    /// Swap this with rhs
78    void swapWith(ThisType& rhs);
79
80    /// Default Ctor
81    FreeList() { _init(); }
82    /// Ctor
83    FreeList(size_t elementSize, size_t alignment, size_t elemsPerBlock)
84    {
85        _init(elementSize, alignment, elemsPerBlock);
86    }
87    /// Dtor
88    ~FreeList();
89
90protected:
91    /// Initializes assuming freelist is not constructed
92    void _init(size_t elementSize, size_t alignment, size_t elemsPerBlock);
93    void* _allocate();
94    void _deallocateBlocks(Block* block);
95    /// Initializes setting everything to empty (doesn't free anything if already allocated)
96    void _init();
97
98    SLANG_FORCE_INLINE static size_t _calcAlignedBlockSize(size_t align)
99    {
100        return (sizeof(Block) + align - 1) & ~(align - 1);
101    }
102
103    void _initAllocate(void* mem);
104    void _initDeallocate(void* mem);
105
106    uint8_t* m_top; ///< The top position of the current block
107    uint8_t* m_end; ///< The end of the current block
108
109    Block* m_activeBlocks; ///< The blocks there are potentially allocations from
110    Block* m_freeBlocks;   ///< Blocks that there are no allocations in
111
112    Element* m_freeElements; ///< A singly linked list of elements available
113
114    size_t m_elementSize;
115    size_t m_alignment;
116    size_t m_blockSize;
117    size_t m_blockAllocationSize; ///< The actual allocation size. Maybe bigger than m_blockSize if
118                                  ///< alignment requires it.
119};
120
121// --------------------------------------------------------------------------
122SLANG_FORCE_INLINE void* FreeList::allocate()
123{
124    // First see if there are any freeElements ready to go
125    {
126        Element* element = m_freeElements;
127        if (element)
128        {
129            m_freeElements = element->m_next;
130            SLANG_FREE_LIST_INIT_ALLOCATE(element)
131            return element;
132        }
133    }
134    if (m_top >= m_end)
135    {
136        return _allocate();
137    }
138    void* data = (void*)m_top;
139    SLANG_FREE_LIST_INIT_ALLOCATE(data)
140
141    m_top += m_elementSize;
142    return data;
143}
144// --------------------------------------------------------------------------
145SLANG_FORCE_INLINE void FreeList::deallocate(void* data)
146{
147    assert(isValidAllocation(data));
148
149    SLANG_FREE_LIST_INIT_DEALLOCATE(data)
150
151    // Put onto the singly linked free element list
152    Element* ele = (Element*)data;
153    ele->m_next = m_freeElements;
154    m_freeElements = ele;
155}
156
157} // namespace Slang
158
159#endif // SLANG_FREE_LIST_H