1// Copyright (c) 2013 Austin T. Clements. All rights reserved.
2// Use of this source code is governed by an MIT license
3// that can be found in the LICENSE file.
4
5#ifndef _DWARFPP_SMALL_VECTOR_HH_
6#define _DWARFPP_SMALL_VECTOR_HH_
7
8DWARFPP_BEGIN_NAMESPACE
9
10/**
11 * A vector-like class that only heap allocates above a specified
12 * size.
13 */
14template<class T, unsigned Min>
15class small_vector
16{
17public:
18 typedef T value_type;
19 typedef value_type& reference;
20 typedef const value_type& const_reference;
21 typedef size_t size_type;
22
23 small_vector()
24 : base((T*)buf), end(base), cap((T*)&buf[sizeof(T[Min])])
25 {
26 }
27
28 small_vector(const small_vector<T, Min> &o)
29 : base((T*)buf), end(base), cap((T*)&buf[sizeof(T[Min])])
30 {
31 *this = o;
32 }
33
34 small_vector(small_vector<T, Min> &&o)
35 : base((T*)buf), end(base), cap((T*)&buf[sizeof(T[Min])])
36 {
37 if ((char*)o.base == o.buf) {
38 // Elements are inline; have to copy them
39 base = (T*)buf;
40 end = base;
41 cap = (T*)&buf[sizeof(T[Min])];
42
43 *this = o;
44 o.clear();
45 } else {
46 // Elements are external; swap pointers
47 base = o.base;
48 end = o.end;
49 cap = o.cap;
50
51 o.base = (T*)o.buf;
52 o.end = o.base;
53 o.cap = (T*)&o.buf[sizeof(T[Min])];
54 }
55 }
56
57 ~small_vector()
58 {
59 clear();
60 if ((char*)base != buf)
61 delete[] (char*)base;
62 }
63
64 small_vector &operator=(const small_vector<T, Min> &o)
65 {
66 size_type osize = o.size();
67 clear();
68 reserve(osize);
69 for (size_type i = 0; i < osize; i++)
70 new (&base[i]) T(o[i]);
71 end = base + osize;
72 return *this;
73 }
74
75 size_type size() const
76 {
77 return end - base;
78 }
79
80 bool empty() const
81 {
82 return base == end;
83 }
84
85 void reserve(size_type n)
86 {
87 if (n <= (size_type)(cap - base))
88 return;
89
90 size_type target = cap - base;
91 if (target == 0)
92 target = 1;
93 while (target < n)
94 target <<= 1;
95
96 char *newbuf = new char[sizeof(T)*target];
97 T *src = base, *dest = (T*)newbuf;
98 for (; src < end; src++, dest++) {
99 new(dest) T(*src);
100 dest->~T();
101 }
102 if ((char*)base != buf)
103 delete[] (char*)base;
104 base = (T*)newbuf;
105 end = dest;
106 cap = base + target;
107 }
108
109 reference operator[](size_type n)
110 {
111 return base[n];
112 }
113
114 const_reference operator[](size_type n) const
115 {
116 return base[n];
117 }
118
119 reference at(size_type n)
120 {
121 return base[n];
122 }
123
124 const_reference at(size_type n) const
125 {
126 return base[n];
127 }
128
129 /**
130 * "Reverse at". revat(0) is equivalent to back(). revat(1)
131 * is the element before back. Etc.
132 */
133 reference revat(size_type n)
134 {
135 return *(end - 1 - n);
136 }
137
138 const_reference revat(size_type n) const
139 {
140 return *(end - 1 - n);
141 }
142
143 reference front()
144 {
145 return base[0];
146 }
147
148 const_reference front() const
149 {
150 return base[0];
151 }
152
153 reference back()
154 {
155 return *(end-1);
156 }
157
158 const_reference back() const
159 {
160 return *(end-1);
161 }
162
163 void push_back(const T& x)
164 {
165 reserve(size() + 1);
166 new (end) T(x);
167 end++;
168 }
169
170 void push_back(T&& x)
171 {
172 reserve(size() + 1);
173 new (end) T(std::move(x));
174 end++;
175 }
176
177 void pop_back()
178 {
179 end--;
180 end->~T();
181 }
182
183 void clear()
184 {
185 for (T* p = base; p < end; ++p)
186 p->~T();
187 end = base;
188 }
189
190private:
191 char buf[sizeof(T[Min])];
192 T *base, *end, *cap;
193};
194
195DWARFPP_END_NAMESPACE
196
197#endif
198