Pigweed
C/C++ API Reference
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
Loading...
Searching...
No Matches
dynamic_deque.h
1// Copyright 2025 The Pigweed Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License"); you may not
4// use this file except in compliance with the License. You may obtain a copy of
5// the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12// License for the specific language governing permissions and limitations under
13// the License.
14#pragma once
15
16#include <cstddef>
17#include <cstdint>
18#include <initializer_list>
19#include <limits>
20#include <memory>
21#include <type_traits>
22#include <utility>
23
24#include "pw_allocator/allocator.h"
25#include "pw_assert/assert.h"
26#include "pw_containers/internal/count_and_capacity.h"
27#include "pw_containers/internal/generic_deque.h"
28#include "pw_numeric/saturating_arithmetic.h"
29
30namespace pw {
31
51template <typename ValueType, typename SizeType = uint16_t>
53 DynamicDeque<ValueType, SizeType>,
54 ValueType,
55 containers::internal::CountAndCapacity<SizeType>> {
56 private:
59 ValueType,
60 containers::internal::CountAndCapacity<SizeType>>;
61
62 public:
63 using typename Base::const_iterator;
64 using typename Base::const_pointer;
65 using typename Base::const_reference;
66 using typename Base::difference_type;
67 using typename Base::iterator;
68 using typename Base::pointer;
69 using typename Base::reference;
70 using typename Base::size_type;
71 using typename Base::value_type;
72
74
79 constexpr DynamicDeque(Allocator& allocator) noexcept
80 : Base(0), allocator_(&allocator), buffer_(nullptr) {}
81
82 DynamicDeque(const DynamicDeque&) = delete;
83 DynamicDeque& operator=(const DynamicDeque&) = delete;
84
88 constexpr DynamicDeque(DynamicDeque&& other) noexcept
89 : allocator_(other.allocator_), buffer_(other.buffer_) {
90 other.buffer_ = nullptr; // clean other's buffer_, but not its allocator_
91 Base::MoveAssignIndices(other);
92 }
93
94 DynamicDeque& operator=(DynamicDeque&& other) noexcept;
95
97
98 // Provide try_* versions of functions that return false if allocation fails.
99 using Base::try_assign;
100 using Base::try_emplace;
101 using Base::try_emplace_back;
102 using Base::try_emplace_front;
103 using Base::try_insert;
104 using Base::try_push_back;
105 using Base::try_push_front;
106 using Base::try_resize;
107
108 // The GenericDeque's input iterator insert implementation emplaces items one
109 // at a time, which is inefficient. For DynamicDeque, use a more efficient
110 // implementation that inserts all items into a temporary DynamicDeque first.
111 template <typename InputIt,
112 typename = containers::internal::EnableIfInputIterator<InputIt>>
113 iterator insert(const_iterator pos, InputIt first, InputIt last);
114
115 iterator insert(const_iterator pos, const value_type& value) {
116 return Base::insert(pos, value);
117 }
118
119 iterator insert(const_iterator pos, value_type&& value) {
120 return Base::insert(pos, std::move(value));
121 }
122
123 iterator insert(const_iterator pos,
124 size_type count,
125 const value_type& value) {
126 return Base::insert(pos, count, value);
127 }
128
129 iterator insert(const_iterator pos, std::initializer_list<value_type> ilist) {
130 return Base::insert(pos, ilist);
131 }
132
143 [[nodiscard]] bool try_reserve(size_type new_capacity);
144
146 void reserve(size_type new_capacity) { PW_ASSERT(try_reserve(new_capacity)); }
147
157 [[nodiscard]] bool try_reserve_exact(size_type new_capacity) {
158 return new_capacity <= Base::capacity() || IncreaseCapacity(new_capacity);
159 }
160
162 void reserve_exact(size_type new_capacity) {
163 PW_ASSERT(try_reserve_exact(new_capacity));
164 }
165
168
169 constexpr size_type max_size() const noexcept {
170 return std::numeric_limits<size_type>::max();
171 }
172
174 constexpr allocator_type& get_allocator() const { return *allocator_; }
175
177 void swap(DynamicDeque& other) noexcept {
178 Base::SwapIndices(other);
179 std::swap(allocator_, other.allocator_);
180 std::swap(buffer_, other.buffer_);
181 }
182
183 private:
184 friend Base;
185
186 template <typename, typename>
187 friend class DynamicVector; // Allow direct access to data()
188
189 static constexpr bool kFixedCapacity = false; // uses dynamic allocation
190
191 pointer data() { return std::launder(reinterpret_cast<pointer>(buffer_)); }
192 const_pointer data() const {
193 return std::launder(reinterpret_cast<const_pointer>(buffer_));
194 }
195
196 [[nodiscard]] bool IncreaseCapacity(size_type new_capacity);
197
198 size_type GetNewCapacity(const size_type new_size) {
199 // For the initial allocation, allocate at least 4 words worth of items.
200 if (Base::capacity() == 0) {
201 return std::max(size_type{4 * sizeof(void*) / sizeof(value_type)},
202 new_size);
203 }
204 // Double the capacity. May introduce other allocation policies later.
205 return std::max(mul_sat(Base::capacity(), size_type{2}), new_size);
206 }
207
208 bool ReallocateBuffer(size_type new_capacity);
209
210 Allocator* allocator_;
211 std::byte* buffer_; // raw array for in-place construction and destruction
212};
213
214template <typename ValueType, typename SizeType>
215DynamicDeque<ValueType, SizeType>& DynamicDeque<ValueType, SizeType>::operator=(
216 DynamicDeque&& other) noexcept {
217 Base::clear();
218 allocator_->Deallocate(buffer_);
219
220 allocator_ = other.allocator_; // The other deque keeps its allocator
221 buffer_ = other.buffer_;
222 other.buffer_ = nullptr;
223
224 Base::MoveAssignIndices(other);
225 return *this;
226}
227
228template <typename ValueType, typename SizeType>
229DynamicDeque<ValueType, SizeType>::~DynamicDeque() {
230 Base::clear();
231 allocator_->Deallocate(buffer_);
232}
233
234template <typename ValueType, typename SizeType>
236 return new_capacity <= Base::capacity() ||
237 IncreaseCapacity(GetNewCapacity(new_capacity)) ||
238 IncreaseCapacity(new_capacity);
239}
240
241template <typename ValueType, typename SizeType>
243 size_type new_capacity) {
244 // Try resizing the existing array. Only works if inserting at the end.
245 if (buffer_ != nullptr && Base::CanExtendBuffer() &&
246 allocator_->Resize(buffer_, new_capacity * sizeof(value_type))) {
247 Base::HandleExtendedBuffer(new_capacity);
248 return true;
249 }
250
251 // Allocate a new array and move items to it.
252 return ReallocateBuffer(new_capacity);
253}
254
255template <typename ValueType, typename SizeType>
257 if (Base::size() == Base::capacity()) {
258 return; // Nothing to do; deque is full or buffer_ is nullptr
259 }
260
261 if (Base::empty()) { // Empty deque, but a buffer_ is allocated; free it
262 allocator_->Deallocate(buffer_);
263 buffer_ = nullptr;
264 Base::HandleShrunkBuffer(0);
265 return;
266 }
267
268 // Attempt to shrink if buffer if possible, and reallocate it if needed.
269 //
270 // If there are unused slots at the start, could shift back and Resize()
271 // instead of calling ReallocateBuffer(), but may not be worth the complexity.
272 if (Base::CanShrinkBuffer() &&
273 allocator_->Resize(buffer_, Base::size() * sizeof(value_type))) {
274 Base::HandleShrunkBuffer(Base::size());
275 } else {
276 ReallocateBuffer(Base::size());
277 }
278}
279
280template <typename ValueType, typename SizeType>
282 size_type new_capacity) {
283 std::byte* new_buffer = static_cast<std::byte*>(
284 allocator_->Allocate(allocator::Layout::Of<value_type[]>(new_capacity)));
285 if (new_buffer == nullptr) {
286 return false;
287 }
288
289 pointer dest = std::launder(reinterpret_cast<pointer>(new_buffer));
290 auto [data_1, data_2] = Base::contiguous_data();
291
292 if constexpr (std::is_move_constructible_v<value_type>) {
293 dest = std::uninitialized_move(data_1.begin(), data_1.end(), dest);
294 std::uninitialized_move(data_2.begin(), data_2.end(), dest);
295 } else { // if it can't be moved, try copying
296 dest = std::uninitialized_copy(data_1.begin(), data_1.end(), dest);
297 std::uninitialized_copy(data_2.begin(), data_2.end(), dest);
298 }
299
300 std::destroy(data_1.begin(), data_1.end());
301 std::destroy(data_2.begin(), data_2.end());
302
303 allocator_->Deallocate(buffer_);
304 buffer_ = new_buffer;
305
306 Base::HandleNewBuffer(new_capacity);
307 return true;
308}
309
310template <typename ValueType, typename SizeType>
311template <typename InputIt, typename>
312typename DynamicDeque<ValueType, SizeType>::iterator
313DynamicDeque<ValueType, SizeType>::insert(const_iterator pos,
314 InputIt first,
315 InputIt last) {
316 // Can't safely check std::distance for InputIterator. Use a workaround.
317 if constexpr (std::is_same_v<std::input_iterator_tag,
318 typename std::iterator_traits<
319 InputIt>::iterator_category>) {
320 // Read into a temporary deque so the items can be counted. Then, move into
321 // this deque in one operation. This way, existing items are shifted once to
322 // their final positions, instead of shifting N times for repeated inserts.
323 DynamicDeque temp(*allocator_);
324 temp.assign(first, last);
325 return Base::insert(pos,
326 std::make_move_iterator(temp.data()),
327 std::make_move_iterator(temp.data() + temp.size()));
328 } else { // Use the efficient base implementation for forward iterators.
329 return Base::insert(pos, first, last);
330 }
331}
332
333} // namespace pw
Definition: allocator.h:34
Definition: dynamic_deque.h:55
void reserve(size_type new_capacity)
Increases capacity() to at least new_capacity. Crashes on failure.
Definition: dynamic_deque.h:146
void reserve_exact(size_type new_capacity)
Increases capacity() to exactly new_capacity. Crashes on failure.
Definition: dynamic_deque.h:162
constexpr DynamicDeque(DynamicDeque &&other) noexcept
Definition: dynamic_deque.h:88
void swap(DynamicDeque &other) noexcept
Swaps the contents of two deques. No allocations occur.
Definition: dynamic_deque.h:177
bool try_reserve(size_type new_capacity)
Definition: dynamic_deque.h:235
void shrink_to_fit()
Attempts to reduce capacity() to size(). Not guaranteed to succeed.
Definition: dynamic_deque.h:256
constexpr allocator_type & get_allocator() const
Returns the deque's allocator.
Definition: dynamic_deque.h:174
bool try_reserve_exact(size_type new_capacity)
Definition: dynamic_deque.h:157
constexpr DynamicDeque(Allocator &allocator) noexcept
Definition: dynamic_deque.h:79
Definition: dynamic_vector.h:48
Definition: generic_deque.h:189
bool try_assign(size_type count, const value_type &value)
Definition: generic_deque.h:612
iterator insert(const_iterator pos, const value_type &value)
Definition: generic_deque.h:364
std::optional< iterator > try_emplace(const_iterator pos, Args &&... args)
constexpr size_type capacity() const noexcept
Returns the maximum number of elements in the deque.
Definition: generic_deque.h:63
std::optional< iterator > try_insert(const_iterator pos, const value_type &value)
Definition: generic_deque.h:474
Provides basic helpers for reading and writing UTF-8 encoded strings.
Definition: alignment.h:27
constexpr T mul_sat(T lhs, T rhs) noexcept
Definition: saturating_arithmetic.h:71