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