blob: 7017b0aca196793dcfb52b1ea36ad83a654f4adb (
plain)
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
|
#include "LooseQuadtree-impl.h"
#include "compat/assert.hpp"
#undef assert
#define assert fm_assert
namespace loose_quadtree::detail {
BlocksAllocator::BlocksAllocator() {}
BlocksAllocator::~BlocksAllocator() {
for (auto& size_block_pair : size_to_blocks_) {
BlocksHead& blocks_head = size_block_pair.second;
for (auto& address_empty_pair : blocks_head.address_to_empty_slot_number) {
assert(address_empty_pair.second == blocks_head.slots_in_a_block_);
Block* block = address_empty_pair.first;
delete block;
}
}
}
void* BlocksAllocator::Allocate(std::size_t object_size) {
#ifdef LQT_USE_OWN_ALLOCATOR
if (object_size < sizeof(void*)) object_size = sizeof(void*);
assert(object_size <= kMaxAllowedAlloc);
auto size_blocks_it = size_to_blocks_.find(object_size);
if (size_blocks_it == size_to_blocks_.end()) {
size_blocks_it = size_to_blocks_.emplace(object_size, object_size).first;
}
BlocksHead& blocks_head = size_blocks_it->second;
assert(blocks_head.slots_in_a_block_ == kBlockSize / object_size);
if (blocks_head.first_empty_slot == nullptr) {
Block* new_block = new Block();
std::size_t empties = blocks_head.slots_in_a_block_;
blocks_head.address_to_empty_slot_number.emplace(new_block, empties);
blocks_head.first_empty_slot = reinterpret_cast<void*>(new_block);
void* current_slot = reinterpret_cast<void*>(new_block);
empties--;
while (empties > 0) {
void* next_slot =
reinterpret_cast<void*>(reinterpret_cast<char*>(current_slot)
+ object_size);
*reinterpret_cast<void**>(current_slot) = next_slot;
current_slot = next_slot;
empties--;
}
*reinterpret_cast<void**>(current_slot) = nullptr;
}
assert(blocks_head.first_empty_slot != nullptr);
void* slot = blocks_head.first_empty_slot;
blocks_head.first_empty_slot = *reinterpret_cast<void**>(slot);
auto address_empties_it =
blocks_head.address_to_empty_slot_number.upper_bound(reinterpret_cast<Block*>(slot));
assert(address_empties_it != blocks_head.address_to_empty_slot_number.begin());
address_empties_it--;
assert(address_empties_it->first <= reinterpret_cast<Block*>(slot) &&
(std::size_t)(reinterpret_cast<char*>(slot) -
reinterpret_cast<char*>(address_empties_it->first)) < kBlockSize);
assert((std::size_t)(reinterpret_cast<char*>(slot) -
reinterpret_cast<char*>(address_empties_it->first)) % object_size == 0);
assert(address_empties_it->second > 0 &&
address_empties_it->second <= blocks_head.slots_in_a_block_);
address_empties_it->second--;
return slot;
#else
return reinterpret_cast<void*>(new char[object_size]);
#endif
}
void BlocksAllocator::Deallocate(void* p, std::size_t object_size) {
#ifdef LQT_USE_OWN_ALLOCATOR
if (object_size < sizeof(void*)) object_size = sizeof(void*);
assert(object_size <= kMaxAllowedAlloc);
auto size_blocks_it = size_to_blocks_.find(object_size);
assert(size_blocks_it != size_to_blocks_.end());
BlocksHead& blocks_head = size_blocks_it->second;
assert(blocks_head.slots_in_a_block_ == kBlockSize / object_size);
auto address_empties_it =
blocks_head.address_to_empty_slot_number.upper_bound(reinterpret_cast<Block*>(p));
assert(address_empties_it != blocks_head.address_to_empty_slot_number.begin());
address_empties_it--;
assert(address_empties_it->first <= reinterpret_cast<Block*>(p) &&
(std::size_t)(reinterpret_cast<char*>(p) -
reinterpret_cast<char*>(address_empties_it->first)) < kBlockSize);
assert((std::size_t)(reinterpret_cast<char*>(p) -
reinterpret_cast<char*>(address_empties_it->first)) % object_size == 0);
assert(address_empties_it->second < blocks_head.slots_in_a_block_);
void* slot = p;
*reinterpret_cast<void**>(slot) = blocks_head.first_empty_slot;
blocks_head.first_empty_slot = slot;
address_empties_it->second++;
assert(address_empties_it->second > 0 &&
address_empties_it->second <= blocks_head.slots_in_a_block_);
#else
(void)object_size;
delete[] reinterpret_cast<char*>(p);
#endif
}
void BlocksAllocator::ReleaseFreeBlocks() {
for (auto& size_block_pair : size_to_blocks_) {
BlocksHead& blocks_head = size_block_pair.second;
void** current = &blocks_head.first_empty_slot;
while (*current != nullptr) {
auto address_empties_it =
blocks_head.address_to_empty_slot_number.upper_bound(reinterpret_cast<Block*>(*current));
assert(address_empties_it != blocks_head.address_to_empty_slot_number.begin());
address_empties_it--;
assert(address_empties_it->first <= reinterpret_cast<Block*>(*current) &&
(std::size_t)(reinterpret_cast<char*>(*current) -
reinterpret_cast<char*>(address_empties_it->first)) < kBlockSize);
assert((std::size_t)(reinterpret_cast<char*>(*current) -
reinterpret_cast<char*>(address_empties_it->first)) % size_block_pair.first == 0);
assert(address_empties_it->second > 0 &&
address_empties_it->second <= blocks_head.slots_in_a_block_);
if (address_empties_it->second >= blocks_head.slots_in_a_block_) {
*current = **(void***)current;
}
else {
current = *(void***)current;
}
}
auto address_empties_it = blocks_head.address_to_empty_slot_number.begin();
while (address_empties_it != blocks_head.address_to_empty_slot_number.end()) {
if (address_empties_it->second >= blocks_head.slots_in_a_block_) {
auto prev_address_empties_it = address_empties_it;
address_empties_it++;
blocks_head.address_to_empty_slot_number.erase(prev_address_empties_it);
}
else {
address_empties_it++;
}
}
}
}
} // namespace loose_quadtree::detail
|
