xref: /aosp_15_r20/frameworks/minikin/include/minikin/PackedVector.h (revision 834a2baab5fdfc28e9a428ee87c7ea8f6a06a53d) 
1 /*
2  * Copyright (C) 2024 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef MINIKIN_PACKED_VECTOR_H
18 #define MINIKIN_PACKED_VECTOR_H
19 
20 #include <log/log.h>
21 
22 #include <type_traits>
23 #include <vector>
24 
25 namespace minikin {
26 
27 // PackedVector optimize short term allocations for small size objects.
28 // The public interfaces are following the std::vector.
29 template <typename T, size_t ARRAY_SIZE = 2, typename SIZE_TYPE = uint32_t>
30 class PackedVector {
31 private:
32     // At least two elements of pointer array is reserved.
33     static constexpr size_t PTR_ARRAY_SIZE =
34             std::max(static_cast<size_t>(2),
35                      (ARRAY_SIZE * sizeof(T) + sizeof(uintptr_t) - 1) / sizeof(uintptr_t));
36     // Number of elements can be stored into array.
37     static constexpr size_t ARRAY_CAPACITY = PTR_ARRAY_SIZE * sizeof(uintptr_t) / sizeof(T);
38     static_assert(std::is_pod<T>::value, "only POD can be stored in PackedVector.");
39 
40 public:
41     typedef T value_type;
42 
43     // Constructors
PackedVector()44     PackedVector() : mSize(0), mCapacity(ARRAY_CAPACITY) {}
PackedVector(const T * ptr,SIZE_TYPE size)45     PackedVector(const T* ptr, SIZE_TYPE size) : PackedVector() { copy(ptr, size); }
PackedVector(const std::vector<T> & src)46     PackedVector(const std::vector<T>& src) : PackedVector() {
47         LOG_ALWAYS_FATAL_IF(src.size() >= std::numeric_limits<SIZE_TYPE>::max());
48         copy(src.data(), src.size());
49     }
PackedVector(std::initializer_list<T> init)50     PackedVector(std::initializer_list<T> init) : PackedVector() {
51         copy(init.begin(), init.size());
52     }
53 
54     // Assignments
PackedVector(const PackedVector & o)55     PackedVector(const PackedVector& o) : PackedVector() { copy(o.getPtr(), o.mSize); }
56     PackedVector& operator=(const PackedVector& o) {
57         copy(o.getPtr(), o.mSize);
58         return *this;
59     }
60 
61     // Movement
PackedVector(PackedVector && o)62     PackedVector(PackedVector&& o) : PackedVector() { move(std::move(o)); }
63     PackedVector& operator=(PackedVector&& o) {
64         move(std::move(o));
65         return *this;
66     }
67 
~PackedVector()68     ~PackedVector() { free(); }
69 
70     // Compare
71     inline bool operator==(const PackedVector& o) const {
72         return mSize == o.mSize && memcmp(getPtr(), o.getPtr(), mSize * sizeof(T)) == 0;
73     }
74     inline bool operator!=(const PackedVector& o) const { return !(*this == o); }
75 
data()76     const T* data() const { return getPtr(); }
data()77     T* data() { return getPtr(); }
78 
79     const T& operator[](SIZE_TYPE i) const { return getPtr()[i]; }
80     T& operator[](SIZE_TYPE i) { return getPtr()[i]; }
81 
reserve(SIZE_TYPE capacity)82     void reserve(SIZE_TYPE capacity) { ensureCapacity(capacity); }
83 
84     void resize(SIZE_TYPE size, T value = T()) {
85         if (mSize == size) {
86             return;
87         } else if (mSize > size) {  // reduce size
88             if (isArrayUsed()) {    // array to array reduction, so no need to reallocate.
89                 mSize = size;
90             } else if (size > ARRAY_CAPACITY) {  // heap to heap reduction
91                 T* newPtr = new T[size];
92                 const T* oldPtr = getPtr();
93                 std::copy(oldPtr, oldPtr + size, newPtr);
94                 free();
95                 mArray[0] = reinterpret_cast<uintptr_t>(newPtr);
96                 mSize = size;
97                 mCapacity = size;
98             } else {  // heap to array reduction.
99                 const T* oldPtr = getPtr();
100                 T* newPtr = reinterpret_cast<T*>(&mArray[0]);
101                 std::copy(oldPtr, oldPtr + size, newPtr);
102                 delete[] oldPtr;  // we cannot use free() here because we wrote data to mArray.
103                 mSize = size;
104                 mCapacity = ARRAY_CAPACITY;
105             }
106         } else {  // mSize < size  // increase size
107             ensureCapacity(size);
108             T* ptr = getPtr();
109             for (SIZE_TYPE i = mSize; i < size; ++i) {
110                 ptr[i] = value;
111             }
112             mSize = size;
113         }
114     }
115 
push_back(const T & x)116     void push_back(const T& x) {
117         if (mSize >= mCapacity) [[unlikely]] {
118             // exponential backoff
119             constexpr SIZE_TYPE kMaxIncrease = static_cast<SIZE_TYPE>(4096 / sizeof(T));
120             ensureCapacity(mCapacity + std::min(mCapacity, kMaxIncrease));
121         }
122         *(getPtr() + mSize) = x;
123         mSize++;
124     }
125 
shrink_to_fit()126     void shrink_to_fit() {
127         if (mSize == mCapacity || mCapacity == ARRAY_CAPACITY) {
128             return;
129         }
130 
131         bool needFree = !isArrayUsed();
132 
133         const T* oldPtr = getPtr();
134         T* newPtr;
135         if (mSize <= ARRAY_CAPACITY) {
136             newPtr = reinterpret_cast<T*>(&mArray[0]);
137             mCapacity = ARRAY_CAPACITY;
138             std::copy(oldPtr, oldPtr + mSize, newPtr);
139         } else {
140             newPtr = new T[mSize];
141             mCapacity = mSize;
142             std::copy(oldPtr, oldPtr + mSize, newPtr);
143             mArray[0] = reinterpret_cast<uintptr_t>(newPtr);
144         }
145         if (needFree) {
146             delete[] oldPtr;
147         }
148     }
149 
clear()150     void clear() {
151         mSize = 0;  // don't free up until free is called.
152     }
153 
empty()154     bool empty() const { return mSize == 0; }
155 
size()156     SIZE_TYPE size() const { return mSize; }
capacity()157     SIZE_TYPE capacity() const { return mCapacity; }
158 
159 private:
160     uintptr_t mArray[PTR_ARRAY_SIZE];
161     SIZE_TYPE mSize;
162     SIZE_TYPE mCapacity;
163 
copy(const T * src,SIZE_TYPE count)164     void copy(const T* src, SIZE_TYPE count) {
165         clear();
166         ensureCapacity(count);
167         mSize = count;
168         memcpy(getPtr(), src, count * sizeof(T));
169     }
170 
move(PackedVector && o)171     void move(PackedVector&& o) {
172         mSize = o.mSize;
173         o.mSize = 0;
174         mCapacity = o.mCapacity;
175         o.mCapacity = ARRAY_CAPACITY;
176         for (uint32_t i = 0; i < PTR_ARRAY_SIZE; ++i) {
177             mArray[i] = o.mArray[i];
178             o.mArray[i] = 0;
179         }
180     }
181 
isArrayUsed()182     inline bool isArrayUsed() const { return mCapacity <= ARRAY_CAPACITY; }
183 
ensureCapacity(SIZE_TYPE capacity)184     void ensureCapacity(SIZE_TYPE capacity) {
185         if (capacity <= mCapacity) {
186             return;
187         }
188 
189         if (capacity > ARRAY_CAPACITY) {
190             T* newPtr = new T[capacity];
191             const T* oldPtr = getPtr();
192             std::copy(oldPtr, oldPtr + mSize, newPtr);
193             free();
194             mArray[0] = reinterpret_cast<uintptr_t>(newPtr);
195             mCapacity = capacity;
196         } else {
197             mCapacity = ARRAY_CAPACITY;
198         }
199     }
200 
free()201     void free() {
202         if (!isArrayUsed()) {
203             delete[] reinterpret_cast<T*>(mArray[0]);
204             mArray[0] = 0;
205             mCapacity = ARRAY_CAPACITY;
206         }
207     }
208 
getPtr()209     inline T* getPtr() {
210         return isArrayUsed() ? reinterpret_cast<T*>(&mArray[0]) : reinterpret_cast<T*>(mArray[0]);
211     }
212 
getPtr()213     inline const T* getPtr() const {
214         return isArrayUsed() ? reinterpret_cast<const T*>(&mArray[0])
215                              : reinterpret_cast<const T*>(mArray[0]);
216     }
217 
218 public:
begin()219     inline const T* begin() const { return getPtr(); }
end()220     inline const T* end() const { return getPtr() + mSize; }
back()221     inline const T* back() const { return getPtr() + mSize - 1; }
begin()222     inline T* begin() { return getPtr(); }
end()223     inline T* end() { return getPtr() + mSize; }
back()224     inline T* back() { return getPtr() + mSize - 1; }
225 };
226 
227 }  // namespace minikin
228 #endif  // MINIKIN_PACKED_VECTOR_H
229