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 <limits> 22 #include <memory> 23 #include <optional> 24 #include <set> 25 #include <string> 26 #include <type_traits> 27 #include <unordered_set> 28 #include <variant> 29 #include <vector> 30 31 #include "perfetto/base/compiler.h" 32 #include "perfetto/trace_processor/basic_types.h" 33 #include "src/trace_processor/containers/bit_vector.h" 34 #include "src/trace_processor/containers/row_map.h" 35 #include "src/trace_processor/db/column/data_layer.h" 36 #include "src/trace_processor/db/column/types.h" 37 #include "src/trace_processor/db/column/utils.h" 38 39 namespace perfetto::trace_processor::column { 40 41 // Storage for all numeric type data (i.e. doubles, int32, int64, uint32). 42 class NumericStorageBase : public DataLayer { 43 protected: 44 class ChainImpl : public DataLayerChain { 45 public: 46 SearchValidationResult ValidateSearchConstraints(FilterOp, 47 SqlValue) const override; 48 49 RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const override; 50 51 void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override; 52 53 void Serialize(StorageProto*) const override; 54 DebugString()55 std::string DebugString() const override { return "NumericStorage"; } 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 90 // The implementation of this function is given by 91 // make_chain.cc/make_chain_minimal.cc depending on whether this is a minimal 92 // or full build of trace processor. 93 std::unique_ptr<DataLayerChain> MakeChain(); 94 95 private: 96 class ChainImpl : public NumericStorageBase::ChainImpl { 97 public: ChainImpl(const std::vector<T> * vector,ColumnType type,bool is_sorted)98 ChainImpl(const std::vector<T>* vector, ColumnType type, bool is_sorted) 99 : NumericStorageBase::ChainImpl(vector, type, is_sorted), 100 vector_(vector) {} 101 SingleSearch(FilterOp op,SqlValue sql_val,uint32_t i)102 SingleSearchResult SingleSearch(FilterOp op, 103 SqlValue sql_val, 104 uint32_t i) const override { 105 return utils::SingleSearchNumeric(op, (*vector_)[i], sql_val); 106 } 107 Distinct(Indices & indices)108 void Distinct(Indices& indices) const override { 109 std::unordered_set<T> s; 110 indices.tokens.erase( 111 std::remove_if(indices.tokens.begin(), indices.tokens.end(), 112 [&s, this](const Token& idx) { 113 return !s.insert((*vector_)[idx.index]).second; 114 }), 115 indices.tokens.end()); 116 } 117 MaxElement(Indices & indices)118 std::optional<Token> MaxElement(Indices& indices) const override { 119 auto tok = 120 std::max_element(indices.tokens.begin(), indices.tokens.end(), 121 [this](const Token& t1, const Token& t2) { 122 return (*vector_)[t1.index] < (*vector_)[t2.index]; 123 }); 124 125 if (tok == indices.tokens.end()) { 126 return std::nullopt; 127 } 128 129 return *tok; 130 } 131 MinElement(Indices & indices)132 std::optional<Token> MinElement(Indices& indices) const override { 133 auto tok = 134 std::min_element(indices.tokens.begin(), indices.tokens.end(), 135 [this](const Token& t1, const Token& t2) { 136 return (*vector_)[t1.index] < (*vector_)[t2.index]; 137 }); 138 if (tok == indices.tokens.end()) { 139 return std::nullopt; 140 } 141 142 return *tok; 143 } 144 Get_AvoidUsingBecauseSlow(uint32_t index)145 SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const override { 146 if constexpr (std::is_same_v<T, double>) { 147 return SqlValue::Double((*vector_)[index]); 148 } 149 return SqlValue::Long((*vector_)[index]); 150 } 151 StableSort(SortToken * start,SortToken * end,SortDirection direction)152 void StableSort(SortToken* start, 153 SortToken* end, 154 SortDirection direction) const override { 155 const T* base = vector_->data(); 156 switch (direction) { 157 case SortDirection::kAscending: 158 std::stable_sort(start, end, 159 [base](const SortToken& a, const SortToken& b) { 160 return base[a.index] < base[b.index]; 161 }); 162 break; 163 case SortDirection::kDescending: 164 std::stable_sort(start, end, 165 [base](const SortToken& a, const SortToken& b) { 166 return base[a.index] > base[b.index]; 167 }); 168 break; 169 } 170 } 171 size()172 uint32_t size() const override { 173 return static_cast<uint32_t>(vector_->size()); 174 } 175 176 private: 177 const std::vector<T>* vector_; 178 }; GetImpl()179 Impl GetImpl() { 180 if constexpr (std::is_same_v<T, double>) { 181 return Impl::kNumericDouble; 182 } else if constexpr (std::is_same_v<T, uint32_t>) { 183 return Impl::kNumericUint32; 184 } else if constexpr (std::is_same_v<T, int32_t>) { 185 return Impl::kNumericInt32; 186 } else if constexpr (std::is_same_v<T, int64_t>) { 187 return Impl::kNumericInt64; 188 } else { 189 // false doesn't work as expression has to depend on the template 190 // parameter 191 static_assert(sizeof(T*) == 0, "T is not supported"); 192 } 193 } 194 195 const std::vector<T>* vector_; 196 }; 197 198 // Define external templates to reduce binary size bloat. 199 extern template class NumericStorage<double>; 200 extern template class NumericStorage<uint32_t>; 201 extern template class NumericStorage<int32_t>; 202 extern template class NumericStorage<int64_t>; 203 204 // Define external templates to allow splitting minimal vs full targets. 205 extern template std::unique_ptr<DataLayerChain> 206 NumericStorage<double>::MakeChain(); 207 extern template std::unique_ptr<DataLayerChain> 208 NumericStorage<uint32_t>::MakeChain(); 209 extern template std::unique_ptr<DataLayerChain> 210 NumericStorage<int32_t>::MakeChain(); 211 extern template std::unique_ptr<DataLayerChain> 212 NumericStorage<int64_t>::MakeChain(); 213 214 } // namespace perfetto::trace_processor::column 215 216 #endif // SRC_TRACE_PROCESSOR_DB_COLUMN_NUMERIC_STORAGE_H_ 217