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