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 <memory>
21 #include <new>
22 #include <utility>
23
24 #include "chre/platform/assert.h"
25 #include "chre/platform/memory.h"
26 #include "chre/util/memory.h"
27
28 namespace chre {
29
30 template<typename ElementType>
DynamicVector()31 DynamicVector<ElementType>::DynamicVector() {}
32
33 template<typename ElementType>
DynamicVector(DynamicVector<ElementType> && other)34 DynamicVector<ElementType>::DynamicVector(DynamicVector<ElementType>&& other)
35 : mData(other.mData),
36 mSize(other.mSize),
37 mCapacity(other.mCapacity),
38 mDataIsWrapped(other.mDataIsWrapped) {
39 other.mData = nullptr;
40 other.mSize = 0;
41 other.mCapacity = 0;
42 other.mDataIsWrapped = false;
43 }
44
45 template<typename ElementType>
~DynamicVector()46 DynamicVector<ElementType>::~DynamicVector() {
47 if (owns_data()) {
48 clear();
49 memoryFree(mData);
50 }
51 }
52
53 template <typename ElementType>
clear()54 void DynamicVector<ElementType>::clear() {
55 destroy(mData, mSize);
56 mSize = 0;
57 }
58
59 template<typename ElementType>
data()60 ElementType *DynamicVector<ElementType>::data() {
61 return mData;
62 }
63
64 template<typename ElementType>
data()65 const ElementType *DynamicVector<ElementType>::data() const {
66 return mData;
67 }
68
69 template<typename ElementType>
size()70 size_t DynamicVector<ElementType>::size() const {
71 return mSize;
72 }
73
74 template<typename ElementType>
capacity()75 size_t DynamicVector<ElementType>::capacity() const {
76 return mCapacity;
77 }
78
79 template<typename ElementType>
empty()80 bool DynamicVector<ElementType>::empty() const {
81 return (mSize == 0);
82 }
83
84 template<typename ElementType>
push_back(const ElementType & element)85 bool DynamicVector<ElementType>::push_back(const ElementType& element) {
86 bool spaceAvailable = prepareForPush();
87 if (spaceAvailable) {
88 new (&mData[mSize++]) ElementType(element);
89 }
90
91 return spaceAvailable;
92 }
93
94 template<typename ElementType>
push_back(ElementType && element)95 bool DynamicVector<ElementType>::push_back(ElementType&& element) {
96 bool spaceAvailable = prepareForPush();
97 if (spaceAvailable) {
98 new (&mData[mSize++]) ElementType(std::move(element));
99 }
100
101 return spaceAvailable;
102 }
103
104 template<typename ElementType>
105 template<typename... Args>
emplace_back(Args &&...args)106 bool DynamicVector<ElementType>::emplace_back(Args&&... args) {
107 bool spaceAvailable = prepareForPush();
108 if (spaceAvailable) {
109 new (&data()[mSize++]) ElementType(std::forward<Args>(args)...);
110 }
111
112 return spaceAvailable;
113 }
114
115 template<typename ElementType>
116 ElementType& DynamicVector<ElementType>::operator[](size_t index) {
117 CHRE_ASSERT(index < mSize);
118 if (index >= mSize) {
119 index = mSize - 1;
120 }
121
122 return data()[index];
123 }
124
125 template<typename ElementType>
126 const ElementType& DynamicVector<ElementType>::operator[](size_t index) const {
127 CHRE_ASSERT(index < mSize);
128 if (index >= mSize) {
129 index = mSize - 1;
130 }
131
132 return data()[index];
133 }
134
135 template<typename ElementType>
reserve(size_t newCapacity)136 bool DynamicVector<ElementType>::reserve(size_t newCapacity) {
137 bool success = false;
138
139 CHRE_ASSERT_LOG(owns_data(), "Wrapped buffers can't be resized");
140 if (newCapacity <= mCapacity) {
141 success = true;
142 } else if (owns_data()) {
143 ElementType *newData = static_cast<ElementType *>(
144 memoryAlloc(newCapacity * sizeof(ElementType)));
145 if (newData != nullptr) {
146 uninitializedMoveOrCopy(mData, mSize, newData);
147 destroy(mData, mSize);
148 memoryFree(mData);
149 mData = newData;
150 mCapacity = newCapacity;
151 success = true;
152 }
153 }
154
155 return success;
156 }
157
158 template<typename ElementType>
insert(size_t index,const ElementType & element)159 bool DynamicVector<ElementType>::insert(size_t index,
160 const ElementType& element) {
161 bool inserted = prepareInsert(index);
162 if (inserted) {
163 new (&mData[index]) ElementType(element);
164 }
165 return inserted;
166 }
167
168 template<typename ElementType>
insert(size_t index,ElementType && element)169 bool DynamicVector<ElementType>::insert(size_t index, ElementType&& element) {
170 bool inserted = prepareInsert(index);
171 if (inserted) {
172 new (&mData[index]) ElementType(std::move(element));
173 }
174 return inserted;
175 }
176
177 template<typename ElementType>
prepareInsert(size_t index)178 bool DynamicVector<ElementType>::prepareInsert(size_t index) {
179 // Insertions are not allowed to create a sparse array.
180 CHRE_ASSERT(index <= mSize);
181
182 // TODO: this can be optimized in the case where we need to grow the vector to
183 // do the shift when transferring the values from the old array to the new.
184 bool readyForInsert = (index <= mSize && prepareForPush());
185 if (readyForInsert) {
186 // If we aren't simply appending the new object, create an opening where
187 // we'll insert it
188 if (index < mSize) {
189 // Make a duplicate of the last item in the slot where we're growing
190 uninitializedMoveOrCopy(&mData[mSize - 1], 1, &mData[mSize]);
191 // Shift all elements starting at index towards the end
192 for (size_t i = mSize - 1; i > index; i--) {
193 moveOrCopyAssign(mData[i], mData[i - 1]);
194 }
195
196 mData[index].~ElementType();
197 }
198
199 mSize++;
200 }
201
202 return readyForInsert;
203 }
204
205 template<typename ElementType>
copy_array(const ElementType * array,size_t elementCount)206 bool DynamicVector<ElementType>::copy_array(const ElementType *array,
207 size_t elementCount) {
208 CHRE_ASSERT(owns_data());
209
210 bool success = false;
211 if (owns_data() && reserve(elementCount)) {
212 clear();
213 std::copy(array, array + elementCount, mData);
214 mSize = elementCount;
215 success = true;
216 }
217
218 return success;
219 }
220
221 template<typename ElementType>
erase(size_t index)222 void DynamicVector<ElementType>::erase(size_t index) {
223 CHRE_ASSERT(index < mSize);
224 if (index < mSize) {
225 mSize--;
226 for (size_t i = index; i < mSize; i++) {
227 moveOrCopyAssign(mData[i], mData[i + 1]);
228 }
229
230 mData[mSize].~ElementType();
231 }
232 }
233
234 template<typename ElementType>
find(const ElementType & element)235 size_t DynamicVector<ElementType>::find(const ElementType& element) const {
236 // TODO: Consider adding iterator support and making this a free function.
237 size_t i;
238 for (i = 0; i < size(); i++) {
239 if (mData[i] == element) {
240 break;
241 }
242 }
243
244 return i;
245 }
246
247 template<typename ElementType>
swap(size_t index0,size_t index1)248 void DynamicVector<ElementType>::swap(size_t index0, size_t index1) {
249 CHRE_ASSERT(index0 < mSize && index1 < mSize);
250 if (index0 < mSize && index1 < mSize && index0 != index1) {
251 typename std::aligned_storage<sizeof(ElementType),
252 alignof(ElementType)>::type tempStorage;
253 ElementType& temp = *reinterpret_cast<ElementType *>(&tempStorage);
254 uninitializedMoveOrCopy(&mData[index0], 1, &temp);
255 moveOrCopyAssign(mData[index0], mData[index1]);
256 moveOrCopyAssign(mData[index1], temp);
257 }
258 }
259
260 template<typename ElementType>
wrap(ElementType * array,size_t elementCount)261 void DynamicVector<ElementType>::wrap(ElementType *array, size_t elementCount) {
262 // If array is nullptr, elementCount must also be 0
263 CHRE_ASSERT(array != nullptr || elementCount == 0);
264 this->~DynamicVector();
265
266 mData = array;
267 mSize = elementCount;
268 mCapacity = mSize;
269 mDataIsWrapped = true;
270 }
271
272 template<typename ElementType>
unwrap()273 void DynamicVector<ElementType>::unwrap() {
274 if (mDataIsWrapped) {
275 mData = nullptr;
276 mSize = 0;
277 mCapacity = 0;
278 mDataIsWrapped = false;
279 }
280 }
281
282 template<typename ElementType>
owns_data()283 bool DynamicVector<ElementType>::owns_data() const {
284 return !mDataIsWrapped;
285 }
286
287 template<typename ElementType>
front()288 ElementType& DynamicVector<ElementType>::front() {
289 CHRE_ASSERT(mSize > 0);
290 return mData[0];
291 }
292
293 template<typename ElementType>
front()294 const ElementType& DynamicVector<ElementType>::front() const {
295 CHRE_ASSERT(mSize > 0);
296 return mData[0];
297 }
298
299 template<typename ElementType>
back()300 ElementType& DynamicVector<ElementType>::back() {
301 CHRE_ASSERT(mSize > 0);
302 return mData[mSize - 1];
303 }
304
305 template<typename ElementType>
back()306 const ElementType& DynamicVector<ElementType>::back() const {
307 CHRE_ASSERT(mSize > 0);
308 return mData[mSize - 1];
309 }
310
311 template<typename ElementType>
prepareForPush()312 bool DynamicVector<ElementType>::prepareForPush() {
313 bool spaceAvailable = true;
314 if (mSize == mCapacity) {
315 size_t newCapacity = mCapacity * 2;
316 if (newCapacity == 0) {
317 newCapacity = 1;
318 }
319
320 if (!reserve(newCapacity)) {
321 spaceAvailable = false;
322 }
323 }
324
325 return spaceAvailable;
326 }
327
328 template<typename ElementType>
329 typename DynamicVector<ElementType>::iterator
begin()330 DynamicVector<ElementType>::begin() {
331 return mData;
332 }
333
334 template<typename ElementType>
335 typename DynamicVector<ElementType>::iterator
end()336 DynamicVector<ElementType>::end() {
337 return (mData + mSize);
338 }
339
340 template<typename ElementType>
341 typename DynamicVector<ElementType>::const_iterator
begin()342 DynamicVector<ElementType>::begin() const {
343 return cbegin();
344 }
345
346 template<typename ElementType>
347 typename DynamicVector<ElementType>::const_iterator
end()348 DynamicVector<ElementType>::end() const {
349 return cend();
350 }
351
352 template<typename ElementType>
353 typename DynamicVector<ElementType>::const_iterator
cbegin()354 DynamicVector<ElementType>::cbegin() const {
355 return mData;
356 }
357
358 template<typename ElementType>
359 typename DynamicVector<ElementType>::const_iterator
cend()360 DynamicVector<ElementType>::cend() const {
361 return (mData + mSize);
362 }
363
364 } // namespace chre
365
366 #endif // CHRE_UTIL_DYNAMIC_VECTOR_IMPL_H_
367