13 files changed, 826 insertions, 0 deletions
diff --git a/immer/heap/cpp_heap.hpp b/immer/heap/cpp_heap.hpp
new file mode 100644
index 000000000000..cd129b406bea
--- /dev/null
+++ b/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/immer/heap/debug_size_heap.hpp b/immer/heap/debug_size_heap.hpp
new file mode 100644
index 000000000000..d5288c646f8d
--- /dev/null
+++ b/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/immer/heap/free_list_heap.hpp b/immer/heap/free_list_heap.hpp
new file mode 100644
index 000000000000..dc25b10184a1
--- /dev/null
+++ b/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/immer/heap/free_list_node.hpp b/immer/heap/free_list_node.hpp
new file mode 100644
index 000000000000..acab4779aa43
--- /dev/null
+++ b/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/immer/heap/gc_heap.hpp b/immer/heap/gc_heap.hpp
new file mode 100644
index 000000000000..8494bd26694f
--- /dev/null
+++ b/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/immer/heap/heap_policy.hpp b/immer/heap/heap_policy.hpp
new file mode 100644
index 000000000000..582c113f334f
--- /dev/null
+++ b/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/immer/heap/identity_heap.hpp b/immer/heap/identity_heap.hpp
new file mode 100644
index 000000000000..032cb3f221d0
--- /dev/null
+++ b/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/immer/heap/malloc_heap.hpp b/immer/heap/malloc_heap.hpp
new file mode 100644
index 000000000000..a0074d17c0fb
--- /dev/null
+++ b/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/immer/heap/split_heap.hpp b/immer/heap/split_heap.hpp
new file mode 100644
index 000000000000..37272d30ecc1
--- /dev/null
+++ b/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/immer/heap/tags.hpp b/immer/heap/tags.hpp
new file mode 100644
index 000000000000..d1ce48d05c89
--- /dev/null
+++ b/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/immer/heap/thread_local_free_list_heap.hpp b/immer/heap/thread_local_free_list_heap.hpp
new file mode 100644
index 000000000000..9f7f48f43f6c
--- /dev/null
+++ b/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/immer/heap/unsafe_free_list_heap.hpp b/immer/heap/unsafe_free_list_heap.hpp
new file mode 100644
index 000000000000..942f07802476
--- /dev/null
+++ b/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/immer/heap/with_data.hpp b/immer/heap/with_data.hpp
new file mode 100644
index 000000000000..1e8c2abb082e
--- /dev/null
+++ b/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