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
swapPointers(char ** p1,char ** p2)23 static inline void swapPointers(char** p1, char** p2) {
24 char* tmp = *p1;
25 *p1 = *p2;
26 *p2 = tmp;
27 }
28
PodVectorBase(const PodVectorBase & other)29 PodVectorBase::PodVectorBase(const PodVectorBase& other) {
30 initFrom(other.begin(), other.byteSize());
31 }
32
operator =(const PodVectorBase & other)33 PodVectorBase& PodVectorBase::operator=(const PodVectorBase& other) {
34 initFrom(other.begin(), other.byteSize());
35 return *this;
36 }
37
~PodVectorBase()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
initFrom(const void * from,size_t fromLen)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
assignFrom(const PodVectorBase & other)63 void PodVectorBase::assignFrom(const PodVectorBase& other) {
64 resize(other.byteSize(), 1U);
65 ::memmove(begin(), other.begin(), byteSize());
66 }
67
resize(size_t newSize,size_t itemSize)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
reserve(size_t newSize,size_t itemSize)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
removeAt(size_t itemPos,size_t itemSize)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
insertAt(size_t itemPos,size_t itemSize)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
swapAll(PodVectorBase * other)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