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 | |
15 | namespace immer { |
16 | namespace detail { |
17 | |
18 | template <typename Heap> |
19 | struct 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 | |
34 | template <template<class>class Storage, |
35 | std::size_t Size, |
36 | std::size_t Limit, |
37 | typename Base> |
38 | class unsafe_free_list_heap_impl : Base |
39 | { |
40 | using storage = Storage<unsafe_free_list_heap_impl>; |
41 | |
42 | public: |
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 | */ |
100 | template <std::size_t Size, std::size_t Limit, typename Base> |
101 | struct 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 | |