MySQL  8.0.27
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, 2021, 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"
32 #include "mysql/psi/psi_memory.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/assignement
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  */
58 template <typename objtype, size_t array_size = 16>
60  private:
61  std::vector<objtype *> m_obj_arrays;
63  size_t m_obj_count;
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:
114  explicit Inplace_vector(PSI_memory_key psi_key)
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 shrinked.
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++)
185  my_free(m_obj_arrays[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  */
218  void clear() { delete_all_objects(); }
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
objtype & back()
STL std::vector::back interface.
Definition: inplace_vector.h:234
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
size_t m_obj_count
Definition: inplace_vector.h:63
Inplace_vector & operator=(const Inplace_vector &rhs)
objtype * push_back(const objtype &obj)
STL std::vector::push_back interface.
Definition: inplace_vector.h:156
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
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
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
~Inplace_vector()
Release memory space and destroy all contained objects.
Definition: inplace_vector.h:123
void append_new_array()
Definition: inplace_vector.h:97
objtype & operator[](size_t i)
STL std::vector::operator[] interface.
Definition: inplace_vector.h:258
Inplace_vector(const Inplace_vector &)
size_t size() const
STL std::vector::size interface.
Definition: inplace_vector.h:198
bool m_outof_mem
Definition: inplace_vector.h:64
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
const objtype & back() const
STL std::vector::back interface.
Definition: inplace_vector.h:224
PSI_memory_key m_psi_key
Definition: inplace_vector.h:62
objtype * append_object()
Allocate space for an object, and construct it using its default constructor, and return its address.
Definition: inplace_vector.h:141
const char * p
Definition: ctype-mb.cc:1236
#define MY_FAE
Definition: my_sys.h:121
unsigned int PSI_memory_key
Instrumented memory key.
Definition: psi_memory_bits.h:48
#define MYF(v)
Definition: my_inttypes.h:96
void my_free(void *ptr)
Frees the memory pointed by the ptr.
Definition: my_memory.cc:80
void * my_malloc(PSI_memory_key key, size_t size, int flags)
Allocates size bytes of memory.
Definition: my_memory.cc:56
Common header for many mysys elements.
Performance schema instrumentation interface.