1 /*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef CHRE_UTIL_DYNAMIC_VECTOR_IMPL_H_
18 #define CHRE_UTIL_DYNAMIC_VECTOR_IMPL_H_
19
20 #include "chre/util/dynamic_vector.h"
21
22 #include <memory>
23 #include <new>
24 #include <utility>
25
26 #include "chre/util/container_support.h"
27 #include "chre/util/memory.h"
28
29 namespace chre {
30
31 template <typename ElementType>
DynamicVector()32 DynamicVector<ElementType>::DynamicVector() {}
33
34 template <typename ElementType>
DynamicVector(DynamicVector<ElementType> && other)35 DynamicVector<ElementType>::DynamicVector(DynamicVector<ElementType> &&other)
36 : DynamicVectorBase(std::move(other)) {}
37
38 template <typename ElementType>
~DynamicVector()39 DynamicVector<ElementType>::~DynamicVector() {
40 clear();
41 memoryFree(data());
42 }
43
44 template <typename ElementType>
45 DynamicVector<ElementType> &DynamicVector<ElementType>::operator=(
46 DynamicVector<ElementType> &&other) {
47 if (this != &other) {
48 this->~DynamicVector();
49 mData = other.mData;
50 mSize = other.mSize;
51 mCapacity = other.mCapacity;
52
53 other.mData = nullptr;
54 other.mSize = 0;
55 other.mCapacity = 0;
56 }
57
58 return *this;
59 }
60
61 template <typename ElementType>
clear()62 void DynamicVector<ElementType>::clear() {
63 destroy(data(), mSize);
64 mSize = 0;
65 }
66
67 template <typename ElementType>
data()68 ElementType *DynamicVector<ElementType>::data() {
69 return static_cast<ElementType *>(mData);
70 }
71
72 template <typename ElementType>
data()73 const ElementType *DynamicVector<ElementType>::data() const {
74 return static_cast<const ElementType *>(mData);
75 }
76
77 template <typename ElementType>
78 typename DynamicVector<ElementType>::size_type
size()79 DynamicVector<ElementType>::size() const {
80 return mSize;
81 }
82
83 template <typename ElementType>
84 typename DynamicVector<ElementType>::size_type
capacity()85 DynamicVector<ElementType>::capacity() const {
86 return mCapacity;
87 }
88
89 template <typename ElementType>
empty()90 bool DynamicVector<ElementType>::empty() const {
91 return (mSize == 0);
92 }
93
94 template <typename ElementType>
pop_back()95 void DynamicVector<ElementType>::pop_back() {
96 CHRE_ASSERT(!empty());
97 erase(mSize - 1);
98 }
99
100 template <typename ElementType>
push_back(const ElementType & element)101 bool DynamicVector<ElementType>::push_back(const ElementType &element) {
102 return doPushBack(element, typename std::is_trivial<ElementType>::type());
103 }
104
105 template <typename ElementType>
doPushBack(const ElementType & element,std::true_type)106 bool DynamicVector<ElementType>::doPushBack(const ElementType &element,
107 std::true_type) {
108 return DynamicVectorBase::doPushBack(static_cast<const void *>(&element),
109 sizeof(ElementType));
110 }
111
112 template <typename ElementType>
doPushBack(const ElementType & element,std::false_type)113 bool DynamicVector<ElementType>::doPushBack(const ElementType &element,
114 std::false_type) {
115 bool spaceAvailable = prepareForPush();
116 if (spaceAvailable) {
117 new (&data()[mSize++]) ElementType(element);
118 }
119
120 return spaceAvailable;
121 }
122
123 template <typename ElementType>
push_back(ElementType && element)124 bool DynamicVector<ElementType>::push_back(ElementType &&element) {
125 bool spaceAvailable = prepareForPush();
126 if (spaceAvailable) {
127 new (&data()[mSize++]) ElementType(std::move(element));
128 }
129
130 return spaceAvailable;
131 }
132
133 template <typename ElementType>
134 template <typename... Args>
emplace_back(Args &&...args)135 bool DynamicVector<ElementType>::emplace_back(Args &&... args) {
136 bool spaceAvailable = prepareForPush();
137 if (spaceAvailable) {
138 new (&data()[mSize++]) ElementType(std::forward<Args>(args)...);
139 }
140
141 return spaceAvailable;
142 }
143
144 template <typename ElementType>
145 ElementType &DynamicVector<ElementType>::operator[](size_type index) {
146 CHRE_ASSERT(index < mSize);
147 return data()[index];
148 }
149
150 template <typename ElementType>
151 const ElementType &DynamicVector<ElementType>::operator[](
152 size_type index) const {
153 CHRE_ASSERT(index < mSize);
154 return data()[index];
155 }
156
157 template <typename ElementType>
158 bool DynamicVector<ElementType>::operator==(
159 const DynamicVector<ElementType> &other) const {
160 bool vectorsAreEqual = (mSize == other.mSize);
161 if (vectorsAreEqual) {
162 for (size_type i = 0; i < mSize; i++) {
163 if (!(data()[i] == other.data()[i])) {
164 vectorsAreEqual = false;
165 break;
166 }
167 }
168 }
169
170 return vectorsAreEqual;
171 }
172
173 template <typename ElementType>
reserve(size_type newCapacity)174 bool DynamicVector<ElementType>::reserve(size_type newCapacity) {
175 return doReserve(newCapacity, typename std::is_trivial<ElementType>::type());
176 }
177
178 template <typename ElementType>
doReserve(size_type newCapacity,std::true_type)179 bool DynamicVector<ElementType>::doReserve(size_type newCapacity,
180 std::true_type) {
181 return DynamicVectorBase::doReserve(newCapacity, sizeof(ElementType));
182 }
183
184 template <typename ElementType>
doReserve(size_type newCapacity,std::false_type)185 bool DynamicVector<ElementType>::doReserve(size_type newCapacity,
186 std::false_type) {
187 bool success = (newCapacity <= mCapacity);
188 if (!success) {
189 ElementType *newData = static_cast<ElementType *>(
190 memoryAlloc(newCapacity * sizeof(ElementType)));
191 if (newData != nullptr) {
192 uninitializedMoveOrCopy(data(), mSize, newData);
193 destroy(data(), mSize);
194 memoryFree(data());
195 mData = newData;
196 mCapacity = newCapacity;
197 success = true;
198 }
199 }
200
201 return success;
202 }
203
204 template <typename ElementType>
resize(size_type newSize)205 bool DynamicVector<ElementType>::resize(size_type newSize) {
206 // Remove elements from the back to minimize move operations.
207 while (mSize > newSize) {
208 pop_back();
209 }
210
211 bool success = reserve(newSize);
212 if (success) {
213 while (mSize < newSize) {
214 new (&data()[mSize++]) ElementType();
215 }
216 }
217
218 return success;
219 }
220
221 template <typename ElementType>
insert(size_type index,const ElementType & element)222 bool DynamicVector<ElementType>::insert(size_type index,
223 const ElementType &element) {
224 bool inserted = prepareInsert(index);
225 if (inserted) {
226 new (&data()[index]) ElementType(element);
227 }
228 return inserted;
229 }
230
231 template <typename ElementType>
insert(size_type index,ElementType && element)232 bool DynamicVector<ElementType>::insert(size_type index,
233 ElementType &&element) {
234 bool inserted = prepareInsert(index);
235 if (inserted) {
236 new (&data()[index]) ElementType(std::move(element));
237 }
238 return inserted;
239 }
240
241 template <typename ElementType>
prepareInsert(size_type index)242 bool DynamicVector<ElementType>::prepareInsert(size_type index) {
243 // Insertions are not allowed to create a sparse array.
244 CHRE_ASSERT(index <= mSize);
245
246 // TODO: this can be optimized in the case where we need to grow the vector to
247 // do the shift when transferring the values from the old array to the new.
248 bool readyForInsert = (index <= mSize && prepareForPush());
249 if (readyForInsert) {
250 // If we aren't simply appending the new object, create an opening where
251 // we'll insert it
252 if (index < mSize) {
253 // Make a duplicate of the last item in the slot where we're growing
254 uninitializedMoveOrCopy(&data()[mSize - 1], 1, &data()[mSize]);
255 // Shift all elements starting at index towards the end
256 for (size_type i = mSize - 1; i > index; i--) {
257 moveOrCopyAssign(data()[i], data()[i - 1]);
258 }
259
260 data()[index].~ElementType();
261 }
262
263 mSize++;
264 }
265
266 return readyForInsert;
267 }
268
269 template <typename ElementType>
erase(size_type index)270 void DynamicVector<ElementType>::erase(size_type index) {
271 CHRE_ASSERT(index < mSize);
272 doErase(index, typename std::is_trivial<ElementType>::type());
273 }
274
275 template <typename ElementType>
doErase(size_type index,std::true_type)276 void DynamicVector<ElementType>::doErase(size_type index, std::true_type) {
277 DynamicVectorBase::doErase(index, sizeof(ElementType));
278 }
279
280 template <typename ElementType>
doErase(size_type index,std::false_type)281 void DynamicVector<ElementType>::doErase(size_type index, std::false_type) {
282 mSize--;
283 for (size_type i = index; i < mSize; i++) {
284 moveOrCopyAssign(data()[i], data()[i + 1]);
285 }
286
287 data()[mSize].~ElementType();
288 }
289
290 template <typename ElementType>
find(const ElementType & element)291 typename DynamicVector<ElementType>::size_type DynamicVector<ElementType>::find(
292 const ElementType &element) const {
293 // TODO: Consider adding iterator support and making this a free function.
294 size_type i;
295 for (i = 0; i < size(); i++) {
296 if (data()[i] == element) {
297 break;
298 }
299 }
300
301 return i;
302 }
303
304 template <typename ElementType>
swap(size_type index0,size_type index1)305 void DynamicVector<ElementType>::swap(size_type index0, size_type index1) {
306 CHRE_ASSERT(index0 < mSize && index1 < mSize);
307 if (index0 != index1) {
308 typename std::aligned_storage<sizeof(ElementType),
309 alignof(ElementType)>::type tempStorage;
310 ElementType &temp = *reinterpret_cast<ElementType *>(&tempStorage);
311 uninitializedMoveOrCopy(&data()[index0], 1, &temp);
312 moveOrCopyAssign(data()[index0], data()[index1]);
313 moveOrCopyAssign(data()[index1], temp);
314 }
315 }
316
317 template <typename ElementType>
front()318 ElementType &DynamicVector<ElementType>::front() {
319 CHRE_ASSERT(mSize > 0);
320 return data()[0];
321 }
322
323 template <typename ElementType>
front()324 const ElementType &DynamicVector<ElementType>::front() const {
325 CHRE_ASSERT(mSize > 0);
326 return data()[0];
327 }
328
329 template <typename ElementType>
back()330 ElementType &DynamicVector<ElementType>::back() {
331 CHRE_ASSERT(mSize > 0);
332 return data()[mSize - 1];
333 }
334
335 template <typename ElementType>
back()336 const ElementType &DynamicVector<ElementType>::back() const {
337 CHRE_ASSERT(mSize > 0);
338 return data()[mSize - 1];
339 }
340
341 template <typename ElementType>
prepareForPush()342 bool DynamicVector<ElementType>::prepareForPush() {
343 return doPrepareForPush(typename std::is_trivial<ElementType>::type());
344 }
345
346 template <typename ElementType>
doPrepareForPush(std::true_type)347 bool DynamicVector<ElementType>::doPrepareForPush(std::true_type) {
348 return DynamicVectorBase::doPrepareForPush(sizeof(ElementType));
349 }
350
351 template <typename ElementType>
doPrepareForPush(std::false_type)352 bool DynamicVector<ElementType>::doPrepareForPush(std::false_type) {
353 return reserve(getNextGrowthCapacity());
354 }
355
356 template <typename ElementType>
357 typename DynamicVector<ElementType>::iterator
begin()358 DynamicVector<ElementType>::begin() {
359 return data();
360 }
361
362 template <typename ElementType>
363 typename DynamicVector<ElementType>::iterator
end()364 DynamicVector<ElementType>::end() {
365 return (data() + mSize);
366 }
367
368 template <typename ElementType>
369 typename DynamicVector<ElementType>::const_iterator
begin()370 DynamicVector<ElementType>::begin() const {
371 return cbegin();
372 }
373
374 template <typename ElementType>
375 typename DynamicVector<ElementType>::const_iterator
end()376 DynamicVector<ElementType>::end() const {
377 return cend();
378 }
379
380 template <typename ElementType>
381 typename DynamicVector<ElementType>::const_iterator
cbegin()382 DynamicVector<ElementType>::cbegin() const {
383 return data();
384 }
385
386 template <typename ElementType>
387 typename DynamicVector<ElementType>::const_iterator
cend()388 DynamicVector<ElementType>::cend() const {
389 return (data() + mSize);
390 }
391
392 } // namespace chre
393
394 #endif // CHRE_UTIL_DYNAMIC_VECTOR_IMPL_H_
395