dynamic_vector_impl.h revision 1a16de2440b92ac60a94029589a20f92011b6841 
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>
85bool 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
94template<typename ElementType>
95bool 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
104template<typename ElementType>
105template<typename... Args>
106bool 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
115template<typename ElementType>
116ElementType& 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
125template<typename ElementType>
126const 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
135template<typename ElementType>
136bool 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
158template<typename ElementType>
159bool 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
168template<typename ElementType>
169bool 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
177template<typename ElementType>
178bool 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
205template<typename ElementType>
206bool 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
221template<typename ElementType>
222void 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
234template<typename ElementType>
235size_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
247template<typename ElementType>
248void 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
260template<typename ElementType>
261void 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
272template<typename ElementType>
273void DynamicVector<ElementType>::unwrap() {
274  if (mDataIsWrapped) {
275    mData = nullptr;
276    mSize = 0;
277    mCapacity = 0;
278    mDataIsWrapped = false;
279  }
280}
281
282template<typename ElementType>
283bool DynamicVector<ElementType>::owns_data() const {
284  return !mDataIsWrapped;
285}
286
287template<typename ElementType>
288ElementType& DynamicVector<ElementType>::front() {
289  CHRE_ASSERT(mSize > 0);
290  return mData[0];
291}
292
293template<typename ElementType>
294const ElementType& DynamicVector<ElementType>::front() const {
295  CHRE_ASSERT(mSize > 0);
296  return mData[0];
297}
298
299template<typename ElementType>
300ElementType& DynamicVector<ElementType>::back() {
301  CHRE_ASSERT(mSize > 0);
302  return mData[mSize - 1];
303}
304
305template<typename ElementType>
306const ElementType& DynamicVector<ElementType>::back() const {
307  CHRE_ASSERT(mSize > 0);
308  return mData[mSize - 1];
309}
310
311template<typename ElementType>
312bool 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
328template<typename ElementType>
329typename DynamicVector<ElementType>::iterator
330    DynamicVector<ElementType>::begin() {
331  return mData;
332}
333
334template<typename ElementType>
335typename DynamicVector<ElementType>::iterator
336    DynamicVector<ElementType>::end() {
337  return (mData + mSize);
338}
339
340template<typename ElementType>
341typename DynamicVector<ElementType>::const_iterator
342    DynamicVector<ElementType>::begin() const {
343  return cbegin();
344}
345
346template<typename ElementType>
347typename DynamicVector<ElementType>::const_iterator
348    DynamicVector<ElementType>::end() const {
349  return cend();
350}
351
352template<typename ElementType>
353typename DynamicVector<ElementType>::const_iterator
354    DynamicVector<ElementType>::cbegin() const {
355  return mData;
356}
357
358template<typename ElementType>
359typename DynamicVector<ElementType>::const_iterator
360    DynamicVector<ElementType>::cend() const {
361  return (mData + mSize);
362}
363
364}  // namespace chre
365
366#endif  // CHRE_UTIL_DYNAMIC_VECTOR_IMPL_H_
367