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