1//
2// immer: immutable data structures for C++
3// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
4//
5// This software is distributed under the Boost Software License, Version 1.0.
6// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
7//
8
9#pragma once
10
11#include <immer/config.hpp>
12#include <immer/heap/free_list_node.hpp>
13#include <cassert>
14
15namespace immer {
16namespace detail {
17
18template <typename Heap>
19struct unsafe_free_list_storage
20{
21 struct head_t
22 {
23 free_list_node* data;
24 std::size_t count;
25 };
26
27 static head_t& head()
28 {
29 static head_t head_ {nullptr, 0};
30 return head_;
31 }
32};
33
34template <template<class>class Storage,
35 std::size_t Size,
36 std::size_t Limit,
37 typename Base>
38class unsafe_free_list_heap_impl : Base
39{
40 using storage = Storage<unsafe_free_list_heap_impl>;
41
42public:
43 using base_t = Base;
44
45 template <typename... Tags>
46 static void* allocate(std::size_t size, Tags...)
47 {
48 assert(size <= sizeof(free_list_node) + Size);
49 assert(size >= sizeof(free_list_node));
50
51 auto n = storage::head().data;
52 if (!n) {
53 auto p = base_t::allocate(Size + sizeof(free_list_node));
54 return static_cast<free_list_node*>(p);
55 }
56 --storage::head().count;
57 storage::head().data = n->next;
58 return n;
59 }
60
61 template <typename... Tags>
62 static void deallocate(std::size_t size, void* data, Tags...)
63 {
64 assert(size <= sizeof(free_list_node) + Size);
65 assert(size >= sizeof(free_list_node));
66
67 if (storage::head().count >= Limit)
68 base_t::deallocate(Size + sizeof(free_list_node), data);
69 else {
70 auto n = static_cast<free_list_node*>(data);
71 n->next = storage::head().data;
72 storage::head().data = n;
73 ++storage::head().count;
74 }
75 }
76
77 static void clear()
78 {
79 while (storage::head().data) {
80 auto n = storage::head().data->next;
81 base_t::deallocate(Size + sizeof(free_list_node), storage::head().data);
82 storage::head().data = n;
83 --storage::head().count;
84 }
85 }
86};
87
88} // namespace detail
89
90/*!
91 * Adaptor that does not release the memory to the parent heap but
92 * instead it keeps the memory in a global free list that **is not
93 * thread-safe**. Must be preceded by a `with_data<free_list_node,
94 * ...>` heap adaptor.
95 *
96 * @tparam Size Maximum size of the objects to be allocated.
97 * @tparam Limit Maximum number of elements to keep in the free list.
98 * @tparam Base Type of the parent heap.
99 */
100template <std::size_t Size, std::size_t Limit, typename Base>
101struct unsafe_free_list_heap : detail::unsafe_free_list_heap_impl<
102 detail::unsafe_free_list_storage,
103 Size,
104 Limit,
105 Base>
106{};
107
108} // namespace immer
109