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