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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
//------------------------------------------------------------------------------
// Author: Pavel Karneliuk
// Description: BlockAllocator for fixed size Chunks of memory
// Copyright (c) 2013 EPAM Systems
//------------------------------------------------------------------------------
/*
This file is part of Nfstrace.
Nfstrace is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, version 2 of the License.
Nfstrace is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with Nfstrace. If not, see <http://www.gnu.org/licenses/>.
*/
//------------------------------------------------------------------------------
#ifndef BLOCK_ALLOCATOR_H
#define BLOCK_ALLOCATOR_H
//------------------------------------------------------------------------------
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <memory>
#include <vector>
//------------------------------------------------------------------------------
namespace NST
{
namespace utils
{
// May throw std::bad_alloc during creation or allocation
class BlockAllocator
{
struct Chunk // type for linking free chunks of memory in a list
{
Chunk* next; // pointer to next chunk in a list
};
using Chunks = std::unique_ptr<char[]>;
using Blocks = std::vector<Chunks>;
public:
constexpr static std::size_t padding = 16;
BlockAllocator() = default;
~BlockAllocator() noexcept
{
assert(max_chunks() == free_chunks());
}
void init_allocation(std::size_t chunk_size,
std::size_t block_size,
std::size_t block_limit)
{
chunk = ((chunk_size + padding - 1) / padding) * padding;
assert(chunk % padding == 0);
assert(chunk >= chunk_size);
assert(chunk >= sizeof(Chunk));
block = block_size;
assert(block >= 1);
limit = block_limit;
assert(limit >= 1);
blocks.reserve(limit);
list = preallocate_block();
assert(list);
}
void* allocate()
{
if(list == nullptr)
{
if(blocks.size() == limit) // all blocks are allocated!
{
// soft limit of blocks is reached
}
list = preallocate_block();
++limit;
}
Chunk* chunk = list;
assert(chunk);
list = list->next;
--nfree;
return chunk;
}
void deallocate(void* ptr) noexcept
{
assert(ptr);
assert(std::any_of(std::begin(blocks), std::end(blocks),
[&](const Chunks& chunks) {
const auto b = reinterpret_cast<void*>(chunks.get());
const auto e = reinterpret_cast<void*>(chunks.get() + block * chunk);
return (b <= ptr) && (ptr < e);
}));
Chunk* chunk = reinterpret_cast<Chunk*>(ptr);
chunk->next = list;
list = chunk;
++nfree;
}
std::size_t max_chunks() const noexcept { return block * limit; }
std::size_t max_memory() const noexcept { return block * limit * chunk; }
std::size_t max_blocks() const noexcept { return limit; }
std::size_t free_chunks() const noexcept { return nfree; }
private:
Chunk* getof(std::size_t i, const Chunks& chunks) const noexcept
{
assert(i < block);
return reinterpret_cast<Chunk*>(&chunks.get()[i * chunk]);
}
Chunk* preallocate_block()
{
Chunks chunks(std::make_unique<Chunks::element_type[]>(block * chunk));
// link chunks to a list
for(std::size_t i = 0; i < block - 1; ++i)
{
getof(i, chunks)->next = getof(i + 1, chunks);
}
getof(block - 1, chunks)->next = nullptr;
Chunk* first = getof(0, chunks);
blocks.emplace_back(std::move(chunks));
nfree += block;
return first;
}
Chunk* list = nullptr; // head of list of free chunks
std::size_t chunk = 0; // size of chunk
std::size_t block = 0; // num chunks in block
std::size_t limit = 0; // max blocks, soft limit
std::size_t nfree = 0; // num of avaliable chunks
Blocks blocks; // array of blocks
};
} // namespace utils
} // namespace NST
//------------------------------------------------------------------------------
#endif // BLOCK_ALLOCATOR_H
//------------------------------------------------------------------------------
|
