1#pragma once
2
3#include <cstddef>
4#include <cstdlib>
5
6#include <Common/Exception.h>
7#include <Common/formatReadable.h>
8
9
10namespace DB
11{
12
13namespace ErrorCodes
14{
15 extern const int CANNOT_ALLOCATE_MEMORY;
16}
17
18/** An array of (almost) unchangable size:
19 * the size is specified in the constructor;
20 * `resize` method removes old data, and necessary only for
21 * so that you can first create an empty object using the default constructor,
22 * and then decide on the size.
23 *
24 * There is a possibility to not initialize elements by default, but create them inplace.
25 * Member destructors are called automatically.
26 *
27 * `sizeof` is equal to the size of one pointer.
28 *
29 * Not exception-safe.
30 *
31 * Copying is supported via assign() method. Moving empties the original object.
32 * That is, it is inconvenient to use this array in many cases.
33 *
34 * Designed for situations in which many arrays of the same small size are created,
35 * but the size is not known at compile time.
36 * Also gives a significant advantage in cases where it is important that `sizeof` is minimal.
37 * For example, if arrays are put in an open-addressing hash table with inplace storage of values (like HashMap)
38 *
39 * In this case, compared to std::vector:
40 * - for arrays of 1 element size - an advantage of about 2 times;
41 * - for arrays of 5 elements - an advantage of about 1.5 times
42 * (DB::Field, containing UInt64 and String, used as T);
43 */
44
45const size_t empty_auto_array_helper = 0;
46
47template <typename T>
48class AutoArray
49{
50public:
51 /// For deferred creation.
52 AutoArray()
53 {
54 setEmpty();
55 }
56
57 explicit AutoArray(size_t size_)
58 {
59 init(size_, false);
60 }
61
62 /** Initializes all elements with a copy constructor with the `value` parameter.
63 */
64 AutoArray(size_t size_, const T & value)
65 {
66 init(size_, true);
67
68 for (size_t i = 0; i < size_; ++i)
69 {
70 new (place(i)) T(value);
71 }
72 }
73
74 /** `resize` removes all existing items.
75 */
76 void resize(size_t size_, bool dont_init_elems = false)
77 {
78 uninit();
79 init(size_, dont_init_elems);
80 }
81
82 /** Move operations.
83 */
84 AutoArray(AutoArray && src)
85 {
86 if (this == &src)
87 return;
88 setEmpty();
89 data_ptr = src.data_ptr;
90 src.setEmpty();
91 }
92
93 AutoArray & operator= (AutoArray && src)
94 {
95 if (this == &src)
96 return *this;
97 uninit();
98 data_ptr = src.data_ptr;
99 src.setEmpty();
100
101 return *this;
102 }
103
104 ~AutoArray()
105 {
106 uninit();
107 }
108
109 size_t size() const
110 {
111 return m_size();
112 }
113
114 bool empty() const
115 {
116 return size() == 0;
117 }
118
119 void clear()
120 {
121 uninit();
122 setEmpty();
123 }
124
125 template <typename It>
126 void assign(It from_begin, It from_end)
127 {
128 uninit();
129
130 size_t size = from_end - from_begin;
131 init(size, /* dont_init_elems = */ true);
132
133 It it = from_begin;
134 for (size_t i = 0; i < size; ++i, ++it)
135 new (place(i)) T(*it);
136 }
137
138 void assign(const AutoArray & from)
139 {
140 assign(from.begin(), from.end());
141 }
142
143 /** You can read and modify elements using the [] operator
144 * only if items were initialized
145 * (that is, into the constructor was not passed DontInitElemsTag,
146 * or you initialized them using `place` and `placement new`).
147 */
148 T & operator[](size_t i)
149 {
150 return elem(i);
151 }
152
153 const T & operator[](size_t i) const
154 {
155 return elem(i);
156 }
157
158 T * data()
159 {
160 return elemPtr(0);
161 }
162
163 const T * data() const
164 {
165 return elemPtr(0);
166 }
167
168 /** Get the piece of memory in which the element should be located.
169 * The function is intended to initialize an element,
170 * which has not yet been initialized
171 * new (arr.place(i)) T(args);
172 */
173 char * place(size_t i)
174 {
175 return data_ptr + sizeof(T) * i;
176 }
177
178 using iterator = T *;
179 using const_iterator = const T *;
180
181 iterator begin() { return elemPtr(0); }
182 iterator end() { return elemPtr(size()); }
183
184 const_iterator begin() const { return elemPtr(0); }
185 const_iterator end() const { return elemPtr(size()); }
186
187 bool operator== (const AutoArray<T> & rhs) const
188 {
189 size_t s = size();
190
191 if (s != rhs.size())
192 return false;
193
194 for (size_t i = 0; i < s; ++i)
195 if (elem(i) != rhs.elem(i))
196 return false;
197
198 return true;
199 }
200
201 bool operator!= (const AutoArray<T> & rhs) const
202 {
203 return !(*this == rhs);
204 }
205
206 bool operator< (const AutoArray<T> & rhs) const
207 {
208 size_t s = size();
209 size_t rhs_s = rhs.size();
210
211 if (s < rhs_s)
212 return true;
213 if (s > rhs_s)
214 return false;
215
216 for (size_t i = 0; i < s; ++i)
217 {
218 if (elem(i) < rhs.elem(i))
219 return true;
220 if (elem(i) > rhs.elem(i))
221 return false;
222 }
223
224 return false;
225 }
226
227private:
228 static constexpr size_t alignment = alignof(T);
229 /// Bytes allocated to store size of array before data. It is padded to have minimum size as alignment.
230 /// Padding is at left and the size is stored at right (just before the first data element).
231 static constexpr size_t prefix_size = std::max(sizeof(size_t), alignment);
232
233 char * data_ptr;
234
235 size_t & m_size()
236 {
237 return reinterpret_cast<size_t *>(data_ptr)[-1];
238 }
239
240 size_t m_size() const
241 {
242 return reinterpret_cast<const size_t *>(data_ptr)[-1];
243 }
244
245 T * elemPtr(size_t i)
246 {
247 return reinterpret_cast<T *>(data_ptr) + i;
248 }
249
250 const T * elemPtr(size_t i) const
251 {
252 return reinterpret_cast<const T *>(data_ptr) + i;
253 }
254
255 T & elem(size_t i)
256 {
257 return *elemPtr(i);
258 }
259
260 const T & elem(size_t i) const
261 {
262 return *elemPtr(i);
263 }
264
265 void setEmpty()
266 {
267 data_ptr = const_cast<char *>(reinterpret_cast<const char *>(&empty_auto_array_helper)) + sizeof(size_t);
268 }
269
270 void init(size_t new_size, bool dont_init_elems)
271 {
272 if (!new_size)
273 {
274 setEmpty();
275 return;
276 }
277
278 void * new_data = nullptr;
279 int res = posix_memalign(&new_data, alignment, prefix_size + new_size * sizeof(T));
280 if (0 != res)
281 throwFromErrno("Cannot allocate memory (posix_memalign) " + formatReadableSizeWithBinarySuffix(new_size) + ".",
282 ErrorCodes::CANNOT_ALLOCATE_MEMORY, res);
283
284 data_ptr = static_cast<char *>(new_data);
285 data_ptr += prefix_size;
286
287 m_size() = new_size;
288
289 if (!dont_init_elems)
290 for (size_t i = 0; i < new_size; ++i)
291 new (place(i)) T();
292 }
293
294 void uninit()
295 {
296 size_t s = size();
297
298 if (s)
299 {
300 for (size_t i = 0; i < s; ++i)
301 elem(i).~T();
302
303 data_ptr -= prefix_size;
304 free(data_ptr);
305 }
306 }
307};
308
309}
310