xref: /aosp_15_r20/external/perfetto/src/trace_processor/db/column/utils.h (revision 6dbdd20afdafa5e3ca9b8809fa73465d530080dc)
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_UTILS_H_
17 #define SRC_TRACE_PROCESSOR_DB_COLUMN_UTILS_H_
18 
19 #include <algorithm>
20 #include <cstdint>
21 #include <functional>
22 #include <limits>
23 #include <optional>
24 #include <type_traits>
25 #include <vector>
26 
27 #include "perfetto/base/logging.h"
28 #include "perfetto/trace_processor/basic_types.h"
29 #include "src/trace_processor/containers/bit_vector.h"
30 #include "src/trace_processor/db/column/data_layer.h"
31 #include "src/trace_processor/db/column/types.h"
32 
33 namespace perfetto::trace_processor::column::utils {
34 namespace internal {
35 
36 template <typename T, typename Comparator>
SingleSearchNumeric(T left,const SqlValue & right_v)37 SingleSearchResult SingleSearchNumeric(T left, const SqlValue& right_v) {
38   if constexpr (std::is_same_v<T, double>) {
39     if (right_v.type != SqlValue::kDouble) {
40       // Because of the large amount of code needing for handling comparisons
41       // with integers, just defer to the full search.
42       return SingleSearchResult::kNeedsFullSearch;
43     }
44     return Comparator()(left, right_v.double_value)
45                ? SingleSearchResult::kMatch
46                : SingleSearchResult::kNoMatch;
47   } else if constexpr (std::is_integral_v<T>) {
48     if (right_v.type != SqlValue::kLong ||
49         right_v.long_value > std::numeric_limits<T>::max() ||
50         right_v.long_value < std::numeric_limits<T>::min()) {
51       // Because of the large amount of code needing for handling comparisons
52       // with doubles or out of range values, just defer to the full search.
53       return SingleSearchResult::kNeedsFullSearch;
54     }
55     return Comparator()(left, static_cast<T>(right_v.long_value))
56                ? SingleSearchResult::kMatch
57                : SingleSearchResult::kNoMatch;
58   } else {
59     static_assert(std::is_same_v<T, void>, "Illegal type");
60   }
61 }
62 
63 }  // namespace internal
64 
65 template <typename Comparator, typename ValType, typename DataType>
LinearSearchWithComparator(ValType val,const DataType * data_ptr,Comparator comparator,BitVector::Builder & builder)66 void LinearSearchWithComparator(ValType val,
67                                 const DataType* data_ptr,
68                                 Comparator comparator,
69                                 BitVector::Builder& builder) {
70   // Slow path: we compare <64 elements and append to get us to a word
71   // boundary.
72   const DataType* cur_val = data_ptr;
73   uint32_t front_elements = builder.BitsUntilWordBoundaryOrFull();
74   for (uint32_t i = 0; i < front_elements; ++i, ++cur_val) {
75     builder.Append(comparator(*cur_val, val));
76   }
77 
78   // Fast path: we compare as many groups of 64 elements as we can.
79   // This should be very easy for the compiler to auto-vectorize.
80   uint32_t fast_path_elements = builder.BitsInCompleteWordsUntilFull();
81   for (uint32_t i = 0; i < fast_path_elements; i += BitVector::kBitsInWord) {
82     uint64_t word = 0;
83     // This part should be optimised by SIMD and is expected to be fast.
84     for (uint32_t k = 0; k < BitVector::kBitsInWord; ++k, ++cur_val) {
85       bool comp_result = comparator(*cur_val, val);
86       word |= static_cast<uint64_t>(comp_result) << k;
87     }
88     builder.AppendWord(word);
89   }
90 
91   // Slow path: we compare <64 elements and append to fill the Builder.
92   uint32_t back_elements = builder.BitsUntilFull();
93   for (uint32_t i = 0; i < back_elements; ++i, ++cur_val) {
94     builder.Append(comparator(*cur_val, val));
95   }
96 }
97 
98 template <typename Comparator, typename ValType, typename DataType>
IndexSearchWithComparator(ValType val,const DataType * data_ptr,DataLayerChain::Indices & indices,Comparator comparator)99 void IndexSearchWithComparator(ValType val,
100                                const DataType* data_ptr,
101                                DataLayerChain::Indices& indices,
102                                Comparator comparator) {
103   auto it = std::remove_if(indices.tokens.begin(), indices.tokens.end(),
104                            [&comparator, data_ptr, &val](const Token& token) {
105                              return !comparator(*(data_ptr + token.index), val);
106                            });
107   indices.tokens.erase(it, indices.tokens.end());
108 }
109 
110 template <typename T>
SingleSearchNumeric(FilterOp op,T left,const SqlValue & right_v)111 SingleSearchResult SingleSearchNumeric(FilterOp op,
112                                        T left,
113                                        const SqlValue& right_v) {
114   switch (op) {
115     case FilterOp::kEq:
116       return internal::SingleSearchNumeric<T, std::equal_to<T>>(left, right_v);
117     case FilterOp::kNe:
118       return internal::SingleSearchNumeric<T, std::not_equal_to<T>>(left,
119                                                                     right_v);
120     case FilterOp::kGe:
121       return internal::SingleSearchNumeric<T, std::greater_equal<T>>(left,
122                                                                      right_v);
123     case FilterOp::kGt:
124       return internal::SingleSearchNumeric<T, std::greater<T>>(left, right_v);
125     case FilterOp::kLe:
126       return internal::SingleSearchNumeric<T, std::less_equal<T>>(left,
127                                                                   right_v);
128     case FilterOp::kLt:
129       return internal::SingleSearchNumeric<T, std::less<T>>(left, right_v);
130     case FilterOp::kIsNotNull:
131       return SingleSearchResult::kMatch;
132     case FilterOp::kGlob:
133     case FilterOp::kRegex:
134     case FilterOp::kIsNull:
135       return SingleSearchResult::kNoMatch;
136   }
137   PERFETTO_FATAL("For GCC");
138 }
139 
140 // Used for comparing the integer column ({u|}int{32|64}) with a double value.
141 // If further search is required it would return kOk and change the SqlValue to
142 // a `SqlLong` which would return real results.
143 SearchValidationResult CompareIntColumnWithDouble(FilterOp op,
144                                                   SqlValue* sql_val);
145 
146 // If the validation result doesn't require further search, it will return a
147 // Range that can be passed further. Else it returns nullopt.
148 std::optional<Range> CanReturnEarly(SearchValidationResult, Range);
149 
150 // If the validation result doesn't require further search, it will return a
151 // Range that can be passed further. Else it returns nullopt.
152 std::optional<Range> CanReturnEarly(SearchValidationResult,
153                                     uint32_t indices_size);
154 
155 // If the validation result doesn't require further search, will modify
156 // |indices| to match and return true. Otherwise returns false.
157 bool CanReturnEarly(SearchValidationResult res,
158                     DataLayerChain::Indices& indices);
159 
160 std::vector<uint32_t> ExtractPayloadForTesting(std::vector<Token>&);
161 
162 std::vector<uint32_t> ToIndexVectorForTests(RangeOrBitVector&);
163 
164 std::vector<uint32_t> ExtractPayloadForTesting(const DataLayerChain::Indices&);
165 
166 }  // namespace perfetto::trace_processor::column::utils
167 
168 #endif  // SRC_TRACE_PROCESSOR_DB_COLUMN_UTILS_H_
169