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