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