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