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
|
// Copyright 2025 The Abseil Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef ABSL_CONTAINER_INTERNAL_CHUNKED_QUEUE_H_
#define ABSL_CONTAINER_INTERNAL_CHUNKED_QUEUE_H_
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <initializer_list>
#include <iterator>
#include <memory>
#include <new>
#include <tuple>
#include <type_traits>
#include <utility>
#include "absl/base/attributes.h"
#include "absl/base/config.h"
#include "absl/base/macros.h"
#include "absl/container/internal/layout.h"
namespace absl {
ABSL_NAMESPACE_BEGIN
namespace container_internal {
// ChunkedQueueBlock defines a node in a forward list of uninitialized storage
// of size T's. The user is responsible for constructing and destroying T's in
// said storage.
//
// ChunkedQueueBlock::New(size) returns said node, with at least size_hint T's
// of uninitialized storage.
template <typename T, typename Allocator>
class ChunkedQueueBlock {
private:
using ChunkedQueueBlockAllocator = typename std::allocator_traits<
Allocator>::template rebind_alloc<ChunkedQueueBlock>;
using ByteAllocator =
typename std::allocator_traits<Allocator>::template rebind_alloc<char>;
public:
// NB, instances of this must not be created or destroyed directly, only via
// the New() and Delete() methods. (This notionally-private constructor is
// public only to allow access from allocator types used by New().)
explicit ChunkedQueueBlock(size_t size)
: next_(nullptr), limit_(start() + size) {}
// Must be deleted by ChunkedQueueBlock::Delete.
static ChunkedQueueBlock* New(size_t size_hint, Allocator* alloc) { // NOLINT
ABSL_ASSERT(size_hint >= size_t{1});
size_t allocation_bytes = AllocSize(size_hint);
void* mem;
std::tie(mem, allocation_bytes) = Allocate(allocation_bytes, alloc);
const size_t element_count =
(allocation_bytes - start_offset()) / sizeof(T);
ChunkedQueueBlock* as_block = static_cast<ChunkedQueueBlock*>(mem);
ChunkedQueueBlockAllocator block_alloc(*alloc);
std::allocator_traits<ChunkedQueueBlockAllocator>::construct(
block_alloc, as_block, element_count);
return as_block;
}
static void Delete(ChunkedQueueBlock* ptr, Allocator* alloc) {
const size_t allocation_bytes = AllocSize(ptr->size());
ChunkedQueueBlockAllocator block_alloc(*alloc);
std::allocator_traits<ChunkedQueueBlockAllocator>::destroy(block_alloc,
ptr);
if constexpr (std::is_same_v<ByteAllocator, std::allocator<char>>) {
#ifdef __STDCPP_DEFAULT_NEW_ALIGNMENT__
if (alignment() > __STDCPP_DEFAULT_NEW_ALIGNMENT__) {
::operator delete(ptr
#ifdef __cpp_sized_deallocation
,
allocation_bytes
#endif
,
std::align_val_t(alignment()));
return;
}
#endif
::operator delete(ptr);
} else {
void* mem = ptr;
ByteAllocator byte_alloc(*alloc);
std::allocator_traits<ByteAllocator>::deallocate(
byte_alloc, static_cast<char*>(mem), allocation_bytes);
}
}
ChunkedQueueBlock* next() const { return next_; }
void set_next(ChunkedQueueBlock* next) { next_ = next; }
T* start() {
return reinterpret_cast<T*>(reinterpret_cast<uintptr_t>(this) +
start_offset());
}
T* limit() { return limit_; }
size_t size() { return limit() - start(); }
static constexpr size_t block_size_from_bytes(size_t bytes) {
return bytes <= static_cast<size_t>(start_offset())
? size_t{1}
: elements_in_bytes(bytes - start_offset());
}
private:
ChunkedQueueBlock(const ChunkedQueueBlock&) = delete;
ChunkedQueueBlock& operator=(const ChunkedQueueBlock&) = delete;
// The byte size to allocate to ensure space for `min_element_count` elements.
static constexpr size_t AllocSize(size_t min_element_count) {
return absl::container_internal::Layout<ChunkedQueueBlock, T>(
1, min_element_count)
.AllocSize();
}
static constexpr ptrdiff_t start_offset() {
return absl::container_internal::Layout<ChunkedQueueBlock, T>(1, 1)
.template Offset<1>();
}
static constexpr size_t alignment() {
return absl::container_internal::Layout<ChunkedQueueBlock, T>(1, 1)
.Alignment();
}
static constexpr size_t elements_in_bytes(size_t bytes) {
return (bytes + sizeof(T) - 1) / sizeof(T);
}
static std::pair<void*, size_t> Allocate(size_t allocation_bytes,
Allocator* alloc) {
// If we're using the default allocator, then we can use new.
void* mem;
if constexpr (std::is_same_v<ByteAllocator, std::allocator<char>>) {
// Older GCC versions have an unused variable warning on `alloc` inside
// this constexpr branch.
static_cast<void>(alloc);
#ifdef __STDCPP_DEFAULT_NEW_ALIGNMENT__
if (alignment() > __STDCPP_DEFAULT_NEW_ALIGNMENT__) {
// Align the allocation to respect alignof(T).
mem = ::operator new(allocation_bytes, std::align_val_t(alignment()));
return {mem, allocation_bytes};
}
#endif
mem = ::operator new(allocation_bytes);
} else {
ByteAllocator byte_alloc(*alloc);
mem = std::allocator_traits<ByteAllocator>::allocate(byte_alloc,
allocation_bytes);
}
return {mem, allocation_bytes};
}
ChunkedQueueBlock* next_;
T* limit_;
};
} // namespace container_internal
ABSL_NAMESPACE_END
} // namespace absl
#endif // ABSL_CONTAINER_INTERNAL_CHUNKED_QUEUE_H_
|
