|
danderson@0
|
1 |
// vim: set sts=8 ts=2 sw=2 tw=99 et: |
|
danderson@0
|
2 |
// |
|
danderson@0
|
3 |
// Copyright (C) 2013, David Anderson and AlliedModders LLC |
|
danderson@0
|
4 |
// All rights reserved. |
|
danderson@0
|
5 |
// |
|
danderson@0
|
6 |
// Redistribution and use in source and binary forms, with or without |
|
danderson@0
|
7 |
// modification, are permitted provided that the following conditions are met: |
|
danderson@0
|
8 |
// |
|
danderson@0
|
9 |
// * Redistributions of source code must retain the above copyright notice, this |
|
danderson@0
|
10 |
// list of conditions and the following disclaimer. |
|
danderson@0
|
11 |
// * Redistributions in binary form must reproduce the above copyright notice, |
|
danderson@0
|
12 |
// this list of conditions and the following disclaimer in the documentation |
|
danderson@0
|
13 |
// and/or other materials provided with the distribution. |
|
danderson@0
|
14 |
// * Neither the name of AlliedModders LLC nor the names of its contributors |
|
danderson@0
|
15 |
// may be used to endorse or promote products derived from this software |
|
danderson@0
|
16 |
// without specific prior written permission. |
|
danderson@0
|
17 |
// |
|
danderson@0
|
18 |
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
|
danderson@0
|
19 |
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
|
danderson@0
|
20 |
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
|
danderson@0
|
21 |
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
|
danderson@0
|
22 |
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
|
danderson@0
|
23 |
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
|
danderson@0
|
24 |
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
|
danderson@0
|
25 |
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
|
danderson@0
|
26 |
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
|
danderson@0
|
27 |
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
|
danderson@0
|
28 |
// POSSIBILITY OF SUCH DAMAGE. |
|
danderson@0
|
29 |
|
|
danderson@0
|
30 |
#ifndef _INCLUDE_KEIMA_TPL_CPP_VECTOR_H_ |
|
danderson@0
|
31 |
#define _INCLUDE_KEIMA_TPL_CPP_VECTOR_H_ |
|
danderson@0
|
32 |
|
|
danderson@0
|
33 |
#include <new> |
|
danderson@0
|
34 |
#include <stdlib.h> |
|
danderson@0
|
35 |
#include <am-allocator-policies.h> |
|
danderson@0
|
36 |
#include <am-utility.h> |
|
dvander@10
|
37 |
#include <am-moveable.h> |
|
danderson@0
|
38 |
|
|
danderson@0
|
39 |
namespace ke { |
|
danderson@0
|
40 |
|
|
danderson@0
|
41 |
template <typename T, typename AllocPolicy = SystemAllocatorPolicy> |
|
danderson@0
|
42 |
class Vector : public AllocPolicy |
|
danderson@0
|
43 |
{ |
|
danderson@0
|
44 |
public: |
|
danderson@0
|
45 |
Vector(AllocPolicy = AllocPolicy()) |
|
danderson@0
|
46 |
: data_(NULL), |
|
danderson@0
|
47 |
nitems_(0), |
|
danderson@0
|
48 |
maxsize_(0) |
|
danderson@0
|
49 |
{ |
|
danderson@0
|
50 |
} |
|
danderson@0
|
51 |
|
|
danderson@0
|
52 |
~Vector() { |
|
danderson@0
|
53 |
zap(); |
|
danderson@0
|
54 |
} |
|
danderson@0
|
55 |
|
|
danderson@0
|
56 |
void steal(Vector &other) { |
|
danderson@0
|
57 |
zap(); |
|
danderson@0
|
58 |
data_ = other.data_; |
|
danderson@0
|
59 |
nitems_ = other.nitems_; |
|
danderson@0
|
60 |
maxsize_ = other.maxsize_; |
|
danderson@0
|
61 |
other.reset(); |
|
danderson@0
|
62 |
} |
|
danderson@0
|
63 |
|
|
dvander@6
|
64 |
bool append(const T &item) { |
|
danderson@0
|
65 |
if (!growIfNeeded(1)) |
|
danderson@0
|
66 |
return false; |
|
danderson@0
|
67 |
new (&data_[nitems_]) T(item); |
|
danderson@0
|
68 |
nitems_++; |
|
danderson@0
|
69 |
return true; |
|
danderson@0
|
70 |
} |
|
danderson@0
|
71 |
void infallibleAppend(const T &item) { |
|
danderson@0
|
72 |
assert(growIfNeeded(1)); |
|
danderson@0
|
73 |
new (&data_[nitems_]) T(item); |
|
danderson@0
|
74 |
nitems_++; |
|
danderson@0
|
75 |
} |
|
danderson@0
|
76 |
T popCopy() { |
|
danderson@0
|
77 |
T t = at(length() - 1); |
|
danderson@0
|
78 |
pop(); |
|
danderson@0
|
79 |
return t; |
|
danderson@0
|
80 |
} |
|
danderson@0
|
81 |
void pop() { |
|
danderson@0
|
82 |
assert(nitems_); |
|
danderson@0
|
83 |
data_[nitems_ - 1].~T(); |
|
danderson@0
|
84 |
nitems_--; |
|
danderson@0
|
85 |
} |
|
danderson@0
|
86 |
bool empty() const { |
|
danderson@0
|
87 |
return length() == 0; |
|
danderson@0
|
88 |
} |
|
danderson@0
|
89 |
size_t length() const { |
|
danderson@0
|
90 |
return nitems_; |
|
danderson@0
|
91 |
} |
|
danderson@0
|
92 |
T& at(size_t i) { |
|
danderson@0
|
93 |
assert(i < length()); |
|
danderson@0
|
94 |
return data_[i]; |
|
danderson@0
|
95 |
} |
|
danderson@0
|
96 |
const T& at(size_t i) const { |
|
danderson@0
|
97 |
assert(i < length()); |
|
danderson@0
|
98 |
return data_[i]; |
|
danderson@0
|
99 |
} |
|
danderson@0
|
100 |
T& operator [](size_t i) { |
|
danderson@0
|
101 |
return at(i); |
|
danderson@0
|
102 |
} |
|
danderson@0
|
103 |
const T& operator [](size_t i) const { |
|
danderson@0
|
104 |
return at(i); |
|
danderson@0
|
105 |
} |
|
danderson@0
|
106 |
void clear() { |
|
danderson@0
|
107 |
nitems_ = 0; |
|
danderson@0
|
108 |
} |
|
danderson@0
|
109 |
const T &back() const { |
|
danderson@0
|
110 |
return at(length() - 1); |
|
danderson@0
|
111 |
} |
|
danderson@0
|
112 |
T &back() { |
|
danderson@0
|
113 |
return at(length() - 1); |
|
danderson@0
|
114 |
} |
|
danderson@0
|
115 |
|
|
danderson@0
|
116 |
T *buffer() const { |
|
danderson@0
|
117 |
return data_; |
|
danderson@0
|
118 |
} |
|
danderson@0
|
119 |
|
|
danderson@0
|
120 |
bool ensure(size_t desired) { |
|
danderson@0
|
121 |
if (desired <= length()) |
|
danderson@0
|
122 |
return true; |
|
danderson@0
|
123 |
|
|
danderson@0
|
124 |
return growIfNeeded(desired - length()); |
|
danderson@0
|
125 |
} |
|
danderson@0
|
126 |
|
|
danderson@0
|
127 |
private: |
|
danderson@0
|
128 |
// These are disallowed because they basically violate the failure handling |
|
danderson@0
|
129 |
// model for AllocPolicies and are also likely to have abysmal performance. |
|
danderson@0
|
130 |
Vector(const Vector<T> &other) KE_DELETE; |
|
danderson@0
|
131 |
Vector &operator =(const Vector<T> &other) KE_DELETE; |
|
danderson@0
|
132 |
|
|
danderson@0
|
133 |
private: |
|
danderson@0
|
134 |
void zap() { |
|
danderson@0
|
135 |
for (size_t i = 0; i < nitems_; i++) |
|
danderson@0
|
136 |
data_[i].~T(); |
|
danderson@0
|
137 |
this->free(data_); |
|
danderson@0
|
138 |
} |
|
danderson@0
|
139 |
void reset() { |
|
danderson@0
|
140 |
data_ = NULL; |
|
danderson@0
|
141 |
nitems_ = 0; |
|
danderson@0
|
142 |
maxsize_ = 0; |
|
danderson@0
|
143 |
} |
|
danderson@0
|
144 |
|
|
danderson@0
|
145 |
bool growIfNeeded(size_t needed) |
|
danderson@0
|
146 |
{ |
|
danderson@0
|
147 |
if (!IsUintPtrAddSafe(nitems_, needed)) { |
|
danderson@0
|
148 |
this->reportAllocationOverflow(); |
|
danderson@0
|
149 |
return false; |
|
danderson@0
|
150 |
} |
|
danderson@0
|
151 |
if (nitems_ + needed < maxsize_) |
|
danderson@0
|
152 |
return true; |
|
danderson@0
|
153 |
|
|
danderson@0
|
154 |
size_t new_maxsize = maxsize_ ? maxsize_ : 8; |
|
danderson@0
|
155 |
while (nitems_ + needed > new_maxsize) { |
|
danderson@0
|
156 |
if (!IsUintPtrMultiplySafe(new_maxsize, 2)) { |
|
danderson@0
|
157 |
this->reportAllocationOverflow(); |
|
danderson@0
|
158 |
return false; |
|
danderson@0
|
159 |
} |
|
danderson@0
|
160 |
new_maxsize *= 2; |
|
danderson@0
|
161 |
} |
|
danderson@0
|
162 |
|
|
danderson@0
|
163 |
T* newdata = (T*)this->malloc(sizeof(T) * new_maxsize); |
|
danderson@0
|
164 |
if (newdata == NULL) |
|
danderson@0
|
165 |
return false; |
|
danderson@0
|
166 |
for (size_t i = 0; i < nitems_; i++) { |
|
dvander@10
|
167 |
new (&newdata[i]) T(Moveable<T>(data_[i])); |
|
danderson@0
|
168 |
data_[i].~T(); |
|
danderson@0
|
169 |
} |
|
danderson@0
|
170 |
this->free(data_); |
|
danderson@0
|
171 |
|
|
danderson@0
|
172 |
data_ = newdata; |
|
danderson@0
|
173 |
maxsize_ = new_maxsize; |
|
danderson@0
|
174 |
return true; |
|
danderson@0
|
175 |
} |
|
danderson@0
|
176 |
|
|
danderson@0
|
177 |
private: |
|
danderson@0
|
178 |
T* data_; |
|
danderson@0
|
179 |
size_t nitems_; |
|
danderson@0
|
180 |
size_t maxsize_; |
|
danderson@0
|
181 |
}; |
|
danderson@0
|
182 |
|
|
danderson@0
|
183 |
} |
|
danderson@0
|
184 |
|
|
danderson@0
|
185 |
#endif /* _INCLUDE_KEIMA_TPL_CPP_VECTOR_H_ */ |
|
danderson@0
|
186 |
|