MySQL  8.0.26
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 
35 template <class Element_type>
36 static 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  */
108 template <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),
151  m_begin_idx(other.m_begin_idx),
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());
241  ::destroy(&get(--m_end_idx));
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<
313  std::is_same<typename T::value_type,
314  std::remove_const_t<Iterator_element_type>>::value>>
315  Iterator(const T &other)
316  : m_deque(other.m_deque), m_physical_idx(other.m_physical_idx) {
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  }
329  ++m_physical_idx;
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;
352  ++m_physical_idx;
353  return ret;
354  }
355 
356  // BidirectionalIterator (required for RandomAccessIterator).
359  --m_physical_idx;
360  return *this;
361  }
364  Iterator ret = *this;
365  --m_physical_idx;
366  return ret;
367  }
368 
369  // RandomAccessIterator.
372  m_physical_idx += diff;
373  return *this;
374  }
375 
378  m_physical_idx -= diff;
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 
425  void assert_not_invalidated() const {
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()); }
443  const_iterator begin() const { return const_iterator{this, m_begin_idx}; }
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  */
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.
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 
627 template <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 
646 template <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:571
Definition: mem_root_deque.h:286
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 & operator-=(difference_type diff)
Definition: mem_root_deque.h:376
Iterator_element_type * pointer
Definition: mem_root_deque.h:290
Iterator & operator--()
Definition: mem_root_deque.h:357
Iterator & operator+=(difference_type diff)
Definition: mem_root_deque.h:370
Iterator_element_type & operator[](size_t idx) const
Definition: mem_root_deque.h:398
Iterator operator-(difference_type offset)
Definition: mem_root_deque.h:387
void assert_not_invalidated() const
Definition: mem_root_deque.h:425
Iterator_element_type * operator->() const
Definition: mem_root_deque.h:343
Iterator & operator++()
Definition: mem_root_deque.h:327
Iterator_element_type & reference
Definition: mem_root_deque.h:291
Iterator_element_type & operator*() const
Definition: mem_root_deque.h:323
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
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 & front()
Returns the first element in the deque.
Definition: mem_root_deque.h:253
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
const Element_type & front() const
Definition: mem_root_deque.h:258
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
mem_root_deque & operator=(const mem_root_deque &other)
Definition: mem_root_deque.h:138
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
Element_type & operator[](size_t idx) const
Definition: mem_root_deque.h:168
reverse_const_iterator rend() const
Definition: mem_root_deque.h:454
reverse_const_iterator crbegin() const
Definition: mem_root_deque.h:445
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
mem_root_deque(const mem_root_deque &other)
Definition: mem_root_deque.h:125
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
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
const Element_type & back() const
Definition: mem_root_deque.h:269
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 & 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
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 * pointer
Definition: mem_root_deque.h:115
reverse_const_iterator crend() const
Definition: mem_root_deque.h:448
const_iterator begin() const
Definition: mem_root_deque.h:443
Element_type & back()
Returns the last element in the deque.
Definition: mem_root_deque.h:264
~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
const string value("\"Value\"")
The MEM_ROOT is a simple arena, where allocations are carved out of larger blocks.
Definition: my_alloc.h:78
void * Alloc(size_t length)
Allocate memory.
Definition: my_alloc.h:135
T * ArrayAlloc(size_t num, Args &&... args)
Allocate “num” objects of type T, and default-construct them.
Definition: my_alloc.h:165
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