1 /* 2 * Copyright (C) 2021 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 INCLUDE_PERFETTO_EXT_BASE_SMALL_VECTOR_H_ 18 #define INCLUDE_PERFETTO_EXT_BASE_SMALL_VECTOR_H_ 19 20 #include <algorithm> 21 #include <type_traits> 22 #include <utility> 23 24 #include "perfetto/base/compiler.h" 25 #include "perfetto/base/logging.h" 26 #include "perfetto/ext/base/utils.h" 27 28 namespace perfetto { 29 namespace base { 30 31 // Uses inline storage first, switches to dynamic storage when it overflows. 32 template <typename T, size_t kSize> 33 class SmallVector { 34 public: 35 static constexpr size_t kInlineSize = kSize; 36 37 explicit SmallVector() = default; 38 ~SmallVector()39 ~SmallVector() { 40 clear(); 41 if (PERFETTO_UNLIKELY(is_using_heap())) 42 AlignedFree(begin_); 43 begin_ = end_ = end_of_storage_ = nullptr; 44 } 45 46 // Move operators. noexcept(std::is_nothrow_move_constructible<T>::value)47 SmallVector(SmallVector&& other) noexcept( 48 std::is_nothrow_move_constructible<T>::value) { 49 if (other.is_using_heap()) { 50 // Move the heap content, no need to move the individual objects as their 51 // location won't change. 52 begin_ = other.begin_; 53 end_ = other.end_; 54 end_of_storage_ = other.end_of_storage_; 55 } else { 56 const size_t other_size = other.size(); 57 PERFETTO_DCHECK(other_size <= capacity()); 58 for (size_t i = 0; i < other_size; i++) { 59 // Move the entries and destroy the ones in the moved-from object. 60 new (&begin_[i]) T(std::move(other.begin_[i])); 61 other.begin_[i].~T(); 62 } 63 end_ = begin_ + other_size; 64 } 65 auto* const other_inline_storage = other.inline_storage_begin(); 66 other.end_ = other.begin_ = other_inline_storage; 67 other.end_of_storage_ = other_inline_storage + kInlineSize; 68 } 69 noexcept(std::is_nothrow_move_constructible<T>::value)70 SmallVector& operator=(SmallVector&& other) noexcept( 71 std::is_nothrow_move_constructible<T>::value) { 72 this->~SmallVector(); 73 new (this) SmallVector<T, kSize>(std::move(other)); 74 return *this; 75 } 76 77 // Copy operators. SmallVector(const SmallVector & other)78 SmallVector(const SmallVector& other) { 79 const size_t other_size = other.size(); 80 if (other_size > capacity()) 81 Grow(other_size); 82 // Copy-construct the elements. 83 for (size_t i = 0; i < other_size; ++i) 84 new (&begin_[i]) T(other.begin_[i]); 85 end_ = begin_ + other_size; 86 } 87 88 SmallVector& operator=(const SmallVector& other) { 89 if (PERFETTO_UNLIKELY(this == &other)) 90 return *this; 91 this->~SmallVector(); 92 new (this) SmallVector<T, kSize>(other); 93 return *this; 94 } 95 data()96 T* data() { return begin_; } data()97 const T* data() const { return begin_; } 98 begin()99 T* begin() { return begin_; } begin()100 const T* begin() const { return begin_; } 101 end()102 T* end() { return end_; } end()103 const T* end() const { return end_; } 104 size()105 size_t size() const { return static_cast<size_t>(end_ - begin_); } 106 empty()107 bool empty() const { return end_ == begin_; } 108 capacity()109 size_t capacity() const { 110 return static_cast<size_t>(end_of_storage_ - begin_); 111 } 112 front()113 T& front() { 114 PERFETTO_DCHECK(!empty()); 115 return begin_[0]; 116 } front()117 const T& front() const { 118 PERFETTO_DCHECK(!empty()); 119 return begin_[0]; 120 } 121 back()122 T& back() { 123 PERFETTO_DCHECK(!empty()); 124 return end_[-1]; 125 } back()126 const T& back() const { 127 PERFETTO_DCHECK(!empty()); 128 return end_[-1]; 129 } 130 131 T& operator[](size_t index) { 132 PERFETTO_DCHECK(index < size()); 133 return begin_[index]; 134 } 135 136 const T& operator[](size_t index) const { 137 PERFETTO_DCHECK(index < size()); 138 return begin_[index]; 139 } 140 141 template <typename... Args> emplace_back(Args &&...args)142 void emplace_back(Args&&... args) { 143 T* end = end_; 144 if (PERFETTO_UNLIKELY(end == end_of_storage_)) 145 end = Grow(); 146 new (end) T(std::forward<Args>(args)...); 147 end_ = end + 1; 148 } 149 pop_back()150 void pop_back() { 151 PERFETTO_DCHECK(!empty()); 152 back().~T(); 153 --end_; 154 } 155 156 // Clear without reverting back to inline storage. clear()157 void clear() { 158 while (!empty()) 159 pop_back(); 160 } 161 162 private: 163 PERFETTO_NO_INLINE T* Grow(size_t desired_capacity = 0) { 164 size_t cur_size = size(); 165 size_t new_capacity = desired_capacity; 166 if (desired_capacity <= cur_size) 167 new_capacity = std::max(capacity() * 2, size_t(128)); 168 T* new_storage = 169 static_cast<T*>(AlignedAlloc(alignof(T), new_capacity * sizeof(T))); 170 for (size_t i = 0; i < cur_size; ++i) { 171 // Move the elements into the new heap buffer and destroy the old ones. 172 new (&new_storage[i]) T(std::move(begin_[i])); 173 begin_[i].~T(); 174 } 175 if (is_using_heap()) 176 AlignedFree(begin_); 177 begin_ = new_storage; 178 end_ = new_storage + cur_size; 179 end_of_storage_ = new_storage + new_capacity; 180 return end_; 181 } 182 inline_storage_begin()183 T* inline_storage_begin() { return reinterpret_cast<T*>(&inline_storage_); } is_using_heap()184 bool is_using_heap() { return begin_ != inline_storage_begin(); } 185 186 T* begin_ = inline_storage_begin(); 187 T* end_ = begin_; 188 T* end_of_storage_ = begin_ + kInlineSize; 189 190 typename std::aligned_storage<sizeof(T) * kInlineSize, alignof(T)>::type 191 inline_storage_; 192 }; 193 194 } // namespace base 195 } // namespace perfetto 196 197 #endif // INCLUDE_PERFETTO_EXT_BASE_SMALL_VECTOR_H_ 198