| /* |
| * Copyright (C) 2016 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #ifndef CHRE_UTIL_DYNAMIC_VECTOR_IMPL_H_ |
| #define CHRE_UTIL_DYNAMIC_VECTOR_IMPL_H_ |
| |
| #include <memory> |
| #include <new> |
| #include <utility> |
| |
| #include "chre/platform/assert.h" |
| #include "chre/platform/memory.h" |
| #include "chre/util/memory.h" |
| |
| namespace chre { |
| |
| template<typename ElementType> |
| DynamicVector<ElementType>::DynamicVector() {} |
| |
| template<typename ElementType> |
| DynamicVector<ElementType>::DynamicVector(DynamicVector<ElementType>&& other) |
| : mData(other.mData), |
| mSize(other.mSize), |
| mCapacity(other.mCapacity), |
| mDataIsWrapped(other.mDataIsWrapped) { |
| other.mData = nullptr; |
| other.mSize = 0; |
| other.mCapacity = 0; |
| other.mDataIsWrapped = false; |
| } |
| |
| template<typename ElementType> |
| DynamicVector<ElementType>::~DynamicVector() { |
| if (owns_data()) { |
| clear(); |
| memoryFree(mData); |
| } |
| } |
| |
| template <typename ElementType> |
| void DynamicVector<ElementType>::clear() { |
| destroy(mData, mSize); |
| mSize = 0; |
| } |
| |
| template<typename ElementType> |
| ElementType *DynamicVector<ElementType>::data() { |
| return mData; |
| } |
| |
| template<typename ElementType> |
| const ElementType *DynamicVector<ElementType>::data() const { |
| return mData; |
| } |
| |
| template<typename ElementType> |
| size_t DynamicVector<ElementType>::size() const { |
| return mSize; |
| } |
| |
| template<typename ElementType> |
| size_t DynamicVector<ElementType>::capacity() const { |
| return mCapacity; |
| } |
| |
| template<typename ElementType> |
| bool DynamicVector<ElementType>::empty() const { |
| return (mSize == 0); |
| } |
| |
| template<typename ElementType> |
| bool DynamicVector<ElementType>::push_back(const ElementType& element) { |
| bool spaceAvailable = prepareForPush(); |
| if (spaceAvailable) { |
| new (&mData[mSize++]) ElementType(element); |
| } |
| |
| return spaceAvailable; |
| } |
| |
| template<typename ElementType> |
| bool DynamicVector<ElementType>::push_back(ElementType&& element) { |
| bool spaceAvailable = prepareForPush(); |
| if (spaceAvailable) { |
| new (&mData[mSize++]) ElementType(std::move(element)); |
| } |
| |
| return spaceAvailable; |
| } |
| |
| template<typename ElementType> |
| template<typename... Args> |
| bool DynamicVector<ElementType>::emplace_back(Args&&... args) { |
| bool spaceAvailable = prepareForPush(); |
| if (spaceAvailable) { |
| new (&data()[mSize++]) ElementType(std::forward<Args>(args)...); |
| } |
| |
| return spaceAvailable; |
| } |
| |
| template<typename ElementType> |
| ElementType& DynamicVector<ElementType>::operator[](size_t index) { |
| CHRE_ASSERT(index < mSize); |
| if (index >= mSize) { |
| index = mSize - 1; |
| } |
| |
| return data()[index]; |
| } |
| |
| template<typename ElementType> |
| const ElementType& DynamicVector<ElementType>::operator[](size_t index) const { |
| CHRE_ASSERT(index < mSize); |
| if (index >= mSize) { |
| index = mSize - 1; |
| } |
| |
| return data()[index]; |
| } |
| |
| template<typename ElementType> |
| bool DynamicVector<ElementType>::reserve(size_t newCapacity) { |
| bool success = false; |
| |
| CHRE_ASSERT_LOG(owns_data(), "Wrapped buffers can't be resized"); |
| if (newCapacity <= mCapacity) { |
| success = true; |
| } else if (owns_data()) { |
| ElementType *newData = static_cast<ElementType *>( |
| memoryAlloc(newCapacity * sizeof(ElementType))); |
| if (newData != nullptr) { |
| uninitializedMoveOrCopy(mData, mSize, newData); |
| destroy(mData, mSize); |
| memoryFree(mData); |
| mData = newData; |
| mCapacity = newCapacity; |
| success = true; |
| } |
| } |
| |
| return success; |
| } |
| |
| template<typename ElementType> |
| bool DynamicVector<ElementType>::insert(size_t index, |
| const ElementType& element) { |
| bool inserted = prepareInsert(index); |
| if (inserted) { |
| new (&mData[index]) ElementType(element); |
| } |
| return inserted; |
| } |
| |
| template<typename ElementType> |
| bool DynamicVector<ElementType>::insert(size_t index, ElementType&& element) { |
| bool inserted = prepareInsert(index); |
| if (inserted) { |
| new (&mData[index]) ElementType(std::move(element)); |
| } |
| return inserted; |
| } |
| |
| template<typename ElementType> |
| bool DynamicVector<ElementType>::prepareInsert(size_t index) { |
| // Insertions are not allowed to create a sparse array. |
| CHRE_ASSERT(index <= mSize); |
| |
| // TODO: this can be optimized in the case where we need to grow the vector to |
| // do the shift when transferring the values from the old array to the new. |
| bool readyForInsert = (index <= mSize && prepareForPush()); |
| if (readyForInsert) { |
| // If we aren't simply appending the new object, create an opening where |
| // we'll insert it |
| if (index < mSize) { |
| // Make a duplicate of the last item in the slot where we're growing |
| uninitializedMoveOrCopy(&mData[mSize - 1], 1, &mData[mSize]); |
| // Shift all elements starting at index towards the end |
| for (size_t i = mSize - 1; i > index; i--) { |
| moveOrCopyAssign(mData[i], mData[i - 1]); |
| } |
| |
| mData[index].~ElementType(); |
| } |
| |
| mSize++; |
| } |
| |
| return readyForInsert; |
| } |
| |
| template<typename ElementType> |
| bool DynamicVector<ElementType>::copy_array(const ElementType *array, |
| size_t elementCount) { |
| CHRE_ASSERT(owns_data()); |
| |
| bool success = false; |
| if (owns_data() && reserve(elementCount)) { |
| clear(); |
| std::copy(array, array + elementCount, mData); |
| mSize = elementCount; |
| success = true; |
| } |
| |
| return success; |
| } |
| |
| template<typename ElementType> |
| void DynamicVector<ElementType>::erase(size_t index) { |
| CHRE_ASSERT(index < mSize); |
| if (index < mSize) { |
| mSize--; |
| for (size_t i = index; i < mSize; i++) { |
| moveOrCopyAssign(mData[i], mData[i + 1]); |
| } |
| |
| mData[mSize].~ElementType(); |
| } |
| } |
| |
| template<typename ElementType> |
| size_t DynamicVector<ElementType>::find(const ElementType& element) const { |
| // TODO: Consider adding iterator support and making this a free function. |
| size_t i; |
| for (i = 0; i < size(); i++) { |
| if (mData[i] == element) { |
| break; |
| } |
| } |
| |
| return i; |
| } |
| |
| template<typename ElementType> |
| void DynamicVector<ElementType>::swap(size_t index0, size_t index1) { |
| CHRE_ASSERT(index0 < mSize && index1 < mSize); |
| if (index0 < mSize && index1 < mSize && index0 != index1) { |
| typename std::aligned_storage<sizeof(ElementType), |
| alignof(ElementType)>::type tempStorage; |
| ElementType& temp = *reinterpret_cast<ElementType *>(&tempStorage); |
| uninitializedMoveOrCopy(&mData[index0], 1, &temp); |
| moveOrCopyAssign(mData[index0], mData[index1]); |
| moveOrCopyAssign(mData[index1], temp); |
| } |
| } |
| |
| template<typename ElementType> |
| void DynamicVector<ElementType>::wrap(ElementType *array, size_t elementCount) { |
| // If array is nullptr, elementCount must also be 0 |
| CHRE_ASSERT(array != nullptr || elementCount == 0); |
| this->~DynamicVector(); |
| |
| mData = array; |
| mSize = elementCount; |
| mCapacity = mSize; |
| mDataIsWrapped = true; |
| } |
| |
| template<typename ElementType> |
| void DynamicVector<ElementType>::unwrap() { |
| if (mDataIsWrapped) { |
| mData = nullptr; |
| mSize = 0; |
| mCapacity = 0; |
| mDataIsWrapped = false; |
| } |
| } |
| |
| template<typename ElementType> |
| bool DynamicVector<ElementType>::owns_data() const { |
| return !mDataIsWrapped; |
| } |
| |
| template<typename ElementType> |
| ElementType& DynamicVector<ElementType>::front() { |
| CHRE_ASSERT(mSize > 0); |
| return mData[0]; |
| } |
| |
| template<typename ElementType> |
| const ElementType& DynamicVector<ElementType>::front() const { |
| CHRE_ASSERT(mSize > 0); |
| return mData[0]; |
| } |
| |
| template<typename ElementType> |
| ElementType& DynamicVector<ElementType>::back() { |
| CHRE_ASSERT(mSize > 0); |
| return mData[mSize - 1]; |
| } |
| |
| template<typename ElementType> |
| const ElementType& DynamicVector<ElementType>::back() const { |
| CHRE_ASSERT(mSize > 0); |
| return mData[mSize - 1]; |
| } |
| |
| template<typename ElementType> |
| bool DynamicVector<ElementType>::prepareForPush() { |
| bool spaceAvailable = true; |
| if (mSize == mCapacity) { |
| size_t newCapacity = mCapacity * 2; |
| if (newCapacity == 0) { |
| newCapacity = 1; |
| } |
| |
| if (!reserve(newCapacity)) { |
| spaceAvailable = false; |
| } |
| } |
| |
| return spaceAvailable; |
| } |
| |
| template<typename ElementType> |
| typename DynamicVector<ElementType>::iterator |
| DynamicVector<ElementType>::begin() { |
| return mData; |
| } |
| |
| template<typename ElementType> |
| typename DynamicVector<ElementType>::iterator |
| DynamicVector<ElementType>::end() { |
| return (mData + mSize); |
| } |
| |
| template<typename ElementType> |
| typename DynamicVector<ElementType>::const_iterator |
| DynamicVector<ElementType>::begin() const { |
| return cbegin(); |
| } |
| |
| template<typename ElementType> |
| typename DynamicVector<ElementType>::const_iterator |
| DynamicVector<ElementType>::end() const { |
| return cend(); |
| } |
| |
| template<typename ElementType> |
| typename DynamicVector<ElementType>::const_iterator |
| DynamicVector<ElementType>::cbegin() const { |
| return mData; |
| } |
| |
| template<typename ElementType> |
| typename DynamicVector<ElementType>::const_iterator |
| DynamicVector<ElementType>::cend() const { |
| return (mData + mSize); |
| } |
| |
| } // namespace chre |
| |
| #endif // CHRE_UTIL_DYNAMIC_VECTOR_IMPL_H_ |