1 /* 2 * Copyright (C) 2023 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 #ifndef SRC_TRACE_PROCESSOR_DB_COLUMN_NUMERIC_STORAGE_H_ 17 #define SRC_TRACE_PROCESSOR_DB_COLUMN_NUMERIC_STORAGE_H_ 18 19 #include <algorithm> 20 #include <cstdint> 21 #include <memory> 22 #include <optional> 23 #include <string> 24 #include <type_traits> 25 #include <unordered_set> 26 #include <variant> 27 #include <vector> 28 29 #include "perfetto/public/compiler.h" 30 #include "perfetto/trace_processor/basic_types.h" 31 #include "src/trace_processor/containers/bit_vector.h" 32 #include "src/trace_processor/db/column/data_layer.h" 33 #include "src/trace_processor/db/column/storage_layer.h" 34 #include "src/trace_processor/db/column/types.h" 35 #include "src/trace_processor/db/column/utils.h" 36 37 namespace perfetto::trace_processor::column { 38 39 // Storage for all numeric type data (i.e. doubles, int32, int64, uint32). 40 class NumericStorageBase : public StorageLayer { 41 protected: 42 class ChainImpl : public DataLayerChain { 43 public: 44 SearchValidationResult ValidateSearchConstraints(FilterOp, 45 SqlValue) const override; 46 47 RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const override; 48 49 void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override; 50 DebugString()51 std::string DebugString() const override { return "NumericStorage"; } 52 is_sorted()53 bool is_sorted() const { return is_sorted_; } 54 column_type()55 ColumnType column_type() const { return storage_type_; } 56 57 protected: 58 ChainImpl(const void* vector_ptr, ColumnType type, bool is_sorted); 59 60 private: 61 // All viable numeric values for ColumnTypes. 62 using NumericValue = std::variant<uint32_t, int32_t, int64_t, double>; 63 64 BitVector LinearSearchInternal(FilterOp op, NumericValue val, Range) const; 65 66 Range BinarySearchIntrinsic(FilterOp op, 67 NumericValue val, 68 Range search_range) const; 69 70 const void* vector_ptr_ = nullptr; 71 const ColumnType storage_type_ = ColumnType::kDummy; 72 const bool is_sorted_ = false; 73 }; 74 75 NumericStorageBase(ColumnType type, bool is_sorted, Impl impl); 76 ~NumericStorageBase() override; 77 78 const ColumnType storage_type_ = ColumnType::kDummy; 79 const bool is_sorted_ = false; 80 }; 81 82 // Storage for all numeric type data (i.e. doubles, int32, int64, uint32). 83 template <typename T> 84 class NumericStorage final : public NumericStorageBase { 85 public: 86 PERFETTO_NO_INLINE NumericStorage(const std::vector<T>* vec, 87 ColumnType type, 88 bool is_sorted); 89 GetStoragePtr()90 StoragePtr GetStoragePtr() override { return vector_->data(); } 91 92 // The implementation of this function is given by 93 // make_chain.cc/make_chain_minimal.cc depending on whether this is a minimal 94 // or full build of trace processor. 95 std::unique_ptr<DataLayerChain> MakeChain(); 96 97 private: 98 class ChainImpl : public NumericStorageBase::ChainImpl { 99 public: ChainImpl(const std::vector<T> * vector,ColumnType type,bool is_sorted)100 ChainImpl(const std::vector<T>* vector, ColumnType type, bool is_sorted) 101 : NumericStorageBase::ChainImpl(vector, type, is_sorted), 102 vector_(vector) {} 103 SingleSearch(FilterOp op,SqlValue sql_val,uint32_t i)104 SingleSearchResult SingleSearch(FilterOp op, 105 SqlValue sql_val, 106 uint32_t i) const override { 107 return utils::SingleSearchNumeric(op, (*vector_)[i], sql_val); 108 } 109 Distinct(Indices & indices)110 void Distinct(Indices& indices) const override { 111 std::unordered_set<T> s; 112 indices.tokens.erase( 113 std::remove_if(indices.tokens.begin(), indices.tokens.end(), 114 [&s, this](const Token& idx) { 115 return !s.insert((*vector_)[idx.index]).second; 116 }), 117 indices.tokens.end()); 118 } 119 MaxElement(Indices & indices)120 std::optional<Token> MaxElement(Indices& indices) const override { 121 auto tok = 122 std::max_element(indices.tokens.begin(), indices.tokens.end(), 123 [this](const Token& t1, const Token& t2) { 124 return (*vector_)[t1.index] < (*vector_)[t2.index]; 125 }); 126 return tok == indices.tokens.end() ? std::nullopt 127 : std::make_optional(*tok); 128 } 129 MinElement(Indices & indices)130 std::optional<Token> MinElement(Indices& indices) const override { 131 auto tok = 132 std::min_element(indices.tokens.begin(), indices.tokens.end(), 133 [this](const Token& t1, const Token& t2) { 134 return (*vector_)[t1.index] < (*vector_)[t2.index]; 135 }); 136 return tok == indices.tokens.end() ? std::nullopt 137 : std::make_optional(*tok); 138 } 139 Get_AvoidUsingBecauseSlow(uint32_t index)140 SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const override { 141 if constexpr (std::is_same_v<T, double>) { 142 return SqlValue::Double((*vector_)[index]); 143 } 144 return SqlValue::Long((*vector_)[index]); 145 } 146 StableSort(Token * start,Token * end,SortDirection direction)147 void StableSort(Token* start, 148 Token* end, 149 SortDirection direction) const override { 150 const T* base = vector_->data(); 151 switch (direction) { 152 case SortDirection::kAscending: 153 std::stable_sort(start, end, [base](const Token& a, const Token& b) { 154 return base[a.index] < base[b.index]; 155 }); 156 break; 157 case SortDirection::kDescending: 158 std::stable_sort(start, end, [base](const Token& a, const Token& b) { 159 return base[a.index] > base[b.index]; 160 }); 161 break; 162 } 163 } 164 size()165 uint32_t size() const override { 166 return static_cast<uint32_t>(vector_->size()); 167 } 168 169 private: 170 const std::vector<T>* vector_; 171 }; GetImpl()172 Impl GetImpl() { 173 if constexpr (std::is_same_v<T, double>) { 174 return Impl::kNumericDouble; 175 } else if constexpr (std::is_same_v<T, uint32_t>) { 176 return Impl::kNumericUint32; 177 } else if constexpr (std::is_same_v<T, int32_t>) { 178 return Impl::kNumericInt32; 179 } else if constexpr (std::is_same_v<T, int64_t>) { 180 return Impl::kNumericInt64; 181 } else { 182 // false doesn't work as expression has to depend on the template 183 // parameter 184 static_assert(sizeof(T*) == 0, "T is not supported"); 185 } 186 } 187 188 const std::vector<T>* vector_; 189 }; 190 191 // Define external templates to reduce binary size bloat. 192 extern template class NumericStorage<double>; 193 extern template class NumericStorage<uint32_t>; 194 extern template class NumericStorage<int32_t>; 195 extern template class NumericStorage<int64_t>; 196 197 // Define external templates to allow splitting minimal vs full targets. 198 extern template std::unique_ptr<DataLayerChain> 199 NumericStorage<double>::MakeChain(); 200 extern template std::unique_ptr<DataLayerChain> 201 NumericStorage<uint32_t>::MakeChain(); 202 extern template std::unique_ptr<DataLayerChain> 203 NumericStorage<int32_t>::MakeChain(); 204 extern template std::unique_ptr<DataLayerChain> 205 NumericStorage<int64_t>::MakeChain(); 206 207 } // namespace perfetto::trace_processor::column 208 209 #endif // SRC_TRACE_PROCESSOR_DB_COLUMN_NUMERIC_STORAGE_H_ 210