MySQL  8.0.27
Source Code Documentation
mem_root_array.h
Go to the documentation of this file.
1 /* Copyright (c) 2011, 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_ARRAY_INCLUDED
24 #define MEM_ROOT_ARRAY_INCLUDED
25 
26 #include <assert.h>
27 #include <algorithm>
28 #include <type_traits>
29 #include <utility>
30 
31 #include "my_alloc.h"
32 
33 #include "sql/thr_malloc.h"
34 
35 /**
36  A typesafe replacement for DYNAMIC_ARRAY.
37  We use MEM_ROOT for allocating storage, rather than the C++ heap.
38  The interface is chosen to be similar to std::vector.
39 
40  @remark
41  Mem_root_array_YY is constructor-less for use in the parser stack of unions.
42  For other needs please use Mem_root_array.
43 
44  @remark
45  Unlike DYNAMIC_ARRAY, elements are properly copied
46  (rather than memcpy()d) if the underlying array needs to be expanded.
47 
48  @remark
49  Unless Element_type's destructor is trivial, we destroy objects when they are
50  removed from the array (including when the array object itself is destroyed).
51 
52  @remark
53  Note that MEM_ROOT has no facility for reusing free space,
54  so don't use this if multiple re-expansions are likely to happen.
55 
56  @tparam Element_type The type of the elements of the container.
57  Elements must be copyable.
58 */
59 template <typename Element_type>
61  /**
62  Is Element_type trivially destructible? If it is, we don't destroy
63  elements when they are removed from the array or when the array is
64  destroyed.
65  */
66  static constexpr bool has_trivial_destructor =
68 
69  public:
70  /// Convenience typedef, same typedef name as std::vector
71  typedef Element_type value_type;
72 
73  void init(MEM_ROOT *root) {
74  assert(root != nullptr);
75 
76  m_root = root;
77  m_array = nullptr;
78  m_size = 0;
79  m_capacity = 0;
80  }
81 
82  /// Initialize empty array that we aren't going to grow
84  m_root = nullptr;
85  m_array = nullptr;
86  m_size = 0;
87  m_capacity = 0;
88  }
89 
90  Element_type &at(size_t n) {
91  assert(n < size());
92  return m_array[n];
93  }
94 
95  const Element_type &at(size_t n) const {
96  assert(n < size());
97  return m_array[n];
98  }
99 
100  Element_type &operator[](size_t n) { return at(n); }
101  const Element_type &operator[](size_t n) const { return at(n); }
102 
103  Element_type &back() { return at(size() - 1); }
104  const Element_type &back() const { return at(size() - 1); }
105 
106  /// Random access iterators to value_type and const value_type.
107  typedef Element_type *iterator;
108  typedef const Element_type *const_iterator;
109 
110  /// Returns a pointer to the first element in the array.
111  Element_type *begin() { return &m_array[0]; }
112  const Element_type *begin() const { return &m_array[0]; }
113 
114  /// Returns a pointer to the past-the-end element in the array.
115  Element_type *end() { return &m_array[size()]; }
116  const Element_type *end() const { return &m_array[size()]; }
117 
118  /// Returns a constant pointer to the first element in the array.
119  const_iterator cbegin() const { return begin(); }
120 
121  /// Returns a constant pointer to the past-the-end element in the array.
122  const_iterator cend() const { return end(); }
123 
124  /// Erases all of the elements.
125  void clear() {
126  if (!empty()) chop(0);
127  }
128 
129  /**
130  Chops the tail off the array, erasing all tail elements.
131  @param pos Index of first element to erase.
132  */
133  void chop(const size_t pos) {
134  assert(pos < m_size);
135  if (!has_trivial_destructor) {
136  for (size_t ix = pos; ix < m_size; ++ix) {
137  Element_type *p = &m_array[ix];
138  p->~Element_type(); // Destroy discarded element.
139  }
140  }
141  m_size = pos;
142  }
143 
144  /**
145  Reserves space for array elements.
146  Copies over existing elements, in case we are re-expanding the array.
147 
148  @param n number of elements.
149  @retval true if out-of-memory, false otherwise.
150  */
151  bool reserve(size_t n) {
152  if (n <= m_capacity) return false;
153 
154  void *mem = m_root->Alloc(n * element_size());
155  if (!mem) return true;
156  Element_type *array = static_cast<Element_type *>(mem);
157 
158  // Copy all the existing elements into the new array.
159  for (size_t ix = 0; ix < m_size; ++ix) {
160  Element_type *new_p = &array[ix];
161  Element_type *old_p = &m_array[ix];
162  ::new (new_p)
163  Element_type(std::move(*old_p)); // Copy or move into new location.
165  old_p->~Element_type(); // Destroy the old element.
166  }
167 
168  // Forget the old array.
169  m_array = array;
170  m_capacity = n;
171  return false;
172  }
173 
174  /**
175  Adds a new element at the end of the array, after its current last
176  element. The content of this new element is initialized to a copy of
177  the input argument.
178 
179  @param element Object to copy.
180  @retval true if out-of-memory, false otherwise.
181  */
182  bool push_back(const Element_type &element) {
183  const size_t min_capacity = 20;
184  const size_t expansion_factor = 2;
185  if (0 == m_capacity && reserve(min_capacity)) return true;
186  if (m_size == m_capacity && reserve(m_capacity * expansion_factor))
187  return true;
188  Element_type *p = &m_array[m_size++];
189  ::new (p) Element_type(element);
190  return false;
191  }
192 
193  /**
194  Adds a new element at the end of the array, after its current last
195  element. The content of this new element is initialized by moving
196  the input element.
197 
198  @param element Object to move.
199  @retval true if out-of-memory, false otherwise.
200  */
201  bool push_back(Element_type &&element) {
202  const size_t min_capacity = 20;
203  const size_t expansion_factor = 2;
204  if (0 == m_capacity && reserve(min_capacity)) return true;
205  if (m_size == m_capacity && reserve(m_capacity * expansion_factor))
206  return true;
207  Element_type *p = &m_array[m_size++];
208  ::new (p) Element_type(std::move(element));
209  return false;
210  }
211 
212  /**
213  Adds a new element at the beginning of the array.
214  The content of this new element is initialized to a copy of
215  the input argument.
216 
217  @param element Object to copy.
218  @retval true if out-of-memory, false otherwise.
219  */
220  bool push_front(const Element_type &element) {
221  if (push_back(element)) return true;
222  std::rotate(begin(), end() - 1, end());
223  return false;
224  }
225 
226  /**
227  Adds a new element at the front of the array.
228  The content of this new element is initialized by moving the input element.
229 
230  @param element Object to move.
231  @retval true if out-of-memory, false otherwise.
232  */
233  bool push_front(Element_type &&element) {
234  if (push_back(std::move(element))) return true;
235  std::rotate(begin(), end() - 1, end());
236  return false;
237  }
238 
239  /**
240  Removes the last element in the array, effectively reducing the
241  container size by one. This destroys the removed element.
242  */
243  void pop_back() {
244  assert(!empty());
245  if (!has_trivial_destructor) back().~Element_type();
246  m_size -= 1;
247  }
248 
249  /**
250  Resizes the container so that it contains n elements.
251 
252  If n is smaller than the current container size, the content is
253  reduced to its first n elements, removing those beyond (and
254  destroying them).
255 
256  If n is greater than the current container size, the content is
257  expanded by inserting at the end as many elements as needed to
258  reach a size of n. If val is specified, the new elements are
259  initialized as copies of val, otherwise, they are
260  value-initialized.
261 
262  If n is also greater than the current container capacity, an automatic
263  reallocation of the allocated storage space takes place.
264 
265  Notice that this function changes the actual content of the
266  container by inserting or erasing elements from it.
267  */
268  void resize(size_t n, const value_type &val) {
269  if (n == m_size) return;
270  if (n > m_size) {
271  if (!reserve(n)) {
272  while (n != m_size) push_back(val);
273  }
274  return;
275  }
276  if (!has_trivial_destructor) {
277  while (n != m_size) pop_back();
278  }
279  m_size = n;
280  }
281 
282  /**
283  Same as resize(size_t, const value_type &val), but default-constructs
284  the new elements. This allows one to resize containers even if
285  value_type is not copy-constructible.
286  */
287  void resize(size_t n) {
288  if (n == m_size) return;
289  if (n > m_size) {
290  if (!reserve(n)) {
291  while (n != m_size) push_back(value_type());
292  }
293  return;
294  }
295  if (!has_trivial_destructor) {
296  while (n != m_size) pop_back();
297  }
298  m_size = n;
299  }
300 
301  /**
302  Erase all the elements in the specified range.
303 
304  @param first iterator that points to the first element to remove
305  @param last iterator that points to the element after the
306  last one to remove
307  @return an iterator to the first element after the removed range
308  */
310  iterator pos = begin() + (first - cbegin());
311  if (first != last) {
312  iterator new_end = std::move(last, cend(), pos);
313  chop(new_end - begin());
314  }
315  return pos;
316  }
317 
318  /**
319  Removes a single element from the array.
320 
321  @param position iterator that points to the element to remove
322 
323  @return an iterator to the first element after the removed range
324  */
326  return erase(position, std::next(position));
327  }
328 
329  /**
330  Removes a single element from the array.
331 
332  @param ix zero-based number of the element to remove
333 
334  @return an iterator to the first element after the removed range
335  */
336  iterator erase(size_t ix) {
337  assert(ix < size());
338  return erase(std::next(this->cbegin(), ix));
339  }
340 
341  /**
342  Insert an element at a given position.
343 
344  @param pos the new element is inserted before the element
345  at this position
346  @param value the value of the new element
347  @return an iterator that points to the inserted element
348  */
349  iterator insert(const_iterator pos, const Element_type &value) {
350  ptrdiff_t idx = pos - cbegin();
351  if (!push_back(value)) std::rotate(begin() + idx, end() - 1, end());
352  return begin() + idx;
353  }
354 
355  /**
356  Removes a single element from the array by value.
357  The removed element is destroyed. This effectively reduces the
358  container size by one.
359  Note that if there are multiple elements having the same
360  value, only the first element is removed.
361 
362  This is generally an inefficient operation, since we need to copy
363  elements to fill the "hole" in the array.
364 
365  We use std::copy to move objects, hence Element_type must be
366  assignable.
367 
368  @retval number of elements removed, 0 or 1.
369  */
370  size_t erase_value(const value_type &val) {
371  iterator position = std::find(begin(), end(), val);
372  if (position != end()) {
373  erase(position);
374  return 1;
375  }
376  return 0; // Not found
377  }
378 
379  /**
380  Removes a single element from the array.
381  The removed element is destroyed.
382  This effectively reduces the container size by one.
383 
384  This is generally an inefficient operation, since we need to copy
385  elements to fill the "hole" in the array.
386 
387  We use std::copy to move objects, hence Element_type must be assignable.
388  */
389  iterator erase(iterator position) {
390  assert(position != end());
391  if (position + 1 != end()) std::copy(position + 1, end(), position);
392  this->pop_back();
393  return position;
394  }
395 
396  size_t capacity() const { return m_capacity; }
397  size_t element_size() const { return sizeof(Element_type); }
398  bool empty() const { return size() == 0; }
399  size_t size() const { return m_size; }
400 
401  protected:
403  Element_type *m_array;
404  size_t m_size;
405  size_t m_capacity;
406 
407  // No CTOR/DTOR for this class!
408  // Mem_root_array_YY(const Mem_root_array_YY&);
409  // Mem_root_array_YY &operator=(const Mem_root_array_YY&);
410 };
411 
412 /**
413  A typesafe replacement for DYNAMIC_ARRAY.
414 
415  @see Mem_root_array_YY.
416 */
417 template <typename Element_type>
418 class Mem_root_array : public Mem_root_array_YY<Element_type> {
420 
421  public:
422  /// Convenience typedef, same typedef name as std::vector
423  typedef Element_type value_type;
424 
426 
428 
429  explicit Mem_root_array(MEM_ROOT *root) { super::init(root); }
430 
431  /// Move constructor and assignment.
433  this->m_root = other.m_root;
434  this->m_array = other.m_array;
435  this->m_size = other.m_size;
436  this->m_capacity = other.m_capacity;
437  other.init_empty_const();
438  other.m_root = this->m_root;
439  }
441  if (this != &other) {
442  this->~Mem_root_array();
443  new (this) Mem_root_array(std::move(other));
444  }
445  return *this;
446  }
447 
448  Mem_root_array(MEM_ROOT *root, size_t n) {
449  super::init(root);
450  super::resize(n);
451  }
452 
453  Mem_root_array(MEM_ROOT *root, size_t n, const value_type &val) {
454  super::init(root);
455  super::resize(n, val);
456  }
457 
458  /**
459  Range constructor.
460 
461  Constructs a container with as many elements as the range [first,last),
462  with each element constructed from its corresponding element in that range,
463  in the same order.
464 
465  @param root MEM_ROOT to use for memory allocation.
466  @param first iterator that points to the first element to copy
467  @param last iterator that points to the element after the
468  last one to copy
469  */
471  super::init(root);
472  if (this->reserve(last - first)) return;
473  for (auto it = first; it != last; ++it) this->push_back(*it);
474  }
475 
477  : Mem_root_array(root, x.cbegin(), x.cend()) {}
478 
479  Mem_root_array(std::initializer_list<Element_type> elements)
480  : Mem_root_array(*THR_MALLOC, begin(elements), end(elements)) {}
481 
483 
484  // Not (yet) implemented.
485  Mem_root_array(const Mem_root_array &) = delete;
487 };
488 
489 #endif // MEM_ROOT_ARRAY_INCLUDED
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:60
bool push_back(Element_type &&element)
Adds a new element at the end of the array, after its current last element.
Definition: mem_root_array.h:201
const Element_type * begin() const
Definition: mem_root_array.h:112
const Element_type * const_iterator
Definition: mem_root_array.h:108
iterator erase(iterator position)
Removes a single element from the array.
Definition: mem_root_array.h:389
bool push_front(Element_type &&element)
Adds a new element at the front of the array.
Definition: mem_root_array.h:233
Element_type & back()
Definition: mem_root_array.h:103
const Element_type * end() const
Definition: mem_root_array.h:116
bool empty() const
Definition: mem_root_array.h:398
void init(MEM_ROOT *root)
Definition: mem_root_array.h:73
MEM_ROOT * m_root
Definition: mem_root_array.h:402
bool push_back(const Element_type &element)
Adds a new element at the end of the array, after its current last element.
Definition: mem_root_array.h:182
const Element_type & at(size_t n) const
Definition: mem_root_array.h:95
size_t capacity() const
Definition: mem_root_array.h:396
iterator erase(size_t ix)
Removes a single element from the array.
Definition: mem_root_array.h:336
Element_type & at(size_t n)
Definition: mem_root_array.h:90
size_t size() const
Definition: mem_root_array.h:399
size_t m_capacity
Definition: mem_root_array.h:405
void chop(const size_t pos)
Chops the tail off the array, erasing all tail elements.
Definition: mem_root_array.h:133
const Element_type & back() const
Definition: mem_root_array.h:104
static constexpr bool has_trivial_destructor
Is Element_type trivially destructible? If it is, we don't destroy elements when they are removed fro...
Definition: mem_root_array.h:66
size_t erase_value(const value_type &val)
Removes a single element from the array by value.
Definition: mem_root_array.h:370
Element_type * iterator
Random access iterators to value_type and const value_type.
Definition: mem_root_array.h:107
Element_type value_type
Convenience typedef, same typedef name as std::vector.
Definition: mem_root_array.h:71
Element_type * end()
Returns a pointer to the past-the-end element in the array.
Definition: mem_root_array.h:115
const_iterator cend() const
Returns a constant pointer to the past-the-end element in the array.
Definition: mem_root_array.h:122
Element_type & operator[](size_t n)
Definition: mem_root_array.h:100
void resize(size_t n)
Same as resize(size_t, const value_type &val), but default-constructs the new elements.
Definition: mem_root_array.h:287
size_t m_size
Definition: mem_root_array.h:404
bool push_front(const Element_type &element)
Adds a new element at the beginning of the array.
Definition: mem_root_array.h:220
iterator insert(const_iterator pos, const Element_type &value)
Insert an element at a given position.
Definition: mem_root_array.h:349
const_iterator cbegin() const
Returns a constant pointer to the first element in the array.
Definition: mem_root_array.h:119
size_t element_size() const
Definition: mem_root_array.h:397
Element_type * m_array
Definition: mem_root_array.h:403
iterator erase(const_iterator first, const_iterator last)
Erase all the elements in the specified range.
Definition: mem_root_array.h:309
void clear()
Erases all of the elements.
Definition: mem_root_array.h:125
void pop_back()
Removes the last element in the array, effectively reducing the container size by one.
Definition: mem_root_array.h:243
void resize(size_t n, const value_type &val)
Resizes the container so that it contains n elements.
Definition: mem_root_array.h:268
bool reserve(size_t n)
Reserves space for array elements.
Definition: mem_root_array.h:151
void init_empty_const()
Initialize empty array that we aren't going to grow.
Definition: mem_root_array.h:83
const Element_type & operator[](size_t n) const
Definition: mem_root_array.h:101
iterator erase(const_iterator position)
Removes a single element from the array.
Definition: mem_root_array.h:325
Element_type * begin()
Returns a pointer to the first element in the array.
Definition: mem_root_array.h:111
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:418
Mem_root_array(MEM_ROOT *root, const_iterator first, const_iterator last)
Range constructor.
Definition: mem_root_array.h:470
Mem_root_array(Mem_root_array &&other)
Move constructor and assignment.
Definition: mem_root_array.h:432
Mem_root_array(MEM_ROOT *root, size_t n)
Definition: mem_root_array.h:448
Mem_root_array(MEM_ROOT *root, size_t n, const value_type &val)
Definition: mem_root_array.h:453
Element_type value_type
Convenience typedef, same typedef name as std::vector.
Definition: mem_root_array.h:423
Mem_root_array & operator=(Mem_root_array &&other)
Definition: mem_root_array.h:440
Mem_root_array(const Mem_root_array &)=delete
Mem_root_array()
Definition: mem_root_array.h:427
~Mem_root_array()
Definition: mem_root_array.h:482
Mem_root_array(std::initializer_list< Element_type > elements)
Definition: mem_root_array.h:479
Mem_root_array_YY< Element_type > super
Definition: mem_root_array.h:419
Mem_root_array(MEM_ROOT *root, const Mem_root_array &x)
Definition: mem_root_array.h:476
Mem_root_array & operator=(const Mem_root_array &)=delete
super::const_iterator const_iterator
Definition: mem_root_array.h:425
Mem_root_array(MEM_ROOT *root)
Definition: mem_root_array.h:429
const char * p
Definition: ctype-mb.cc:1236
char * pos
Definition: do_ctype.cc:76
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...
thread_local MEM_ROOT ** THR_MALLOC
Definition: mysqld.cc:1527
const byte * find(const Pages *pages, const page_id_t &page_id) noexcept
Find a doublewrite copy of a page.
Definition: buf0dblwr.cc:2519
const string value("\"Value\"")
static MEM_ROOT mem
Definition: sql_servers.cc:98
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
int n
Definition: xcom_base.cc:505