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