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
17namespace 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 */
27template <std::size_t Size, std::size_t Limit, typename Base>
28struct 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
69private:
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