1d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner// Copyright 2014 The Android Open Source Project 2d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner// 3d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner// This software is licensed under the terms of the GNU General Public 4d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner// License version 2, as published by the Free Software Foundation, and 5d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner// may be copied, distributed, and modified under those terms. 6d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner// 7d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner// This program is distributed in the hope that it will be useful, 8d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner// but WITHOUT ANY WARRANTY; without even the implied warranty of 9d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner// GNU General Public License for more details. 11d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 12d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner#include "android/base/containers/PodVector.h" 13d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 14d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner#include "android/base/Log.h" 15e87cd78d4634396f2734c381f5ac77fd70e8858eDavid 'Digit' Turner#include "android/base/memory/MallocUsableSize.h" 16d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 17d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner#include <stdlib.h> 18d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner#include <string.h> 19d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 20d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turnernamespace android { 21d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turnernamespace base { 22d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 23d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turnerstatic inline void swapPointers(char** p1, char** p2) { 24d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner char* tmp = *p1; 25d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner *p1 = *p2; 26d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner *p2 = tmp; 27d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner} 28d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 29d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' TurnerPodVectorBase::PodVectorBase(const PodVectorBase& other) { 30d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner initFrom(other.begin(), other.byteSize()); 31d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner} 32d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 33d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' TurnerPodVectorBase& PodVectorBase::operator=(const PodVectorBase& other) { 34d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner initFrom(other.begin(), other.byteSize()); 35d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner return *this; 36d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner} 37d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 38d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' TurnerPodVectorBase::~PodVectorBase() { 39d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner if (mBegin) { 40d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner // Sanity. 41d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner ::memset(mBegin, 0xee, byteSize()); 42d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner ::free(mBegin); 43d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mBegin = NULL; 44d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mEnd = NULL; 45d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mLimit = NULL; 46d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner } 47d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner} 48d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 49d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turnervoid PodVectorBase::initFrom(const void* from, size_t fromLen) { 50d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner if (!fromLen || !from) { 51d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mBegin = NULL; 52d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mEnd = NULL; 53d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mLimit = NULL; 54d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner } else { 55d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mBegin = static_cast<char*>(::malloc(fromLen)); 56d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner PCHECK(mBegin) 57d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner << LogString("Could not allocate %zd bytes.", fromLen); 58d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mEnd = mLimit = mBegin + fromLen; 59d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner ::memcpy(mBegin, from, fromLen); 60d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner } 61d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner} 62d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 63d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turnervoid PodVectorBase::assignFrom(const PodVectorBase& other) { 64d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner resize(other.byteSize(), 1U); 65d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner ::memmove(begin(), other.begin(), byteSize()); 66d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner} 67d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 68d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turnervoid PodVectorBase::resize(size_t newSize, size_t itemSize) { 69d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner const size_t kMaxSize = maxItemCapacity(itemSize); 70d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner CHECK(newSize <= kMaxSize) << LogString( 71d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner "Trying to resize vector to %zd items of %zd bytes " 72d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner "(%zd max allowed)", 73d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner newSize, 74d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner kMaxSize); 75d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner size_t oldCapacity = itemCapacity(itemSize); 76d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner const size_t kMinCapacity = 256 / itemSize; 77d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 78d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner if (newSize < oldCapacity) { 79d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner // Only shrink if the new size is really small. 80d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner if (newSize < oldCapacity / 2 && oldCapacity > kMinCapacity) { 81d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner reserve(newSize, itemSize); 82d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner } 83d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner } else if (newSize > oldCapacity) { 84d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner size_t newCapacity = oldCapacity; 85d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner while (newCapacity < newSize) { 86d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner size_t newCapacity2 = newCapacity + (newCapacity >> 2) + 8; 87d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner if (newCapacity2 < newCapacity || newCapacity > kMaxSize) { 88d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner newCapacity = kMaxSize; 89d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner } else { 90d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner newCapacity = newCapacity2; 91d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner } 92d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner } 93d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner reserve(newCapacity, itemSize); 94d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner } 95d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mEnd = mBegin + newSize * itemSize; 96d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner} 97d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 98d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turnervoid PodVectorBase::reserve(size_t newSize, size_t itemSize) { 99d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner const size_t kMaxSize = maxItemCapacity(itemSize); 100d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner CHECK(newSize <= kMaxSize) << LogString( 101d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner "Trying to allocate %zd items of %zd bytes (%zd max allowed)", 102d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner newSize, 103d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner kMaxSize); 104d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 105d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner if (newSize == 0) { 106d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner ::free(mBegin); 107d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mBegin = NULL; 108d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mEnd = NULL; 109d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mLimit = NULL; 110d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner return; 111d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner } 112d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 113d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner size_t oldByteSize = byteSize(); 114d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner size_t newByteCapacity = newSize * itemSize; 115d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner char* newBegin = static_cast<char*>(::realloc(mBegin, newByteCapacity)); 116d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner PCHECK(newBegin) << LogString( 117d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner "Could not reallocate array from %zd tp %zd items of %zd bytes", 118d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner oldByteSize / itemSize, 119d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner newSize, 120d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner itemSize); 121d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 122d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mBegin = newBegin; 123d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mEnd = newBegin + oldByteSize; 124d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner#if USE_MALLOC_USABLE_SIZE 125d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner size_t usableSize = malloc_usable_size(mBegin); 126d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner if (usableSize > newByteCapacity) { 127d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner newByteCapacity = usableSize - (usableSize % itemSize); 128d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner } 129d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner#endif 130d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mLimit = newBegin + newByteCapacity; 131d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner // Sanity. 132d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner if (newByteCapacity > oldByteSize) { 133d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner ::memset(mBegin + oldByteSize, 0, newByteCapacity - oldByteSize); 134d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner } 135d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner} 136d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 137d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turnervoid PodVectorBase::removeAt(size_t itemPos, size_t itemSize) { 138d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner size_t count = itemCount(itemSize); 139d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner DCHECK(itemPos <= count) << "Item position is too large!"; 140d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner if (itemPos < count) { 141d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner size_t pos = itemPos * itemSize; 142d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner ::memmove(mBegin + pos, 143d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mBegin + pos + itemSize, 144d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner byteSize() - pos - itemSize); 145d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner resize(count - 1U, itemSize); 146d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner } 147d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner} 148d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 149d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turnervoid* PodVectorBase::insertAt(size_t itemPos, size_t itemSize) { 150d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner size_t count = this->itemCount(itemSize); 151d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner DCHECK(itemPos <= count) << "Item position is too large"; 152d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner resize(count + 1, itemSize); 153d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner size_t pos = itemPos * itemSize; 154d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner if (itemPos < count) { 155d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner ::memmove(mBegin + pos + itemSize, 156d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner mBegin + pos, 157d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner count * itemSize - pos); 158d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner // Sanity to avoid copying pointers and other bad stuff. 159d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner ::memset(mBegin + pos, 0, itemSize); 160d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner } 161d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner return mBegin + pos; 162d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner} 163d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 164d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turnervoid PodVectorBase::swapAll(PodVectorBase* other) { 165d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner swapPointers(&mBegin, &other->mBegin); 166d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner swapPointers(&mEnd, &other->mEnd); 167d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner swapPointers(&mLimit, &other->mLimit); 168d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner} 169d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner 170d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner} // namespace base 171d3f2c27ff9f611e5047a35cb20ed53f548214fedDavid 'Digit' Turner} // namespace android 172