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 back()113 T& back() { 114 PERFETTO_DCHECK(!empty()); 115 return end_[-1]; 116 } back()117 const T& back() const { 118 PERFETTO_DCHECK(!empty()); 119 return end_[-1]; 120 } 121 122 T& operator[](size_t index) { 123 PERFETTO_DCHECK(index < size()); 124 return begin_[index]; 125 } 126 127 const T& operator[](size_t index) const { 128 PERFETTO_DCHECK(index < size()); 129 return begin_[index]; 130 } 131 132 template <typename... Args> emplace_back(Args &&...args)133 void emplace_back(Args&&... args) { 134 T* end = end_; 135 if (PERFETTO_UNLIKELY(end == end_of_storage_)) 136 end = Grow(); 137 new (end) T(std::forward<Args>(args)...); 138 end_ = end + 1; 139 } 140 pop_back()141 void pop_back() { 142 PERFETTO_DCHECK(!empty()); 143 back().~T(); 144 --end_; 145 } 146 147 // Clear without reverting back to inline storage. clear()148 void clear() { 149 while (!empty()) 150 pop_back(); 151 } 152 153 private: 154 PERFETTO_NO_INLINE T* Grow(size_t desired_capacity = 0) { 155 size_t cur_size = size(); 156 size_t new_capacity = desired_capacity; 157 if (desired_capacity <= cur_size) 158 new_capacity = std::max(capacity() * 2, size_t(128)); 159 T* new_storage = 160 static_cast<T*>(AlignedAlloc(alignof(T), new_capacity * sizeof(T))); 161 for (size_t i = 0; i < cur_size; ++i) { 162 // Move the elements into the new heap buffer and destroy the old ones. 163 new (&new_storage[i]) T(std::move(begin_[i])); 164 begin_[i].~T(); 165 } 166 if (is_using_heap()) 167 AlignedFree(begin_); 168 begin_ = new_storage; 169 end_ = new_storage + cur_size; 170 end_of_storage_ = new_storage + new_capacity; 171 return end_; 172 } 173 inline_storage_begin()174 T* inline_storage_begin() { return reinterpret_cast<T*>(&inline_storage_); } is_using_heap()175 bool is_using_heap() { return begin_ != inline_storage_begin(); } 176 177 T* begin_ = inline_storage_begin(); 178 T* end_ = begin_; 179 T* end_of_storage_ = begin_ + kInlineSize; 180 181 typename std::aligned_storage<sizeof(T) * kInlineSize, alignof(T)>::type 182 inline_storage_; 183 }; 184 185 } // namespace base 186 } // namespace perfetto 187 188 #endif // INCLUDE_PERFETTO_EXT_BASE_SMALL_VECTOR_H_ 189