1 files changed, 116 insertions, 0 deletions
diff --git a/experimental/lfpAlloc/ChunkList.hpp b/experimental/lfpAlloc/ChunkList.hpp
new file mode 100644
index 0000000..760c670
--- /dev/null
+++ b/experimental/lfpAlloc/ChunkList.hpp
@@ -0,0 +1,116 @@
+#ifndef LF_POOL_ALLOC_CHUNK_LIST
+#define LF_POOL_ALLOC_CHUNK_LIST
+
+#include <cstdint>
+#include <atomic>
+#include <type_traits>
+
+#ifndef LFP_ALLOW_BLOCKING
+static_assert(ATOMIC_POINTER_LOCK_FREE == 2,
+              "Atomic pointer is not lock-free.");
+#endif
+
+namespace lfpAlloc {
+
+template <std::size_t Size>
+struct Cell {
+    uint8_t val_[Size];
+    Cell* next_ = this + 1;
+};
+
+// For small types (less than the size of void*), no additional
+// space is needed, so union val_ with next_ to avoid overhead.
+template <>
+struct Cell<0> {
+    Cell() : next_{this + 1} {}
+    union {
+        uint8_t val_[sizeof(Cell*)];
+        Cell* next_;
+    };
+};
+
+template <std::size_t Size, std::size_t AllocationsPerChunk>
+struct Chunk {
+    Chunk() noexcept {
+        auto& last = memBlock_[AllocationsPerChunk - 1];
+        last.next_ = nullptr;
+    }
+    Cell<Size> memBlock_[AllocationsPerChunk];
+};
+
+template <typename T>
+struct Node {
+    Node() : val_(), next_(nullptr) {}
+    Node(const T& val) : val_(val), next_(nullptr) {}
+    T val_;
+    std::atomic<Node<T>*> next_;
+};
+
+template <std::size_t Size, std::size_t AllocationsPerChunk>
+class ChunkList {
+    static constexpr auto CellSize =
+        (Size > sizeof(void*)) ? Size - sizeof(void*) : 0;
+    using Chunk_t = Chunk<CellSize, AllocationsPerChunk>;
+    using Cell_t = Cell<CellSize>;
+
+    using ChunkNode = Node<Chunk_t>;
+    using CellNode = Node<Cell_t*>;
+
+public:
+    static ChunkList& getInstance() {
+        static ChunkList c;
+        return c;
+    }
+
+    Cell_t* allocateChain() {
+        CellNode* recentHead = head_.load();
+        CellNode* currentNext = nullptr;
+        do {
+            // If there are no available chains, allocate a new chunk
+            if (!recentHead) {
+                ChunkNode* currentHandle;
+
+                // Make a new node
+                auto newChunk = new ChunkNode();
+
+                // Add the chunk to the chain
+                do {
+                    currentHandle = handle_.load();
+                    newChunk->next_ = currentHandle;
+                } while (
+                    !handle_.compare_exchange_weak(currentHandle, newChunk));
+                return &newChunk->val_.memBlock_[0];
+            }
+
+            currentNext = recentHead->next_;
+        } while (!head_.compare_exchange_weak(recentHead, currentNext));
+
+        auto retnValue = recentHead->val_;
+        delete recentHead;
+        return retnValue;
+    }
+
+    void deallocateChain(Cell_t* newCell) {
+        if (!newCell) {
+            return;
+        }
+        CellNode* currentHead = head_.load();
+
+        // Construct a new node to be added to the linked list
+        CellNode* newHead = new CellNode(newCell);
+
+        // Add the chain to the linked list
+        do {
+            newHead->next_.store(currentHead, std::memory_order_release);
+        } while (!head_.compare_exchange_weak(currentHead, newHead));
+    }
+
+private:
+    ChunkList() : handle_(nullptr), head_(nullptr) {}
+
+    std::atomic<ChunkNode*> handle_;
+    std::atomic<CellNode*> head_;
+};
+}
+
+#endif