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::__anon849280040111::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::__anon849280040111::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::__anon849280040111::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::__anon849280040111::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::__anon849280040111::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::__anon849280040111::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::__anon849280040111::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::__anon849280040111::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::__anon849280040111::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::__anon849280040111::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::__anon849280040111::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::__anon849280040111::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::__anon849280040111::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
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 data_->begin(),
302 std::partition_point(data_->begin() + search_range.start,
303 data_->begin() + search_range.end,
304 [](StringPool::Id id) {
305 return id == StringPool::Id::Null();
306 })));
307 return RangeOrBitVector(BinarySearchIntrinsic(
308 op, sql_val,
309 {std::max(search_range.start, first_non_null), search_range.end}));
310 }
311 case FilterOp::kNe: {
312 // Not equal is a special operation on binary search, as it doesn't
313 // define a range, and rather just `not` range returned with `equal`
314 // operation on non null values.
315 auto first_non_null = static_cast<uint32_t>(std::distance(
316 data_->begin(),
317 std::partition_point(data_->begin() + search_range.start,
318 data_->begin() + search_range.end,
319 [](StringPool::Id id) {
320 return id == StringPool::Id::Null();
321 })));
322 Range ret = BinarySearchIntrinsic(
323 FilterOp::kEq, sql_val,
324 {std::max(search_range.start, first_non_null), search_range.end});
325 BitVector bv(first_non_null, false);
326 bv.Resize(ret.start, true);
327 bv.Resize(ret.end, false);
328 bv.Resize(search_range.end, true);
329 return RangeOrBitVector(std::move(bv));
330 }
331 case FilterOp::kGlob:
332 case FilterOp::kRegex:
333 case FilterOp::kIsNull:
334 case FilterOp::kIsNotNull:
335 // Those operations can't be binary searched so we fall back on not
336 // sorted algorithm.
337 break;
338 }
339 }
340 return RangeOrBitVector(LinearSearch(op, sql_val, search_range));
341 }
342
IndexSearchValidated(FilterOp op,SqlValue sql_val,Indices & indices) const343 void StringStorage::ChainImpl::IndexSearchValidated(FilterOp op,
344 SqlValue sql_val,
345 Indices& indices) const {
346 PERFETTO_DCHECK(indices.tokens.size() <= size());
347 PERFETTO_TP_TRACE(
348 metatrace::Category::DB, "StringStorage::ChainImpl::IndexSearch",
349 [&indices, op](metatrace::Record* r) {
350 r->AddArg("Count", std::to_string(indices.tokens.size()));
351 r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
352 });
353
354 StringPool::Id val =
355 (op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
356 ? StringPool::Id::Null()
357 : string_pool_->InternString(base::StringView(sql_val.AsString()));
358 const StringPool::Id* start = data_->data();
359 switch (op) {
360 case FilterOp::kEq:
361 utils::IndexSearchWithComparator(val, start, indices, std::equal_to<>());
362 break;
363 case FilterOp::kNe:
364 utils::IndexSearchWithComparator(val, start, indices, NotEqual());
365 break;
366 case FilterOp::kLe:
367 utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
368 LessEqual{string_pool_});
369 break;
370 case FilterOp::kLt:
371 utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
372 Less{string_pool_});
373 break;
374 case FilterOp::kGt:
375 utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
376 Greater{string_pool_});
377 break;
378 case FilterOp::kGe:
379 utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
380 GreaterEqual{string_pool_});
381 break;
382 case FilterOp::kGlob: {
383 util::GlobMatcher matcher =
384 util::GlobMatcher::FromPattern(sql_val.AsString());
385 if (matcher.IsEquality()) {
386 utils::IndexSearchWithComparator(val, start, indices,
387 std::equal_to<>());
388 break;
389 }
390 utils::IndexSearchWithComparator(std::move(matcher), start, indices,
391 Glob{string_pool_});
392 break;
393 }
394 case FilterOp::kRegex: {
395 base::StatusOr<regex::Regex> regex =
396 regex::Regex::Create(sql_val.AsString());
397 utils::IndexSearchWithComparator(std::move(regex.value()), start, indices,
398 Regex{string_pool_});
399 break;
400 }
401 case FilterOp::kIsNull:
402 utils::IndexSearchWithComparator(val, start, indices, IsNull());
403 break;
404 case FilterOp::kIsNotNull:
405 utils::IndexSearchWithComparator(val, start, indices, IsNotNull());
406 break;
407 }
408 }
409
LinearSearch(FilterOp op,SqlValue sql_val,Range range) const410 BitVector StringStorage::ChainImpl::LinearSearch(FilterOp op,
411 SqlValue sql_val,
412 Range range) const {
413 StringPool::Id val =
414 (op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
415 ? StringPool::Id::Null()
416 : string_pool_->InternString(base::StringView(sql_val.AsString()));
417
418 const StringPool::Id* start = data_->data() + range.start;
419
420 BitVector::Builder builder(range.end, range.start);
421 switch (op) {
422 case FilterOp::kEq:
423 utils::LinearSearchWithComparator(val, start, std::equal_to<>(), builder);
424 break;
425 case FilterOp::kNe:
426 utils::LinearSearchWithComparator(val, start, NotEqual(), builder);
427 break;
428 case FilterOp::kLe:
429 utils::LinearSearchWithComparator(string_pool_->Get(val), start,
430 LessEqual{string_pool_}, builder);
431 break;
432 case FilterOp::kLt:
433 utils::LinearSearchWithComparator(string_pool_->Get(val), start,
434 Less{string_pool_}, builder);
435 break;
436 case FilterOp::kGt:
437 utils::LinearSearchWithComparator(string_pool_->Get(val), start,
438 Greater{string_pool_}, builder);
439 break;
440 case FilterOp::kGe:
441 utils::LinearSearchWithComparator(string_pool_->Get(val), start,
442 GreaterEqual{string_pool_}, builder);
443 break;
444 case FilterOp::kGlob: {
445 util::GlobMatcher matcher =
446 util::GlobMatcher::FromPattern(sql_val.AsString());
447
448 // If glob pattern doesn't involve any special characters, the function
449 // called should be equality.
450 if (matcher.IsEquality()) {
451 utils::LinearSearchWithComparator(val, start, std::equal_to<>(),
452 builder);
453 break;
454 }
455
456 // For very big string pools (or small ranges) or pools with large strings
457 // run a standard glob function.
458 if (range.size() < string_pool_->size() ||
459 string_pool_->HasLargeString()) {
460 utils::LinearSearchWithComparator(std::move(matcher), start,
461 Glob{string_pool_}, builder);
462 break;
463 }
464
465 utils::LinearSearchWithComparator(
466 StringPool::Id::Null(), start,
467 GlobFullStringPool{string_pool_, matcher}, builder);
468 break;
469 }
470 case FilterOp::kRegex: {
471 // Caller should ensure that the regex is valid.
472 base::StatusOr<regex::Regex> regex =
473 regex::Regex::Create(sql_val.AsString());
474 PERFETTO_CHECK(regex.status().ok());
475
476 // For very big string pools (or small ranges) or pools with large
477 // strings run a standard regex function.
478 if (range.size() < string_pool_->size() ||
479 string_pool_->HasLargeString()) {
480 utils::LinearSearchWithComparator(std::move(regex.value()), start,
481 Regex{string_pool_}, builder);
482 break;
483 }
484 utils::LinearSearchWithComparator(
485 StringPool::Id::Null(), start,
486 RegexFullStringPool{string_pool_, regex.value()}, builder);
487 break;
488 }
489 case FilterOp::kIsNull:
490 utils::LinearSearchWithComparator(val, start, IsNull(), builder);
491 break;
492 case FilterOp::kIsNotNull:
493 utils::LinearSearchWithComparator(val, start, IsNotNull(), builder);
494 }
495
496 return std::move(builder).Build();
497 }
498
BinarySearchIntrinsic(FilterOp op,SqlValue sql_val,Range search_range) const499 Range StringStorage::ChainImpl::BinarySearchIntrinsic(
500 FilterOp op,
501 SqlValue sql_val,
502 Range search_range) const {
503 StringPool::Id val =
504 (op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
505 ? StringPool::Id::Null()
506 : string_pool_->InternString(base::StringView(sql_val.AsString()));
507 NullTermStringView val_str = string_pool_->Get(val);
508
509 switch (op) {
510 case FilterOp::kEq:
511 return {LowerBoundIntrinsic(string_pool_, data_->data(), val_str,
512 search_range),
513 UpperBoundIntrinsic(string_pool_, data_->data(), val_str,
514 search_range)};
515 case FilterOp::kLe:
516 return {search_range.start,
517 UpperBoundIntrinsic(string_pool_, data_->data(), val_str,
518 search_range)};
519 case FilterOp::kLt:
520 return {search_range.start,
521 LowerBoundIntrinsic(string_pool_, data_->data(), val_str,
522 search_range)};
523 case FilterOp::kGe:
524 return {LowerBoundIntrinsic(string_pool_, data_->data(), val_str,
525 search_range),
526 search_range.end};
527 case FilterOp::kGt:
528 return {UpperBoundIntrinsic(string_pool_, data_->data(), val_str,
529 search_range),
530 search_range.end};
531 case FilterOp::kNe:
532 case FilterOp::kIsNull:
533 case FilterOp::kIsNotNull:
534 case FilterOp::kGlob:
535 case FilterOp::kRegex:
536 PERFETTO_FATAL("Shouldn't be called");
537 }
538 PERFETTO_FATAL("For GCC");
539 }
540
StableSort(Token * start,Token * end,SortDirection direction) const541 void StringStorage::ChainImpl::StableSort(Token* start,
542 Token* end,
543 SortDirection direction) const {
544 PERFETTO_TP_TRACE(metatrace::Category::DB,
545 "StringStorage::ChainImpl::StableSort");
546 switch (direction) {
547 case SortDirection::kAscending: {
548 std::stable_sort(start, end, [this](const Token& lhs, const Token& rhs) {
549 // If RHS is NULL, we know that LHS is not less than
550 // NULL, as nothing is less then null. This check is
551 // only required to keep the stability of the sort.
552 if ((*data_)[rhs.index] == StringPool::Id::Null()) {
553 return false;
554 }
555
556 // If LHS is NULL, it will always be smaller than any
557 // RHS value.
558 if ((*data_)[lhs.index] == StringPool::Id::Null()) {
559 return true;
560 }
561
562 // If neither LHS or RHS are NULL, we have to simply
563 // check which string is smaller.
564 return string_pool_->Get((*data_)[lhs.index]) <
565 string_pool_->Get((*data_)[rhs.index]);
566 });
567 return;
568 }
569 case SortDirection::kDescending: {
570 std::stable_sort(start, end, [this](const Token& lhs, const Token& rhs) {
571 // If LHS is NULL, we know that it's not greater than
572 // any RHS. This check is only required to keep the
573 // stability of the sort.
574 if ((*data_)[lhs.index] == StringPool::Id::Null()) {
575 return false;
576 }
577
578 // If RHS is NULL, everything will be greater from it.
579 if ((*data_)[rhs.index] == StringPool::Id::Null()) {
580 return true;
581 }
582
583 // If neither LHS or RHS are NULL, we have to simply
584 // check which string is smaller.
585 return string_pool_->Get((*data_)[lhs.index]) >
586 string_pool_->Get((*data_)[rhs.index]);
587 });
588 return;
589 }
590 }
591 PERFETTO_FATAL("For GCC");
592 }
593
Distinct(Indices & indices) const594 void StringStorage::ChainImpl::Distinct(Indices& indices) const {
595 PERFETTO_TP_TRACE(metatrace::Category::DB,
596 "StringStorage::ChainImpl::Distinct");
597 std::unordered_set<StringPool::Id> s;
598 indices.tokens.erase(
599 std::remove_if(indices.tokens.begin(), indices.tokens.end(),
600 [&s, this](const Token& idx) {
601 return !s.insert((*data_)[idx.index]).second;
602 }),
603 indices.tokens.end());
604 }
605
MaxElement(Indices & indices) const606 std::optional<Token> StringStorage::ChainImpl::MaxElement(
607 Indices& indices) const {
608 PERFETTO_TP_TRACE(metatrace::Category::DB,
609 "StringStorage::ChainImpl::MaxElement");
610 auto tok = std::max_element(indices.tokens.begin(), indices.tokens.end(),
611 [this](const Token& lhs, const Token& rhs) {
612 return LessForTokens(lhs, rhs);
613 });
614 if (tok == indices.tokens.end()) {
615 return std::nullopt;
616 }
617
618 return *tok;
619 }
620
MinElement(Indices & indices) const621 std::optional<Token> StringStorage::ChainImpl::MinElement(
622 Indices& indices) const {
623 PERFETTO_TP_TRACE(metatrace::Category::DB,
624 "StringStorage::ChainImpl::MinElement");
625 auto tok = std::min_element(indices.tokens.begin(), indices.tokens.end(),
626 [this](const Token& lhs, const Token& rhs) {
627 return LessForTokens(lhs, rhs);
628 });
629 if (tok == indices.tokens.end()) {
630 return std::nullopt;
631 }
632
633 return *tok;
634 }
635
Get_AvoidUsingBecauseSlow(uint32_t index) const636 SqlValue StringStorage::ChainImpl::Get_AvoidUsingBecauseSlow(
637 uint32_t index) const {
638 StringPool::Id id = (*data_)[index];
639 return id == StringPool::Id::Null()
640 ? SqlValue()
641 : SqlValue::String(string_pool_->Get(id).c_str());
642 }
643
644 } // namespace perfetto::trace_processor::column
645