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