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 20 namespace android { 21 namespace base { 22 23 static inline void swapPointers(char** p1, char** p2) { 24 char* tmp = *p1; 25 *p1 = *p2; 26 *p2 = tmp; 27 } 28 29 PodVectorBase::PodVectorBase(const PodVectorBase& other) { 30 initFrom(other.begin(), other.byteSize()); 31 } 32 33 PodVectorBase& PodVectorBase::operator=(const PodVectorBase& other) { 34 initFrom(other.begin(), other.byteSize()); 35 return *this; 36 } 37 38 PodVectorBase::~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 49 void 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 63 void PodVectorBase::assignFrom(const PodVectorBase& other) { 64 resize(other.byteSize(), 1U); 65 ::memmove(begin(), other.begin(), byteSize()); 66 } 67 68 void 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 98 void 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 137 void 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 149 void* 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 164 void 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