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/debug_size_heap.hpp>
12#include <immer/heap/free_list_heap.hpp>
13#include <immer/heap/split_heap.hpp>
14#include <immer/heap/thread_local_free_list_heap.hpp>
15#include <immer/config.hpp>
16
17#include <cstdlib>
18#include <algorithm>
19
20namespace immer {
21
22/*!
23 * Heap policy that unconditionally uses its `Heap` argument.
24 */
25template <typename Heap>
26struct heap_policy
27{
28 using type = Heap;
29
30 template <std::size_t>
31 struct optimized
32 {
33 using type = Heap;
34 };
35};
36
37template <typename Deriv, typename HeapPolicy>
38struct enable_optimized_heap_policy
39{
40 static void* operator new (std::size_t size)
41 {
42 using heap_type = typename HeapPolicy
43 ::template optimized<sizeof(Deriv)>::type;
44
45 return heap_type::allocate(size);
46 }
47
48 static void operator delete (void* data, std::size_t size)
49 {
50 using heap_type = typename HeapPolicy
51 ::template optimized<sizeof(Deriv)>::type;
52
53 heap_type::deallocate(size, data);
54 }
55};
56
57/*!
58 * Heap policy that returns a heap with a free list of objects
59 * of `max_size = max(Sizes...)` on top an underlying `Heap`. Note
60 * these two properties of the resulting heap:
61 *
62 * - Allocating an object that is bigger than `max_size` may trigger
63 * *undefined behavior*.
64 *
65 * - Allocating an object of size less than `max_size` still
66 * returns an object of `max_size`.
67 *
68 * Basically, this heap will always return objects of `max_size`.
69 * When an object is freed, it does not directly invoke `std::free`,
70 * but it keeps the object in a global linked list instead. When a
71 * new object is requested, it does not need to call `std::malloc` but
72 * it can directly pop and return the other object from the global
73 * list, a much faster operation.
74 *
75 * This actually creates a hierarchy with two free lists:
76 *
77 * - A `thread_local` free list is used first. It does not need any
78 * kind of synchronization and is very fast. When the thread
79 * finishes, its contents are returned to the next free list.
80 *
81 * - A global free list using lock-free access via atomics.
82 *
83 * @tparam Heap Heap to be used when the free list is empty.
84 *
85 * @rst
86 *
87 * .. tip:: For many applications that use immutable data structures
88 * significantly, this is actually the best heap policy, and it
89 * might become the default in the future.
90 *
91 * Note that most our data structures internally use trees with the
92 * same big branching factors. This means that all *vectors*,
93 * *maps*, etc. can just allocate elements from the same free-list
94 * optimized heap. Not only does this lowers the allocation time,
95 * but also makes up for more efficient *cache utilization*. When
96 * a new node is needed, there are high chances the allocator will
97 * return a node that was just accessed. When batches of immutable
98 * updates are made, this can make a significant difference.
99 *
100 * @endrst
101 */
102template <typename Heap,
103 std::size_t Limit = default_free_list_size>
104struct free_list_heap_policy
105{
106 using type = debug_size_heap<Heap>;
107
108 template <std::size_t Size>
109 struct optimized
110 {
111 using type = split_heap<
112 Size,
113 with_free_list_node<
114 thread_local_free_list_heap<
115 Size,
116 Limit,
117 free_list_heap<
118 Size, Limit,
119 debug_size_heap<Heap>>>>,
120 debug_size_heap<Heap>>;
121 };
122};
123
124/*!
125 * Similar to @ref free_list_heap_policy, but it assumes no
126 * multi-threading, so a single global free list with no concurrency
127 * checks is used.
128 */
129template <typename Heap,
130 std::size_t Limit = default_free_list_size>
131struct unsafe_free_list_heap_policy
132{
133 using type = Heap;
134
135 template <std::size_t Size>
136 struct optimized
137 {
138 using type = split_heap<
139 Size,
140 with_free_list_node<
141 unsafe_free_list_heap<
142 Size, Limit,
143 debug_size_heap<Heap>>>,
144 debug_size_heap<Heap>>;
145 };
146};
147
148} // namespace immer
149