1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
// Copyright (C) 2015-2025 Jonathan Müller and foonathan/memory contributors
// SPDX-License-Identifier: Zlib
#ifndef FOONATHAN_MEMORY_DETAIL_FREE_LIST_ARRAY_HPP
#define FOONATHAN_MEMORY_DETAIL_FREE_LIST_ARRAY_HPP
#include "align.hpp"
#include "assert.hpp"
#include "memory_stack.hpp"
#include "../config.hpp"
namespace foonathan
{
namespace memory
{
namespace detail
{
// an array of free_memory_list types
// indexed via size, AccessPolicy does necessary conversions
// requires trivial destructible FreeList type
template <class FreeList, class AccessPolicy>
class free_list_array
{
// not supported on GCC 4.7
//static_assert(std::is_trivially_destructible<FreeList>::value,
// "free list must be trivially destructible");
public:
// creates sufficient elements to support up to given maximum node size
// all lists are initially empty
// actual number is calculated via policy
// memory is taken from fixed_memory_stack, it must be sufficient
free_list_array(fixed_memory_stack& stack, const char* end,
std::size_t max_node_size) noexcept
: no_elements_(AccessPolicy::index_from_size(max_node_size) - min_size_index + 1)
{
array_ = static_cast<FreeList*>(
stack.allocate(end, no_elements_ * sizeof(FreeList), alignof(FreeList)));
FOONATHAN_MEMORY_ASSERT_MSG(array_, "insufficient memory for free lists");
for (std::size_t i = 0u; i != no_elements_; ++i)
{
auto node_size = AccessPolicy::size_from_index(i + min_size_index);
::new (static_cast<void*>(array_ + i)) FreeList(node_size);
}
}
// move constructor, does not actually move the elements, just the pointer
free_list_array(free_list_array&& other) noexcept
: array_(other.array_), no_elements_(other.no_elements_)
{
other.array_ = nullptr;
other.no_elements_ = 0u;
}
// destructor, does nothing, list must be trivially destructible!
~free_list_array() noexcept = default;
free_list_array& operator=(free_list_array&& other) noexcept
{
array_ = other.array_;
no_elements_ = other.no_elements_;
other.array_ = nullptr;
other.no_elements_ = 0u;
return *this;
}
// access free list for given size
FreeList& get(std::size_t node_size) const noexcept
{
auto i = AccessPolicy::index_from_size(node_size);
if (i < min_size_index)
i = min_size_index;
return array_[i - min_size_index];
}
// number of free lists
std::size_t size() const noexcept
{
return no_elements_;
}
// maximum supported node size
std::size_t max_node_size() const noexcept
{
return AccessPolicy::size_from_index(no_elements_ + min_size_index - 1);
}
private:
static const std::size_t min_size_index;
FreeList* array_;
std::size_t no_elements_;
};
template <class FL, class AP>
const std::size_t free_list_array<FL, AP>::min_size_index =
AP::index_from_size(FL::min_element_size);
// AccessPolicy that maps size to indices 1:1
// creates a free list for each size!
struct identity_access_policy
{
static std::size_t index_from_size(std::size_t size) noexcept
{
return size;
}
static std::size_t size_from_index(std::size_t index) noexcept
{
return index;
}
};
// AccessPolicy that maps sizes to the integral log2
// this creates more nodes and never wastes more than half the size
struct log2_access_policy
{
static std::size_t index_from_size(std::size_t size) noexcept;
static std::size_t size_from_index(std::size_t index) noexcept;
};
} // namespace detail
} // namespace memory
} // namespace foonathan
#endif //FOONATHAN_MEMORY_DETAIL_FREE_LIST_ARRAY_HPP
|
