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