diff options
Diffstat (limited to 'third_party/immer/immer/heap')
| -rw-r--r-- | third_party/immer/immer/heap/cpp_heap.hpp | 41 | ||||
| -rw-r--r-- | third_party/immer/immer/heap/debug_size_heap.hpp | 69 | ||||
| -rw-r--r-- | third_party/immer/immer/heap/free_list_heap.hpp | 83 | ||||
| -rw-r--r-- | third_party/immer/immer/heap/free_list_node.hpp | 24 | ||||
| -rw-r--r-- | third_party/immer/immer/heap/gc_heap.hpp | 127 | ||||
| -rw-r--r-- | third_party/immer/immer/heap/heap_policy.hpp | 141 | ||||
| -rw-r--r-- | third_party/immer/immer/heap/identity_heap.hpp | 34 | ||||
| -rw-r--r-- | third_party/immer/immer/heap/malloc_heap.hpp | 44 | ||||
| -rw-r--r-- | third_party/immer/immer/heap/split_heap.hpp | 40 | ||||
| -rw-r--r-- | third_party/immer/immer/heap/tags.hpp | 16 | ||||
| -rw-r--r-- | third_party/immer/immer/heap/thread_local_free_list_heap.hpp | 55 | ||||
| -rw-r--r-- | third_party/immer/immer/heap/unsafe_free_list_heap.hpp | 109 | ||||
| -rw-r--r-- | third_party/immer/immer/heap/with_data.hpp | 43 |
13 files changed, 826 insertions, 0 deletions
diff --git a/third_party/immer/immer/heap/cpp_heap.hpp b/third_party/immer/immer/heap/cpp_heap.hpp new file mode 100644 index 0000000000..cd129b406b --- /dev/null +++ b/third_party/immer/immer/heap/cpp_heap.hpp @@ -0,0 +1,41 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <memory> + +namespace immer { + +/*! + * A heap that uses `operator new` and `operator delete`. + */ +struct cpp_heap +{ + /*! + * Returns a pointer to a memory region of size `size`, if the + * allocation was successful, and throws otherwise. + */ + template <typename... Tags> + static void* allocate(std::size_t size, Tags...) + { + return ::operator new(size); + } + + /*! + * Releases a memory region `data` that was previously returned by + * `allocate`. One must not use nor deallocate again a memory + * region that once it has been deallocated. + */ + static void deallocate(std::size_t size, void* data) + { + ::operator delete(data); + } +}; + +} // namespace immer diff --git a/third_party/immer/immer/heap/debug_size_heap.hpp b/third_party/immer/immer/heap/debug_size_heap.hpp new file mode 100644 index 0000000000..d5288c646f --- /dev/null +++ b/third_party/immer/immer/heap/debug_size_heap.hpp @@ -0,0 +1,69 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <immer/config.hpp> +#include <immer/heap/identity_heap.hpp> + +#include <cassert> +#include <cstddef> +#include <type_traits> +#include <memory> + +namespace immer { + +#if IMMER_ENABLE_DEBUG_SIZE_HEAP + +/*! + * A heap that in debug mode ensures that the sizes for allocation and + * deallocation do match. + */ +template <typename Base> +struct debug_size_heap +{ +#if defined(__MINGW32__) && !defined(__MINGW64__) + // There is a bug in MinGW 32bit: + // https://sourceforge.net/p/mingw-w64/bugs/778/ It causes different + // versions of std::max_align_t to be defined, depending on inclusion order + // of stddef.h and stdint.h. As we have no control over the inclusion order + // here (as it might be set in stone by the outside world), we can't easily + // pin it to one of both versions of std::max_align_t. This means, we have + // to hardcode extra_size for MinGW 32bit builds until the mentioned bug is + // fixed. + constexpr static auto extra_size = 8; +#else + constexpr static auto extra_size = sizeof( + std::aligned_storage_t<sizeof(std::size_t), alignof(std::max_align_t)>); +#endif + + template <typename... Tags> + static void* allocate(std::size_t size, Tags... tags) + { + auto p = (std::size_t*) Base::allocate(size + extra_size, tags...); + new (p) std::size_t{size}; + return ((char*) p) + extra_size; + } + + template <typename... Tags> + static void deallocate(std::size_t size, void* data, Tags... tags) + { + auto p = (std::size_t*) (((char*) data) - extra_size); + assert(*p == size); + Base::deallocate(size + extra_size, p, tags...); + } +}; + +#else // IMMER_ENABLE_DEBUG_SIZE_HEAP + +template <typename Base> +using debug_size_heap = identity_heap<Base>; + +#endif // !IMMER_ENABLE_DEBUG_SIZE_HEAP + +} // namespace immer diff --git a/third_party/immer/immer/heap/free_list_heap.hpp b/third_party/immer/immer/heap/free_list_heap.hpp new file mode 100644 index 0000000000..dc25b10184 --- /dev/null +++ b/third_party/immer/immer/heap/free_list_heap.hpp @@ -0,0 +1,83 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <immer/heap/free_list_node.hpp> +#include <immer/heap/with_data.hpp> + +#include <atomic> +#include <cassert> + +namespace immer { + +/*! + * Adaptor that does not release the memory to the parent heap but + * instead it keeps the memory in a thread-safe global free list. Must + * be preceded by a `with_data<free_list_node, ...>` heap adaptor. + * + * @tparam Size Maximum size of the objects to be allocated. + * @tparam Base Type of the parent heap. + */ +template <std::size_t Size, std::size_t Limit, typename Base> +struct free_list_heap : Base +{ + using base_t = Base; + + template <typename... Tags> + static void* allocate(std::size_t size, Tags...) + { + assert(size <= sizeof(free_list_node) + Size); + assert(size >= sizeof(free_list_node)); + + free_list_node* n; + do { + n = head().data; + if (!n) { + auto p = base_t::allocate(Size + sizeof(free_list_node)); + return static_cast<free_list_node*>(p); + } + } while (!head().data.compare_exchange_weak(n, n->next)); + head().count.fetch_sub(1u, std::memory_order_relaxed); + return n; + } + + template <typename... Tags> + static void deallocate(std::size_t size, void* data, Tags...) + { + assert(size <= sizeof(free_list_node) + Size); + assert(size >= sizeof(free_list_node)); + + // we use relaxed, because we are fine with temporarily having + // a few more/less buffers in free list + if (head().count.load(std::memory_order_relaxed) >= Limit) { + base_t::deallocate(Size + sizeof(free_list_node), data); + } else { + auto n = static_cast<free_list_node*>(data); + do { + n->next = head().data; + } while (!head().data.compare_exchange_weak(n->next, n)); + head().count.fetch_add(1u, std::memory_order_relaxed); + } + } + +private: + struct head_t + { + std::atomic<free_list_node*> data; + std::atomic<std::size_t> count; + }; + + static head_t& head() + { + static head_t head_{{nullptr}, {0}}; + return head_; + } +}; + +} // namespace immer diff --git a/third_party/immer/immer/heap/free_list_node.hpp b/third_party/immer/immer/heap/free_list_node.hpp new file mode 100644 index 0000000000..acab4779aa --- /dev/null +++ b/third_party/immer/immer/heap/free_list_node.hpp @@ -0,0 +1,24 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <immer/heap/with_data.hpp> + +namespace immer { + +struct free_list_node +{ + free_list_node* next; +}; + +template <typename Base> +struct with_free_list_node : with_data<free_list_node, Base> +{}; + +} // namespace immer diff --git a/third_party/immer/immer/heap/gc_heap.hpp b/third_party/immer/immer/heap/gc_heap.hpp new file mode 100644 index 0000000000..8494bd2669 --- /dev/null +++ b/third_party/immer/immer/heap/gc_heap.hpp @@ -0,0 +1,127 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <immer/config.hpp> +#include <immer/heap/tags.hpp> + +#if IMMER_HAS_LIBGC +#include <gc/gc.h> +#else +#error "Using garbage collection requires libgc" +#endif + +#include <cstdlib> +#include <memory> + +namespace immer { + +#ifdef __APPLE__ +#define IMMER_GC_REQUIRE_INIT 1 +#else +#define IMMER_GC_REQUIRE_INIT 0 +#endif + +#if IMMER_GC_REQUIRE_INIT + +namespace detail { + +template <int Dummy = 0> +struct gc_initializer +{ + gc_initializer() { GC_init(); } + static gc_initializer init; +}; + +template <int D> +gc_initializer<D> gc_initializer<D>::init{}; + +inline void gc_initializer_guard() +{ + static gc_initializer<> init_ = gc_initializer<>::init; + (void) init_; +} + +} // namespace detail + +#define IMMER_GC_INIT_GUARD_ ::immer::detail::gc_initializer_guard() + +#else + +#define IMMER_GC_INIT_GUARD_ + +#endif // IMMER_GC_REQUIRE_INIT + +/*! + * Heap that uses a tracing garbage collector. + * + * @rst + * + * This heap uses the `Boehm's conservative garbage collector`_ under + * the hood. This is a tracing garbage collector that automatically + * reclaims unused memory. Thus, it is not needed to call + * ``deallocate()`` in order to release memory. + * + * .. admonition:: Dependencies + * :class: tip + * + * In order to use this header file, you need to make sure that + * Boehm's ``libgc`` is your include path and link to its binary + * library. + * + * .. caution:: Memory that is allocated with the standard ``malloc`` + * and ``free`` is not visible to ``libgc`` when it is looking for + * references. This means that if, let's say, you store a + * :cpp:class:`immer::vector` using a ``gc_heap`` inside a + * ``std::vector`` that uses a standard allocator, the memory of + * the former might be released automatically at unexpected times + * causing crashes. + * + * .. caution:: When using a ``gc_heap`` in combination with immutable + * containers, the destructors of the contained objects will never + * be called. It is ok to store containers inside containers as + * long as all of them use a ``gc_heap`` consistently, but storing + * other kinds of objects with relevant destructors + * (e.g. containers with reference counting or other kinds of + * *resource handles*) might cause memory leaks and other problems. + * + * .. _boehm's conservative garbage collector: https://github.com/ivmai/bdwgc + * + * @endrst + */ +class gc_heap +{ +public: + static void* allocate(std::size_t n) + { + IMMER_GC_INIT_GUARD_; + auto p = GC_malloc(n); + if (IMMER_UNLIKELY(!p)) + throw std::bad_alloc{}; + return p; + } + + static void* allocate(std::size_t n, norefs_tag) + { + IMMER_GC_INIT_GUARD_; + auto p = GC_malloc_atomic(n); + if (IMMER_UNLIKELY(!p)) + throw std::bad_alloc{}; + return p; + } + + static void deallocate(std::size_t, void* data) { GC_free(data); } + + static void deallocate(std::size_t, void* data, norefs_tag) + { + GC_free(data); + } +}; + +} // namespace immer diff --git a/third_party/immer/immer/heap/heap_policy.hpp b/third_party/immer/immer/heap/heap_policy.hpp new file mode 100644 index 0000000000..582c113f33 --- /dev/null +++ b/third_party/immer/immer/heap/heap_policy.hpp @@ -0,0 +1,141 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <immer/config.hpp> +#include <immer/heap/debug_size_heap.hpp> +#include <immer/heap/free_list_heap.hpp> +#include <immer/heap/split_heap.hpp> +#include <immer/heap/thread_local_free_list_heap.hpp> + +#include <algorithm> +#include <cstdlib> + +namespace immer { + +/*! + * Heap policy that unconditionally uses its `Heap` argument. + */ +template <typename Heap> +struct heap_policy +{ + using type = Heap; + + template <std::size_t> + struct optimized + { + using type = Heap; + }; +}; + +template <typename Deriv, typename HeapPolicy> +struct enable_optimized_heap_policy +{ + static void* operator new(std::size_t size) + { + using heap_type = + typename HeapPolicy ::template optimized<sizeof(Deriv)>::type; + + return heap_type::allocate(size); + } + + static void operator delete(void* data, std::size_t size) + { + using heap_type = + typename HeapPolicy ::template optimized<sizeof(Deriv)>::type; + + heap_type::deallocate(size, data); + } +}; + +/*! + * Heap policy that returns a heap with a free list of objects + * of `max_size = max(Sizes...)` on top an underlying `Heap`. Note + * these two properties of the resulting heap: + * + * - Allocating an object that is bigger than `max_size` may trigger + * *undefined behavior*. + * + * - Allocating an object of size less than `max_size` still + * returns an object of `max_size`. + * + * Basically, this heap will always return objects of `max_size`. + * When an object is freed, it does not directly invoke `std::free`, + * but it keeps the object in a global linked list instead. When a + * new object is requested, it does not need to call `std::malloc` but + * it can directly pop and return the other object from the global + * list, a much faster operation. + * + * This actually creates a hierarchy with two free lists: + * + * - A `thread_local` free list is used first. It does not need any + * kind of synchronization and is very fast. When the thread + * finishes, its contents are returned to the next free list. + * + * - A global free list using lock-free access via atomics. + * + * @tparam Heap Heap to be used when the free list is empty. + * + * @rst + * + * .. tip:: For many applications that use immutable data structures + * significantly, this is actually the best heap policy, and it + * might become the default in the future. + * + * Note that most our data structures internally use trees with the + * same big branching factors. This means that all *vectors*, + * *maps*, etc. can just allocate elements from the same free-list + * optimized heap. Not only does this lowers the allocation time, + * but also makes up for more efficient *cache utilization*. When + * a new node is needed, there are high chances the allocator will + * return a node that was just accessed. When batches of immutable + * updates are made, this can make a significant difference. + * + * @endrst + */ +template <typename Heap, std::size_t Limit = default_free_list_size> +struct free_list_heap_policy +{ + using type = debug_size_heap<Heap>; + + template <std::size_t Size> + struct optimized + { + using type = + split_heap<Size, + with_free_list_node<thread_local_free_list_heap< + Size, + Limit, + free_list_heap<Size, Limit, debug_size_heap<Heap>>>>, + debug_size_heap<Heap>>; + }; +}; + +/*! + * Similar to @ref free_list_heap_policy, but it assumes no + * multi-threading, so a single global free list with no concurrency + * checks is used. + */ +template <typename Heap, std::size_t Limit = default_free_list_size> +struct unsafe_free_list_heap_policy +{ + using type = Heap; + + template <std::size_t Size> + struct optimized + { + using type = split_heap< + Size, + with_free_list_node< + unsafe_free_list_heap<Size, Limit, debug_size_heap<Heap>>>, + debug_size_heap<Heap>>; + }; +}; + +} // namespace immer diff --git a/third_party/immer/immer/heap/identity_heap.hpp b/third_party/immer/immer/heap/identity_heap.hpp new file mode 100644 index 0000000000..032cb3f221 --- /dev/null +++ b/third_party/immer/immer/heap/identity_heap.hpp @@ -0,0 +1,34 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <cstdlib> + +namespace immer { + +/*! + * A heap that simply passes on to the parent heap. + */ +template <typename Base> +struct identity_heap : Base +{ + template <typename... Tags> + static void* allocate(std::size_t size, Tags... tags) + { + return Base::allocate(size, tags...); + } + + template <typename... Tags> + static void deallocate(std::size_t size, void* data, Tags... tags) + { + Base::deallocate(size, data, tags...); + } +}; + +} // namespace immer diff --git a/third_party/immer/immer/heap/malloc_heap.hpp b/third_party/immer/immer/heap/malloc_heap.hpp new file mode 100644 index 0000000000..a0074d17c0 --- /dev/null +++ b/third_party/immer/immer/heap/malloc_heap.hpp @@ -0,0 +1,44 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <immer/config.hpp> + +#include <cstdlib> +#include <memory> + +namespace immer { + +/*! + * A heap that uses `std::malloc` and `std::free` to manage memory. + */ +struct malloc_heap +{ + /*! + * Returns a pointer to a memory region of size `size`, if the + * allocation was successful and throws `std::bad_alloc` otherwise. + */ + template <typename... Tags> + static void* allocate(std::size_t size, Tags...) + { + auto p = std::malloc(size); + if (IMMER_UNLIKELY(!p)) + throw std::bad_alloc{}; + return p; + } + + /*! + * Releases a memory region `data` that was previously returned by + * `allocate`. One must not use nor deallocate again a memory + * region that once it has been deallocated. + */ + static void deallocate(std::size_t, void* data) { std::free(data); } +}; + +} // namespace immer diff --git a/third_party/immer/immer/heap/split_heap.hpp b/third_party/immer/immer/heap/split_heap.hpp new file mode 100644 index 0000000000..37272d30ec --- /dev/null +++ b/third_party/immer/immer/heap/split_heap.hpp @@ -0,0 +1,40 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <atomic> +#include <cassert> + +namespace immer { + +/*! + * Adaptor that uses `SmallHeap` for allocations that are smaller or + * equal to `Size` and `BigHeap` otherwise. + */ +template <std::size_t Size, typename SmallHeap, typename BigHeap> +struct split_heap +{ + template <typename... Tags> + static void* allocate(std::size_t size, Tags... tags) + { + return size <= Size ? SmallHeap::allocate(size, tags...) + : BigHeap::allocate(size, tags...); + } + + template <typename... Tags> + static void deallocate(std::size_t size, void* data, Tags... tags) + { + if (size <= Size) + SmallHeap::deallocate(size, data, tags...); + else + BigHeap::deallocate(size, data, tags...); + } +}; + +} // namespace immer diff --git a/third_party/immer/immer/heap/tags.hpp b/third_party/immer/immer/heap/tags.hpp new file mode 100644 index 0000000000..d1ce48d05c --- /dev/null +++ b/third_party/immer/immer/heap/tags.hpp @@ -0,0 +1,16 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +namespace immer { + +struct norefs_tag +{}; + +} // namespace immer diff --git a/third_party/immer/immer/heap/thread_local_free_list_heap.hpp b/third_party/immer/immer/heap/thread_local_free_list_heap.hpp new file mode 100644 index 0000000000..9f7f48f43f --- /dev/null +++ b/third_party/immer/immer/heap/thread_local_free_list_heap.hpp @@ -0,0 +1,55 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <immer/heap/unsafe_free_list_heap.hpp> + +namespace immer { +namespace detail { + +template <typename Heap> +struct thread_local_free_list_storage +{ + struct head_t + { + free_list_node* data; + std::size_t count; + + ~head_t() { Heap::clear(); } + }; + + static head_t& head() + { + thread_local static head_t head_{nullptr, 0}; + return head_; + } +}; + +} // namespace detail + +/*! + * Adaptor that does not release the memory to the parent heap but + * instead it keeps the memory in a `thread_local` global free + * list. Must be preceded by a `with_data<free_list_node, ...>` heap + * adaptor. When the current thread finishes, the memory is returned + * to the parent heap. + * + * @tparam Size Maximum size of the objects to be allocated. + * @tparam Limit Maximum number of elements to keep in the free list. + * @tparam Base Type of the parent heap. + */ +template <std::size_t Size, std::size_t Limit, typename Base> +struct thread_local_free_list_heap + : detail::unsafe_free_list_heap_impl<detail::thread_local_free_list_storage, + Size, + Limit, + Base> +{}; + +} // namespace immer diff --git a/third_party/immer/immer/heap/unsafe_free_list_heap.hpp b/third_party/immer/immer/heap/unsafe_free_list_heap.hpp new file mode 100644 index 0000000000..942f078024 --- /dev/null +++ b/third_party/immer/immer/heap/unsafe_free_list_heap.hpp @@ -0,0 +1,109 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <cassert> +#include <immer/config.hpp> +#include <immer/heap/free_list_node.hpp> + +namespace immer { +namespace detail { + +template <typename Heap> +struct unsafe_free_list_storage +{ + struct head_t + { + free_list_node* data; + std::size_t count; + }; + + static head_t& head() + { + static head_t head_{nullptr, 0}; + return head_; + } +}; + +template <template <class> class Storage, + std::size_t Size, + std::size_t Limit, + typename Base> +class unsafe_free_list_heap_impl : Base +{ + using storage = Storage<unsafe_free_list_heap_impl>; + +public: + using base_t = Base; + + template <typename... Tags> + static void* allocate(std::size_t size, Tags...) + { + assert(size <= sizeof(free_list_node) + Size); + assert(size >= sizeof(free_list_node)); + + auto n = storage::head().data; + if (!n) { + auto p = base_t::allocate(Size + sizeof(free_list_node)); + return static_cast<free_list_node*>(p); + } + --storage::head().count; + storage::head().data = n->next; + return n; + } + + template <typename... Tags> + static void deallocate(std::size_t size, void* data, Tags...) + { + assert(size <= sizeof(free_list_node) + Size); + assert(size >= sizeof(free_list_node)); + + if (storage::head().count >= Limit) + base_t::deallocate(Size + sizeof(free_list_node), data); + else { + auto n = static_cast<free_list_node*>(data); + n->next = storage::head().data; + storage::head().data = n; + ++storage::head().count; + } + } + + static void clear() + { + while (storage::head().data) { + auto n = storage::head().data->next; + base_t::deallocate(Size + sizeof(free_list_node), + storage::head().data); + storage::head().data = n; + --storage::head().count; + } + } +}; + +} // namespace detail + +/*! + * Adaptor that does not release the memory to the parent heap but + * instead it keeps the memory in a global free list that **is not + * thread-safe**. Must be preceded by a `with_data<free_list_node, + * ...>` heap adaptor. + * + * @tparam Size Maximum size of the objects to be allocated. + * @tparam Limit Maximum number of elements to keep in the free list. + * @tparam Base Type of the parent heap. + */ +template <std::size_t Size, std::size_t Limit, typename Base> +struct unsafe_free_list_heap + : detail::unsafe_free_list_heap_impl<detail::unsafe_free_list_storage, + Size, + Limit, + Base> +{}; + +} // namespace immer diff --git a/third_party/immer/immer/heap/with_data.hpp b/third_party/immer/immer/heap/with_data.hpp new file mode 100644 index 0000000000..1e8c2abb08 --- /dev/null +++ b/third_party/immer/immer/heap/with_data.hpp @@ -0,0 +1,43 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <cstdio> + +namespace immer { + +/*! + * Appends a default constructed extra object of type `T` at the + * *before* the requested region. + * + * @tparam T Type of the appended data. + * @tparam Base Type of the parent heap. + */ +template <typename T, typename Base> +struct with_data : Base +{ + using base_t = Base; + + template <typename... Tags> + static void* allocate(std::size_t size, Tags... tags) + { + auto p = base_t::allocate(size + sizeof(T), tags...); + return new (p) T{} + 1; + } + + template <typename... Tags> + static void deallocate(std::size_t size, void* p, Tags... tags) + { + auto dp = static_cast<T*>(p) - 1; + dp->~T(); + base_t::deallocate(size + sizeof(T), dp, tags...); + } +}; + +} // namespace immer |