Simulant  21.12-194
A portable game engine for Windows, OSX, Linux, Dreamcast, and PSP
polylist.h
1 #pragma once
2 
3 /* Polylist is a container with the following properties:
4  *
5  * - It can store any leaf element from a heirarchy that subclass
6  * Base
7  * - It pools memory into chunked allocations of ChunkSize
8  * - It provides an id on insertion that allows for constant-time
9  * lookups.
10  *
11  * Usage:
12  *
13  * Polylist<BaseThing, Thing> list;
14  *
15  * auto pair = list.create("mything");
16  * auto it = pair.first;
17  * auto id = pair.second;
18  *
19  * (*it) == list[id]; // true
20  * list[some_other_id] == nullptr; // true
21  *
22  * list.erase(it); // or list.erase(id);
23  */
24 
25 #include <type_traits>
26 #include <cassert>
27 #include <cstdint>
28 #include <utility>
29 #include <vector>
30 #include <memory>
31 #include <cstring>
32 #include <stdexcept>
33 
34 namespace smlt {
35 
36 namespace _polylist {
37 
38 constexpr std::size_t max(std::size_t a, std::size_t b) {
39  return (a > b) ? a : b;
40 }
41 
42 template<typename... Ts> struct MaxSize {
43  static constexpr std::size_t value = 0;
44 };
45 
46 template<typename T, typename... Ts> struct MaxSize<T, Ts...> {
47  static constexpr std::size_t value = max(sizeof(T), MaxSize<Ts...>::value);
48 };
49 
50 
51 template < typename Tp, typename... List >
52 struct contains : std::true_type {};
53 
54 template < typename Tp, typename Head, typename... Rest >
55 struct contains<Tp, Head, Rest...>
56 : std::conditional< std::is_same<Tp, Head>::value,
57  std::true_type,
58  contains<Tp, Rest...>
59 >::type {};
60 
61 template < typename Tp >
62 struct contains<Tp> : std::false_type {};
63 
64 }
65 
66 template<typename Base, typename... Classes>
67 class Polylist {
68  struct EntryMeta;
69 
70 public:
71  const static std::size_t entry_size = _polylist::MaxSize<Base, Classes...>::value;
72  static_assert(sizeof(Base) <= entry_size, "entry_size was invalid");
73 
74  const std::size_t chunk_size;
75 
76  Polylist(const Polylist&) = delete;
77  Polylist& operator=(const Polylist&) = delete;
78 
79  template<bool IsConst>
81  private:
82  PolylistIterator(const Polylist* owner, EntryMeta* meta):
83  owner_(owner),
84  current_(meta) {
85 
86  }
87 
88  const Polylist* owner_;
89  EntryMeta* current_;
90 
91  friend class Polylist;
92 
93  public:
94  using iterator_category = std::forward_iterator_tag;
95  using value_type = Base*;
96  using difference_type = uint32_t;
97  using pointer = Base**;
98  using reference = Base*&;
99 
100  bool operator==(const PolylistIterator& rhs) const {
101  return current_ == rhs.current_;
102  }
103 
104  bool operator!=(const PolylistIterator& rhs) const {
105  return current_ != rhs.current_;
106  }
107 
108  PolylistIterator& operator++() {
109  auto& chunk = owner_->chunks_[current_->chunk];
110 
111  if(current_ != chunk->used_list_tail_) {
112  /* We reached the end last iteration */
113  current_ = current_->next;
114  } else if(current_->chunk < owner_->chunks_.size() - 1) {
115  /* If next is null, we're at the end of the current chunk
116  * so move to the next one that isn't empty */
117  auto next_chunk_id = current_->chunk + 1;
118  auto next_chunk = owner_->chunks_[next_chunk_id];
119  while((!next_chunk->used_list_head_) && next_chunk_id < (int) owner_->chunks_.size() - 1) {
120  next_chunk = owner_->chunks_[++next_chunk_id];
121  }
122 
123  current_ = next_chunk->used_list_head_; // May be null if we reached the end
124  } else {
125  /* We're done */
126  current_ = nullptr;
127  }
128 
129  return *this;
130  }
131 
132  reference operator*() const {
133  return (reference) current_->entry;
134  }
135 
136  pointer operator->() const {
137  if(!current_) {
138  return nullptr;
139  }
140 
141  return &((reference) current_->entry);
142  }
143  };
144 
145  friend class PolylistIterator<true>;
146  friend class PolylistIterator<false>;
147 
150  typedef std::size_t id;
151 
152  Polylist(std::size_t chunk_size):
153  chunk_size(chunk_size) {
154 
155  assert(chunk_size > 0);
156  }
157 
158  ~Polylist() {
159  clear();
160  }
161 
162  /* Create a new element using placement new, with the set of
163  * args for the constructor. */
164  template<typename T, typename... Args>
165  std::pair<T*, id> create(Args&&... args) {
166  static_assert(std::is_base_of<Base, T>::value, "Must be a subclass of Base");
167  static_assert(_polylist::contains<T, Classes...>::value, "T not in Classes...");
168  static_assert(sizeof(T) <= entry_size, "sizeof(T) was greater than entry_size");
169 
170  id new_id;
171  EntryWithMeta* ewm = find_free_entry(&new_id);
172 
173  assert(!ewm->meta.reserved);
174 
175  // Ensure further calls do not return this entry!
176  ewm->meta.reserved = 1;
177  T* ret = nullptr;
178  try {
179  /* Construct the object */
180  ret = new (ewm->data) T(std::forward<Args>(args)...);
181  // We're all good now
182  ewm->meta.reserved = 0;
183  } catch(...) {
184  ewm->meta.reserved = 0;
185  throw;
186  }
187 
188  alloc_entry(ewm, (T*) ewm->data);
189 
190  assert(ret);
191  assert((void*) ret == (void*) ewm->data);
192  assert((void*) ret == (void*) ewm);
193  assert((Base*) ret == ewm->meta.entry);
194 
195  return std::make_pair(ret, new_id);
196  }
197 
198  iterator find(const id& i) const {
199  auto ewm = object_from_id(i);
200  Base* obj = ewm->meta.entry;
201 
202  if(obj) {
203  EntryMeta* meta = &ewm->meta;
204  assert(meta->entry);
205 
206  return iterator(
207  this, meta
208  );
209  } else {
210  return end();
211  }
212  }
213 
214  /* Erase an element, and return an iterator to the next used
215  * element */
216  iterator erase(iterator it) {
217  auto meta = it.current_;
218  assert(meta);
219 
220  auto next = iterator(this, meta);
221  ++next;
222 
223  assert(meta->entry);
224 
225 
226  auto chunk_idx = meta->chunk;
227  auto& chunk = chunks_[chunk_idx];
228 
229  assert(meta->next);
230  assert(meta->prev);
231 
232  /* Remove from the used list */
233  meta->prev->next = meta->next;
234  meta->next->prev = meta->prev;
235 
236  if(chunk->used_list_head_ == meta && chunk->used_list_tail_ == meta) {
237  chunk->used_list_head_ = chunk->used_list_tail_ = nullptr;
238  } else if(chunk->used_list_head_ == meta) {
239  chunk->used_list_head_ = meta->next;
240  } else if(chunk->used_list_tail_ == meta) {
241  chunk->used_list_tail_ = meta->prev;
242  }
243 
244  /* Detach completely */
245  meta->next = meta->prev = meta;
246 
247  /* Destroy and then add to the free list, an exception in
248  a destructor will terminate anyway so we don't need to worry
249  about leaving stuff in an inconsistent state
250  */
251  Base* obj = meta->entry;
252  obj->~Base();
253 
254  /* Wipe out the entry */
255  auto ewm = get_ewm(meta);
256  memset(ewm->data, 0, sizeof(ewm->data));
257 
258  assert(meta->entry);
259  meta->entry = nullptr;
260 
261  /* No free list? */
262  if(!chunk->free_list_tail_) {
263  assert(!chunk->free_list_head_);
264  /* This is now the free list */
265  chunk->free_list_head_ = chunk->free_list_tail_ = meta;
266  } else {
267  /* Otherwise, add to the end, and update the tail */
268  meta->prev = chunk->free_list_tail_;
269  meta->next = chunk->free_list_head_;
270 
271  chunk->free_list_tail_->next = meta;
272  chunk->free_list_head_->prev = meta;
273 
274  chunk->free_list_tail_ = meta;
275  }
276 
277  /* If we just deallocated, this must be non-null */
278  assert(chunk->free_list_head_);
279  assert(chunk->free_list_tail_);
280 
281  /* Check all the things */
282  assert(chunk->free_list_head_ != chunk->used_list_head_);
283  assert(chunk->free_list_head_ != chunk->used_list_tail_);
284  assert(chunk->free_list_tail_ != chunk->used_list_head_);
285  assert(chunk->free_list_tail_ != chunk->used_list_tail_);
286 
287  assert(
288  (chunk->used_list_head_ && chunk->used_list_tail_) ||
289  (!chunk->used_list_head_ && !chunk->used_list_tail_)
290  );
291 
292  assert(size_ > 0);
293  size_--;
294  chunk->used_count--;
295  return next;
296  }
297 
298  void shrink_to_fit() {
299  /* Release the last chunk if it's empty */
300  while(chunks_.size() && !chunks_.back()->used_count) {
301  pop_chunk();
302  }
303  }
304 
305  void reserve(std::size_t amount) {
306  while(capacity() < amount) {
307  push_chunk();
308  }
309  }
310 
311  iterator begin() const {
312  for(auto& chunk: chunks_) {
313  if(chunk->used_list_head_){
314  return iterator(this, chunk->used_list_head_);
315  }
316  }
317 
318  return iterator(this, nullptr);
319  }
320 
321  iterator end() const {
322  return iterator(this, nullptr);
323  }
324 
325  /* Destroy all the elements */
326  void clear() {
327  for(auto it = begin(); it != end();) {
328  it = erase(it);
329  }
330 
331  while(!chunks_.empty()) {
332  pop_chunk();
333  }
334  }
335 
336  Base* operator[](id i) {
337  auto obj = object_from_id(i);
338  if(obj) {
339  return obj->meta.entry;
340  } else {
341  return nullptr;
342  }
343  }
344 
345  const Base* operator[](id i) const {
346  return object_from_id(i)->meta.entry;
347  }
348 
349  bool empty() const {
350  return size_ == 0;
351  }
352 
353  std::size_t size() const {
354  return size_;
355  }
356 
357  std::size_t capacity() const {
358  return chunk_size * chunks_.size();
359  }
360 
361 private:
362  typedef uint8_t byte;
363  std::size_t size_ = 0;
364 
365  struct EntryMeta {
366  EntryMeta* prev = nullptr; //4
367  EntryMeta* next = nullptr; //4
368 
369  /* We reserve entries during type construction
370  * and mark them as unreserved when done */
371  uint16_t reserved = 0; // 2
372 
373  Base* entry = nullptr; // 4
374  uint32_t padding = 0; // 4
375 
376  uint16_t chunk = 0; // 2
377  std::size_t index = 0; // 4
378  };
379 
380  typedef struct {
381  byte data[entry_size] __attribute__((aligned(8)));
382  EntryMeta meta;
383  } __attribute__((aligned(8))) EntryWithMeta;
384 
385  struct Chunk {
386  uint32_t used_count = 0;
387  EntryWithMeta* data = nullptr;
388 
389  EntryMeta* free_list_head_ = nullptr;
390  EntryMeta* free_list_tail_ = nullptr;
391 
392  EntryMeta* used_list_head_ = nullptr;
393  EntryMeta* used_list_tail_ = nullptr;
394  };
395 
396  const static std::size_t slot_size = entry_size + sizeof(EntryMeta);
397 
398  /* Each chunk is a dynamically allocated block of data that is
399  * sizeof(ElementWithMeta) * ChunkSize in size */
400  std::vector<std::shared_ptr<Chunk>> chunks_;
401 
402  void push_chunk() {
403  /* Allocate the new chunk */
404  auto new_chunk = std::make_shared<Chunk>();
405  new_chunk->data = new EntryWithMeta[chunk_size];
406 
407  /* Get pointers to the first meta (which follows the actual entry)
408  * and the previous in the list, which would be the current free tail
409  */
410  EntryWithMeta* ewm = new_chunk->data;
411 
412  /* Set the free list head to the first thing */
413  new_chunk->free_list_head_ = &ewm->meta;
414 
415  EntryMeta* prev = nullptr;
416  /* Go through all metas and set prev/next pointers */
417  for(std::size_t i = 0; i < chunk_size; ++i) {
418  EntryMeta* meta = &ewm->meta;
419  memset(ewm->data, 0, sizeof(ewm->data));
420 
421  meta->prev = prev;
422  meta->chunk = chunks_.size();
423  meta->index = i; // Set the ID
424  meta->entry = nullptr;
425 
426  if(i < chunk_size - 1) {
427  meta->next = &(ewm + 1)->meta;
428  }
429 
430  ewm++;
431  prev = meta;
432  }
433 
434  new_chunk->free_list_tail_ = prev;
435 
436  /* Make circular */
437  new_chunk->free_list_head_->prev = new_chunk->free_list_tail_;
438  new_chunk->free_list_tail_->next = new_chunk->free_list_head_;
439  assert(new_chunk->free_list_head_->prev);
440  assert(new_chunk->free_list_tail_->next);
441 
442  assert(new_chunk->free_list_head_);
443  assert(new_chunk->free_list_tail_);
444  assert(!new_chunk->used_list_head_);
445  assert(!new_chunk->used_list_tail_);
446 
447  /* Finally, make the new chunk available and set the free list tail
448  * to the last of the new chunk */
449  chunks_.push_back(new_chunk);
450  }
451 
452  bool pop_chunk() {
453  if(chunks_.empty()) {
454  return false;
455  }
456 
457  auto chunk = chunks_.back();
458 
459  auto it = iterator(this, chunk->used_list_head_);
460 
461  /* End really means end, because this is the final chunk *
462  * this wouldn't work to delete any chunk as the end iterator
463  * would be the used head of the next chunk in that case */
464  auto end = iterator(this, nullptr);
465 
466  for(; it != end;) {
467  it = erase(it);
468  }
469 
470  delete [] chunk->data;
471  chunk->data = nullptr;
472 
473  chunks_.pop_back();
474 
475  return true;
476  }
477 
478  void alloc_entry(EntryWithMeta* ewm, Base* obj) {
479  auto& chunk = chunks_[ewm->meta.chunk];
480 
481  assert(ewm->meta.next);
482  assert(ewm->meta.prev);
483 
484  assert(chunk->free_list_head_);
485  assert(chunk->free_list_tail_);
486 
487  if(chunk->free_list_head_ == &ewm->meta && chunk->free_list_tail_ == &ewm->meta) {
488  // Last entry in the free list! Wipe out the head and tail
489  chunk->free_list_head_ = chunk->free_list_tail_ = nullptr;
490  } else if(chunk->free_list_head_ == &ewm->meta) {
491  chunk->free_list_head_ = chunk->free_list_head_->next;
492  } else if(chunk->free_list_tail_ == &ewm->meta) {
493  chunk->free_list_tail_ = chunk->free_list_tail_->prev;
494  }
495 
496  if(!chunk->used_list_tail_) {
497  assert(!chunk->used_list_head_);
498 
499  chunk->used_list_head_ = chunk->used_list_tail_ = &ewm->meta;
500  } else {
501  /* Add to the end of the used list */
502  ewm->meta.prev = chunk->used_list_tail_;
503  ewm->meta.next = chunk->used_list_head_;
504 
505  ewm->meta.prev->next = &ewm->meta;
506  ewm->meta.next->prev = &ewm->meta;
507 
508  chunk->used_list_tail_ = &ewm->meta;
509  }
510 
511  ewm->meta.entry = obj;
512 
513  assert(ewm->meta.next);
514  assert(ewm->meta.prev);
515 
516  /* If we just allocated, this must be non-null */
517  assert(chunk->used_list_head_);
518  assert(chunk->used_list_tail_);
519 
520  assert(
521  (!chunk->free_list_head_ && !chunk->free_list_tail_) ||
522  (chunk->free_list_head_ && chunk->free_list_tail_)
523  );
524 
525  ++chunk->used_count;
526  ++size_;
527  }
528 
529  EntryWithMeta* find_free_entry(id* new_id) {
530  uint32_t i = 0;
531  for(auto chunk: chunks_) {
532  if(chunk->free_list_head_ && !chunk->free_list_head_->reserved) {
533  EntryMeta* result = chunk->free_list_head_;
534 
535  assert(result->chunk == i);
536  *new_id = ((i * chunk_size) + result->index) + 1;
537 
538  return get_ewm(result);
539  }
540 
541  ++i;
542  }
543 
544  /* If no free entry was found, we need a new chunk */
545  push_chunk();
546 
547  return find_free_entry(new_id);
548  }
549 
550  EntryWithMeta* object_from_id(id i) const {
551  if(i == 0) {
552  return nullptr;
553  }
554 
555  std::size_t idx = i - 1;
556  std::size_t chunk_id = (idx / chunk_size);
557  std::size_t index = (idx % chunk_size);
558 
559  if(chunk_id >= chunks_.size()) {
560  return nullptr;
561  }
562 
563  if(index >= chunk_size) {
564  return nullptr;
565  }
566 
567  EntryWithMeta* ewm = &chunks_[chunk_id]->data[index];
568 
569  assert(chunk_id == ewm->meta.chunk);
570  assert(index == ewm->meta.index);
571 
572  return ewm;
573  }
574 
575  EntryWithMeta* get_ewm(EntryMeta* meta) {
576  return &chunks_[meta->chunk]->data[meta->index];
577  }
578 };
579 
580 }
smlt::Polylist::PolylistIterator
Definition: polylist.h:80
smlt::_polylist::MaxSize
Definition: polylist.h:42
smlt
Definition: animation.cpp:25
smlt::_polylist::contains
Definition: polylist.h:52
smlt::Polylist
Definition: polylist.h:67