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