dynamic_vector_impl.h revision 83be94436ec4d35296e00da877c7198f67b6af44 
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 <algorithm>
21#include <utility>
22
23#include "chre/platform/assert.h"
24#include "chre/platform/memory.h"
25#include "chre/util/dynamic_vector.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  for (size_t i = 0; i < mSize; i++) {
55    mData[i].~ElementType();
56  }
57  mSize = 0;
58}
59
60template<typename ElementType>
61ElementType *DynamicVector<ElementType>::data() {
62  return mData;
63}
64
65template<typename ElementType>
66const ElementType *DynamicVector<ElementType>::data() const {
67  return mData;
68}
69
70template<typename ElementType>
71size_t DynamicVector<ElementType>::size() const {
72  return mSize;
73}
74
75template<typename ElementType>
76size_t 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>
86bool DynamicVector<ElementType>::push_back(const ElementType& element) {
87  bool spaceAvailable = prepareForPush();
88  if (spaceAvailable) {
89    mData[mSize++] = element;
90  }
91
92  return spaceAvailable;
93}
94
95template<typename ElementType>
96bool DynamicVector<ElementType>::push_back(ElementType&& element) {
97  bool spaceAvailable = prepareForPush();
98  if (spaceAvailable) {
99    mData[mSize++] = std::move(element);
100  }
101
102  return spaceAvailable;
103}
104
105template<typename ElementType>
106template<typename... Args>
107bool DynamicVector<ElementType>::emplace_back(Args&&... args) {
108  bool spaceAvailable = prepareForPush();
109  if (spaceAvailable) {
110    new (&data()[mSize++]) ElementType(std::forward<Args>(args)...);
111  }
112
113  return spaceAvailable;
114}
115
116template<typename ElementType>
117ElementType& DynamicVector<ElementType>::operator[](size_t index) {
118  CHRE_ASSERT(index < mSize);
119  if (index >= mSize) {
120    index = mSize - 1;
121  }
122
123  return data()[index];
124}
125
126template<typename ElementType>
127const ElementType& DynamicVector<ElementType>::operator[](size_t index) const {
128  CHRE_ASSERT(index < mSize);
129  if (index >= mSize) {
130    index = mSize - 1;
131  }
132
133  return data()[index];
134}
135
136/**
137 *  Moves a range of data items. This is part of the template specialization for
138 *  when the underlying type is move-assignable.
139 *
140 *  @param data The beginning of the data to move.
141 *  @param count The number of data items to move.
142 *  @param newData The location to move these items to.
143 */
144template<typename ElementType>
145void moveOrCopy(ElementType *data, size_t count, ElementType *newData,
146                std::true_type) {
147  std::move(data, data + count, newData);
148}
149
150/**
151 * Copies a range of data items. This is part of the template specialization
152 * for when the underlying type is not move-assignable.
153 *
154 * @param data The beginning of the data to copy.
155 * @param count The number of data items to copy.
156 * @param newData The location to copy these items to.
157 */
158template<typename ElementType>
159void moveOrCopy(ElementType *data, size_t count, ElementType *newData,
160                std::false_type) {
161  std::copy(data, data + count, newData);
162}
163
164template<typename ElementType>
165bool DynamicVector<ElementType>::reserve(size_t newCapacity) {
166  bool success = false;
167
168  CHRE_ASSERT_LOG(owns_data(), "Wrapped buffers can't be resized");
169  if (newCapacity <= mCapacity) {
170    success = true;
171  } else if (owns_data()) {
172    ElementType *newData = static_cast<ElementType *>(
173        memoryAlloc(newCapacity * sizeof(ElementType)));
174    if (newData != nullptr) {
175      moveOrCopy(mData, mSize, newData,
176                 typename std::is_move_assignable<ElementType>::type());
177
178      memoryFree(mData);
179      mData = newData;
180      mCapacity = newCapacity;
181      success = true;
182    }
183  }
184
185  return success;
186}
187
188template<typename ElementType>
189bool DynamicVector<ElementType>::insert(size_t index,
190    const ElementType& element) {
191  // Insertions are not allowed to create a sparse array.
192  CHRE_ASSERT(index <= mSize);
193
194  bool inserted = false;
195  if (index <= mSize && prepareForPush()) {
196    // Shift all elements starting at the given index backward one position.
197    for (size_t i = mSize; i > index; i--) {
198      mData[i] = std::move(mData[i - 1]);
199    }
200
201    mData[index].~ElementType();
202    mData[index] = element;
203    mSize++;
204
205    inserted = true;
206  }
207
208  return inserted;
209}
210
211template<typename ElementType>
212void DynamicVector<ElementType>::erase(size_t index) {
213  CHRE_ASSERT(index < mSize);
214  if (index < mSize) {
215    mSize--;
216    for (size_t i = index; i < mSize; i++) {
217      mData[i] = std::move(mData[i + 1]);
218    }
219
220    mData[mSize].~ElementType();
221  }
222}
223
224template<typename ElementType>
225size_t DynamicVector<ElementType>::find(const ElementType& element) const {
226  // TODO: Consider adding iterator support and making this a free function.
227  size_t i;
228  for (i = 0; i < size(); i++) {
229    if (mData[i] == element) {
230      break;
231    }
232  }
233
234  return i;
235}
236
237template<typename ElementType>
238void DynamicVector<ElementType>::swap(size_t index0, size_t index1) {
239  CHRE_ASSERT(index0 < mSize && index1 < mSize);
240  if (index0 < mSize && index1 < mSize) {
241    ElementType temp = std::move(mData[index0]);
242    mData[index0] = std::move(mData[index1]);
243    mData[index1] = std::move(temp);
244  }
245}
246
247template<typename ElementType>
248void DynamicVector<ElementType>::wrap(ElementType *array, size_t elementCount) {
249  // If array is nullptr, elementCount must also be 0
250  CHRE_ASSERT(array != nullptr || elementCount == 0);
251  this->~DynamicVector();
252
253  mData = array;
254  mSize = elementCount;
255  mCapacity = mSize;
256  mDataIsWrapped = true;
257}
258
259template<typename ElementType>
260void DynamicVector<ElementType>::unwrap() {
261  if (mDataIsWrapped) {
262    mData = nullptr;
263    mSize = 0;
264    mCapacity = 0;
265    mDataIsWrapped = false;
266  }
267}
268
269template<typename ElementType>
270bool DynamicVector<ElementType>::owns_data() const {
271  return !mDataIsWrapped;
272}
273
274template<typename ElementType>
275ElementType& DynamicVector<ElementType>::front() {
276  CHRE_ASSERT(mSize > 0);
277  return mData[0];
278}
279
280template<typename ElementType>
281const ElementType& DynamicVector<ElementType>::front() const {
282  CHRE_ASSERT(mSize > 0);
283  return mData[0];
284}
285
286template<typename ElementType>
287ElementType& DynamicVector<ElementType>::back() {
288  CHRE_ASSERT(mSize > 0);
289  return mData[mSize - 1];
290}
291
292template<typename ElementType>
293const ElementType& DynamicVector<ElementType>::back() const {
294  CHRE_ASSERT(mSize > 0);
295  return mData[mSize - 1];
296}
297
298template<typename ElementType>
299typename DynamicVector<ElementType>::iterator
300    DynamicVector<ElementType>::begin() {
301  return mData;
302}
303
304template<typename ElementType>
305typename DynamicVector<ElementType>::iterator
306    DynamicVector<ElementType>::end() {
307  return (mData + mSize);
308}
309
310template<typename ElementType>
311typename DynamicVector<ElementType>::const_iterator
312    DynamicVector<ElementType>::cbegin() const {
313  return mData;
314}
315
316template<typename ElementType>
317typename DynamicVector<ElementType>::const_iterator
318    DynamicVector<ElementType>::cend() const {
319  return (mData + mSize);
320}
321
322template<typename ElementType>
323bool DynamicVector<ElementType>::prepareForPush() {
324  bool spaceAvailable = true;
325  if (mSize == mCapacity) {
326    size_t newCapacity = mCapacity * 2;
327    if (newCapacity == 0) {
328      newCapacity = 1;
329    }
330
331    if (!reserve(newCapacity)) {
332      spaceAvailable = false;
333    }
334  }
335
336  return spaceAvailable;
337}
338
339}  // namespace chre
340
341#endif  // CHRE_UTIL_DYNAMIC_VECTOR_IMPL_H_
342