MySQL 9.2.0
Source Code Documentation
mem_root_deque.h
Go to the documentation of this file.
1/* Copyright (c) 2019, 2024, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is designed to work with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have either included with
13 the program or referenced in the documentation.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
23
24#ifndef MEM_ROOT_DEQUE_H
25#define MEM_ROOT_DEQUE_H
26
27#include <algorithm>
28#include <memory>
29#include <type_traits>
30#include <utility>
31
32#include <assert.h>
33#include <stdint.h>
34
35#include "my_alloc.h"
36
37template <class Element_type>
38static constexpr size_t FindElementsPerBlock() {
39 // Aim for 1 kB.
40 size_t base_number_elems =
41 1024 / sizeof(Element_type); // NOLINT(bugprone-sizeof-expression)
42
43 // Find the next power of two, rounded up. We should have at least 16 elements
44 // per block to avoid allocating way too often (although the code itself
45 // should work fine with 1, for debugging purposes).
46 for (size_t block_size = 16; block_size < 1024; ++block_size) {
47 if (block_size >= base_number_elems) {
48 return block_size;
49 }
50 }
51 return 1024;
52}
53
54/**
55 A (partial) implementation of std::deque allocating its blocks on a MEM_ROOT.
56
57 This class works pretty much like an std::deque with a Mem_root_allocator,
58 and used to be a forwarder to it. However, libstdc++ has a very complicated
59 implementation of std::deque, leading to code blowup (e.g., operator[] is
60 23 instructions on x86-64, including two branches), and we cannot easily use
61 libc++ on all platforms. This version is instead:
62
63 - Optimized for small, straight-through machine code (few and simple
64 instructions, few branches).
65 - Optimized for few elements; in particular, zero elements is an important
66 special case, much more so than 10,000.
67
68 It gives mostly the same guarantees as std::deque; elements can be
69 inserted efficiently on both front and back [1]. {push,pop}_{front,back}
70 guarantees reference stability except for to removed elements (obviously),
71 and invalidates iterators. (Iterators are forcefully invalidated using
72 asserts.) erase() does the same. Note that unlike std::deque, insert()
73 at begin() will invalidate references. Some functionality, like several
74 constructors, resize(), shrink_to_fit(), swap(), etc. is missing.
75
76 The implementation is the same as classic std::deque: Elements are held in
77 blocks of about 1 kB each. Once an element is in a block, it never moves
78 (giving the aforementioned pointer stability). The blocks are held in an
79 array, which can be reallocated when more blocks are needed. The
80 implementation keeps track of the used items in terms of “physical indexes”;
81 element 0 starts at the first byte of the first block, element 1 starts
82 immediately after 0, and so on. So you can have something like (assuming very
83 small blocks of only 4 elements each for the sake of drawing):
84
85 block 0 block 1 block 2
86 ↓ ↓ ↓
87 [x x 2 3] [4 5 6 7] [8 9 x x]
88 ↑ ↑
89 begin_idx = 2 end_idx = 10
90
91 end_idx counts as is customary one-past-the-end, so in this case, the elements
92 [2,9) would be valid, and e.g. (*this)[4] would give physical index 6, which
93 points to the third element (index 2) in the middle block (block 1). Inserting
94 a new element at the front is as easy as putting it in physical index 1 and
95 adjusting begin_idx to the left. This means a lookup by index requires some
96 shifting, masking and a double indirect load.
97
98 Iterators keep track of which deque they belong to, and what physical index
99 they point to. (So lookup by iterator also requires a double indirect load,
100 but the alternative would be caching the block pointer and having an extra
101 branch when advancing the iterator.) Inserting a new block at the beginning
102 would move around all the physical indexes (which is why iterators get
103 invalidated; we could probably get around this by having an “offset to first
104 block”, but it's likely not worth it.)
105
106 [1] Actually, it's O(n), since there's no exponential growth of the blocks
107 array. But the blocks are reallocated very rarely, so it is generally
108 efficient nevertheless.
109 */
110template <class Element_type>
112 public:
113 /// Used to conform to STL algorithm demands.
114 using size_type = size_t;
115 using difference_type = ptrdiff_t;
116 using value_type = Element_type;
117 using pointer = Element_type *;
118 using reference = Element_type &;
119 using const_pointer = const Element_type *;
120 using const_reference = const Element_type &;
121
122 /// Constructor. Leaves the array in an empty, valid state.
124
125 // Copy constructor and assignment. We could probably be a bit smarter
126 // about these for large arrays, if the source array has e.g. empty blocks.
128 : m_begin_idx(other.m_begin_idx),
129 m_end_idx(other.m_end_idx),
130 m_capacity(other.m_capacity),
131 m_root(other.m_root) {
133 for (size_t block_idx = 0; block_idx < num_blocks(); ++block_idx) {
134 m_blocks[block_idx].init(m_root);
135 }
136 for (size_t idx = m_begin_idx; idx != m_end_idx; ++idx) {
137 new (&get(idx)) Element_type(other.get(idx));
138 }
139 }
141 if (this != &other) {
142 clear();
143 for (const Element_type &elem : other) {
144 push_back(elem);
145 }
146 }
147 return *this;
148 }
149
150 // Move constructor and assignment.
152 : m_blocks(other.m_blocks),
154 m_end_idx(other.m_end_idx),
155 m_capacity(other.m_capacity),
156 m_root(other.m_root) {
157 other.m_blocks = nullptr;
158 other.m_begin_idx = other.m_end_idx = other.m_capacity = 0;
159 other.invalidate_iterators();
160 }
162 if (this != &other) {
163 this->~mem_root_deque();
164 new (this) mem_root_deque(std::move(other));
165 }
166 return *this;
167 }
168
170
171 Element_type &operator[](size_t idx) const { return get(idx + m_begin_idx); }
172
173 /**
174 Adds the given element to the end of the deque.
175 The element is a copy of the given one.
176
177 @returns true on OOM (no change is done if so)
178 */
179 bool push_back(const Element_type &element) {
180 if (m_end_idx == m_capacity) {
181 if (add_block_back()) {
182 return true;
183 }
184 }
185 new (&get(m_end_idx++)) Element_type(element);
187 return false;
188 }
189
190 /**
191 Adds the given element to the end of the deque.
192 The element is moved into place.
193
194 @returns true on OOM (no change is done if so)
195 */
196 bool push_back(Element_type &&element) {
197 if (m_end_idx == m_capacity) {
198 if (add_block_back()) {
199 return true;
200 }
201 }
202 new (&get(m_end_idx++)) Element_type(std::move(element));
204 return false;
205 }
206
207 /**
208 Adds the given element to the beginning of the deque.
209 The element is a copy of the given one.
210
211 @returns true on OOM (no change is done if so)
212 */
213 bool push_front(const Element_type &element) {
214 if (m_begin_idx == 0) {
215 if (add_block_front()) {
216 return true;
217 }
218 assert(m_begin_idx != 0);
219 }
220 new (&get(--m_begin_idx)) Element_type(element);
222 return false;
223 }
224
225 /**
226 Adds the given element to the end of the deque.
227 The element is moved into place.
228 */
229 bool push_front(Element_type &&element) {
230 if (m_begin_idx == 0) {
231 if (add_block_front()) {
232 return true;
233 }
234 assert(m_begin_idx != 0);
235 }
236 new (&get(--m_begin_idx)) Element_type(std::move(element));
238 return false;
239 }
240
241 /// Removes the last element from the deque.
242 void pop_back() {
243 assert(!empty());
246 }
247
248 /// Removes the first element from the deque.
249 void pop_front() {
250 assert(!empty());
253 }
254
255 /// Returns the first element in the deque.
256 Element_type &front() {
257 assert(!empty());
258 return get(m_begin_idx);
259 }
260
261 const Element_type &front() const {
262 assert(!empty());
263 return get(m_begin_idx);
264 }
265
266 /// Returns the last element in the deque.
267 Element_type &back() {
268 assert(!empty());
269 return get(m_end_idx - 1);
270 }
271
272 const Element_type &back() const {
273 assert(!empty());
274 return get(m_end_idx - 1);
275 }
276
277 /// Removes all elements from the deque. Destructors are called,
278 /// but since the elements themselves are allocated on the MEM_ROOT,
279 /// their memory cannot be freed.
280 void clear() {
281 for (size_t idx = m_begin_idx; idx != m_end_idx; ++idx) {
282 ::destroy_at(&get(idx));
283 }
286 }
287
288 template <class Iterator_element_type>
289 class Iterator {
290 public:
291 using difference_type = ptrdiff_t;
292 using value_type = Iterator_element_type;
293 using pointer = Iterator_element_type *;
294 using reference = Iterator_element_type &;
295 using iterator_category = std::random_access_iterator_tag;
296
297 // DefaultConstructible (required for ForwardIterator).
298 Iterator() = default;
299
300 Iterator(const mem_root_deque *deque, size_t physical_idx)
301 : m_deque(deque), m_physical_idx(physical_idx) {
302#ifndef NDEBUG
304#endif
305 }
306
307 /// For const_iterator: Implicit conversion from iterator.
308 /// This is written in a somewhat cumbersome fashion to avoid
309 /// declaring an explicit copy constructor for iterator,
310 /// which causes compiler warnings other places for some compilers.
311 // NOLINTNEXTLINE(google-explicit-constructor): Intentional.
312 template <
313 class T,
314 typename = std::enable_if_t<
315 std::is_const<Iterator_element_type>::value &&
316 std::is_same<typename T::value_type,
317 std::remove_const_t<Iterator_element_type>>::value>>
318 Iterator(const T &other)
320#ifndef NDEBUG
321 m_generation = other.m_generation;
322#endif
323 }
324
325 // Iterator (required for InputIterator).
326 Iterator_element_type &operator*() const {
328 return m_deque->get(m_physical_idx);
329 }
333 return *this;
334 }
335
336 // EqualityComparable (required for InputIterator).
337 bool operator==(const Iterator &other) const {
339 assert(m_deque == other.m_deque);
340 return m_physical_idx == other.m_physical_idx;
341 }
342
343 // InputIterator (required for ForwardIterator).
344 bool operator!=(const Iterator &other) const { return !(*this == other); }
345
346 Iterator_element_type *operator->() const {
348 return &m_deque->get(m_physical_idx);
349 }
350
351 // ForwardIterator (required for RandomAccessIterator).
354 Iterator ret = *this;
356 return ret;
357 }
358
359 // BidirectionalIterator (required for RandomAccessIterator).
363 return *this;
364 }
367 Iterator ret = *this;
369 return ret;
370 }
371
372 // RandomAccessIterator.
376 return *this;
377 }
378
382 return *this;
383 }
384
387 return Iterator{m_deque, m_physical_idx + offset};
388 }
389
392 return Iterator{m_deque, m_physical_idx - offset};
393 }
394
395 difference_type operator-(const Iterator &other) const {
397 assert(m_deque == other.m_deque);
398 return m_physical_idx - other.m_physical_idx;
399 }
400
401 Iterator_element_type &operator[](size_t idx) const {
402 return *(*this + idx);
403 }
404
405 bool operator<(const Iterator &other) const {
407 assert(m_deque == other.m_deque);
408 return m_physical_idx < other.m_physical_idx;
409 }
410
411 bool operator<=(const Iterator &other) const { return !(*this > other); }
412
413 bool operator>(const Iterator &other) const {
415 assert(m_deque == other.m_deque);
416 return m_physical_idx > other.m_physical_idx;
417 }
418
419 bool operator>=(const Iterator &other) const { return !(*this < other); }
420
421 private:
422 const mem_root_deque *m_deque = nullptr;
423 size_t m_physical_idx = 0;
424#ifndef NDEBUG
425 size_t m_generation = 0;
426#endif
427
429 assert(m_generation == m_deque->generation());
430 }
431
432 friend class mem_root_deque;
433 };
434
437 using reverse_iterator = std::reverse_iterator<iterator>;
438 using reverse_const_iterator = std::reverse_iterator<const_iterator>;
439
440 iterator begin() { return iterator{this, m_begin_idx}; }
441 iterator end() { return iterator{this, m_end_idx}; }
442 reverse_iterator rbegin() { return std::make_reverse_iterator(end()); }
443 reverse_iterator rend() { return std::make_reverse_iterator(begin()); }
447 const_iterator end() const { return const_iterator{this, m_end_idx}; }
449 return std::make_reverse_iterator(end());
450 }
452 return std::make_reverse_iterator(begin());
453 }
455 return std::make_reverse_iterator(end());
456 }
458 return std::make_reverse_iterator(begin());
459 }
460
461 size_t size() const { return m_end_idx - m_begin_idx; }
462 bool empty() const { return size() == 0; }
463
464 /**
465 Erase all the elements in the specified range.
466
467 @param first iterator that points to the first element to remove
468 @param last iterator that points to the element after the
469 last one to remove
470 @return an iterator to the first element after the removed range
471 */
473 iterator pos = begin() + (first - cbegin());
474 if (first != last) {
475 iterator new_end = std::move(last, cend(), pos);
476 for (size_t idx = new_end.m_physical_idx; idx != m_end_idx; ++idx) {
477 ::destroy_at(&get(idx));
478 }
479 m_end_idx = new_end.m_physical_idx;
480 }
482#ifndef NDEBUG
483 pos.m_generation = m_generation; // Re-validate.
484#endif
485 return pos;
486 }
487
488 /**
489 Removes a single element from the array.
490
491 @param position iterator that points to the element to remove
492
493 @return an iterator to the first element after the removed range
494 */
496 return erase(position, std::next(position));
497 }
498
499 /**
500 Insert an element at a given position.
501 The element is a copy of the given one.
502
503 @param pos the new element is inserted before the element
504 at this position
505 @param value the value of the new element
506 @return an iterator that points to the inserted element
507 */
508 iterator insert(const_iterator pos, const Element_type &value) {
509 difference_type idx = pos - cbegin();
510 push_back(value);
511 std::rotate(begin() + idx, end() - 1, end());
513 return begin() + idx;
514 }
515
516 /**
517 Insert an element at a given position.
518 The element is moved into place.
519
520 @param pos the new element is inserted before the element
521 at this position
522 @param value the value of the new element
523 @return an iterator that points to the inserted element
524 */
525 iterator insert(const_iterator pos, Element_type &&value) {
526 difference_type idx = pos - cbegin();
527 push_back(std::move(value));
528 std::rotate(begin() + idx, end() - 1, end());
530 return begin() + idx;
531 }
532
533 template <class ForwardIt>
534 iterator insert(const_iterator pos, ForwardIt first, ForwardIt last) {
535 difference_type idx = pos - cbegin();
536 for (ForwardIt it = first; it != last; ++it) {
537 push_back(*it);
538 }
539 std::rotate(begin() + idx, end() - (last - first), end());
541 return begin() + idx;
542 }
543
544 private:
545 /// Number of elements in each block.
546 static constexpr size_t block_elements = FindElementsPerBlock<Element_type>();
547
548 // A block capable of storing <block_elements> elements. Deliberately
549 // has no constructor, since it wouldn't help any of the code that actually
550 // allocates any blocks (all it would do would be to hinder using
551 // ArrayAlloc when allocating new blocks).
552 struct Block {
553 Element_type *elements;
554
556 // Use Alloc instead of ArrayAlloc, so that no constructors are called.
557 elements = static_cast<Element_type *>(mem_root->Alloc(
559 sizeof(Element_type))); // NOLINT(bugprone-sizeof-expression)
560 return elements == nullptr;
561 }
562 };
563
564 /// Pointer to the first block. Can be nullptr if there are no elements
565 /// (this makes the constructor cheaper). Stored on the MEM_ROOT,
566 /// and needs no destruction, so just a raw pointer.
567 Block *m_blocks = nullptr;
568
569 /// Physical index to the first valid element.
570 size_t m_begin_idx = 0;
571
572 /// Physical index one past the last valid element. If begin == end,
573 /// the array is empty (and then it doesn't matter what the values are).
574 size_t m_end_idx = 0;
575
576 /// Number of blocks, multiplied by block_elements. (Storing this instead
577 /// of the number of blocks itself makes testing in push_back cheaper.)
578 size_t m_capacity = 0;
579
580 /// Pointer to the MEM_ROOT that we store our blocks and elements on.
582
583#ifndef NDEBUG
584 /// Incremented each time we make an operation that would invalidate
585 /// iterators. Asserts use this value in debug mode to be able to
586 /// verify that they have not been invalidated. (In optimized mode,
587 /// using an invalidated iterator incurs undefined behavior.)
588 size_t m_generation = 0;
590#else
591 void invalidate_iterators() {}
592#endif
593
594 /// Adds the first block of elements.
597 if (m_blocks == nullptr) {
598 return true;
599 }
600 if (m_blocks[0].init(m_root)) {
601 return true;
602 }
605 return false;
606 }
607
608 // Not inlined, to get them off of the hot path.
609 bool add_block_back();
610 bool add_block_front();
611
612 size_t num_blocks() const { return m_capacity / block_elements; }
613
614 /// Gets a reference to the memory used to store an element with the given
615 /// physical index, starting from zero. Note that block_elements is always
616 /// a power of two, so the division and modulus operations are cheap.
617 Element_type &get(size_t physical_idx) const {
618 return m_blocks[physical_idx / block_elements]
619 .elements[physical_idx % block_elements];
620 }
621
622#ifndef NDEBUG
623 size_t generation() const { return m_generation; }
624#endif
625};
626
627// TODO(sgunders): Consider storing spare blocks at either end to have
628// exponential growth and get true O(1) allocation.
629
630template <class Element_type>
632 if (m_blocks == nullptr) {
633 return add_initial_block();
634 }
635 Block *new_blocks = m_root->ArrayAlloc<Block>(num_blocks() + 1);
636 if (new_blocks == nullptr) {
637 return true;
638 }
639 memcpy(new_blocks, m_blocks, sizeof(Block) * num_blocks());
640 if (new_blocks[num_blocks()].init(m_root)) {
641 return true;
642 }
643
644 m_blocks = new_blocks;
645 m_capacity += block_elements;
646 return false;
647}
648
649template <class Element_type>
651 if (m_blocks == nullptr) {
652 if (add_initial_block()) {
653 return true;
654 }
655 if (m_begin_idx == 0) {
656 // Only relevant for very small values of block_elements.
657 m_begin_idx = m_end_idx = 1;
658 }
659 return false;
660 }
661 Block *new_blocks = m_root->ArrayAlloc<Block>(num_blocks() + 1);
662 memcpy(new_blocks + 1, m_blocks, sizeof(Block) * num_blocks());
663 if (new_blocks[0].init(m_root)) {
664 return true;
665 }
666
667 m_blocks = new_blocks;
668 m_begin_idx += block_elements;
669 m_end_idx += block_elements;
670 m_capacity += block_elements;
671 return false;
672}
673
674#endif // MEM_ROOT_DEQUE_H
static mysql_service_status_t init()
Component initialization.
Definition: audit_api_message_emit.cc:571
Definition: mem_root_deque.h:289
Iterator_element_type * operator->() const
Definition: mem_root_deque.h:346
bool operator>(const Iterator &other) const
Definition: mem_root_deque.h:413
Iterator operator+(difference_type offset) const
Definition: mem_root_deque.h:385
bool operator>=(const Iterator &other) const
Definition: mem_root_deque.h:419
bool operator==(const Iterator &other) const
Definition: mem_root_deque.h:337
Iterator operator--(int)
Definition: mem_root_deque.h:365
bool operator<(const Iterator &other) const
Definition: mem_root_deque.h:405
size_t m_generation
Definition: mem_root_deque.h:425
difference_type operator-(const Iterator &other) const
Definition: mem_root_deque.h:395
std::random_access_iterator_tag iterator_category
Definition: mem_root_deque.h:295
Iterator(const mem_root_deque *deque, size_t physical_idx)
Definition: mem_root_deque.h:300
bool operator<=(const Iterator &other) const
Definition: mem_root_deque.h:411
Iterator_element_type * pointer
Definition: mem_root_deque.h:293
Iterator_element_type & operator[](size_t idx) const
Definition: mem_root_deque.h:401
Iterator & operator--()
Definition: mem_root_deque.h:360
Iterator operator-(difference_type offset) const
Definition: mem_root_deque.h:390
void assert_not_invalidated() const
Definition: mem_root_deque.h:428
Iterator & operator++()
Definition: mem_root_deque.h:330
Iterator_element_type & operator*() const
Definition: mem_root_deque.h:326
Iterator & operator-=(difference_type diff)
Definition: mem_root_deque.h:379
Iterator_element_type & reference
Definition: mem_root_deque.h:294
Iterator operator++(int)
Definition: mem_root_deque.h:352
Iterator(const T &other)
For const_iterator: Implicit conversion from iterator.
Definition: mem_root_deque.h:318
Iterator & operator+=(difference_type diff)
Definition: mem_root_deque.h:373
const mem_root_deque * m_deque
Definition: mem_root_deque.h:422
ptrdiff_t difference_type
Definition: mem_root_deque.h:291
Iterator_element_type value_type
Definition: mem_root_deque.h:292
size_t m_physical_idx
Definition: mem_root_deque.h:423
bool operator!=(const Iterator &other) const
Definition: mem_root_deque.h:344
A (partial) implementation of std::deque allocating its blocks on a MEM_ROOT.
Definition: mem_root_deque.h:111
Element_type & operator[](size_t idx) const
Definition: mem_root_deque.h:171
reverse_iterator rbegin()
Definition: mem_root_deque.h:442
iterator insert(const_iterator pos, Element_type &&value)
Insert an element at a given position.
Definition: mem_root_deque.h:525
std::reverse_iterator< const_iterator > reverse_const_iterator
Definition: mem_root_deque.h:438
const Element_type * const_pointer
Definition: mem_root_deque.h:119
void invalidate_iterators()
Definition: mem_root_deque.h:589
iterator erase(const_iterator first, const_iterator last)
Erase all the elements in the specified range.
Definition: mem_root_deque.h:472
size_t size() const
Definition: mem_root_deque.h:461
iterator insert(const_iterator pos, ForwardIt first, ForwardIt last)
Definition: mem_root_deque.h:534
bool push_back(Element_type &&element)
Adds the given element to the end of the deque.
Definition: mem_root_deque.h:196
static constexpr size_t block_elements
Number of elements in each block.
Definition: mem_root_deque.h:546
reverse_const_iterator rbegin() const
Definition: mem_root_deque.h:454
size_t size_type
Used to conform to STL algorithm demands.
Definition: mem_root_deque.h:114
reverse_const_iterator rend() const
Definition: mem_root_deque.h:457
reverse_const_iterator crbegin() const
Definition: mem_root_deque.h:448
Element_type & front()
Returns the first element in the deque.
Definition: mem_root_deque.h:256
bool add_initial_block()
Adds the first block of elements.
Definition: mem_root_deque.h:595
bool add_block_back()
Definition: mem_root_deque.h:631
const_iterator cend()
Definition: mem_root_deque.h:445
size_t m_begin_idx
Physical index to the first valid element.
Definition: mem_root_deque.h:570
const Element_type & back() const
Definition: mem_root_deque.h:272
mem_root_deque(const mem_root_deque &other)
Definition: mem_root_deque.h:127
size_t m_end_idx
Physical index one past the last valid element.
Definition: mem_root_deque.h:574
Element_type value_type
Definition: mem_root_deque.h:116
bool push_back(const Element_type &element)
Adds the given element to the end of the deque.
Definition: mem_root_deque.h:179
void clear()
Removes all elements from the deque.
Definition: mem_root_deque.h:280
reverse_iterator rend()
Definition: mem_root_deque.h:443
ptrdiff_t difference_type
Definition: mem_root_deque.h:115
std::reverse_iterator< iterator > reverse_iterator
Definition: mem_root_deque.h:437
iterator erase(const_iterator position)
Removes a single element from the array.
Definition: mem_root_deque.h:495
const Element_type & front() const
Definition: mem_root_deque.h:261
const Element_type & const_reference
Definition: mem_root_deque.h:120
Block * m_blocks
Pointer to the first block.
Definition: mem_root_deque.h:567
mem_root_deque & operator=(mem_root_deque &&other)
Definition: mem_root_deque.h:161
const_iterator end() const
Definition: mem_root_deque.h:447
iterator insert(const_iterator pos, const Element_type &value)
Insert an element at a given position.
Definition: mem_root_deque.h:508
bool push_front(const Element_type &element)
Adds the given element to the beginning of the deque.
Definition: mem_root_deque.h:213
mem_root_deque(MEM_ROOT *mem_root)
Constructor. Leaves the array in an empty, valid state.
Definition: mem_root_deque.h:123
mem_root_deque & operator=(const mem_root_deque &other)
Definition: mem_root_deque.h:140
size_t m_capacity
Number of blocks, multiplied by block_elements.
Definition: mem_root_deque.h:578
Element_type & reference
Definition: mem_root_deque.h:118
Element_type & back()
Returns the last element in the deque.
Definition: mem_root_deque.h:267
Element_type * pointer
Definition: mem_root_deque.h:117
reverse_const_iterator crend() const
Definition: mem_root_deque.h:451
Element_type & get(size_t physical_idx) const
Gets a reference to the memory used to store an element with the given physical index,...
Definition: mem_root_deque.h:617
const_iterator begin() const
Definition: mem_root_deque.h:446
~mem_root_deque()
Definition: mem_root_deque.h:169
const_iterator cbegin()
Definition: mem_root_deque.h:444
void pop_front()
Removes the first element from the deque.
Definition: mem_root_deque.h:249
bool empty() const
Definition: mem_root_deque.h:462
bool push_front(Element_type &&element)
Adds the given element to the end of the deque.
Definition: mem_root_deque.h:229
size_t num_blocks() const
Definition: mem_root_deque.h:612
iterator begin()
Definition: mem_root_deque.h:440
size_t generation() const
Definition: mem_root_deque.h:623
MEM_ROOT * m_root
Pointer to the MEM_ROOT that we store our blocks and elements on.
Definition: mem_root_deque.h:581
void pop_back()
Removes the last element from the deque.
Definition: mem_root_deque.h:242
bool add_block_front()
Definition: mem_root_deque.h:650
iterator end()
Definition: mem_root_deque.h:441
size_t m_generation
Incremented each time we make an operation that would invalidate iterators.
Definition: mem_root_deque.h:588
mem_root_deque(mem_root_deque &&other)
Definition: mem_root_deque.h:151
static MEM_ROOT mem_root
Definition: client_plugin.cc:114
static Bigint * diff(Bigint *a, Bigint *b, Stack_alloc *alloc)
Definition: dtoa.cc:1081
static constexpr size_t FindElementsPerBlock()
Definition: mem_root_deque.h:38
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...
void destroy_at(T *ptr)
Definition: my_alloc.h:462
uint16_t value_type
Definition: vt100.h:184
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:83
T * ArrayAlloc(size_t num, Args... args)
Allocate 'num' objects of type T, and initialize them to a default value that is created by passing t...
Definition: my_alloc.h:180
void * Alloc(size_t length)
Allocate memory.
Definition: my_alloc.h:145
Definition: mem_root_deque.h:552
Element_type * elements
Definition: mem_root_deque.h:553
bool init(MEM_ROOT *mem_root)
Definition: mem_root_deque.h:555