1 /*
2  * Copyright 2019, 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 ANDROID_REGION_FAT_VECTOR_H
18 #define ANDROID_REGION_FAT_VECTOR_H
19 
20 #include <stddef.h>
21 #include <stdlib.h>
22 #include <utils/Log.h>
23 #include <type_traits>
24 
25 #include <vector>
26 
27 namespace android {
28 
29 template <typename T, size_t SIZE = 4>
30 class InlineStdAllocator {
31 public:
32     struct Allocation {
33     private:
34         Allocation(const Allocation&) = delete;
35         void operator=(const Allocation&) = delete;
36 
37     public:
AllocationAllocation38         Allocation() {}
39         // char array instead of T array, so memory is uninitialized, with no destructors run
40         char array[sizeof(T) * SIZE];
41         bool inUse = false;
42     };
43 
44     typedef T value_type; // needed to implement std::allocator
45     typedef T* pointer;   // needed to implement std::allocator
46 
InlineStdAllocator(Allocation & allocation)47     explicit InlineStdAllocator(Allocation& allocation) : mAllocation(allocation) {}
InlineStdAllocator(const InlineStdAllocator & other)48     InlineStdAllocator(const InlineStdAllocator& other) : mAllocation(other.mAllocation) {}
~InlineStdAllocator()49     ~InlineStdAllocator() {}
50 
51     T* allocate(size_t num, const void* = 0) {
52         if (!mAllocation.inUse && num <= SIZE) {
53             mAllocation.inUse = true;
54             return static_cast<T*>(static_cast<void*>(mAllocation.array));
55         } else {
56             return static_cast<T*>(static_cast<void*>(malloc(num * sizeof(T))));
57         }
58     }
59 
deallocate(pointer p,size_t)60     void deallocate(pointer p, size_t) {
61         if (p == static_cast<T*>(static_cast<void*>(mAllocation.array))) {
62             mAllocation.inUse = false;
63         } else {
64             // 'free' instead of delete here - destruction handled separately
65             free(p);
66         }
67     }
68 
69     // The STL checks that this member type is present so that
70     // std::allocator_traits<InlineStdAllocator<T, SIZE>>::rebind_alloc<Other>
71     // works. std::vector won't be able to construct an
72     // InlineStdAllocator<Other, SIZE>, because InlineStdAllocator has no
73     // default constructor, but vector presumably doesn't rebind the allocator
74     // because it doesn't allocate internal node types.
75     template <class Other>
76     struct rebind {
77         typedef InlineStdAllocator<Other, SIZE> other;
78     };
79     Allocation& mAllocation;
80 };
81 
82 /**
83  * std::vector with SIZE elements preallocated into an internal buffer.
84  *
85  * Useful for avoiding the cost of malloc in cases where only SIZE or
86  * fewer elements are needed in the common case.
87  */
88 template <typename T, size_t SIZE = 4>
89 class FatVector : public std::vector<T, InlineStdAllocator<T, SIZE>> {
90 public:
FatVector()91     FatVector()
92           : std::vector<T, InlineStdAllocator<T, SIZE>>(InlineStdAllocator<T, SIZE>(mAllocation)) {
93         this->reserve(SIZE);
94     }
95 
FatVector(std::initializer_list<T> init)96     FatVector(std::initializer_list<T> init)
97           : std::vector<T, InlineStdAllocator<T, SIZE>>(init,
98                                                         InlineStdAllocator<T, SIZE>(mAllocation)) {
99         this->reserve(SIZE);
100     }
101 
FatVector(size_t capacity)102     explicit FatVector(size_t capacity) : FatVector() { this->resize(capacity); }
103 
104 private:
105     typename InlineStdAllocator<T, SIZE>::Allocation mAllocation;
106 };
107 
108 } // namespace android
109 
110 #endif // ANDROID_REGION_FAT_VECTOR_H
111