MySQL 8.0.30
Source Code Documentation
mem_root_array.h
Go to the documentation of this file.
1/* Copyright (c) 2011, 2022, 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) {
186 const size_t min_capacity = 20;
187 const size_t expansion_factor = 2;
188 if (0 == m_capacity && reserve(min_capacity)) return true;
189 if (m_size == m_capacity && reserve(m_capacity * expansion_factor))
190 return true;
191 Element_type *p = &m_array[m_size++];
192 ::new (p) Element_type(element);
193 return false;
194 }
195
196 /**
197 Adds a new element at the end of the array, after its current last
198 element. The content of this new element is initialized by moving
199 the input element.
200
201 @param element Object to move.
202 @retval true if out-of-memory, false otherwise.
203 */
204 bool push_back(Element_type &&element) {
205 const size_t min_capacity = 20;
206 const size_t expansion_factor = 2;
207 if (0 == m_capacity && reserve(min_capacity)) return true;
208 if (m_size == m_capacity && reserve(m_capacity * expansion_factor))
209 return true;
210 Element_type *p = &m_array[m_size++];
211 ::new (p) Element_type(std::move(element));
212 return false;
213 }
214
215 /**
216 Adds a new element at the beginning of the array.
217 The content of this new element is initialized to a copy of
218 the input argument.
219
220 @param element Object to copy.
221 @retval true if out-of-memory, false otherwise.
222 */
223 bool push_front(const Element_type &element) {
224 if (push_back(element)) return true;
225 std::rotate(begin(), end() - 1, end());
226 return false;
227 }
228
229 /**
230 Adds a new element at the front of the array.
231 The content of this new element is initialized by moving the input element.
232
233 @param element Object to move.
234 @retval true if out-of-memory, false otherwise.
235 */
236 bool push_front(Element_type &&element) {
237 if (push_back(std::move(element))) return true;
238 std::rotate(begin(), end() - 1, end());
239 return false;
240 }
241
242 /**
243 Removes the last element in the array, effectively reducing the
244 container size by one. This destroys the removed element.
245 */
246 void pop_back() {
247 assert(!empty());
248 if (!has_trivial_destructor) back().~Element_type();
249 m_size -= 1;
250 }
251
252 /**
253 Resizes the container so that it contains n elements.
254
255 If n is smaller than the current container size, the content is
256 reduced to its first n elements, removing those beyond (and
257 destroying them).
258
259 If n is greater than the current container size, the content is
260 expanded by inserting at the end as many elements as needed to
261 reach a size of n. If val is specified, the new elements are
262 initialized as copies of val, otherwise, they are
263 value-initialized.
264
265 If n is also greater than the current container capacity, an automatic
266 reallocation of the allocated storage space takes place.
267
268 Notice that this function changes the actual content of the
269 container by inserting or erasing elements from it.
270 */
271 void resize(size_t n, const value_type &val) {
272 if (n == m_size) return;
273 if (n > m_size) {
274 if (!reserve(n)) {
275 while (n != m_size) push_back(val);
276 }
277 return;
278 }
280 while (n != m_size) pop_back();
281 }
282 m_size = n;
283 }
284
285 /**
286 Same as resize(size_t, const value_type &val), but default-constructs
287 the new elements. This allows one to resize containers even if
288 value_type is not copy-constructible.
289 */
290 void resize(size_t n) {
291 if (n == m_size) return;
292 if (n > m_size) {
293 if (!reserve(n)) {
294 while (n != m_size) push_back(value_type());
295 }
296 return;
297 }
299 while (n != m_size) pop_back();
300 }
301 m_size = n;
302 }
303
304 /**
305 Erase all the elements in the specified range.
306
307 @param first iterator that points to the first element to remove
308 @param last iterator that points to the element after the
309 last one to remove
310 @return an iterator to the first element after the removed range
311 */
313 iterator pos = begin() + (first - cbegin());
314 if (first != last) {
315 iterator new_end = std::move(last, cend(), pos);
316 chop(new_end - begin());
317 }
318 return pos;
319 }
320
321 /**
322 Removes a single element from the array.
323
324 @param position iterator that points to the element to remove
325
326 @return an iterator to the first element after the removed range
327 */
329 return erase(position, std::next(position));
330 }
331
332 /**
333 Removes a single element from the array.
334
335 @param ix zero-based number of the element to remove
336
337 @return an iterator to the first element after the removed range
338 */
339 iterator erase(size_t ix) {
340 assert(ix < size());
341 return erase(std::next(this->cbegin(), ix));
342 }
343
344 /**
345 Insert an element at a given position.
346
347 @param pos the new element is inserted before the element
348 at this position
349 @param value the value of the new element
350 @return an iterator that points to the inserted element
351 */
352 iterator insert(const_iterator pos, const Element_type &value) {
353 ptrdiff_t idx = pos - cbegin();
354 if (!push_back(value)) std::rotate(begin() + idx, end() - 1, end());
355 return begin() + idx;
356 }
357
358 /**
359 Removes a single element from the array by value.
360 The removed element is destroyed. This effectively reduces the
361 container size by one.
362 Note that if there are multiple elements having the same
363 value, only the first element is removed.
364
365 This is generally an inefficient operation, since we need to copy
366 elements to fill the "hole" in the array.
367
368 We use std::copy to move objects, hence Element_type must be
369 assignable.
370
371 @retval number of elements removed, 0 or 1.
372 */
373 size_t erase_value(const value_type &val) {
374 iterator position = std::find(begin(), end(), val);
375 if (position != end()) {
376 erase(position);
377 return 1;
378 }
379 return 0; // Not found
380 }
381
382 /**
383 Removes a single element from the array.
384 The removed element is destroyed.
385 This effectively reduces the container size by one.
386
387 This is generally an inefficient operation, since we need to copy
388 elements to fill the "hole" in the array.
389
390 We use std::copy to move objects, hence Element_type must be assignable.
391 */
393 assert(position != end());
394 if (position + 1 != end()) std::copy(position + 1, end(), position);
395 this->pop_back();
396 return position;
397 }
398
399 size_t capacity() const { return m_capacity; }
400 size_t element_size() const { return sizeof(Element_type); }
401 bool empty() const { return size() == 0; }
402 size_t size() const { return m_size; }
403
404 protected:
406 Element_type *m_array;
407 size_t m_size;
409
410 // No CTOR/DTOR for this class!
411 // Mem_root_array_YY(const Mem_root_array_YY&);
412 // Mem_root_array_YY &operator=(const Mem_root_array_YY&);
413};
414
415/**
416 A typesafe replacement for DYNAMIC_ARRAY.
417
418 @see Mem_root_array_YY.
419*/
420template <typename Element_type>
421class Mem_root_array : public Mem_root_array_YY<Element_type> {
423
424 public:
425 /// Convenience typedef, same typedef name as std::vector
426 typedef Element_type value_type;
427
429
431
432 explicit Mem_root_array(MEM_ROOT *root) { super::init(root); }
433
434 /// Move constructor and assignment.
436 this->m_root = other.m_root;
437 this->m_array = other.m_array;
438 this->m_size = other.m_size;
439 this->m_capacity = other.m_capacity;
440 other.init_empty_const();
441 other.m_root = this->m_root;
442 }
444 if (this != &other) {
445 this->~Mem_root_array();
446 new (this) Mem_root_array(std::move(other));
447 }
448 return *this;
449 }
450
451 Mem_root_array(MEM_ROOT *root, size_t n) {
452 super::init(root);
454 }
455
456 Mem_root_array(MEM_ROOT *root, size_t n, const value_type &val) {
457 super::init(root);
458 super::resize(n, val);
459 }
460
461 /**
462 Range constructor.
463
464 Constructs a container with as many elements as the range [first,last),
465 with each element constructed from its corresponding element in that range,
466 in the same order.
467
468 @param root MEM_ROOT to use for memory allocation.
469 @param first iterator that points to the first element to copy
470 @param last iterator that points to the element after the
471 last one to copy
472 */
474 super::init(root);
475 if (this->reserve(last - first)) return;
476 for (auto it = first; it != last; ++it) this->push_back(*it);
477 }
478
480 : Mem_root_array(root, x.cbegin(), x.cend()) {}
481
482 Mem_root_array(std::initializer_list<Element_type> elements)
483 : Mem_root_array(*THR_MALLOC, begin(elements), end(elements)) {}
484
486
487 // Not (yet) implemented.
490};
491
492#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:204
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:392
bool push_front(Element_type &&element)
Adds a new element at the front of the array.
Definition: mem_root_array.h:236
const Element_type & at(size_t n) const
Definition: mem_root_array.h:98
bool empty() const
Definition: mem_root_array.h:401
void init(MEM_ROOT *root)
Definition: mem_root_array.h:73
MEM_ROOT * m_root
Definition: mem_root_array.h:405
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:399
iterator erase(size_t ix)
Removes a single element from the array.
Definition: mem_root_array.h:339
Element_type & back()
Definition: mem_root_array.h:106
Element_type & at(size_t n)
Definition: mem_root_array.h:93
size_t size() const
Definition: mem_root_array.h:402
size_t m_capacity
Definition: mem_root_array.h:408
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:373
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:290
const Element_type * end() const
Definition: mem_root_array.h:119
size_t m_size
Definition: mem_root_array.h:407
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:223
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:352
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:400
Element_type * m_array
Definition: mem_root_array.h:406
iterator erase(const_iterator first, const_iterator last)
Erase all the elements in the specified range.
Definition: mem_root_array.h:312
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:246
void resize(size_t n, const value_type &val)
Resizes the container so that it contains n elements.
Definition: mem_root_array.h:271
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:328
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:421
Mem_root_array(MEM_ROOT *root, const_iterator first, const_iterator last)
Range constructor.
Definition: mem_root_array.h:473
Mem_root_array(Mem_root_array &&other)
Move constructor and assignment.
Definition: mem_root_array.h:435
Mem_root_array(MEM_ROOT *root, size_t n)
Definition: mem_root_array.h:451
Mem_root_array & operator=(Mem_root_array &&other)
Definition: mem_root_array.h:443
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:456
Element_type value_type
Convenience typedef, same typedef name as std::vector.
Definition: mem_root_array.h:426
Mem_root_array(const Mem_root_array &)=delete
Mem_root_array()
Definition: mem_root_array.h:430
~Mem_root_array()
Definition: mem_root_array.h:485
Mem_root_array(std::initializer_list< Element_type > elements)
Definition: mem_root_array.h:482
Mem_root_array_YY< Element_type > super
Definition: mem_root_array.h:422
Mem_root_array(MEM_ROOT *root, const Mem_root_array &x)
Definition: mem_root_array.h:479
super::const_iterator const_iterator
Definition: mem_root_array.h:428
Mem_root_array(MEM_ROOT *root)
Definition: mem_root_array.h:432
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:1540
const byte * find(const Pages *pages, const page_id_t &page_id) noexcept
Find a doublewrite copy of a page.
Definition: buf0dblwr.cc:3592
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:82
void * Alloc(size_t length)
Allocate memory.
Definition: my_alloc.h:144
int n
Definition: xcom_base.cc:505