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 : mData(other.mData),
37 mSize(other.mSize),
38 mCapacity(other.mCapacity),
39 mDataIsWrapped(other.mDataIsWrapped) {
40 other.mData = nullptr;
41 other.mSize = 0;
42 other.mCapacity = 0;
43 other.mDataIsWrapped = false;
44 }
45
46 template<typename ElementType>
~DynamicVector()47 DynamicVector<ElementType>::~DynamicVector() {
48 if (owns_data()) {
49 clear();
50 memoryFree(mData);
51 }
52 }
53
54 template<typename ElementType>
55 DynamicVector<ElementType>& DynamicVector<ElementType>::operator=(
56 DynamicVector<ElementType>&& other) {
57 if (this == &other) {
58 return *this;
59 }
60 this->~DynamicVector();
61
62 mData = other.mData;
63 mSize = other.mSize;
64 mCapacity = other.mCapacity;
65 mDataIsWrapped = other.mDataIsWrapped;
66
67 other.mData = nullptr;
68 other.mSize = 0;
69 other.mCapacity = 0;
70 other.mDataIsWrapped = false;
71 return *this;
72 }
73
74 template <typename ElementType>
clear()75 void DynamicVector<ElementType>::clear() {
76 destroy(mData, mSize);
77 mSize = 0;
78 }
79
80 template<typename ElementType>
data()81 ElementType *DynamicVector<ElementType>::data() {
82 return mData;
83 }
84
85 template<typename ElementType>
data()86 const ElementType *DynamicVector<ElementType>::data() const {
87 return mData;
88 }
89
90 template<typename ElementType>
91 typename DynamicVector<ElementType>::size_type
size()92 DynamicVector<ElementType>::size() const {
93 return mSize;
94 }
95
96 template<typename ElementType>
97 typename DynamicVector<ElementType>::size_type
capacity()98 DynamicVector<ElementType>::capacity() const {
99 return mCapacity;
100 }
101
102 template<typename ElementType>
empty()103 bool DynamicVector<ElementType>::empty() const {
104 return (mSize == 0);
105 }
106
107 template<typename ElementType>
pop_back()108 void DynamicVector<ElementType>::pop_back() {
109 CHRE_ASSERT(!empty());
110 erase(mSize - 1);
111 }
112
113 template<typename ElementType>
push_back(const ElementType & element)114 bool DynamicVector<ElementType>::push_back(const ElementType& element) {
115 bool spaceAvailable = prepareForPush();
116 if (spaceAvailable) {
117 new (&mData[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 (&mData[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[](size_type index)
152 const {
153 CHRE_ASSERT(index < mSize);
154 return data()[index];
155 }
156
157 template<typename ElementType>
158 bool DynamicVector<ElementType>::operator==(const DynamicVector<ElementType>& other)
159 const {
160 bool vectorsAreEqual = (mSize == other.mSize);
161 if (vectorsAreEqual) {
162 for (size_type i = 0; i < mSize; i++) {
163 if (!(mData[i] == other.mData[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 bool success = false;
176
177 CHRE_ASSERT(owns_data());
178 if (newCapacity <= mCapacity) {
179 success = true;
180 } else if (owns_data()) {
181 ElementType *newData = static_cast<ElementType *>(
182 memoryAlloc(newCapacity * sizeof(ElementType)));
183 if (newData != nullptr) {
184 uninitializedMoveOrCopy(mData, mSize, newData);
185 destroy(mData, mSize);
186 memoryFree(mData);
187 mData = newData;
188 mCapacity = newCapacity;
189 success = true;
190 }
191 }
192
193 return success;
194 }
195
196 template<typename ElementType>
resize(size_type newSize)197 bool DynamicVector<ElementType>::resize(size_type newSize) {
198 // Remove elements from the back to minimize move operations.
199 while (mSize > newSize) {
200 pop_back();
201 }
202
203 bool success = true;
204 while (success && mSize < newSize) {
205 success = emplace_back();
206 }
207
208 return success;
209 }
210
211 template<typename ElementType>
insert(size_type index,const ElementType & element)212 bool DynamicVector<ElementType>::insert(size_type index,
213 const ElementType& element) {
214 bool inserted = prepareInsert(index);
215 if (inserted) {
216 new (&mData[index]) ElementType(element);
217 }
218 return inserted;
219 }
220
221 template<typename ElementType>
insert(size_type index,ElementType && element)222 bool DynamicVector<ElementType>::insert(size_type index, ElementType&& element) {
223 bool inserted = prepareInsert(index);
224 if (inserted) {
225 new (&mData[index]) ElementType(std::move(element));
226 }
227 return inserted;
228 }
229
230 template<typename ElementType>
prepareInsert(size_type index)231 bool DynamicVector<ElementType>::prepareInsert(size_type index) {
232 // Insertions are not allowed to create a sparse array.
233 CHRE_ASSERT(index <= mSize);
234
235 // TODO: this can be optimized in the case where we need to grow the vector to
236 // do the shift when transferring the values from the old array to the new.
237 bool readyForInsert = (index <= mSize && prepareForPush());
238 if (readyForInsert) {
239 // If we aren't simply appending the new object, create an opening where
240 // we'll insert it
241 if (index < mSize) {
242 // Make a duplicate of the last item in the slot where we're growing
243 uninitializedMoveOrCopy(&mData[mSize - 1], 1, &mData[mSize]);
244 // Shift all elements starting at index towards the end
245 for (size_type i = mSize - 1; i > index; i--) {
246 moveOrCopyAssign(mData[i], mData[i - 1]);
247 }
248
249 mData[index].~ElementType();
250 }
251
252 mSize++;
253 }
254
255 return readyForInsert;
256 }
257
258 template<typename ElementType>
copy_array(const ElementType * array,size_type elementCount)259 bool DynamicVector<ElementType>::copy_array(const ElementType *array,
260 size_type elementCount) {
261 CHRE_ASSERT(owns_data());
262
263 bool success = false;
264 if (owns_data() && reserve(elementCount)) {
265 clear();
266 std::copy(array, array + elementCount, mData);
267 mSize = elementCount;
268 success = true;
269 }
270
271 return success;
272 }
273
274 template<typename ElementType>
erase(size_type index)275 void DynamicVector<ElementType>::erase(size_type index) {
276 CHRE_ASSERT(index < mSize);
277 mSize--;
278 for (size_type i = index; i < mSize; i++) {
279 moveOrCopyAssign(mData[i], mData[i + 1]);
280 }
281
282 mData[mSize].~ElementType();
283 }
284
285 template<typename ElementType>
286 typename DynamicVector<ElementType>::size_type
find(const ElementType & element)287 DynamicVector<ElementType>::find(const ElementType& element) const {
288 // TODO: Consider adding iterator support and making this a free function.
289 size_type i;
290 for (i = 0; i < size(); i++) {
291 if (mData[i] == element) {
292 break;
293 }
294 }
295
296 return i;
297 }
298
299 template<typename ElementType>
swap(size_type index0,size_type index1)300 void DynamicVector<ElementType>::swap(size_type index0, size_type index1) {
301 CHRE_ASSERT(index0 < mSize && index1 < mSize);
302 if (index0 != index1) {
303 typename std::aligned_storage<sizeof(ElementType),
304 alignof(ElementType)>::type tempStorage;
305 ElementType& temp = *reinterpret_cast<ElementType *>(&tempStorage);
306 uninitializedMoveOrCopy(&mData[index0], 1, &temp);
307 moveOrCopyAssign(mData[index0], mData[index1]);
308 moveOrCopyAssign(mData[index1], temp);
309 }
310 }
311
312 template<typename ElementType>
wrap(ElementType * array,size_type elementCount)313 void DynamicVector<ElementType>::wrap(ElementType *array, size_type elementCount) {
314 // If array is nullptr, elementCount must also be 0
315 CHRE_ASSERT(array != nullptr || elementCount == 0);
316 this->~DynamicVector();
317
318 mData = array;
319 mSize = elementCount;
320 mCapacity = mSize;
321 mDataIsWrapped = true;
322 }
323
324 template<typename ElementType>
unwrap()325 void DynamicVector<ElementType>::unwrap() {
326 if (mDataIsWrapped) {
327 mData = nullptr;
328 mSize = 0;
329 mCapacity = 0;
330 mDataIsWrapped = false;
331 }
332 }
333
334 template<typename ElementType>
owns_data()335 bool DynamicVector<ElementType>::owns_data() const {
336 return !mDataIsWrapped;
337 }
338
339 template<typename ElementType>
front()340 ElementType& DynamicVector<ElementType>::front() {
341 CHRE_ASSERT(mSize > 0);
342 return mData[0];
343 }
344
345 template<typename ElementType>
front()346 const ElementType& DynamicVector<ElementType>::front() const {
347 CHRE_ASSERT(mSize > 0);
348 return mData[0];
349 }
350
351 template<typename ElementType>
back()352 ElementType& DynamicVector<ElementType>::back() {
353 CHRE_ASSERT(mSize > 0);
354 return mData[mSize - 1];
355 }
356
357 template<typename ElementType>
back()358 const ElementType& DynamicVector<ElementType>::back() const {
359 CHRE_ASSERT(mSize > 0);
360 return mData[mSize - 1];
361 }
362
363 template<typename ElementType>
prepareForPush()364 bool DynamicVector<ElementType>::prepareForPush() {
365 bool spaceAvailable = true;
366 if (mSize == mCapacity) {
367 size_type newCapacity = mCapacity * 2;
368 if (newCapacity == 0) {
369 newCapacity = 1;
370 }
371
372 if (!reserve(newCapacity)) {
373 spaceAvailable = false;
374 }
375 }
376
377 return spaceAvailable;
378 }
379
380 template<typename ElementType>
381 typename DynamicVector<ElementType>::iterator
begin()382 DynamicVector<ElementType>::begin() {
383 return mData;
384 }
385
386 template<typename ElementType>
387 typename DynamicVector<ElementType>::iterator
end()388 DynamicVector<ElementType>::end() {
389 return (mData + mSize);
390 }
391
392 template<typename ElementType>
393 typename DynamicVector<ElementType>::const_iterator
begin()394 DynamicVector<ElementType>::begin() const {
395 return cbegin();
396 }
397
398 template<typename ElementType>
399 typename DynamicVector<ElementType>::const_iterator
end()400 DynamicVector<ElementType>::end() const {
401 return cend();
402 }
403
404 template<typename ElementType>
405 typename DynamicVector<ElementType>::const_iterator
cbegin()406 DynamicVector<ElementType>::cbegin() const {
407 return mData;
408 }
409
410 template<typename ElementType>
411 typename DynamicVector<ElementType>::const_iterator
cend()412 DynamicVector<ElementType>::cend() const {
413 return (mData + mSize);
414 }
415
416 } // namespace chre
417
418 #endif // CHRE_UTIL_DYNAMIC_VECTOR_IMPL_H_
419