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