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