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 = true;
212 while (success && mSize < newSize) {
213 success = emplace_back();
214 }
215
216 return success;
217 }
218
219 template <typename ElementType>
insert(size_type index,const ElementType & element)220 bool DynamicVector<ElementType>::insert(size_type index,
221 const ElementType &element) {
222 bool inserted = prepareInsert(index);
223 if (inserted) {
224 new (&data()[index]) ElementType(element);
225 }
226 return inserted;
227 }
228
229 template <typename ElementType>
insert(size_type index,ElementType && element)230 bool DynamicVector<ElementType>::insert(size_type index,
231 ElementType &&element) {
232 bool inserted = prepareInsert(index);
233 if (inserted) {
234 new (&data()[index]) ElementType(std::move(element));
235 }
236 return inserted;
237 }
238
239 template <typename ElementType>
prepareInsert(size_type index)240 bool DynamicVector<ElementType>::prepareInsert(size_type index) {
241 // Insertions are not allowed to create a sparse array.
242 CHRE_ASSERT(index <= mSize);
243
244 // TODO: this can be optimized in the case where we need to grow the vector to
245 // do the shift when transferring the values from the old array to the new.
246 bool readyForInsert = (index <= mSize && prepareForPush());
247 if (readyForInsert) {
248 // If we aren't simply appending the new object, create an opening where
249 // we'll insert it
250 if (index < mSize) {
251 // Make a duplicate of the last item in the slot where we're growing
252 uninitializedMoveOrCopy(&data()[mSize - 1], 1, &data()[mSize]);
253 // Shift all elements starting at index towards the end
254 for (size_type i = mSize - 1; i > index; i--) {
255 moveOrCopyAssign(data()[i], data()[i - 1]);
256 }
257
258 data()[index].~ElementType();
259 }
260
261 mSize++;
262 }
263
264 return readyForInsert;
265 }
266
267 template <typename ElementType>
erase(size_type index)268 void DynamicVector<ElementType>::erase(size_type index) {
269 CHRE_ASSERT(index < mSize);
270 doErase(index, typename std::is_trivial<ElementType>::type());
271 }
272
273 template <typename ElementType>
doErase(size_type index,std::true_type)274 void DynamicVector<ElementType>::doErase(size_type index, std::true_type) {
275 DynamicVectorBase::doErase(index, sizeof(ElementType));
276 }
277
278 template <typename ElementType>
doErase(size_type index,std::false_type)279 void DynamicVector<ElementType>::doErase(size_type index, std::false_type) {
280 mSize--;
281 for (size_type i = index; i < mSize; i++) {
282 moveOrCopyAssign(data()[i], data()[i + 1]);
283 }
284
285 data()[mSize].~ElementType();
286 }
287
288 template <typename ElementType>
find(const ElementType & element)289 typename DynamicVector<ElementType>::size_type DynamicVector<ElementType>::find(
290 const ElementType &element) const {
291 // TODO: Consider adding iterator support and making this a free function.
292 size_type i;
293 for (i = 0; i < size(); i++) {
294 if (data()[i] == element) {
295 break;
296 }
297 }
298
299 return i;
300 }
301
302 template <typename ElementType>
swap(size_type index0,size_type index1)303 void DynamicVector<ElementType>::swap(size_type index0, size_type index1) {
304 CHRE_ASSERT(index0 < mSize && index1 < mSize);
305 if (index0 != index1) {
306 typename std::aligned_storage<sizeof(ElementType),
307 alignof(ElementType)>::type tempStorage;
308 ElementType &temp = *reinterpret_cast<ElementType *>(&tempStorage);
309 uninitializedMoveOrCopy(&data()[index0], 1, &temp);
310 moveOrCopyAssign(data()[index0], data()[index1]);
311 moveOrCopyAssign(data()[index1], temp);
312 }
313 }
314
315 template <typename ElementType>
front()316 ElementType &DynamicVector<ElementType>::front() {
317 CHRE_ASSERT(mSize > 0);
318 return data()[0];
319 }
320
321 template <typename ElementType>
front()322 const ElementType &DynamicVector<ElementType>::front() const {
323 CHRE_ASSERT(mSize > 0);
324 return data()[0];
325 }
326
327 template <typename ElementType>
back()328 ElementType &DynamicVector<ElementType>::back() {
329 CHRE_ASSERT(mSize > 0);
330 return data()[mSize - 1];
331 }
332
333 template <typename ElementType>
back()334 const ElementType &DynamicVector<ElementType>::back() const {
335 CHRE_ASSERT(mSize > 0);
336 return data()[mSize - 1];
337 }
338
339 template <typename ElementType>
prepareForPush()340 bool DynamicVector<ElementType>::prepareForPush() {
341 return doPrepareForPush(typename std::is_trivial<ElementType>::type());
342 }
343
344 template <typename ElementType>
doPrepareForPush(std::true_type)345 bool DynamicVector<ElementType>::doPrepareForPush(std::true_type) {
346 return DynamicVectorBase::doPrepareForPush(sizeof(ElementType));
347 }
348
349 template <typename ElementType>
doPrepareForPush(std::false_type)350 bool DynamicVector<ElementType>::doPrepareForPush(std::false_type) {
351 return reserve(getNextGrowthCapacity());
352 }
353
354 template <typename ElementType>
355 typename DynamicVector<ElementType>::iterator
begin()356 DynamicVector<ElementType>::begin() {
357 return data();
358 }
359
360 template <typename ElementType>
361 typename DynamicVector<ElementType>::iterator
end()362 DynamicVector<ElementType>::end() {
363 return (data() + mSize);
364 }
365
366 template <typename ElementType>
367 typename DynamicVector<ElementType>::const_iterator
begin()368 DynamicVector<ElementType>::begin() const {
369 return cbegin();
370 }
371
372 template <typename ElementType>
373 typename DynamicVector<ElementType>::const_iterator
end()374 DynamicVector<ElementType>::end() const {
375 return cend();
376 }
377
378 template <typename ElementType>
379 typename DynamicVector<ElementType>::const_iterator
cbegin()380 DynamicVector<ElementType>::cbegin() const {
381 return data();
382 }
383
384 template <typename ElementType>
385 typename DynamicVector<ElementType>::const_iterator
cend()386 DynamicVector<ElementType>::cend() const {
387 return (data() + mSize);
388 }
389
390 } // namespace chre
391
392 #endif // CHRE_UTIL_DYNAMIC_VECTOR_IMPL_H_
393