dynamic_vector_impl.h revision bbda86b265077ca90306c5f2e2590807daa39d55
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> 212bool DynamicVector<ElementType>::copy_array(const ElementType *array, 213 size_t elementCount) { 214 CHRE_ASSERT(owns_data()); 215 216 bool success = false; 217 if (owns_data() && reserve(elementCount)) { 218 clear(); 219 std::copy(array, array + elementCount, mData); 220 mSize = elementCount; 221 success = true; 222 } 223 224 return success; 225} 226 227template<typename ElementType> 228void DynamicVector<ElementType>::erase(size_t index) { 229 CHRE_ASSERT(index < mSize); 230 if (index < mSize) { 231 mSize--; 232 for (size_t i = index; i < mSize; i++) { 233 mData[i] = std::move(mData[i + 1]); 234 } 235 236 mData[mSize].~ElementType(); 237 } 238} 239 240template<typename ElementType> 241size_t DynamicVector<ElementType>::find(const ElementType& element) const { 242 // TODO: Consider adding iterator support and making this a free function. 243 size_t i; 244 for (i = 0; i < size(); i++) { 245 if (mData[i] == element) { 246 break; 247 } 248 } 249 250 return i; 251} 252 253template<typename ElementType> 254void DynamicVector<ElementType>::swap(size_t index0, size_t index1) { 255 CHRE_ASSERT(index0 < mSize && index1 < mSize); 256 if (index0 < mSize && index1 < mSize) { 257 ElementType temp = std::move(mData[index0]); 258 mData[index0] = std::move(mData[index1]); 259 mData[index1] = std::move(temp); 260 } 261} 262 263template<typename ElementType> 264void DynamicVector<ElementType>::wrap(ElementType *array, size_t elementCount) { 265 // If array is nullptr, elementCount must also be 0 266 CHRE_ASSERT(array != nullptr || elementCount == 0); 267 this->~DynamicVector(); 268 269 mData = array; 270 mSize = elementCount; 271 mCapacity = mSize; 272 mDataIsWrapped = true; 273} 274 275template<typename ElementType> 276void DynamicVector<ElementType>::unwrap() { 277 if (mDataIsWrapped) { 278 mData = nullptr; 279 mSize = 0; 280 mCapacity = 0; 281 mDataIsWrapped = false; 282 } 283} 284 285template<typename ElementType> 286bool DynamicVector<ElementType>::owns_data() const { 287 return !mDataIsWrapped; 288} 289 290template<typename ElementType> 291ElementType& DynamicVector<ElementType>::front() { 292 CHRE_ASSERT(mSize > 0); 293 return mData[0]; 294} 295 296template<typename ElementType> 297const ElementType& DynamicVector<ElementType>::front() const { 298 CHRE_ASSERT(mSize > 0); 299 return mData[0]; 300} 301 302template<typename ElementType> 303ElementType& DynamicVector<ElementType>::back() { 304 CHRE_ASSERT(mSize > 0); 305 return mData[mSize - 1]; 306} 307 308template<typename ElementType> 309const ElementType& DynamicVector<ElementType>::back() const { 310 CHRE_ASSERT(mSize > 0); 311 return mData[mSize - 1]; 312} 313 314template<typename ElementType> 315typename DynamicVector<ElementType>::iterator 316 DynamicVector<ElementType>::begin() { 317 return mData; 318} 319 320template<typename ElementType> 321typename DynamicVector<ElementType>::iterator 322 DynamicVector<ElementType>::end() { 323 return (mData + mSize); 324} 325 326template<typename ElementType> 327typename DynamicVector<ElementType>::const_iterator 328 DynamicVector<ElementType>::cbegin() const { 329 return mData; 330} 331 332template<typename ElementType> 333typename DynamicVector<ElementType>::const_iterator 334 DynamicVector<ElementType>::cend() const { 335 return (mData + mSize); 336} 337 338template<typename ElementType> 339bool DynamicVector<ElementType>::prepareForPush() { 340 bool spaceAvailable = true; 341 if (mSize == mCapacity) { 342 size_t 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 355} // namespace chre 356 357#endif // CHRE_UTIL_DYNAMIC_VECTOR_IMPL_H_ 358