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