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