MySQL 9.0.0
Source Code Documentation
inplace_vector.h
Go to the documentation of this file.
1#ifndef INPLACE_VECTOR_INCLUDED
2#define INPLACE_VECTOR_INCLUDED
3
4/* Copyright (c) 2014, 2024, Oracle and/or its affiliates.
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License, version 2.0,
8 as published by the Free Software Foundation.
9
10 This program is designed to work with certain software (including
11 but not limited to OpenSSL) that is licensed under separate terms,
12 as designated in a particular file or component or in included license
13 documentation. The authors of MySQL hereby grant you an additional
14 permission to link the program and your derivative works with the
15 separately licensed software that they have either included with
16 the program or referenced in the documentation.
17
18 This program is distributed in the hope that it will be useful,
19 but WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 GNU General Public License, version 2.0, for more details.
22
23 You should have received a copy of the GNU General Public License
24 along with this program; if not, write to the Free Software
25 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
26
27/* This file defines the Inplace_vector class template. */
28
29#include <assert.h>
30#include <vector>
31
32#include "my_sys.h"
35
36/**
37 Utility container class to store elements stably and scalably.
38 The address of an element stored in the container is stable as long as
39 the object is alive, no object is copy-constructed/reassigned by push_back
40 operations once it's stored into this container. And users of such containers
41 *can* assign to elements stored in the container just like using std::vector.
42
43 It is similar to STL vector but it is uniquely suitable in below situation:
44 whenever stable element address, or element copy construction/assignment
45 behaviors are forbidden. It only has a limited subset of the std::vector
46 interface, and especially it doesn't have an iterator interface or element
47 elimination interface, we don't need them for now. And this container
48 is not multi-threading safe. It uses my_malloc/my_free
49 to allocate/free memory arrays and caller can pass PSI key.
50
51 The container keeps a collection of arrays, each of which has a fixed
52 NO. of slots to store elements. When one array is full, another is appended.
53 When the vector shrinks at tail, useless arrays are removed and its memory
54 space released.
55
56 @tparam objtype The type of the elements to store.
57 @tparam array_size The NO. of element slots in each array.
58 */
59template <typename objtype, size_t array_size = 16>
61 private:
62 std::vector<objtype *> m_obj_arrays;
66
67 /**
68 Return an existing used slot, or append exactly one slot at end of the last
69 array and return it. If the last array is already full before the
70 append, allocate a new array then allocate one slot and return it.
71 @param index The index of the element slot to return. It must be
72 one within valid in-use range of the vector, or be equal to
73 the size of the vector.
74 @return the object pointer stored in the specified slot; NULL if need
75 to allocate more space but out of memory.
76 */
77 objtype *get_space(size_t index) {
78 assert(index <= m_obj_count);
79 size_t arr_id = index / array_size;
80 size_t slot_id = index % array_size;
81 objtype *ptr = nullptr;
82
83 assert(arr_id <= m_obj_arrays.size());
84
85 // Appending a new slot causes appending a new array.
86 if (arr_id == m_obj_arrays.size()) {
87 assert(slot_id == 0);
88 if (m_outof_mem) return nullptr;
90 if (m_outof_mem) return nullptr;
91 }
92
93 ptr = m_obj_arrays[arr_id];
94 ptr += slot_id;
95 return ptr;
96 }
97
99 if (m_outof_mem) return;
100
101 void *p = my_malloc(m_psi_key, sizeof(objtype) * array_size, MYF(MY_FAE));
102
103 try {
104 m_obj_arrays.push_back(static_cast<objtype *>(p));
105 } catch (...) {
106 m_outof_mem = true;
107 my_free(p);
108 }
109 }
110
113
114 public:
116 : m_psi_key(psi_key), m_outof_mem(false) {
117 m_obj_count = 0;
119 }
120
121 /**
122 Release memory space and destroy all contained objects.
123 */
125
126 /**
127 Get an existing element's pointer, index must be in [0, m_obj_count).
128 @param index The index of the element to return. It must be
129 within valid in-use range of the vector.
130 @return The element address specified by index; NULL if out of memory.
131 */
132 objtype *get_object(size_t index) {
133 assert(index < m_obj_count);
134 return get_space(index);
135 }
136
137 /**
138 Allocate space for an object, and construct it using its default
139 constructor, and return its address.
140 @return the appended object's address; NULL if out of memory.
141 */
142 objtype *append_object() {
143 // Use placement new operator to construct this object at proper
144 // location.
145 return ::new (get_space(m_obj_count++)) objtype;
146 }
147
148 /**
149 STL std::vector::push_back interface. It's guaranteed that existing
150 elements stored in the vector is never copy constructed/reassigned
151 by this operation. When the last element array is full, a new one is
152 allocated and tracked.
153
154 @param obj The element to store into the vector.
155 @return The appended object stored in the container; NULL if out of memory.
156 */
157 objtype *push_back(const objtype &obj) {
158 // Use placement new operator to construct this object at proper
159 // location.
160 return ::new (get_space(m_obj_count++)) objtype(obj);
161 }
162
163 /**
164 STL std::vector::resize interface. Has identical behavior as STL
165 std::vector::resize except that no element copy construction or
166 reassignment is ever caused by this operation.
167
168 @param new_size New size of vector. If smaller than current size,
169 objects at the tail are removed and destroyed. If greater,
170 new objects are added with default value.
171 @param val default value assigned to extended slots in the vector. Unused
172 if the vector is shrunk.
173 @return true if out of memory; false if successful.
174 */
175 bool resize(size_t new_size, const objtype &val = objtype()) {
176 if (new_size > size()) {
177 for (size_t i = size(); i < new_size; i++) {
178 if (push_back(val) == nullptr) return true;
179 }
180 } else if (new_size < size()) {
181 // Destroy objects at tail.
182 for (size_t i = new_size; i < size(); i++) get_object(i)->~objtype();
183
184 // Free useless array space.
185 for (size_t j = new_size / array_size + 1; j < m_obj_arrays.size(); j++)
187
188 m_obj_count = new_size;
189 m_obj_arrays.resize(new_size / array_size + 1);
190 }
191
192 return false;
193 }
194
195 /**
196 STL std::vector::size interface.
197 @return the number of elements effectively stored in the vector.
198 */
199 size_t size() const { return m_obj_count; }
200
201 /**
202 STL std::vector::capacity interface.
203 @return the max number of element that can be stored into this vector
204 without growing its size.
205 */
206 size_t capacity() const { return m_obj_arrays.size() * array_size; }
207
208 /**
209 STL std::vector::empty interface.
210 @return whether size() == 0.
211 */
212 bool empty() const { return m_obj_count == 0; }
213
214 /**
215 STL std::vector::clear interface.
216 Destroy all elements (by calling each element's destructor) stored in
217 the vector, and then release all memory held by it.
218 */
220
221 /**
222 STL std::vector::back interface.
223 @return the reference of the last object stored in the vector.
224 */
225 const objtype &back() const {
226 assert(size() > 0);
227 objtype *p = get_object(size() - 1);
228 return *p;
229 }
230
231 /**
232 STL std::vector::back interface.
233 @return the reference of the last object stored in the vector.
234 */
235 objtype &back() {
236 assert(size() > 0);
237 objtype *p = get_object(size() - 1);
238 return *p;
239 }
240
241 /**
242 STL std::vector::operator[] interface.
243 @param i The index of the element to return. It must be
244 within valid in-use range of the vector.
245 @return The element reference specified by index.
246 */
247 const objtype &operator[](size_t i) const {
248 assert(i < size());
249 objtype *p = get_object(i);
250 return *p;
251 }
252
253 /**
254 STL std::vector::operator[] interface.
255 @param i The index of the element to return. It must be
256 within valid in-use range of the vector.
257 @return The element reference specified by index.
258 */
259 objtype &operator[](size_t i) {
260 assert(i < size());
261 objtype *p = get_object(i);
262 return *p;
263 }
264
265 /**
266 Destroy all elements (by calling each element's destructor) stored in
267 the vector, and then release all memory held by it.
268 */
270 // Call each element's destructor.
271 for (size_t i = 0; i < size(); i++) {
272 objtype *p = get_object(i);
273 p->~objtype();
274 }
275 for (size_t i = 0; i < m_obj_arrays.size(); ++i) my_free(m_obj_arrays[i]);
276
277 m_obj_arrays.clear();
278 m_obj_count = 0;
279 }
280};
281
282#endif // !INPLACE_VECTOR_INCLUDED
Utility container class to store elements stably and scalably.
Definition: inplace_vector.h:60
const objtype & operator[](size_t i) const
STL std::vector::operator[] interface.
Definition: inplace_vector.h:247
std::vector< objtype * > m_obj_arrays
Definition: inplace_vector.h:62
bool resize(size_t new_size, const objtype &val=objtype())
STL std::vector::resize interface.
Definition: inplace_vector.h:175
void delete_all_objects()
Destroy all elements (by calling each element's destructor) stored in the vector, and then release al...
Definition: inplace_vector.h:269
const objtype & back() const
STL std::vector::back interface.
Definition: inplace_vector.h:225
objtype * get_space(size_t index)
Return an existing used slot, or append exactly one slot at end of the last array and return it.
Definition: inplace_vector.h:77
size_t m_obj_count
Definition: inplace_vector.h:64
bool empty() const
STL std::vector::empty interface.
Definition: inplace_vector.h:212
void clear()
STL std::vector::clear interface.
Definition: inplace_vector.h:219
objtype & operator[](size_t i)
STL std::vector::operator[] interface.
Definition: inplace_vector.h:259
Inplace_vector(PSI_memory_key psi_key)
Definition: inplace_vector.h:115
size_t capacity() const
STL std::vector::capacity interface.
Definition: inplace_vector.h:206
~Inplace_vector()
Release memory space and destroy all contained objects.
Definition: inplace_vector.h:124
void append_new_array()
Definition: inplace_vector.h:98
Inplace_vector(const Inplace_vector &)
Inplace_vector & operator=(const Inplace_vector &rhs)
size_t size() const
STL std::vector::size interface.
Definition: inplace_vector.h:199
objtype * push_back(const objtype &obj)
STL std::vector::push_back interface.
Definition: inplace_vector.h:157
bool m_outof_mem
Definition: inplace_vector.h:65
objtype * append_object()
Allocate space for an object, and construct it using its default constructor, and return its address.
Definition: inplace_vector.h:142
objtype * get_object(size_t index)
Get an existing element's pointer, index must be in [0, m_obj_count).
Definition: inplace_vector.h:132
objtype & back()
STL std::vector::back interface.
Definition: inplace_vector.h:235
PSI_memory_key m_psi_key
Definition: inplace_vector.h:63
const char * p
Definition: ctype-mb.cc:1225
#define MY_FAE
Definition: my_sys.h:127
unsigned int PSI_memory_key
Instrumented memory key.
Definition: psi_memory_bits.h:49
#define MYF(v)
Definition: my_inttypes.h:97
void * my_malloc(PSI_memory_key key, size_t size, int flags)
Allocates size bytes of memory.
Definition: my_memory.cc:57
void my_free(void *ptr)
Frees the memory pointed by the ptr.
Definition: my_memory.cc:81
Common header for many mysys elements.
Performance schema instrumentation interface.