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