diff options
author | Vincent Ambo <mail@tazj.in> | 2020-07-15T07·20+0100 |
---|---|---|
committer | Vincent Ambo <mail@tazj.in> | 2020-07-15T07·20+0100 |
commit | 7f19d641647ac4ef313ed88d6b5c140983ce5436 (patch) | |
tree | 31b66c81465293da5c093c5dde3e419758c0d6cc /immer/heap/unsafe_free_list_heap.hpp |
Squashed 'third_party/immer/' content from commit ad3e3556d
git-subtree-dir: third_party/immer git-subtree-split: ad3e3556d38bb75966dd24c61a774970a7c7957e
Diffstat (limited to 'immer/heap/unsafe_free_list_heap.hpp')
-rw-r--r-- | immer/heap/unsafe_free_list_heap.hpp | 109 |
1 files changed, 109 insertions, 0 deletions
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 |