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
126
127
128
129
130
131
132
|
// Copyright (C) 2015-2023 Jonathan Müller and foonathan/memory contributors
// SPDX-License-Identifier: Zlib
// this examples shows the basic usage of RawAllocator classes with containers and smart pointers
// see https://memory.foonathan.net/md_doc_external_usage.html for more details
#include <algorithm>
#include <iostream>
#include <iterator>
#include <foonathan/memory/container.hpp> // vector, list, list_node_size,...
#include <foonathan/memory/memory_pool.hpp> // memory_pool
#include <foonathan/memory/smart_ptr.hpp> // allocate_unique
#include <foonathan/memory/static_allocator.hpp> // static_allocator_storage, static_block_allocator
#include <foonathan/memory/temporary_allocator.hpp> // temporary_allocator
// alias namespace foonathan::memory as memory for easier access
#include <foonathan/memory/namespace_alias.hpp>
template <typename BiIter>
void merge_sort(BiIter begin, BiIter end);
int main()
{
using namespace memory::literals;
// a memory pool RawAllocator
// allocates a memory block - initially 4KiB - and splits it into chunks of list_node_size<int>::value big
// list_node_size<int>::value is the size of each node of a std::list
memory::memory_pool<> pool(memory::list_node_size<int>::value, 4_KiB);
// just an alias for std::list<int, memory::std_allocator<int, memory::memory_pool<>>
// a std::list using a memory_pool
// std_allocator stores a reference to a RawAllocator and provides the Allocator interface
memory::list<int, memory::memory_pool<>> list(pool);
list.push_back(3);
list.push_back(2);
list.push_back(1);
for (auto e : list)
std::cout << e << ' ';
std::cout << '\n';
merge_sort(list.begin(), list.end());
for (auto e : list)
std::cout << e << ' ';
std::cout << '\n';
// allocate a std::unique_ptr using the pool
// memory::allocate_shared is also available
memory::unique_ptr<int, memory::memory_pool<>> ptr =
memory::allocate_unique<int>(pool, *list.begin());
std::cout << *ptr << '\n';
struct base
{
virtual ~base() = default;
virtual const char* name() const = 0;
};
struct derived : base
{
const char* name() const override
{
return "derived";
}
};
// instead of using memory::unique_ptr<base, ...>, you have to use memory::unique_base_ptr<base, ...>,
// because the deleter has to remember the size of the derived type
memory::unique_base_ptr<base, memory::memory_pool<>> base_ptr =
memory::allocate_unique<derived>(pool);
std::cout << base_ptr->name() << '\n';
// static storage of size 4KiB
memory::static_allocator_storage<4_KiB> storage;
// a memory pool again but this time with a BlockAllocator
// this controls the internal allocations of the pool itself
// we need to specify the first template parameter giving the type of the pool as well
// (node_pool is the default)
// we use a static_block_allocator that uses the static storage above
// all allocations will use a memory block on the stack
using static_pool_t = memory::memory_pool<memory::node_pool, memory::static_block_allocator>;
static_pool_t static_pool(memory::unordered_set_node_size<int>::value, 4_KiB, storage);
// again, just an alias for std::unordered_set<int, std::hash<int>, std::equal_to<int>, memory::std_allocator<int, static_pool_t>
// see why I wrote these?
// now we have a hash set that lives on the stack!
memory::unordered_set<int, static_pool_t>
set(13, std::hash<int>{}, std::equal_to<int>{},
static_pool); // (GCC 4.7 is missing the allocator-only ctor, breaks travis)
set.insert(3);
set.insert(2);
set.insert(3); // running out of stack memory is properly handled, of course
for (auto e : set)
std::cout << e << ' ';
std::cout << '\n';
}
// naive implementation of merge_sort using temporary memory allocator
template <typename BiIter>
void merge_sort(BiIter begin, BiIter end)
{
using value_type = typename std::iterator_traits<BiIter>::value_type;
auto distance = std::distance(begin, end);
if (distance <= 1)
return;
auto mid = begin;
std::advance(mid, distance / 2);
// an allocator for temporary memory
// is similar to alloca() but uses its own stack
// this stack is thread_local and created the first time it's needed
// as soon as the allocator object goes out of scope everything allocated through it will be freed
memory::temporary_allocator alloc;
// alias for std::vector<value_type, memory::std_allocator<value_type, memory::temporary_allocator>>
// a std::vector using a temporary_allocator
memory::vector<value_type, memory::temporary_allocator> first(begin, mid, alloc),
second(mid, end, alloc);
merge_sort(first.begin(), first.end());
merge_sort(second.begin(), second.end());
std::merge(first.begin(), first.end(), second.begin(), second.end(), begin);
}
|
