MySQL  8.0.17
Source Code Documentation
prealloced_array.h
Go to the documentation of this file.
1 /* Copyright (c) 2013, 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 PREALLOCED_ARRAY_INCLUDED
24 #define PREALLOCED_ARRAY_INCLUDED
25 
26 /**
27  @file include/prealloced_array.h
28 */
29 
30 #include <stddef.h>
31 #include <algorithm>
32 #include <new>
33 #include <type_traits>
34 #include <utility>
35 
36 #include "my_compiler.h"
37 #include "my_dbug.h"
38 #include "my_inttypes.h"
39 #include "my_sys.h"
40 #include "mysql/psi/psi_memory.h"
42 
43 /**
44  A typesafe replacement for DYNAMIC_ARRAY. We do our own memory management,
45  and pre-allocate space for a number of elements. The purpose is to
46  pre-allocate enough elements to cover normal use cases, thus saving
47  malloc()/free() overhead.
48  If we run out of space, we use malloc to allocate more space.
49 
50  The interface is chosen to be similar to std::vector.
51  We keep the std::vector property that storage is contiguous.
52 
53  @remark
54  Unlike DYNAMIC_ARRAY, elements are properly copied
55  (rather than memcpy()d) if the underlying array needs to be expanded.
56 
57  @remark
58  Depending on Has_trivial_destructor, we destroy objects which are
59  removed from the array (including when the array object itself is destroyed).
60 
61  @tparam Element_type The type of the elements of the container.
62  Elements must be copyable or movable.
63  @tparam Prealloc Number of elements to pre-allocate.
64  */
65 template <typename Element_type, size_t Prealloc>
67  /**
68  Is Element_type trivially destructible? If it is, we don't destroy
69  elements when they are removed from the array or when the array is
70  destroyed.
71  */
72  static constexpr bool Has_trivial_destructor =
74 
75  /**
76  Casts the raw buffer to the proper Element_type.
77  We use a raw buffer rather than Element_type[] in order to avoid having
78  CTORs/DTORs invoked by the C++ runtime.
79  */
80  Element_type *cast_rawbuff() {
81  return static_cast<Element_type *>(static_cast<void *>(m_buff));
82  }
83 
84  public:
85  /// Initial capacity of the array.
86  static const size_t initial_capacity = Prealloc;
87 
88  /// Standard typedefs.
89  typedef Element_type value_type;
90  typedef size_t size_type;
91  typedef ptrdiff_t difference_type;
92 
93  typedef Element_type *iterator;
94  typedef const Element_type *const_iterator;
95 
96  explicit Prealloced_array(PSI_memory_key psi_key)
97  : m_size(0),
98  m_capacity(Prealloc),
100  m_psi_key(psi_key) {
101  static_assert(Prealloc != 0, "We do not want a zero-size array.");
102  }
103 
104  /**
105  Initializes (parts of) the array with default values.
106  Using 'Prealloc' for initial_size makes this similar to a raw C array.
107  */
108  Prealloced_array(PSI_memory_key psi_key, size_t initial_size)
109  : m_size(0),
110  m_capacity(Prealloc),
112  m_psi_key(psi_key) {
113  static_assert(Prealloc != 0, "We do not want a zero-size array.");
114 
115  if (initial_size > Prealloc) {
116  // We avoid using reserve() since it requires Element_type to be copyable.
117  void *mem =
118  my_malloc(m_psi_key, initial_size * element_size(), MYF(MY_WME));
119  if (!mem) return;
120  m_array_ptr = static_cast<Element_type *>(mem);
121  m_capacity = initial_size;
122  }
123  for (size_t ix = 0; ix < initial_size; ++ix) {
124  Element_type *p = &m_array_ptr[m_size++];
125  ::new (p) Element_type();
126  }
127  }
128 
129  /**
130  An object instance "owns" its array, so we do deep copy here.
131  */
133  : m_size(0),
134  m_capacity(Prealloc),
136  m_psi_key(that.m_psi_key) {
137  if (this->reserve(that.capacity())) return;
138  for (const Element_type *p = that.begin(); p != that.end(); ++p)
139  this->push_back(*p);
140  }
141 
142  /**
143  Range constructor.
144 
145  Constructs a container with as many elements as the range [first,last),
146  with each element constructed from its corresponding element in that range,
147  in the same order.
148  */
150  const_iterator last)
151  : m_size(0),
152  m_capacity(Prealloc),
154  m_psi_key(psi_key) {
155  if (this->reserve(last - first)) return;
156  for (; first != last; ++first) push_back(*first);
157  }
158 
159  /**
160  Copies all the elements from 'that' into this container.
161  Any objects in this container are destroyed first.
162  */
164  this->clear();
165  if (this->reserve(that.capacity())) return *this;
166  for (const Element_type *p = that.begin(); p != that.end(); ++p)
167  this->push_back(*p);
168  return *this;
169  }
170 
171  /**
172  Runs DTOR on all elements if needed.
173  Deallocates array if we exceeded the Preallocated amount.
174  */
176  if (!Has_trivial_destructor) {
177  clear();
178  }
180  }
181 
182  size_t capacity() const { return m_capacity; }
183  size_t element_size() const { return sizeof(Element_type); }
184  bool empty() const { return m_size == 0; }
185  size_t size() const { return m_size; }
186 
187  Element_type &at(size_t n) {
188  DBUG_ASSERT(n < size());
189  return m_array_ptr[n];
190  }
191 
192  const Element_type &at(size_t n) const {
193  DBUG_ASSERT(n < size());
194  return m_array_ptr[n];
195  }
196 
197  Element_type &operator[](size_t n) { return at(n); }
198  const Element_type &operator[](size_t n) const { return at(n); }
199 
200  Element_type &back() { return at(size() - 1); }
201  const Element_type &back() const { return at(size() - 1); }
202 
203  Element_type &front() { return at(0); }
204  const Element_type &front() const { return at(0); }
205 
206  /**
207  begin : Returns a pointer to the first element in the array.
208  end : Returns a pointer to the past-the-end element in the array.
209  */
210  iterator begin() { return m_array_ptr; }
211  iterator end() { return m_array_ptr + size(); }
212  const_iterator begin() const { return m_array_ptr; }
213  const_iterator end() const { return m_array_ptr + size(); }
214  /// Returns a constant pointer to the first element in the array.
215  const_iterator cbegin() const { return begin(); }
216  /// Returns a constant pointer to the past-the-end element in the array.
217  const_iterator cend() const { return end(); }
218 
219  /**
220  Assigns a value to an arbitrary element, even where n >= size().
221  The array is extended with default values if necessary.
222  @retval true if out-of-memory, false otherwise.
223  */
224  bool assign_at(size_t n, const value_type &val) {
225  if (n < size()) {
226  at(n) = val;
227  return false;
228  }
229  if (reserve(n + 1)) return true;
230  resize(n);
231  return push_back(val);
232  }
233 
234  /**
235  Reserves space for array elements.
236  Copies (or moves, if possible) over existing elements, in case we
237  are re-expanding the array.
238 
239  @param n number of elements.
240  @retval true if out-of-memory, false otherwise.
241  */
242  bool reserve(size_t n) {
243  if (n <= m_capacity) return false;
244 
245  void *mem = my_malloc(m_psi_key, n * element_size(), MYF(MY_WME));
246  if (!mem) return true;
247  Element_type *new_array = static_cast<Element_type *>(mem);
248 
249  // Move all the existing elements into the new array.
250  for (size_t ix = 0; ix < m_size; ++ix) {
251  Element_type *new_p = &new_array[ix];
252  Element_type &old_p = m_array_ptr[ix];
253  ::new (new_p) Element_type(std::move(old_p)); // Move into new location.
255  old_p.~Element_type(); // Destroy the old element.
256  }
257 
259 
260  // Forget the old array;
261  m_array_ptr = new_array;
262  m_capacity = n;
263  return false;
264  }
265 
266  /**
267  Copies an element into the back of the array.
268  Complexity: Constant (amortized time, reallocation may happen).
269  @return true if out-of-memory, false otherwise
270  */
271  bool push_back(const Element_type &element) { return emplace_back(element); }
272 
273  /**
274  Copies (or moves, if possible) an element into the back of the array.
275  Complexity: Constant (amortized time, reallocation may happen).
276  @return true if out-of-memory, false otherwise
277  */
278  bool push_back(Element_type &&element) {
279  return emplace_back(std::move(element));
280  }
281 
282  /**
283  Constructs an element at the back of the array.
284  Complexity: Constant (amortized time, reallocation may happen).
285  @return true if out-of-memory, false otherwise
286  */
287  template <typename... Args>
288  bool emplace_back(Args &&... args) {
289  const size_t expansion_factor = 2;
290  if (m_size == m_capacity && reserve(m_capacity * expansion_factor))
291  return true;
292  Element_type *p = &m_array_ptr[m_size++];
293  ::new (p) Element_type(std::forward<Args>(args)...);
294  return false;
295  }
296 
297  /**
298  Removes the last element in the array, effectively reducing the
299  container size by one. This destroys the removed element.
300  */
301  void pop_back() {
302  DBUG_ASSERT(!empty());
303  if (!Has_trivial_destructor) back().~Element_type();
304  m_size -= 1;
305  }
306 
307  /**
308  The array is extended by inserting a new element before the element at the
309  specified position.
310 
311  This is generally an inefficient operation, since we need to copy
312  elements to make a new "hole" in the array.
313 
314  We use std::rotate to move objects, hence Element_type must be
315  move-assignable and move-constructible.
316 
317  @return an iterator pointing to the inserted value
318  */
319  iterator insert(const_iterator position, const value_type &val) {
320  return emplace(position, val);
321  }
322 
323  /**
324  The array is extended by inserting a new element before the element at the
325  specified position. The element is moved into the array, if possible.
326 
327  This is generally an inefficient operation, since we need to copy
328  elements to make a new "hole" in the array.
329 
330  We use std::rotate to move objects, hence Element_type must be
331  move-assignable and move-constructible.
332 
333  @return an iterator pointing to the inserted value
334  */
336  return emplace(position, std::move(val));
337  }
338 
339  /**
340  The array is extended by inserting a new element before the element at the
341  specified position. The element is constructed in-place.
342 
343  This is generally an inefficient operation, since we need to copy
344  elements to make a new "hole" in the array.
345 
346  We use std::rotate to move objects, hence Element_type must be
347  move-assignable and move-constructible.
348 
349  @return an iterator pointing to the inserted value
350  */
351  template <typename... Args>
352  iterator emplace(const_iterator position, Args &&... args) {
353  const difference_type n = position - begin();
354  emplace_back(std::forward<Args>(args)...);
355  std::rotate(begin() + n, end() - 1, end());
356  return begin() + n;
357  }
358 
359  /**
360  Similar to std::set<>::insert()
361  Extends the array by inserting a new element, but only if it cannot be found
362  in the array already.
363 
364  Assumes that the array is sorted with std::less<Element_type>
365  Insertion using this function will maintain order.
366 
367  @retval A pair, with its member pair::first set an iterator pointing to
368  either the newly inserted element, or to the equivalent element
369  already in the array. The pair::second element is set to true if
370  the new element was inserted, or false if an equivalent element
371  already existed.
372  */
373  std::pair<iterator, bool> insert_unique(const value_type &val) {
374  std::pair<iterator, iterator> p = std::equal_range(begin(), end(), val);
375  // p.first == p.second means we did not find it.
376  if (p.first == p.second) return std::make_pair(insert(p.first, val), true);
377  return std::make_pair(p.first, false);
378  }
379 
380  /**
381  Similar to std::set<>::erase()
382  Removes a single element from the array by value.
383  The removed element is destroyed.
384  This effectively reduces the container size by one.
385 
386  This is generally an inefficient operation, since we need to copy
387  elements to fill the "hole" in the array.
388 
389  Assumes that the array is sorted with std::less<Element_type>.
390 
391  @retval number of elements removed, 0 or 1.
392  */
394  std::pair<iterator, iterator> p = std::equal_range(begin(), end(), val);
395  if (p.first == p.second) return 0; // Not found
396  erase(p.first);
397  return 1;
398  }
399 
400  /**
401  Similar to std::set<>::count()
402 
403  @note Assumes that array is maintained with insert_unique/erase_unique.
404 
405  @retval 1 if element is found, 0 otherwise.
406  */
407  size_type count_unique(const value_type &val) const {
408  return std::binary_search(begin(), end(), val);
409  }
410 
411  /**
412  Removes a single element from the array.
413  The removed element is destroyed.
414  This effectively reduces the container size by one.
415 
416  This is generally an inefficient operation, since we need to move
417  or copy elements to fill the "hole" in the array.
418 
419  We use std::move to move objects, hence Element_type must be
420  move-assignable.
421  */
423  DBUG_ASSERT(position != end());
424  return erase(position - begin());
425  }
426 
427  /**
428  Removes a single element from the array.
429  */
430  iterator erase(size_t ix) {
431  DBUG_ASSERT(ix < size());
432  iterator pos = begin() + ix;
433  if (pos + 1 != end()) std::move(pos + 1, end(), pos);
434  pop_back();
435  return pos;
436  }
437 
438  /**
439  Removes tail elements from the array.
440  The removed elements are destroyed.
441  This effectively reduces the containers size by 'end() - first'.
442  */
444  const_iterator last = cend();
445  const difference_type diff = last - first;
446  if (!Has_trivial_destructor) {
447  for (; first != last; ++first) first->~Element_type();
448  }
449  m_size -= diff;
450  }
451 
452  /**
453  Removes a range of elements from the array.
454  The removed elements are destroyed.
455  This effectively reduces the containers size by 'last - first'.
456 
457  This is generally an inefficient operation, since we need to move
458  or copy elements to fill the "hole" in the array.
459 
460  We use std::move to move objects, hence Element_type must be
461  move-assignable.
462  */
464  /*
465  std::move() wants non-const input iterators, otherwise it cannot move and
466  must always copy the elements. Convert first and last from const_iterator
467  to iterator.
468  */
469  iterator start = begin() + (first - cbegin());
470  iterator stop = begin() + (last - cbegin());
471  if (first != last) erase_at_end(std::move(stop, end(), start));
472  return start;
473  }
474 
475  /**
476  Exchanges the content of the container by the content of rhs, which
477  is another vector object of the same type. Sizes may differ.
478 
479  We use std::swap to do the operation.
480  */
481  void swap(Prealloced_array &rhs) {
482  // Just swap pointers if both arrays have done malloc.
483  if (m_array_ptr != cast_rawbuff() &&
484  rhs.m_array_ptr != rhs.cast_rawbuff()) {
485  std::swap(m_size, rhs.m_size);
489  return;
490  }
491  std::swap(*this, rhs);
492  }
493 
494  /**
495  Requests the container to reduce its capacity to fit its size.
496  */
497  void shrink_to_fit() {
498  // Cannot shrink the pre-allocated array.
499  if (m_array_ptr == cast_rawbuff()) return;
500  // No point in swapping.
501  if (size() == capacity()) return;
502  Prealloced_array tmp(m_psi_key, begin(), end());
503  if (size() <= Prealloc) {
504  /*
505  The elements fit in the pre-allocated array. Destruct the
506  heap-allocated array in this, and copy the elements into the
507  pre-allocated array.
508  */
509  this->~Prealloced_array();
510  new (this) Prealloced_array(tmp.m_psi_key, tmp.begin(), tmp.end());
511  } else {
512  // Both this and tmp have a heap-allocated array. Swap pointers.
513  swap(tmp);
514  }
515  }
516 
517  /**
518  Resizes the container so that it contains n elements.
519 
520  If n is smaller than the current container size, the content is
521  reduced to its first n elements, removing those beyond (and
522  destroying them).
523 
524  If n is greater than the current container size, the content is
525  expanded by inserting at the end as many elements as needed to
526  reach a size of n. If val is specified, the new elements are
527  initialized as copies of val, otherwise, they are
528  value-initialized.
529 
530  If n is also greater than the current container capacity, an automatic
531  reallocation of the allocated storage space takes place.
532 
533  Notice that this function changes the actual content of the
534  container by inserting or erasing elements from it.
535  */
536  void resize(size_t n, const Element_type &val = Element_type()) {
537  if (n == m_size) return;
538  if (n > m_size) {
539  if (!reserve(n)) {
540  while (n != m_size) push_back(val);
541  }
542  return;
543  }
544  if (!Has_trivial_destructor) {
545  while (n != m_size) pop_back();
546  }
547  m_size = n;
548  }
549 
550  /**
551  Removes (and destroys) all elements.
552  Does not change capacity.
553  */
554  void clear() {
555  if (!Has_trivial_destructor) {
556  for (Element_type *p = begin(); p != end(); ++p)
557  p->~Element_type(); // Destroy discarded element.
558  }
559  m_size = 0;
560  }
561 
562  private:
563  size_t m_size;
564  size_t m_capacity;
565  // This buffer must be properly aligned.
566  alignas(Element_type) char m_buff[Prealloc * sizeof(Element_type)];
567  Element_type *m_array_ptr;
569 };
570 
571 #endif // PREALLOCED_ARRAY_INCLUDED
size_t capacity() const
Definition: prealloced_array.h:182
const Element_type & operator[](size_t n) const
Definition: prealloced_array.h:198
void resize(size_t n, const Element_type &val=Element_type())
Resizes the container so that it contains n elements.
Definition: prealloced_array.h:536
t pos
Definition: dbug_analyze.cc:148
Element_type * m_array_ptr
Definition: prealloced_array.h:567
iterator erase(size_t ix)
Removes a single element from the array.
Definition: prealloced_array.h:430
#define MY_WME
Definition: my_sys.h:115
Some integer typedefs for easier portability.
Element_type & at(size_t n)
Definition: prealloced_array.h:187
std::pair< iterator, bool > insert_unique(const value_type &val)
Similar to std::set<>::insert() Extends the array by inserting a new element, but only if it cannot b...
Definition: prealloced_array.h:373
Prealloced_array & operator=(const Prealloced_array &that)
Copies all the elements from &#39;that&#39; into this container.
Definition: prealloced_array.h:163
void erase_at_end(const_iterator first)
Removes tail elements from the array.
Definition: prealloced_array.h:443
Prealloced_array(PSI_memory_key psi_key, const_iterator first, const_iterator last)
Range constructor.
Definition: prealloced_array.h:149
Element_type & front()
Definition: prealloced_array.h:203
bool empty() const
Definition: prealloced_array.h:184
const Element_type & back() const
Definition: prealloced_array.h:201
void shrink_to_fit()
Requests the container to reduce its capacity to fit its size.
Definition: prealloced_array.h:497
iterator emplace(const_iterator position, Args &&... args)
The array is extended by inserting a new element before the element at the specified position...
Definition: prealloced_array.h:352
const_iterator begin() const
Definition: prealloced_array.h:212
void my_free(void *ptr)
Frees the memory pointed by the ptr.
Definition: my_memory.cc:81
const_iterator end() const
Definition: prealloced_array.h:213
unsigned int PSI_memory_key
Instrumented memory key.
Definition: psi_memory_bits.h:46
size_type erase_unique(const value_type &val)
Similar to std::set<>::erase() Removes a single element from the array by value.
Definition: prealloced_array.h:393
static const size_t initial_capacity
Initial capacity of the array.
Definition: prealloced_array.h:86
static MEM_ROOT mem
Definition: sql_servers.cc:97
Prealloced_array(const Prealloced_array &that)
An object instance "owns" its array, so we do deep copy here.
Definition: prealloced_array.h:132
ptrdiff_t difference_type
Definition: prealloced_array.h:91
iterator begin()
begin : Returns a pointer to the first element in the array.
Definition: prealloced_array.h:210
static Bigint * diff(Bigint *a, Bigint *b, Stack_alloc *alloc)
Definition: dtoa.cc:1090
A typesafe replacement for DYNAMIC_ARRAY.
Definition: prealloced_array.h:66
const Element_type & front() const
Definition: prealloced_array.h:204
#define DBUG_ASSERT(A)
Definition: my_dbug.h:183
static void stop(PluginFuncEnv *)
Definition: rest_mock_server.cc:277
size_t size() const
Definition: prealloced_array.h:185
bool emplace_back(Args &&... args)
Constructs an element at the back of the array.
Definition: prealloced_array.h:288
bool assign_at(size_t n, const value_type &val)
Assigns a value to an arbitrary element, even where n >= size().
Definition: prealloced_array.h:224
Element_type & back()
Definition: prealloced_array.h:200
const Element_type * const_iterator
Definition: prealloced_array.h:94
SHOW STATUS Server status variable.
Definition: status_var.h:78
iterator insert(const_iterator position, value_type &&val)
The array is extended by inserting a new element before the element at the specified position...
Definition: prealloced_array.h:335
Element_type * cast_rawbuff()
Casts the raw buffer to the proper Element_type.
Definition: prealloced_array.h:80
const_iterator cend() const
Returns a constant pointer to the past-the-end element in the array.
Definition: prealloced_array.h:217
Prealloced_array(PSI_memory_key psi_key)
Definition: prealloced_array.h:96
Header for compiler-dependent features.
#define MYF(v)
Definition: my_inttypes.h:124
char m_buff[Prealloc *sizeof(Element_type)]
Definition: prealloced_array.h:566
void pop_back()
Removes the last element in the array, effectively reducing the container size by one...
Definition: prealloced_array.h:301
iterator end()
Definition: prealloced_array.h:211
size_t size_type
Definition: prealloced_array.h:90
Common header for many mysys elements.
const Element_type & at(size_t n) const
Definition: prealloced_array.h:192
iterator erase(const_iterator first, const_iterator last)
Removes a range of elements from the array.
Definition: prealloced_array.h:463
bool push_back(Element_type &&element)
Copies (or moves, if possible) an element into the back of the array.
Definition: prealloced_array.h:278
PSI_memory_key m_psi_key
Definition: prealloced_array.h:568
~Prealloced_array()
Runs DTOR on all elements if needed.
Definition: prealloced_array.h:175
Performance schema instrumentation interface.
size_type count_unique(const value_type &val) const
Similar to std::set<>::count()
Definition: prealloced_array.h:407
void clear()
Removes (and destroys) all elements.
Definition: prealloced_array.h:554
Prealloced_array(PSI_memory_key psi_key, size_t initial_size)
Initializes (parts of) the array with default values.
Definition: prealloced_array.h:108
size_t m_capacity
Definition: prealloced_array.h:564
Element_type & operator[](size_t n)
Definition: prealloced_array.h:197
size_t element_size() const
Definition: prealloced_array.h:183
const_iterator cbegin() const
Returns a constant pointer to the first element in the array.
Definition: prealloced_array.h:215
static void swap(String &a, String &b) noexcept
Definition: sql_string.h:583
static void start(PluginFuncEnv *env)
Definition: http_server_plugin.cc:572
iterator insert(const_iterator position, const value_type &val)
The array is extended by inserting a new element before the element at the specified position...
Definition: prealloced_array.h:319
iterator erase(const_iterator position)
Removes a single element from the array.
Definition: prealloced_array.h:422
const char * p
Definition: ctype-mb.cc:1232
const string value("\alue\)
bool push_back(const Element_type &element)
Copies an element into the back of the array.
Definition: prealloced_array.h:271
Element_type value_type
Standard typedefs.
Definition: prealloced_array.h:89
void * my_malloc(PSI_memory_key key, size_t size, int flags)
Below functions are used by the components.
Definition: my_memory.cc:57
Element_type * iterator
Definition: prealloced_array.h:93
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: prealloced_array.h:72
bool reserve(size_t n)
Reserves space for array elements.
Definition: prealloced_array.h:242
size_t m_size
Definition: prealloced_array.h:563
void swap(Prealloced_array &rhs)
Exchanges the content of the container by the content of rhs, which is another vector object of the s...
Definition: prealloced_array.h:481