IsoSpec 2.2.1
pod_vector.h
1
17#pragma once
18
19#include <type_traits>
20#include <cstdlib>
21#include <cstddef>
22#include <utility>
23#include <new>
24#include <algorithm>
25#include "platform.h"
26#include "conf.h"
27
28
29
30template<typename T> class unsafe_pod_vector;
31
32template<typename T> class pod_vector
33{
34 T* backend_past_end;
35 T* first_free;
36 T* store;
37
38 public:
39 explicit pod_vector(size_t initial_size = 16)
40 {
41 #if !ISOSPEC_BUILDING_R
42 static_assert(std::is_trivially_copyable<T>::value, "Cannot use a pod_vector with a non-Plain Old Data type.");
43 #endif
44
45 store = reinterpret_cast<T*>(malloc(sizeof(T) * initial_size));
46 if(store == NULL)
47 throw std::bad_alloc();
48 first_free = store;
49 backend_past_end = store + initial_size;
50 }
51
52 pod_vector(const pod_vector<T>& other) = delete;
53 pod_vector& operator=(const pod_vector<T>& other) = delete;
54 pod_vector& operator=(pod_vector<T>&& other)
55 {
56 free(store);
57 backend_past_end = other.backend_past_end;
58 first_free = other.first_free;
59 store = other.store;
60 other.backend_past_end = other.first_free = other.store = NULL;
61 return *this;
62 }
63
65 {
66 backend_past_end = other.backend_past_end;
67 first_free = other.first_free;
68 store = other.store;
69 other.backend_past_end = other.first_free = other.store = NULL;
70 }
71
72 ~pod_vector() { free(store); backend_past_end = first_free = store = NULL; }
73
74 explicit pod_vector(unsafe_pod_vector<T>&& other)
75 {
76 backend_past_end = other.backend_past_end;
77 first_free = other.first_free;
78 store = other.store;
79 other.backend_past_end = other.first_free = other.store = NULL;
80 }
81
82 void fast_reserve(size_t n)
83 {
84 ISOSPEC_IMPOSSIBLE(n < static_cast<size_t>(backend_past_end - store));
85 const std::ptrdiff_t store_used_size = first_free - store;
86 T* new_store = reinterpret_cast<T*>(realloc(store, n * sizeof(T)));
87 if(new_store == NULL)
88 throw std::bad_alloc();
89 first_free = new_store + store_used_size;
90 backend_past_end = new_store + n;
91 store = new_store;
92 }
93
94 void reserve(size_t n)
95 {
96 if (n > static_cast<size_t>(backend_past_end - store))
97 fast_reserve(n);
98 }
99
100 void resize(size_t new_size)
101 {
102 ISOSPEC_IMPOSSIBLE(static_cast<std::ptrdiff_t>(new_size) < first_free - store);
103 size_t cap = capacity();
104 if(cap < new_size)
105 {
106 do {
107 cap = cap * 2;
108 } while(cap < new_size);
109 fast_reserve(cap);
110 }
111 first_free = store + new_size;
112 }
113
114 void resize_and_wipe(size_t new_size)
115 {
116 size_t old_size = size();
117 ISOSPEC_IMPOSSIBLE(new_size <= old_size);
118 resize(new_size);
119 memset(store+old_size, 0, (new_size-old_size) * sizeof(T));
120 }
121
122 ISOSPEC_FORCE_INLINE void nocheck_push_back(const T& val) noexcept
123 {
124 ISOSPEC_IMPOSSIBLE(first_free >= backend_past_end);
125 *first_free = val;
126 first_free++;
127 }
128
129 ISOSPEC_FORCE_INLINE void push_back(const T& val)
130 {
131 if(first_free >= backend_past_end)
132 fast_reserve((std::max<std::ptrdiff_t>)(4, (backend_past_end-store)) * 2);
133 *first_free = val;
134 first_free++;
135 }
136
137 ISOSPEC_FORCE_INLINE T& operator[](size_t n) noexcept
138 {
139 ISOSPEC_IMPOSSIBLE(store + n >= first_free);
140 return store[n];
141 }
142
143 ISOSPEC_FORCE_INLINE const T& operator[](size_t n) const noexcept
144 {
145 ISOSPEC_IMPOSSIBLE(store + n >= first_free);
146 return store[n];
147 }
148
149 ISOSPEC_FORCE_INLINE size_t size() const noexcept
150 {
151 return first_free - store;
152 }
153
154 ISOSPEC_FORCE_INLINE size_t capacity() const noexcept
155 {
156 return backend_past_end - store;
157 }
158
159 ISOSPEC_FORCE_INLINE T* data() noexcept
160 {
161 return store;
162 }
163
164 ISOSPEC_FORCE_INLINE const T* data() const noexcept
165 {
166 return store;
167 }
168
169 ISOSPEC_FORCE_INLINE bool empty() const noexcept
170 {
171 return first_free == store;
172 }
173
174 ISOSPEC_FORCE_INLINE const T& back() const noexcept
175 {
176 ISOSPEC_IMPOSSIBLE(first_free > backend_past_end);
177 return *(first_free-1);
178 }
179
180 ISOSPEC_FORCE_INLINE void pop_back() noexcept
181 {
182 // Unlike std::vector we do not ever shrink backend storage unless explicitly requested.
183 ISOSPEC_IMPOSSIBLE(first_free == store);
184 first_free--;
185 }
186
187 void swap(pod_vector<T>& other) noexcept
188 {
189 std::swap(backend_past_end, other.backend_past_end);
190 std::swap(first_free, other.first_free);
191 std::swap(store, other.store);
192 }
193
194 typedef T* iterator;
195 typedef const T* const_iterator;
196 typedef T value_type;
197 typedef size_t size_type;
198 typedef T& reference;
199 typedef const T& const_reference;
200
201 iterator begin() noexcept { return store; };
202 const_iterator begin() const noexcept { return store; }
203 const_iterator cbegin() const noexcept { return store; }
204 iterator end() noexcept { return first_free; }
205 const_iterator end() const noexcept { return first_free; }
206 const_iterator cend() const noexcept { return first_free; }
207
208 ISOSPEC_FORCE_INLINE const T& front() const noexcept
209 {
210 ISOSPEC_IMPOSSIBLE(store == first_free);
211 return *store;
212 }
213
214 void clear()
215 {
216 free(store);
217 first_free = store = backend_past_end = NULL;
218 }
219
220 friend class unsafe_pod_vector<T>;
221};
222
223
224template<typename T> class unsafe_pod_vector
225{
226
227 T* backend_past_end;
228 T* first_free;
229 T* store;
230
231 public:
232 unsafe_pod_vector() = default;
233
234 void init() {
235 #if !ISOSPEC_BUILDING_R
236 static_assert(std::is_trivially_copyable<T>::value, "Cannot use a pod_vector with a non-Plain Old Data type.");
237 static_assert(std::is_trivially_copyable<unsafe_pod_vector<T> >::value, "Cannot use a pod_vector with a non-Plain Old Data type.");
238 #endif
239 memset(this, 0, sizeof(*this));
240 }
241
242 void init(size_t initial_size)
243 {
244 #if !ISOSPEC_BUILDING_R
245 static_assert(std::is_trivially_copyable<T>::value, "Cannot use a pod_vector with a non-Plain Old Data type.");
246 static_assert(std::is_trivially_copyable<unsafe_pod_vector<T> >::value, "Cannot use a pod_vector with a non-Plain Old Data type.");
247 #endif
248 store = reinterpret_cast<T*>(malloc(sizeof(T) * initial_size));
249 if(store == NULL)
250 throw std::bad_alloc();
251 first_free = store;
252 backend_past_end = store + initial_size;
253 }
254
255 unsafe_pod_vector(const pod_vector<T>& other) = delete; // NOLINT(runtime/explicit) - seriously? Deleted constructors have to be marked explicit?
256 unsafe_pod_vector& operator=(const pod_vector<T>& other) = delete;
257 //unsafe_pod_vector(unsafe_pod_vector<T>&& other) = default;
258
259 ~unsafe_pod_vector() = default;
260
261 void fast_reserve(size_t n)
262 {
263 ISOSPEC_IMPOSSIBLE(n < static_cast<size_t>(backend_past_end - store));
264 T* new_store = reinterpret_cast<T*>(realloc(store, n * sizeof(T)));
265 if(new_store == NULL)
266 throw std::bad_alloc();
267 first_free = new_store + (first_free - store);
268 backend_past_end = new_store + n;
269 store = new_store;
270 }
271
272 void reserve(size_t n)
273 {
274 if (n > backend_past_end - store)
275 fast_reserve(n);
276 }
277
278 void resize(size_t new_size)
279 {
280 ISOSPEC_IMPOSSIBLE(new_size < first_free - store);
281 size_t cap = capacity();
282 if(cap < new_size)
283 {
284 do {
285 cap = cap * 2;
286 } while(cap < new_size);
287 fast_reserve(cap);
288 }
289 first_free = store + new_size;
290 }
291
292 void resize_and_wipe(size_t new_size)
293 {
294 size_t old_size = size();
295 ISOSPEC_IMPOSSIBLE(new_size <= old_size);
296 resize(new_size);
297 memset(store+old_size, 0, (new_size-old_size) * sizeof(T));
298 }
299
300 ISOSPEC_FORCE_INLINE void nocheck_push_back(const T& val) noexcept
301 {
302 ISOSPEC_IMPOSSIBLE(first_free >= backend_past_end);
303 *first_free = val;
304 first_free++;
305 }
306
307 ISOSPEC_FORCE_INLINE void push_back(const T& val)
308 {
309 if(first_free >= backend_past_end)
310 fast_reserve((std::max<std::ptrdiff_t>)(4, (backend_past_end-store)) * 2);
311 *first_free = val;
312 first_free++;
313 }
314
315 ISOSPEC_FORCE_INLINE T& operator[](size_t n) noexcept
316 {
317 ISOSPEC_IMPOSSIBLE(store + n >= first_free);
318 return store[n];
319 }
320
321 ISOSPEC_FORCE_INLINE const T& operator[](size_t n) const noexcept
322 {
323 ISOSPEC_IMPOSSIBLE(store + n >= first_free);
324 return store[n];
325 }
326
327 ISOSPEC_FORCE_INLINE size_t size() const noexcept
328 {
329 return first_free - store;
330 }
331
332 ISOSPEC_FORCE_INLINE size_t capacity() const noexcept
333 {
334 return backend_past_end - store;
335 }
336
337 ISOSPEC_FORCE_INLINE T* data() noexcept
338 {
339 return store;
340 }
341
342 ISOSPEC_FORCE_INLINE const T* data() const noexcept
343 {
344 return store;
345 }
346
347 ISOSPEC_FORCE_INLINE bool empty() const noexcept
348 {
349 return first_free == store;
350 }
351
352 ISOSPEC_FORCE_INLINE const T& back() const noexcept
353 {
354 ISOSPEC_IMPOSSIBLE(first_free > backend_past_end);
355 return *(first_free-1);
356 }
357
358 ISOSPEC_FORCE_INLINE void pop_back() noexcept
359 {
360 // Unlike std::vector we do not ever shrink backend storage unless explicitly requested.
361 ISOSPEC_IMPOSSIBLE(first_free == store);
362 first_free--;
363 }
364
365 void swap(pod_vector<T>& other) noexcept
366 {
367 std::swap(backend_past_end, other.backend_past_end);
368 std::swap(first_free, other.first_free);
369 std::swap(store, other.store);
370 }
371
372 typedef T* iterator;
373 typedef const T* const_iterator;
374 typedef T value_type;
375 typedef size_t size_type;
376 typedef T& reference;
377 typedef const T& const_reference;
378
379 iterator begin() noexcept { return store; };
380 const_iterator begin() const noexcept { return store; }
381 const_iterator cbegin() const noexcept { return store; }
382 iterator end() noexcept { return first_free; }
383 const_iterator end() const noexcept { return first_free; }
384 const_iterator cend() const noexcept { return first_free; }
385
386 ISOSPEC_FORCE_INLINE const T& front() const noexcept
387 {
388 ISOSPEC_IMPOSSIBLE(store == first_free);
389 return *store;
390 }
391
392 void clear()
393 {
394 free(store);
395 first_free = store = backend_past_end = NULL;
396 }
397
398 friend class pod_vector<T>;
399};