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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
// Copyright (c) 2025 GeometryFactory Sarl (France).
//
// This file is part of CGAL (www.cgal.org).
//
// $URL: https://github.com/CGAL/cgal/blob/v6.1/STL_Extension/include/CGAL/Random_allocator.h $
// $Id: include/CGAL/Random_allocator.h b26b07a1242 $
// SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
//
// Author(s) : Laurent Rineau
#ifndef CGAL_RANDOM_ALLOCATOR_H
#define CGAL_RANDOM_ALLOCATOR_H
#include <boost/container/static_vector.hpp>
#include <boost/dynamic_bitset.hpp>
#include <memory>
#include <vector>
#include <random>
#if CGAL_DEBUG_RANDOM_ALLOCATOR
# if __has_include(<format>)
# include <iostream>
# include <format>
# if __cpp_lib_format >= 201907L
# define CGAL_DEBUG_RANDOM_ALLOCATOR_OKAY 1
# endif
# endif
# if ! CGAL_DEBUG_RANDOM_ALLOCATOR_OKAY
# error "CGAL_DEBUG_RANDOM_ALLOCATOR requires <format> and C++20 std::format"
# endif
#endif
namespace CGAL {
// A random allocator that allocates blocks of memory and returns random
// locations. To use only for debugging purposes. That allocator is:
// - not efficient,
// - not thread-safe,
// - and increases memory-fragmentation and non-locality.
template <typename T, typename Upstream_allocator = std::allocator<T>> class Random_allocator
{
constexpr static std::size_t minimal_block_size = 1024;
constexpr static std::size_t random_size = 64;
struct Blocks
{
struct Block
{
T* data = nullptr;
boost::dynamic_bitset<> available;
std::size_t maximal_continuous_free_space = 0;
auto size() const { return available.size(); }
};
Upstream_allocator alloc;
std::vector<Block> blocks; // List of allocated blocks
void allocate_new_block(std::size_t block_size = minimal_block_size)
{
auto& block = blocks.emplace_back();
block.data = alloc.allocate(block_size);
block.available.resize(block_size, true);
block.maximal_continuous_free_space = block_size;
}
Blocks(const Upstream_allocator& alloc) : alloc(alloc) { allocate_new_block(); }
~Blocks()
{
for(auto& block : blocks) {
alloc.deallocate(block.data, block.size());
}
}
};
using Block = typename Blocks::Block;
using Ptr = std::shared_ptr<Blocks>;
Ptr ptr_;
std::mt19937 gen;
public:
using value_type = T;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using const_pointer = const T*;
using reference = T&;
using const_reference = const T&;
using allocator_type = Upstream_allocator;
Random_allocator(const Upstream_allocator& alloc = {}) noexcept;
pointer allocate(size_type n, const void* hint = 0);
void deallocate(pointer p, size_type n);
template <typename U, typename... Args> void construct(U* p, Args&&... args);
template <typename U> void destroy(U* p);
size_type max_size() const noexcept;
template <typename U> struct rebind
{
using upstream_traits = std::allocator_traits<Upstream_allocator>;
using other_upstream_allocator = typename upstream_traits::template rebind_alloc<U>;
using other = Random_allocator<U, other_upstream_allocator>;
};
bool operator==(const Random_allocator&) const noexcept;
bool operator!=(const Random_allocator&) const noexcept;
};
// Implementation of Random_allocator methods
template <typename T, typename Upstream_allocator>
Random_allocator<T, Upstream_allocator>::Random_allocator(const Upstream_allocator& alloc) noexcept
: ptr_(std::make_shared<Blocks>(alloc)), gen(std::random_device()())
{
}
template <typename T, typename Upstream_allocator>
typename Random_allocator<T, Upstream_allocator>::pointer
Random_allocator<T, Upstream_allocator>::allocate(size_type n, const void* hint)
{
boost::container::static_vector<std::pair<Block*, size_type>, random_size> found_spaces;
for(auto it = ptr_->blocks.rbegin(), end = ptr_->blocks.rend(); it != end; ++it) {
auto& block = *it;
if(block.maximal_continuous_free_space < n)
continue;
auto& available = block.available;
const auto block_size = block.size();
size_type found_max_free_space = 0;
auto index = available.find_first();
while(index != boost::dynamic_bitset<>::npos) {
available.flip();
const auto end_of_free_block = (std::min)(available.find_next(index), block_size);
available.flip();
auto free_space = end_of_free_block - index;
found_max_free_space = (std::max)(found_max_free_space, free_space);
while(free_space > n && found_spaces.size() < found_spaces.capacity()) {
found_spaces.emplace_back(std::addressof(block), index);
free_space -= n;
index += n;
}
index = block.available.find_next(end_of_free_block);
}
block.maximal_continuous_free_space = found_max_free_space;
if(found_spaces.size() == found_spaces.capacity())
break;
}
if(!found_spaces.empty()) {
std::uniform_int_distribution<> dis(0, found_spaces.size() - 1);
auto i = dis(gen);
auto [block, index] = found_spaces[i];
block->available.set(index, n, false);
#if CGAL_DEBUG_RANDOM_ALLOCATOR
std::clog << std::format("CGAL::Random_allocator debug info: n = {}, found_spaces.size() = {}, i = {},"
" block id = {}, block size = {}, index = {}\n",
n, found_spaces.size(), i, block - ptr_->blocks.data(), block->size(), index);
#endif // CGAL_DEBUG_RANDOM_ALLOCATOR
return block->data + index;
}
size_type block_size = (std::max)(n * random_size, minimal_block_size);
ptr_->allocate_new_block(block_size);
return allocate(n, hint);
}
template <typename T, typename Upstream_allocator>
void Random_allocator<T, Upstream_allocator>::deallocate(pointer p, size_type n)
{
for(auto& block : ptr_->blocks) {
if(block.data <= p && p < block.data + block.size()) {
block.available.set(p - block.data, n, true);
return;
}
}
}
template <typename T, typename Upstream_allocator>
template <typename U, typename... Args>
void Random_allocator<T, Upstream_allocator>::construct(U* p, Args&&... args)
{
::new((void*)p) U(std::forward<Args>(args)...);
}
template <typename T, typename Upstream_allocator>
template <typename U>
void Random_allocator<T, Upstream_allocator>::destroy(U* p)
{
p->~U();
}
template <typename T, typename Upstream_allocator>
typename Random_allocator<T, Upstream_allocator>::size_type
Random_allocator<T, Upstream_allocator>::max_size() const noexcept
{
return (std::numeric_limits<size_type>::max)() / sizeof(T);
}
} // namespace CGAL
#endif // CGAL_RANDOM_ALLOCATOR_H
|
