dynamic_vector_impl.h revision 4639307f24f079e7e465a3a17ca90bfac4372ad3
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>::back() { 276 CHRE_ASSERT(mSize > 0); 277 return mData[mSize - 1]; 278} 279 280template<typename ElementType> 281const ElementType& DynamicVector<ElementType>::back() const { 282 CHRE_ASSERT(mSize > 0); 283 return mData[mSize - 1]; 284} 285 286template<typename ElementType> 287typename DynamicVector<ElementType>::iterator 288 DynamicVector<ElementType>::begin() { 289 return mData; 290} 291 292template<typename ElementType> 293typename DynamicVector<ElementType>::iterator 294 DynamicVector<ElementType>::end() { 295 return (mData + mSize); 296} 297 298template<typename ElementType> 299typename DynamicVector<ElementType>::const_iterator 300 DynamicVector<ElementType>::cbegin() const { 301 return mData; 302} 303 304template<typename ElementType> 305typename DynamicVector<ElementType>::const_iterator 306 DynamicVector<ElementType>::cend() const { 307 return (mData + mSize); 308} 309 310template<typename ElementType> 311bool DynamicVector<ElementType>::prepareForPush() { 312 bool spaceAvailable = true; 313 if (mSize == mCapacity) { 314 size_t newCapacity = mCapacity * 2; 315 if (newCapacity == 0) { 316 newCapacity = 1; 317 } 318 319 if (!reserve(newCapacity)) { 320 spaceAvailable = false; 321 } 322 } 323 324 return spaceAvailable; 325} 326 327} // namespace chre 328 329#endif // CHRE_UTIL_DYNAMIC_VECTOR_IMPL_H_ 330