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