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
17 #include "src/trace_processor/db/column/string_storage.h"
18
19 #include <algorithm>
20 #include <cstdint>
21 #include <functional>
22 #include <iterator>
23 #include <memory>
24 #include <optional>
25 #include <string>
26 #include <unordered_set>
27 #include <utility>
28 #include <vector>
29
30 #include "perfetto/base/logging.h"
31 #include "perfetto/ext/base/status_or.h"
32 #include "perfetto/ext/base/string_view.h"
33 #include "perfetto/trace_processor/basic_types.h"
34 #include "src/trace_processor/containers/bit_vector.h"
35 #include "src/trace_processor/containers/null_term_string_view.h"
36 #include "src/trace_processor/containers/string_pool.h"
37 #include "src/trace_processor/db/column/data_layer.h"
38 #include "src/trace_processor/db/column/types.h"
39 #include "src/trace_processor/db/column/utils.h"
40 #include "src/trace_processor/tp_metatrace.h"
41 #include "src/trace_processor/util/glob.h"
42 #include "src/trace_processor/util/regex.h"
43
44 #include "protos/perfetto/trace_processor/metatrace_categories.pbzero.h"
45
46 namespace perfetto::trace_processor::column {
47
48 namespace {
49
50 struct Greater {
operator ()perfetto::trace_processor::column::__anonc994ea840111::Greater51 bool operator()(StringPool::Id lhs, NullTermStringView rhs) const {
52 return lhs != StringPool::Id::Null() && pool_->Get(lhs) > rhs;
53 }
54 const StringPool* pool_;
55 };
56
57 struct GreaterEqual {
operator ()perfetto::trace_processor::column::__anonc994ea840111::GreaterEqual58 bool operator()(StringPool::Id lhs, NullTermStringView rhs) const {
59 return lhs != StringPool::Id::Null() && pool_->Get(lhs) >= rhs;
60 }
61 const StringPool* pool_;
62 };
63
64 struct Less {
operator ()perfetto::trace_processor::column::__anonc994ea840111::Less65 bool operator()(StringPool::Id lhs, NullTermStringView rhs) const {
66 return lhs != StringPool::Id::Null() && pool_->Get(lhs) < rhs;
67 }
68 const StringPool* pool_;
69 };
70
71 struct LessEqual {
operator ()perfetto::trace_processor::column::__anonc994ea840111::LessEqual72 bool operator()(StringPool::Id lhs, NullTermStringView rhs) const {
73 return lhs != StringPool::Id::Null() && pool_->Get(lhs) <= rhs;
74 }
75 const StringPool* pool_;
76 };
77
78 struct NotEqual {
operator ()perfetto::trace_processor::column::__anonc994ea840111::NotEqual79 bool operator()(StringPool::Id lhs, StringPool::Id rhs) const {
80 return lhs != StringPool::Id::Null() && lhs != rhs;
81 }
82 };
83
84 struct Glob {
operator ()perfetto::trace_processor::column::__anonc994ea840111::Glob85 bool operator()(StringPool::Id lhs, const util::GlobMatcher& matcher) const {
86 return lhs != StringPool::Id::Null() && matcher.Matches(pool_->Get(lhs));
87 }
88 const StringPool* pool_;
89 };
90
91 struct GlobFullStringPool {
GlobFullStringPoolperfetto::trace_processor::column::__anonc994ea840111::GlobFullStringPool92 GlobFullStringPool(StringPool* pool, const util::GlobMatcher& matcher)
93 : pool_(pool), matches_(pool->MaxSmallStringId().raw_id()) {
94 PERFETTO_DCHECK(!pool->HasLargeString());
95 for (auto it = pool->CreateIterator(); it; ++it) {
96 auto id = it.StringId();
97 matches_[id.raw_id()] = matcher.Matches(pool->Get(id));
98 }
99 }
operator ()perfetto::trace_processor::column::__anonc994ea840111::GlobFullStringPool100 bool operator()(StringPool::Id lhs, StringPool::Id) const {
101 return lhs != StringPool::Id::Null() && matches_[lhs.raw_id()];
102 }
103 StringPool* pool_;
104 std::vector<uint8_t> matches_;
105 };
106
107 struct Regex {
operator ()perfetto::trace_processor::column::__anonc994ea840111::Regex108 bool operator()(StringPool::Id lhs, const regex::Regex& pattern) const {
109 return lhs != StringPool::Id::Null() &&
110 pattern.Search(pool_->Get(lhs).c_str());
111 }
112 const StringPool* pool_;
113 };
114
115 struct RegexFullStringPool {
RegexFullStringPoolperfetto::trace_processor::column::__anonc994ea840111::RegexFullStringPool116 RegexFullStringPool(StringPool* pool, const regex::Regex& regex)
117 : pool_(pool), matches_(pool->MaxSmallStringId().raw_id()) {
118 PERFETTO_DCHECK(!pool->HasLargeString());
119 for (auto it = pool->CreateIterator(); it; ++it) {
120 auto id = it.StringId();
121 matches_[id.raw_id()] =
122 id != StringPool::Id::Null() && regex.Search(pool_->Get(id).c_str());
123 }
124 }
operator ()perfetto::trace_processor::column::__anonc994ea840111::RegexFullStringPool125 bool operator()(StringPool::Id lhs, StringPool::Id) const {
126 return matches_[lhs.raw_id()];
127 }
128 StringPool* pool_;
129 std::vector<uint8_t> matches_;
130 };
131
132 struct IsNull {
operator ()perfetto::trace_processor::column::__anonc994ea840111::IsNull133 bool operator()(StringPool::Id lhs, StringPool::Id) const {
134 return lhs == StringPool::Id::Null();
135 }
136 };
137
138 struct IsNotNull {
operator ()perfetto::trace_processor::column::__anonc994ea840111::IsNotNull139 bool operator()(StringPool::Id lhs, StringPool::Id) const {
140 return lhs != StringPool::Id::Null();
141 }
142 };
143
LowerBoundIntrinsic(StringPool * pool,const StringPool::Id * data,NullTermStringView val,Range search_range)144 uint32_t LowerBoundIntrinsic(StringPool* pool,
145 const StringPool::Id* data,
146 NullTermStringView val,
147 Range search_range) {
148 const auto* lower = std::lower_bound(
149 data + search_range.start, data + search_range.end, val, Less{pool});
150 return static_cast<uint32_t>(std::distance(data, lower));
151 }
152
UpperBoundIntrinsic(StringPool * pool,const StringPool::Id * data,NullTermStringView val,Range search_range)153 uint32_t UpperBoundIntrinsic(StringPool* pool,
154 const StringPool::Id* data,
155 NullTermStringView val,
156 Range search_range) {
157 Greater comp{pool};
158 const auto* upper =
159 std::upper_bound(data + search_range.start, data + search_range.end, val,
160 [comp](NullTermStringView val, StringPool::Id id) {
161 return comp(id, val);
162 });
163 return static_cast<uint32_t>(std::distance(data, upper));
164 }
165
166 } // namespace
167
GetStoragePtr()168 StringStorage::StoragePtr StringStorage::GetStoragePtr() {
169 return data_->data();
170 }
171
ChainImpl(StringPool * string_pool,const std::vector<StringPool::Id> * data,bool is_sorted)172 StringStorage::ChainImpl::ChainImpl(StringPool* string_pool,
173 const std::vector<StringPool::Id>* data,
174 bool is_sorted)
175 : data_(data), string_pool_(string_pool), is_sorted_(is_sorted) {}
176
SingleSearch(FilterOp op,SqlValue sql_val,uint32_t i) const177 SingleSearchResult StringStorage::ChainImpl::SingleSearch(FilterOp op,
178 SqlValue sql_val,
179 uint32_t i) const {
180 if (sql_val.type == SqlValue::kNull) {
181 if (op == FilterOp::kIsNull) {
182 return IsNull()((*data_)[i], StringPool::Id::Null())
183 ? SingleSearchResult::kMatch
184 : SingleSearchResult::kNoMatch;
185 }
186 if (op == FilterOp::kIsNotNull) {
187 return IsNotNull()((*data_)[i], StringPool::Id::Null())
188 ? SingleSearchResult::kMatch
189 : SingleSearchResult::kNoMatch;
190 }
191 return SingleSearchResult::kNeedsFullSearch;
192 }
193
194 if (sql_val.type != SqlValue::kString) {
195 return SingleSearchResult::kNeedsFullSearch;
196 }
197
198 switch (op) {
199 case FilterOp::kEq: {
200 std::optional<StringPool::Id> id =
201 string_pool_->GetId(base::StringView(sql_val.string_value));
202 return id && std::equal_to<>()((*data_)[i], *id)
203 ? SingleSearchResult::kMatch
204 : SingleSearchResult::kNoMatch;
205 }
206 case FilterOp::kNe: {
207 std::optional<StringPool::Id> id =
208 string_pool_->GetId(base::StringView(sql_val.string_value));
209 return !id || NotEqual()((*data_)[i], *id) ? SingleSearchResult::kMatch
210 : SingleSearchResult::kNoMatch;
211 }
212 case FilterOp::kGe:
213 return GreaterEqual{string_pool_}(
214 (*data_)[i], NullTermStringView(sql_val.string_value))
215 ? SingleSearchResult::kMatch
216 : SingleSearchResult::kNoMatch;
217 case FilterOp::kGt:
218 return Greater{string_pool_}((*data_)[i],
219 NullTermStringView(sql_val.string_value))
220 ? SingleSearchResult::kMatch
221 : SingleSearchResult::kNoMatch;
222 case FilterOp::kLe:
223 return LessEqual{string_pool_}((*data_)[i],
224 NullTermStringView(sql_val.string_value))
225 ? SingleSearchResult::kMatch
226 : SingleSearchResult::kNoMatch;
227 case FilterOp::kLt:
228 return Less{string_pool_}((*data_)[i],
229 NullTermStringView(sql_val.string_value))
230 ? SingleSearchResult::kMatch
231 : SingleSearchResult::kNoMatch;
232 case FilterOp::kGlob: {
233 util::GlobMatcher matcher =
234 util::GlobMatcher::FromPattern(sql_val.string_value);
235 return Glob{string_pool_}((*data_)[i], matcher)
236 ? SingleSearchResult::kMatch
237 : SingleSearchResult::kNoMatch;
238 }
239 case FilterOp::kRegex: {
240 // Caller should ensure that the regex is valid.
241 base::StatusOr<regex::Regex> regex =
242 regex::Regex::Create(sql_val.AsString());
243 PERFETTO_CHECK(regex.status().ok());
244 return Regex{string_pool_}((*data_)[i], regex.value())
245 ? SingleSearchResult::kMatch
246 : SingleSearchResult::kNoMatch;
247 }
248 case FilterOp::kIsNull:
249 case FilterOp::kIsNotNull:
250 PERFETTO_FATAL("Already handled above");
251 }
252 PERFETTO_FATAL("For GCC");
253 }
254
ValidateSearchConstraints(FilterOp op,SqlValue val) const255 SearchValidationResult StringStorage::ChainImpl::ValidateSearchConstraints(
256 FilterOp op,
257 SqlValue val) const {
258 // Type checks.
259 switch (val.type) {
260 case SqlValue::kNull:
261 if (op != FilterOp::kIsNotNull && op != FilterOp::kIsNull) {
262 return SearchValidationResult::kNoData;
263 }
264 break;
265 case SqlValue::kString:
266 break;
267 case SqlValue::kLong:
268 case SqlValue::kDouble:
269 // Any string is always more than any numeric.
270 if (op == FilterOp::kGt || op == FilterOp::kGe) {
271 return SearchValidationResult::kAllData;
272 }
273 return SearchValidationResult::kNoData;
274 case SqlValue::kBytes:
275 return SearchValidationResult::kNoData;
276 }
277
278 return SearchValidationResult::kOk;
279 }
280
SearchValidated(FilterOp op,SqlValue sql_val,Range search_range) const281 RangeOrBitVector StringStorage::ChainImpl::SearchValidated(
282 FilterOp op,
283 SqlValue sql_val,
284 Range search_range) const {
285 PERFETTO_TP_TRACE(metatrace::Category::DB, "StringStorage::ChainImpl::Search",
286 [&search_range, op](metatrace::Record* r) {
287 r->AddArg("Start", std::to_string(search_range.start));
288 r->AddArg("End", std::to_string(search_range.end));
289 r->AddArg("Op",
290 std::to_string(static_cast<uint32_t>(op)));
291 });
292 const StringPool::Id* start = data_->data();
293 if (is_sorted_) {
294 switch (op) {
295 case FilterOp::kEq:
296 case FilterOp::kGe:
297 case FilterOp::kGt:
298 case FilterOp::kLe:
299 case FilterOp::kLt: {
300 auto first_non_null = static_cast<uint32_t>(std::distance(
301 start, std::partition_point(start + search_range.start,
302 start + search_range.end,
303 [](StringPool::Id id) {
304 return id == StringPool::Id::Null();
305 })));
306 return RangeOrBitVector(BinarySearchIntrinsic(
307 op, sql_val,
308 {std::max(search_range.start, first_non_null), search_range.end}));
309 }
310 case FilterOp::kNe: {
311 // Not equal is a special operation on binary search, as it doesn't
312 // define a range, and rather just `not` range returned with `equal`
313 // operation on non null values.
314 auto first_non_null = static_cast<uint32_t>(std::distance(
315 start, std::partition_point(start + search_range.start,
316 start + search_range.end,
317 [](StringPool::Id id) {
318 return id == StringPool::Id::Null();
319 })));
320 Range ret = BinarySearchIntrinsic(
321 FilterOp::kEq, sql_val,
322 {std::max(search_range.start, first_non_null), search_range.end});
323 BitVector bv(first_non_null, false);
324 bv.Resize(ret.start, true);
325 bv.Resize(ret.end, false);
326 bv.Resize(search_range.end, true);
327 return RangeOrBitVector(std::move(bv));
328 }
329 case FilterOp::kGlob:
330 case FilterOp::kRegex:
331 case FilterOp::kIsNull:
332 case FilterOp::kIsNotNull:
333 // Those operations can't be binary searched so we fall back on not
334 // sorted algorithm.
335 break;
336 }
337 }
338 return RangeOrBitVector(LinearSearch(op, sql_val, search_range));
339 }
340
IndexSearchValidated(FilterOp op,SqlValue sql_val,Indices & indices) const341 void StringStorage::ChainImpl::IndexSearchValidated(FilterOp op,
342 SqlValue sql_val,
343 Indices& indices) const {
344 PERFETTO_DCHECK(indices.tokens.size() <= size());
345 PERFETTO_TP_TRACE(
346 metatrace::Category::DB, "StringStorage::ChainImpl::IndexSearch",
347 [&indices, op](metatrace::Record* r) {
348 r->AddArg("Count", std::to_string(indices.tokens.size()));
349 r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
350 });
351
352 StringPool::Id val =
353 (op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
354 ? StringPool::Id::Null()
355 : string_pool_->InternString(base::StringView(sql_val.AsString()));
356 const StringPool::Id* start = data_->data();
357 switch (op) {
358 case FilterOp::kEq:
359 utils::IndexSearchWithComparator(val, start, indices, std::equal_to<>());
360 break;
361 case FilterOp::kNe:
362 utils::IndexSearchWithComparator(val, start, indices, NotEqual());
363 break;
364 case FilterOp::kLe:
365 utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
366 LessEqual{string_pool_});
367 break;
368 case FilterOp::kLt:
369 utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
370 Less{string_pool_});
371 break;
372 case FilterOp::kGt:
373 utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
374 Greater{string_pool_});
375 break;
376 case FilterOp::kGe:
377 utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
378 GreaterEqual{string_pool_});
379 break;
380 case FilterOp::kGlob: {
381 util::GlobMatcher matcher =
382 util::GlobMatcher::FromPattern(sql_val.AsString());
383 if (matcher.IsEquality()) {
384 utils::IndexSearchWithComparator(val, start, indices,
385 std::equal_to<>());
386 break;
387 }
388 utils::IndexSearchWithComparator(std::move(matcher), start, indices,
389 Glob{string_pool_});
390 break;
391 }
392 case FilterOp::kRegex: {
393 base::StatusOr<regex::Regex> regex =
394 regex::Regex::Create(sql_val.AsString());
395 utils::IndexSearchWithComparator(std::move(regex.value()), start, indices,
396 Regex{string_pool_});
397 break;
398 }
399 case FilterOp::kIsNull:
400 utils::IndexSearchWithComparator(val, start, indices, IsNull());
401 break;
402 case FilterOp::kIsNotNull:
403 utils::IndexSearchWithComparator(val, start, indices, IsNotNull());
404 break;
405 }
406 }
407
LinearSearch(FilterOp op,SqlValue sql_val,Range range) const408 BitVector StringStorage::ChainImpl::LinearSearch(FilterOp op,
409 SqlValue sql_val,
410 Range range) const {
411 StringPool::Id val =
412 (op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
413 ? StringPool::Id::Null()
414 : string_pool_->InternString(base::StringView(sql_val.AsString()));
415
416 const StringPool::Id* start = data_->data() + range.start;
417
418 BitVector::Builder builder(range.end, range.start);
419 switch (op) {
420 case FilterOp::kEq:
421 utils::LinearSearchWithComparator(val, start, std::equal_to<>(), builder);
422 break;
423 case FilterOp::kNe:
424 utils::LinearSearchWithComparator(val, start, NotEqual(), builder);
425 break;
426 case FilterOp::kLe:
427 utils::LinearSearchWithComparator(string_pool_->Get(val), start,
428 LessEqual{string_pool_}, builder);
429 break;
430 case FilterOp::kLt:
431 utils::LinearSearchWithComparator(string_pool_->Get(val), start,
432 Less{string_pool_}, builder);
433 break;
434 case FilterOp::kGt:
435 utils::LinearSearchWithComparator(string_pool_->Get(val), start,
436 Greater{string_pool_}, builder);
437 break;
438 case FilterOp::kGe:
439 utils::LinearSearchWithComparator(string_pool_->Get(val), start,
440 GreaterEqual{string_pool_}, builder);
441 break;
442 case FilterOp::kGlob: {
443 util::GlobMatcher matcher =
444 util::GlobMatcher::FromPattern(sql_val.AsString());
445
446 // If glob pattern doesn't involve any special characters, the function
447 // called should be equality.
448 if (matcher.IsEquality()) {
449 utils::LinearSearchWithComparator(val, start, std::equal_to<>(),
450 builder);
451 break;
452 }
453
454 // For very big string pools (or small ranges) or pools with large strings
455 // run a standard glob function.
456 if (range.size() < string_pool_->size() ||
457 string_pool_->HasLargeString()) {
458 utils::LinearSearchWithComparator(std::move(matcher), start,
459 Glob{string_pool_}, builder);
460 break;
461 }
462
463 utils::LinearSearchWithComparator(
464 StringPool::Id::Null(), start,
465 GlobFullStringPool{string_pool_, matcher}, builder);
466 break;
467 }
468 case FilterOp::kRegex: {
469 // Caller should ensure that the regex is valid.
470 base::StatusOr<regex::Regex> regex =
471 regex::Regex::Create(sql_val.AsString());
472 PERFETTO_CHECK(regex.status().ok());
473
474 // For very big string pools (or small ranges) or pools with large
475 // strings run a standard regex function.
476 if (range.size() < string_pool_->size() ||
477 string_pool_->HasLargeString()) {
478 utils::LinearSearchWithComparator(std::move(regex.value()), start,
479 Regex{string_pool_}, builder);
480 break;
481 }
482 utils::LinearSearchWithComparator(
483 StringPool::Id::Null(), start,
484 RegexFullStringPool{string_pool_, regex.value()}, builder);
485 break;
486 }
487 case FilterOp::kIsNull:
488 utils::LinearSearchWithComparator(val, start, IsNull(), builder);
489 break;
490 case FilterOp::kIsNotNull:
491 utils::LinearSearchWithComparator(val, start, IsNotNull(), builder);
492 }
493
494 return std::move(builder).Build();
495 }
496
BinarySearchIntrinsic(FilterOp op,SqlValue sql_val,Range search_range) const497 Range StringStorage::ChainImpl::BinarySearchIntrinsic(
498 FilterOp op,
499 SqlValue sql_val,
500 Range search_range) const {
501 StringPool::Id val =
502 (op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
503 ? StringPool::Id::Null()
504 : string_pool_->InternString(base::StringView(sql_val.AsString()));
505 NullTermStringView val_str = string_pool_->Get(val);
506
507 switch (op) {
508 case FilterOp::kEq:
509 return {LowerBoundIntrinsic(string_pool_, data_->data(), val_str,
510 search_range),
511 UpperBoundIntrinsic(string_pool_, data_->data(), val_str,
512 search_range)};
513 case FilterOp::kLe:
514 return {search_range.start,
515 UpperBoundIntrinsic(string_pool_, data_->data(), val_str,
516 search_range)};
517 case FilterOp::kLt:
518 return {search_range.start,
519 LowerBoundIntrinsic(string_pool_, data_->data(), val_str,
520 search_range)};
521 case FilterOp::kGe:
522 return {LowerBoundIntrinsic(string_pool_, data_->data(), val_str,
523 search_range),
524 search_range.end};
525 case FilterOp::kGt:
526 return {UpperBoundIntrinsic(string_pool_, data_->data(), val_str,
527 search_range),
528 search_range.end};
529 case FilterOp::kNe:
530 case FilterOp::kIsNull:
531 case FilterOp::kIsNotNull:
532 case FilterOp::kGlob:
533 case FilterOp::kRegex:
534 PERFETTO_FATAL("Shouldn't be called");
535 }
536 PERFETTO_FATAL("For GCC");
537 }
538
StableSort(Token * start,Token * end,SortDirection direction) const539 void StringStorage::ChainImpl::StableSort(Token* start,
540 Token* end,
541 SortDirection direction) const {
542 PERFETTO_TP_TRACE(metatrace::Category::DB,
543 "StringStorage::ChainImpl::StableSort");
544 switch (direction) {
545 case SortDirection::kAscending: {
546 std::stable_sort(start, end, [this](const Token& lhs, const Token& rhs) {
547 // If RHS is NULL, we know that LHS is not less than
548 // NULL, as nothing is less then null. This check is
549 // only required to keep the stability of the sort.
550 if ((*data_)[rhs.index] == StringPool::Id::Null()) {
551 return false;
552 }
553
554 // If LHS is NULL, it will always be smaller than any
555 // RHS value.
556 if ((*data_)[lhs.index] == StringPool::Id::Null()) {
557 return true;
558 }
559
560 // If neither LHS or RHS are NULL, we have to simply
561 // check which string is smaller.
562 return string_pool_->Get((*data_)[lhs.index]) <
563 string_pool_->Get((*data_)[rhs.index]);
564 });
565 return;
566 }
567 case SortDirection::kDescending: {
568 std::stable_sort(start, end, [this](const Token& lhs, const Token& rhs) {
569 // If LHS is NULL, we know that it's not greater than
570 // any RHS. This check is only required to keep the
571 // stability of the sort.
572 if ((*data_)[lhs.index] == StringPool::Id::Null()) {
573 return false;
574 }
575
576 // If RHS is NULL, everything will be greater from it.
577 if ((*data_)[rhs.index] == StringPool::Id::Null()) {
578 return true;
579 }
580
581 // If neither LHS or RHS are NULL, we have to simply
582 // check which string is smaller.
583 return string_pool_->Get((*data_)[lhs.index]) >
584 string_pool_->Get((*data_)[rhs.index]);
585 });
586 return;
587 }
588 }
589 PERFETTO_FATAL("For GCC");
590 }
591
Distinct(Indices & indices) const592 void StringStorage::ChainImpl::Distinct(Indices& indices) const {
593 PERFETTO_TP_TRACE(metatrace::Category::DB,
594 "StringStorage::ChainImpl::Distinct");
595 std::unordered_set<StringPool::Id> s;
596 indices.tokens.erase(
597 std::remove_if(indices.tokens.begin(), indices.tokens.end(),
598 [&s, this](const Token& idx) {
599 return !s.insert((*data_)[idx.index]).second;
600 }),
601 indices.tokens.end());
602 }
603
MaxElement(Indices & indices) const604 std::optional<Token> StringStorage::ChainImpl::MaxElement(
605 Indices& indices) const {
606 PERFETTO_TP_TRACE(metatrace::Category::DB,
607 "StringStorage::ChainImpl::MaxElement");
608 auto tok = std::max_element(indices.tokens.begin(), indices.tokens.end(),
609 [this](const Token& lhs, const Token& rhs) {
610 return LessForTokens(lhs, rhs);
611 });
612 if (tok == indices.tokens.end()) {
613 return std::nullopt;
614 }
615
616 return *tok;
617 }
618
MinElement(Indices & indices) const619 std::optional<Token> StringStorage::ChainImpl::MinElement(
620 Indices& indices) const {
621 PERFETTO_TP_TRACE(metatrace::Category::DB,
622 "StringStorage::ChainImpl::MinElement");
623 auto tok = std::min_element(indices.tokens.begin(), indices.tokens.end(),
624 [this](const Token& lhs, const Token& rhs) {
625 return LessForTokens(lhs, rhs);
626 });
627 if (tok == indices.tokens.end()) {
628 return std::nullopt;
629 }
630
631 return *tok;
632 }
633
Get_AvoidUsingBecauseSlow(uint32_t index) const634 SqlValue StringStorage::ChainImpl::Get_AvoidUsingBecauseSlow(
635 uint32_t index) const {
636 StringPool::Id id = (*data_)[index];
637 return id == StringPool::Id::Null()
638 ? SqlValue()
639 : SqlValue::String(string_pool_->Get(id).c_str());
640 }
641
642 } // namespace perfetto::trace_processor::column
643