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/heap/with_data.hpp> |
12 | #include <immer/heap/free_list_node.hpp> |
13 | |
14 | #include <atomic> |
15 | #include <cassert> |
16 | |
17 | namespace immer { |
18 | |
19 | /*! |
20 | * Adaptor that does not release the memory to the parent heap but |
21 | * instead it keeps the memory in a thread-safe global free list. Must |
22 | * be preceded by a `with_data<free_list_node, ...>` heap adaptor. |
23 | * |
24 | * @tparam Size Maximum size of the objects to be allocated. |
25 | * @tparam Base Type of the parent heap. |
26 | */ |
27 | template <std::size_t Size, std::size_t Limit, typename Base> |
28 | struct free_list_heap : Base |
29 | { |
30 | using base_t = Base; |
31 | |
32 | template <typename... Tags> |
33 | static void* allocate(std::size_t size, Tags...) |
34 | { |
35 | assert(size <= sizeof(free_list_node) + Size); |
36 | assert(size >= sizeof(free_list_node)); |
37 | |
38 | free_list_node* n; |
39 | do { |
40 | n = head().data; |
41 | if (!n) { |
42 | auto p = base_t::allocate(Size + sizeof(free_list_node)); |
43 | return static_cast<free_list_node*>(p); |
44 | } |
45 | } while (!head().data.compare_exchange_weak(n, n->next)); |
46 | head().count.fetch_sub(1u, std::memory_order_relaxed); |
47 | return n; |
48 | } |
49 | |
50 | template <typename... Tags> |
51 | static void deallocate(std::size_t size, void* data, Tags...) |
52 | { |
53 | assert(size <= sizeof(free_list_node) + Size); |
54 | assert(size >= sizeof(free_list_node)); |
55 | |
56 | // we use relaxed, because we are fine with temporarily having |
57 | // a few more/less buffers in free list |
58 | if (head().count.load(std::memory_order_relaxed) >= Limit) { |
59 | base_t::deallocate(Size + sizeof(free_list_node), data); |
60 | } else { |
61 | auto n = static_cast<free_list_node*>(data); |
62 | do { |
63 | n->next = head().data; |
64 | } while (!head().data.compare_exchange_weak(n->next, n)); |
65 | head().count.fetch_add(1u, std::memory_order_relaxed); |
66 | } |
67 | } |
68 | |
69 | private: |
70 | struct head_t |
71 | { |
72 | std::atomic<free_list_node*> data; |
73 | std::atomic<std::size_t> count; |
74 | }; |
75 | |
76 | static head_t& head() |
77 | { |
78 | static head_t head_{{nullptr}, {0}}; |
79 | return head_; |
80 | } |
81 | }; |
82 | |
83 | } // namespace immer |
84 | |