1 /* 2 * Copyright (c) 2015 Andrew Kelley 3 * 4 * This file is part of zig, which is MIT licensed. 5 * See http://opensource.org/licenses/MIT 6 */ 7 8 #ifndef ZIG_MEM_LIST_HPP 9 #define ZIG_MEM_LIST_HPP 10 11 #include "mem.hpp" 12 13 namespace mem { 14 15 template<typename T> 16 struct List { deinitmem::List17 void deinit(Allocator *allocator) { 18 allocator->deallocate<T>(items, capacity); 19 items = nullptr; 20 length = 0; 21 capacity = 0; 22 } 23 appendmem::List24 void append(Allocator *allocator, const T& item) { 25 ensure_capacity(allocator, length + 1); 26 items[length++] = item; 27 } 28 29 // remember that the pointer to this item is invalid after you 30 // modify the length of the list atmem::List31 const T & at(size_t index) const { 32 assert(index != SIZE_MAX); 33 assert(index < length); 34 return items[index]; 35 } 36 atmem::List37 T & at(size_t index) { 38 assert(index != SIZE_MAX); 39 assert(index < length); 40 return items[index]; 41 } 42 popmem::List43 T pop() { 44 assert(length >= 1); 45 return items[--length]; 46 } 47 add_onemem::List48 T *add_one() { 49 resize(length + 1); 50 return &last(); 51 } 52 lastmem::List53 const T & last() const { 54 assert(length >= 1); 55 return items[length - 1]; 56 } 57 lastmem::List58 T & last() { 59 assert(length >= 1); 60 return items[length - 1]; 61 } 62 resizemem::List63 void resize(Allocator *allocator, size_t new_length) { 64 assert(new_length != SIZE_MAX); 65 ensure_capacity(allocator, new_length); 66 length = new_length; 67 } 68 clearmem::List69 void clear() { 70 length = 0; 71 } 72 ensure_capacitymem::List73 void ensure_capacity(Allocator *allocator, size_t new_capacity) { 74 if (capacity >= new_capacity) 75 return; 76 77 size_t better_capacity = capacity; 78 do { 79 better_capacity = better_capacity * 5 / 2 + 8; 80 } while (better_capacity < new_capacity); 81 82 items = allocator->reallocate_nonzero<T>(items, capacity, better_capacity); 83 capacity = better_capacity; 84 } 85 swap_removemem::List86 T swap_remove(size_t index) { 87 if (length - 1 == index) return pop(); 88 89 assert(index != SIZE_MAX); 90 assert(index < length); 91 92 T old_item = items[index]; 93 items[index] = pop(); 94 return old_item; 95 } 96 97 T *items{nullptr}; 98 size_t length{0}; 99 size_t capacity{0}; 100 }; 101 102 } // namespace mem 103 104 #endif 105