xref: /aosp_15_r20/external/perfetto/src/trace_processor/db/column/string_storage.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_STRING_STORAGE_H_
17 #define SRC_TRACE_PROCESSOR_DB_COLUMN_STRING_STORAGE_H_
18 
19 #include <cstdint>
20 #include <memory>
21 #include <optional>
22 #include <string>
23 #include <vector>
24 
25 #include "perfetto/trace_processor/basic_types.h"
26 #include "src/trace_processor/containers/bit_vector.h"
27 #include "src/trace_processor/containers/string_pool.h"
28 #include "src/trace_processor/db/column/data_layer.h"
29 #include "src/trace_processor/db/column/storage_layer.h"
30 #include "src/trace_processor/db/column/types.h"
31 
32 namespace perfetto::trace_processor::column {
33 
34 // Storage for String columns.
35 class StringStorage final : public StorageLayer {
36  public:
37   StringStorage(StringPool* string_pool,
38                 const std::vector<StringPool::Id>* data,
39                 bool is_sorted = false);
40   ~StringStorage() override;
41 
42   std::unique_ptr<DataLayerChain> MakeChain();
43   StoragePtr GetStoragePtr() override;
44 
45  private:
46   class ChainImpl : public DataLayerChain {
47    public:
48     ChainImpl(StringPool* string_pool,
49               const std::vector<StringPool::Id>* data,
50               bool is_sorted);
51 
52     SingleSearchResult SingleSearch(FilterOp,
53                                     SqlValue,
54                                     uint32_t) const override;
55 
56     SearchValidationResult ValidateSearchConstraints(FilterOp,
57                                                      SqlValue) const override;
58 
59     RangeOrBitVector SearchValidated(FilterOp, SqlValue, Range) const override;
60 
61     void IndexSearchValidated(FilterOp, SqlValue, Indices&) const override;
62 
63     void StableSort(Token* start,
64                     Token* end,
65                     SortDirection direction) const override;
66 
67     void Distinct(Indices&) const override;
68 
69     std::optional<Token> MaxElement(Indices&) const override;
70 
71     std::optional<Token> MinElement(Indices&) const override;
72 
73     SqlValue Get_AvoidUsingBecauseSlow(uint32_t index) const override;
74 
size()75     uint32_t size() const override {
76       return static_cast<uint32_t>(data_->size());
77     }
78 
DebugString()79     std::string DebugString() const override { return "StringStorage"; }
80 
81    private:
82     BitVector LinearSearch(FilterOp, SqlValue, Range) const;
83 
84     RangeOrBitVector IndexSearchInternal(FilterOp op,
85                                          SqlValue sql_val,
86                                          const uint32_t* indices,
87                                          uint32_t indices_size) const;
88 
89     Range BinarySearchIntrinsic(FilterOp op,
90                                 SqlValue val,
91                                 Range search_range) const;
92 
LessForTokens(const Token & lhs,const Token & rhs)93     inline bool LessForTokens(const Token& lhs, const Token& rhs) const {
94       // If RHS is NULL, we know that LHS is not less than
95       // NULL, as nothing is less then null. This check is
96       // only required to keep the stability of the sort.
97       if ((*data_)[rhs.index] == StringPool::Id::Null()) {
98         return false;
99       }
100 
101       // If LHS is NULL, it will always be smaller than any
102       // RHS value.
103       if ((*data_)[lhs.index] == StringPool::Id::Null()) {
104         return true;
105       }
106 
107       // If neither LHS or RHS are NULL, we have to simply
108       // check which string is smaller.
109       return string_pool_->Get((*data_)[lhs.index]) <
110              string_pool_->Get((*data_)[rhs.index]);
111     }
112 
113     // TODO(b/307482437): After the migration vectors should be owned by
114     // storage, so change from pointer to value.
115     const std::vector<StringPool::Id>* data_ = nullptr;
116     StringPool* string_pool_ = nullptr;
117     const bool is_sorted_ = false;
118   };
119 
120   const std::vector<StringPool::Id>* data_ = nullptr;
121   StringPool* string_pool_ = nullptr;
122   const bool is_sorted_ = false;
123 };
124 
125 }  // namespace perfetto::trace_processor::column
126 
127 #endif  // SRC_TRACE_PROCESSOR_DB_COLUMN_STRING_STORAGE_H_
128