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