summaryrefslogtreecommitdiffstats
path: root/source
diff options
context:
space:
mode:
Diffstat (limited to 'source')
-rw-r--r--source/core/core.vcxproj2
-rw-r--r--source/core/slang-com-ptr.h19
-rw-r--r--source/core/slang-free-list.cpp216
-rw-r--r--source/core/slang-free-list.h142
4 files changed, 368 insertions, 11 deletions
diff --git a/source/core/core.vcxproj b/source/core/core.vcxproj
index 2a9a9a4fe..77e91b32f 100644
--- a/source/core/core.vcxproj
+++ b/source/core/core.vcxproj
@@ -32,6 +32,7 @@
<ClInclude Include="secure-crt.h" />
<ClInclude Include="slang-com-ptr.h" />
<ClInclude Include="slang-defines.h" />
+ <ClInclude Include="slang-free-list.h" />
<ClInclude Include="slang-io.h" />
<ClInclude Include="slang-math.h" />
<ClInclude Include="slang-result.h" />
@@ -44,6 +45,7 @@
</ItemGroup>
<ItemGroup>
<ClCompile Include="platform.cpp" />
+ <ClCompile Include="slang-free-list.cpp" />
<ClCompile Include="slang-io.cpp" />
<ClCompile Include="slang-string.cpp" />
<ClCompile Include="stream.cpp" />
diff --git a/source/core/slang-com-ptr.h b/source/core/slang-com-ptr.h
index 729b6b266..9f6651306 100644
--- a/source/core/slang-com-ptr.h
+++ b/source/core/slang-com-ptr.h
@@ -51,21 +51,18 @@ struct Guid
SLANG_FORCE_INLINE bool operator==(const Guid& aIn, const Guid& bIn)
{
+ // Use the largest type the honors the alignment of Guid
+ typedef uint32_t CmpType;
struct GuidCompare
{
- enum { kNum = sizeof(Guid) / sizeof(size_t) };
Guid guid;
- size_t data[kNum];
+ CmpType data[sizeof(Guid) / sizeof(CmpType)];
};
- const GuidCompare& a = reinterpret_cast<const GuidCompare&>(aIn);
- const GuidCompare& b = reinterpret_cast<const GuidCompare&>(bIn);
-
- switch (GuidCompare::kNum)
- {
- case 2: return ((a.data[0] ^ b.data[0]) | (a.data[1] ^ b.data[1])) == 0;
- case 4: return ((a.data[0] ^ b.data[0]) | (a.data[1] ^ b.data[1]) | (a.data[2] ^ b.data[2]) | (a.data[3] ^ b.data[3]) ) == 0;
- default: return false;
- }
+ // Type pun - so compiler can 'see' the pun and not break aliasing rules
+ const CmpType* a = reinterpret_cast<const GuidCompare&>(aIn).data;
+ const CmpType* b = reinterpret_cast<const GuidCompare&>(bIn).data;
+ // Make the guid comparison a single branch, by not using short circuit
+ return ((a[0] ^ b[0]) | (a[1] ^ b[1]) | (a[2] ^ b[2]) | (a[3] ^ b[3])) == 0;
}
SLANG_FORCE_INLINE bool operator!=(const Guid& a, const Guid& b)
diff --git a/source/core/slang-free-list.cpp b/source/core/slang-free-list.cpp
new file mode 100644
index 000000000..0701558aa
--- /dev/null
+++ b/source/core/slang-free-list.cpp
@@ -0,0 +1,216 @@
+#include "slang-free-list.h"
+
+//#include "list.h"
+
+namespace Slang {
+
+FreeList::~FreeList()
+{
+ _deallocateBlocks(m_activeBlocks);
+ _deallocateBlocks(m_freeBlocks);
+}
+
+void FreeList::_init()
+{
+ m_top = nullptr;
+ m_end = nullptr;
+
+ m_activeBlocks = nullptr;
+ m_freeBlocks = nullptr;
+
+ m_freeElements = nullptr;
+
+ m_elementSize = 0;
+ m_alignment = 1;
+ m_blockSize = 0;
+ m_blockAllocationSize = 0;
+}
+
+void FreeList::_init(size_t elementSize, size_t alignment, size_t elemsPerBlock)
+{
+ alignment = (alignment < sizeof(void*)) ? sizeof(void*) : alignment;
+
+ // Alignment must be a power of 2
+ assert(((alignment - 1) & alignment) == 0);
+
+ // The elementSize must at least be
+ elementSize = (elementSize >= alignment) ? elementSize : alignment;
+ m_blockSize = elementSize * elemsPerBlock;
+ m_elementSize = elementSize;
+ m_alignment = alignment;
+
+ // Calculate the block size need, correcting for alignment
+ const size_t alignedBlockSize = (alignment <= DEFAULT_ALIGNMENT) ?
+ _calcAlignedBlockSize(DEFAULT_ALIGNMENT) :
+ _calcAlignedBlockSize(alignment);
+
+ // Make the block struct size aligned
+ m_blockAllocationSize = m_blockSize + alignedBlockSize;
+
+ m_top = nullptr;
+ m_end = nullptr;
+
+ m_activeBlocks = nullptr;
+ m_freeBlocks = nullptr; ///< Blocks that there are no allocations in
+
+ m_freeElements = nullptr;
+}
+
+void FreeList::init(size_t elementSize, size_t alignment, size_t elemsPerBlock)
+{
+ _deallocateBlocks(m_activeBlocks);
+ _deallocateBlocks(m_freeBlocks);
+ _init(elementSize, alignment, elemsPerBlock);
+}
+
+void FreeList::_deallocateBlocks(Block* block)
+{
+ while (block)
+ {
+ Block* next = block->m_next;
+
+#ifdef SLANG_FREE_LIST_INIT_MEM
+ Memory::set(block, 0xfd, m_blockAllocationSize);
+#endif
+
+ ::free(block); // deallocate(block, m_blockAllocationSize);
+ block = next;
+ }
+}
+
+bool FreeList::isValidAllocation(const void* dataIn) const
+{
+ uint8_t* data = (uint8_t*)dataIn;
+
+ Block* block = m_activeBlocks;
+ while (block)
+ {
+ uint8_t* start = block->m_data;
+ uint8_t* end = start + m_blockSize;
+
+ if (data >= start && data < end)
+ {
+ // Check it's aligned correctly
+ if ((data - start) % m_elementSize)
+ {
+ return false;
+ }
+
+ // Non allocated data is between top and end
+ if (data >= m_top && data < m_end)
+ {
+ return false;
+ }
+
+ // It can't be in the free list
+ Element* ele = m_freeElements;
+ while (ele)
+ {
+ if (ele == (Element*)data)
+ {
+ return false;
+ }
+
+ ele = ele->m_next;
+ }
+ return true;
+ }
+
+ block = block->m_next;
+ }
+ // It's not in an active block -> it cannot be a valid allocation
+ return false;
+}
+
+void* FreeList::_allocate()
+{
+ Block* block = m_freeBlocks;
+ if (block)
+ {
+ /// Remove from the free blocks
+ m_freeBlocks = block->m_next;
+ }
+ else
+ {
+ //block = (Block*)m_allocator->allocate(m_blockAllocationSize);
+ block = (Block*)::malloc(m_blockAllocationSize);
+ if (!block)
+ {
+ // Allocation failed... doh
+ return nullptr;
+ }
+ // Do the alignment
+ {
+ size_t fix = (size_t(block) + sizeof(Block) + m_alignment - 1) & ~(m_alignment - 1);
+ block->m_data = (uint8_t*)fix;
+ }
+ }
+
+ // Attach to the active blocks
+ block->m_next = m_activeBlocks;
+ m_activeBlocks = block;
+
+ // Set up top and end
+ m_end = block->m_data + m_blockSize;
+
+ // Return the first element
+ uint8_t* element = block->m_data;
+ m_top = element + m_elementSize;
+
+ SLANG_FREE_LIST_INIT_ALLOCATE(element)
+
+ return element;
+}
+
+void FreeList::deallocateAll()
+{
+ Block* block = m_activeBlocks;
+ if (block)
+ {
+ // Find the end block
+ while (block->m_next)
+ {
+#ifdef SLANG_FREE_LIST_INIT_MEM
+ Memory::set(block->m_data, 0xfd, m_blockSize);
+#endif
+ block = block->m_next;
+ }
+ // Attach to the freeblocks
+ block->m_next = m_freeBlocks;
+ // The list is now all freelists
+ m_freeBlocks = m_activeBlocks;
+ // There are no active blocks
+ m_activeBlocks = nullptr;
+ }
+
+ m_top = nullptr;
+ m_end = nullptr;
+}
+
+void FreeList::reset()
+{
+ _deallocateBlocks(m_activeBlocks);
+ _deallocateBlocks(m_freeBlocks);
+
+ m_top = nullptr;
+ m_end = nullptr;
+
+ m_activeBlocks = nullptr;
+ m_freeBlocks = nullptr;
+
+ m_freeElements = nullptr;
+}
+
+
+void FreeList::_initAllocate(void* mem)
+{
+ ::memset(mem, 0xcd, m_elementSize);
+}
+
+void FreeList::_initDeallocate(void* mem)
+{
+ ::memset(mem, 0xfd, m_elementSize);
+}
+
+} // namespace Slang
+
diff --git a/source/core/slang-free-list.h b/source/core/slang-free-list.h
new file mode 100644
index 000000000..10f0a39ba
--- /dev/null
+++ b/source/core/slang-free-list.h
@@ -0,0 +1,142 @@
+#ifndef SLANG_FREE_LIST_H
+#define SLANG_FREE_LIST_H
+
+#include "slang-defines.h"
+#include "slang-result.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);
+
+ /// 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 \ No newline at end of file
generated by cgit v1.2.3 (git 2.39.1) at 2026-06-01 20:23:02 +0000