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 
30 template<typename T> class unsafe_pod_vector;
31 
32 template<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 
64  pod_vector(pod_vector<T>&& other)
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 
224 template<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 };