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