1 | #pragma once |
2 | |
3 | #include <cstddef> |
4 | #include <cstdlib> |
5 | |
6 | #include <Common/Exception.h> |
7 | #include <Common/formatReadable.h> |
8 | |
9 | |
10 | namespace DB |
11 | { |
12 | |
13 | namespace 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 | |
45 | const size_t empty_auto_array_helper = 0; |
46 | |
47 | template <typename T> |
48 | class AutoArray |
49 | { |
50 | public: |
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 | |
227 | private: |
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 | |