dynamic_vector_impl.h revision f8d6e050ae7a17b5a96886135872d615d111a84a 
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  for (size_t i = 0; i < mSize; i++) {
32    mData[i].~ElementType();
33  }
34
35  memoryFree(mData);
36}
37
38template<typename ElementType>
39ElementType *DynamicVector<ElementType>::data() {
40  return mData;
41}
42
43template<typename ElementType>
44const ElementType *DynamicVector<ElementType>::data() const {
45  return mData;
46}
47
48template<typename ElementType>
49size_t DynamicVector<ElementType>::size() const {
50  return mSize;
51}
52
53template<typename ElementType>
54size_t DynamicVector<ElementType>::capacity() const {
55  return mCapacity;
56}
57
58template<typename ElementType>
59bool DynamicVector<ElementType>::empty() const {
60  return (mSize == 0);
61}
62
63template<typename ElementType>
64bool DynamicVector<ElementType>::push_back(const ElementType& element) {
65  bool spaceAvailable = prepareForPush();
66  if (spaceAvailable) {
67    mData[mSize++] = element;
68  }
69
70  return spaceAvailable;
71}
72
73template<typename ElementType>
74template<typename... Args>
75bool DynamicVector<ElementType>::emplace_back(Args&&... args) {
76  bool spaceAvailable = prepareForPush();
77  if (spaceAvailable) {
78    new (&data()[mSize++]) ElementType(std::forward<Args>(args)...);
79  }
80
81  return spaceAvailable;
82}
83
84template<typename ElementType>
85ElementType& DynamicVector<ElementType>::operator[](size_t index) {
86  CHRE_ASSERT(index < mSize);
87  if (index >= mSize) {
88    index = mSize - 1;
89  }
90
91  return data()[index];
92}
93
94template<typename ElementType>
95const ElementType& DynamicVector<ElementType>::operator[](size_t index) const {
96  CHRE_ASSERT(index < mSize);
97  if (index >= mSize) {
98    index = mSize - 1;
99  }
100
101  return data()[index];
102}
103
104template<typename ElementType>
105bool DynamicVector<ElementType>::reserve(size_t newCapacity) {
106  // If the new capacity is less than or equal to the current capacitywe can
107  // avoid any memory allocation/deallocation/copying.
108  if (newCapacity <= mCapacity) {
109    return true;
110  }
111
112  ElementType *newData = static_cast<ElementType *>(
113      memoryAlloc(newCapacity * sizeof(ElementType)));
114  if (newData == nullptr) {
115    return false;
116  }
117
118  std::copy(mData, mData + mSize, newData);
119  memoryFree(mData);
120  mData = newData;
121  mCapacity = newCapacity;
122  return true;
123}
124
125template<typename ElementType>
126bool DynamicVector<ElementType>::insert(size_t index,
127    const ElementType& element) {
128  // Ensure that the user is not trying to insert an element after the
129  // contiguous block of elements.
130  if (index > mSize) {
131    return false;
132  }
133
134  // Allocate space if needed.
135  if (!prepareForPush()) {
136    return false;
137  }
138
139  // Shift all elements starting at the given index backward one position.
140  for (size_t i = mSize; i > index; i--) {
141    mData[i] = std::move(mData[i - 1]);
142  }
143
144  mData[index].~ElementType();
145
146  // Insert the new element.
147  mData[index] = element;
148  mSize++;
149  return true;
150}
151
152template<typename ElementType>
153void DynamicVector<ElementType>::erase(size_t index) {
154  CHRE_ASSERT(index < mSize);
155  if (index < mSize) {
156    mSize--;
157    for (size_t i = index; i < mSize; i++) {
158      mData[i] = std::move(mData[i + 1]);
159    }
160
161    mData[mSize].~ElementType();
162  }
163}
164
165template<typename ElementType>
166size_t DynamicVector<ElementType>::find(const ElementType& element) const {
167  // TODO: Consider adding iterator support and making this a free function.
168  for (size_t i = 0; i < size(); i++) {
169    if (mData[i] == element) {
170      return i;
171    }
172  }
173
174  return size();
175}
176
177template<typename ElementType>
178bool DynamicVector<ElementType>::prepareForPush() {
179  bool spaceAvailable = true;
180  if (mSize == mCapacity) {
181    size_t newCapacity = mCapacity * 2;
182    if (newCapacity == 0) {
183      newCapacity = 1;
184    }
185
186    if (!reserve(newCapacity)) {
187      spaceAvailable = false;
188    }
189  }
190
191  return spaceAvailable;
192}
193
194}  // namespace chre
195
196#endif  // CHRE_UTIL_DYNAMIC_VECTOR_IMPL_H_
197