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