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 <optional>
24 #include <string>
25 #include <unordered_set>
26 #include <utility>
27 #include <vector>
28
29 #include "perfetto/base/logging.h"
30 #include "perfetto/ext/base/status_or.h"
31 #include "perfetto/ext/base/string_view.h"
32 #include "perfetto/trace_processor/basic_types.h"
33 #include "src/trace_processor/containers/bit_vector.h"
34 #include "src/trace_processor/containers/null_term_string_view.h"
35 #include "src/trace_processor/containers/string_pool.h"
36 #include "src/trace_processor/db/column/data_layer.h"
37 #include "src/trace_processor/db/column/types.h"
38 #include "src/trace_processor/db/column/utils.h"
39 #include "src/trace_processor/tp_metatrace.h"
40 #include "src/trace_processor/util/glob.h"
41 #include "src/trace_processor/util/regex.h"
42
43 #include "protos/perfetto/trace_processor/metatrace_categories.pbzero.h"
44 #include "protos/perfetto/trace_processor/serialization.pbzero.h"
45
46 namespace perfetto::trace_processor::column {
47
48 namespace {
49
50 struct Greater {
operator ()perfetto::trace_processor::column::__anon2a9045220111::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::__anon2a9045220111::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::__anon2a9045220111::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::__anon2a9045220111::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::__anon2a9045220111::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::__anon2a9045220111::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::__anon2a9045220111::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::__anon2a9045220111::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::__anon2a9045220111::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::__anon2a9045220111::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::__anon2a9045220111::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::__anon2a9045220111::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::__anon2a9045220111::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
ChainImpl(StringPool * string_pool,const std::vector<StringPool::Id> * data,bool is_sorted)168 StringStorage::ChainImpl::ChainImpl(StringPool* string_pool,
169 const std::vector<StringPool::Id>* data,
170 bool is_sorted)
171 : data_(data), string_pool_(string_pool), is_sorted_(is_sorted) {}
172
SingleSearch(FilterOp op,SqlValue sql_val,uint32_t i) const173 SingleSearchResult StringStorage::ChainImpl::SingleSearch(FilterOp op,
174 SqlValue sql_val,
175 uint32_t i) const {
176 if (sql_val.type == SqlValue::kNull) {
177 if (op == FilterOp::kIsNull) {
178 return IsNull()((*data_)[i], StringPool::Id::Null())
179 ? SingleSearchResult::kMatch
180 : SingleSearchResult::kNoMatch;
181 }
182 if (op == FilterOp::kIsNotNull) {
183 return IsNotNull()((*data_)[i], StringPool::Id::Null())
184 ? SingleSearchResult::kMatch
185 : SingleSearchResult::kNoMatch;
186 }
187 return SingleSearchResult::kNeedsFullSearch;
188 }
189
190 if (sql_val.type != SqlValue::kString) {
191 return SingleSearchResult::kNeedsFullSearch;
192 }
193
194 switch (op) {
195 case FilterOp::kEq: {
196 std::optional<StringPool::Id> id =
197 string_pool_->GetId(base::StringView(sql_val.string_value));
198 return id && std::equal_to<>()((*data_)[i], *id)
199 ? SingleSearchResult::kMatch
200 : SingleSearchResult::kNoMatch;
201 }
202 case FilterOp::kNe: {
203 std::optional<StringPool::Id> id =
204 string_pool_->GetId(base::StringView(sql_val.string_value));
205 return !id || NotEqual()((*data_)[i], *id) ? SingleSearchResult::kMatch
206 : SingleSearchResult::kNoMatch;
207 }
208 case FilterOp::kGe:
209 return GreaterEqual{string_pool_}(
210 (*data_)[i], NullTermStringView(sql_val.string_value))
211 ? SingleSearchResult::kMatch
212 : SingleSearchResult::kNoMatch;
213 case FilterOp::kGt:
214 return Greater{string_pool_}((*data_)[i],
215 NullTermStringView(sql_val.string_value))
216 ? SingleSearchResult::kMatch
217 : SingleSearchResult::kNoMatch;
218 case FilterOp::kLe:
219 return LessEqual{string_pool_}((*data_)[i],
220 NullTermStringView(sql_val.string_value))
221 ? SingleSearchResult::kMatch
222 : SingleSearchResult::kNoMatch;
223 case FilterOp::kLt:
224 return Less{string_pool_}((*data_)[i],
225 NullTermStringView(sql_val.string_value))
226 ? SingleSearchResult::kMatch
227 : SingleSearchResult::kNoMatch;
228 case FilterOp::kGlob: {
229 util::GlobMatcher matcher =
230 util::GlobMatcher::FromPattern(sql_val.string_value);
231 return Glob{string_pool_}((*data_)[i], matcher)
232 ? SingleSearchResult::kMatch
233 : SingleSearchResult::kNoMatch;
234 }
235 case FilterOp::kRegex: {
236 // Caller should ensure that the regex is valid.
237 base::StatusOr<regex::Regex> regex =
238 regex::Regex::Create(sql_val.AsString());
239 PERFETTO_CHECK(regex.status().ok());
240 return Regex{string_pool_}((*data_)[i], regex.value())
241 ? SingleSearchResult::kMatch
242 : SingleSearchResult::kNoMatch;
243 }
244 case FilterOp::kIsNull:
245 case FilterOp::kIsNotNull:
246 PERFETTO_FATAL("Already handled above");
247 }
248 PERFETTO_FATAL("For GCC");
249 }
250
ValidateSearchConstraints(FilterOp op,SqlValue val) const251 SearchValidationResult StringStorage::ChainImpl::ValidateSearchConstraints(
252 FilterOp op,
253 SqlValue val) const {
254 // Type checks.
255 switch (val.type) {
256 case SqlValue::kNull:
257 case SqlValue::kString:
258 break;
259 case SqlValue::kLong:
260 case SqlValue::kDouble:
261 // Any string is always more than any numeric.
262 if (op == FilterOp::kGt || op == FilterOp::kGe) {
263 return SearchValidationResult::kAllData;
264 }
265 return SearchValidationResult::kNoData;
266 case SqlValue::kBytes:
267 return SearchValidationResult::kNoData;
268 }
269
270 return SearchValidationResult::kOk;
271 }
272
SearchValidated(FilterOp op,SqlValue sql_val,Range search_range) const273 RangeOrBitVector StringStorage::ChainImpl::SearchValidated(
274 FilterOp op,
275 SqlValue sql_val,
276 Range search_range) const {
277 PERFETTO_TP_TRACE(metatrace::Category::DB, "StringStorage::ChainImpl::Search",
278 [&search_range, op](metatrace::Record* r) {
279 r->AddArg("Start", std::to_string(search_range.start));
280 r->AddArg("End", std::to_string(search_range.end));
281 r->AddArg("Op",
282 std::to_string(static_cast<uint32_t>(op)));
283 });
284
285 if (is_sorted_) {
286 switch (op) {
287 case FilterOp::kEq:
288 case FilterOp::kGe:
289 case FilterOp::kGt:
290 case FilterOp::kLe:
291 case FilterOp::kLt: {
292 auto first_non_null = static_cast<uint32_t>(std::distance(
293 data_->begin(),
294 std::partition_point(data_->begin() + search_range.start,
295 data_->begin() + search_range.end,
296 [](StringPool::Id id) {
297 return id == StringPool::Id::Null();
298 })));
299 return RangeOrBitVector(BinarySearchIntrinsic(
300 op, sql_val,
301 {std::max(search_range.start, first_non_null), search_range.end}));
302 }
303 case FilterOp::kNe: {
304 // Not equal is a special operation on binary search, as it doesn't
305 // define a range, and rather just `not` range returned with `equal`
306 // operation on non null values.
307 auto first_non_null = static_cast<uint32_t>(std::distance(
308 data_->begin(),
309 std::partition_point(data_->begin() + search_range.start,
310 data_->begin() + search_range.end,
311 [](StringPool::Id id) {
312 return id == StringPool::Id::Null();
313 })));
314 Range ret = BinarySearchIntrinsic(
315 FilterOp::kEq, sql_val,
316 {std::max(search_range.start, first_non_null), search_range.end});
317 BitVector bv(first_non_null, false);
318 bv.Resize(ret.start, true);
319 bv.Resize(ret.end, false);
320 bv.Resize(search_range.end, true);
321 return RangeOrBitVector(std::move(bv));
322 }
323 case FilterOp::kGlob:
324 case FilterOp::kRegex:
325 case FilterOp::kIsNull:
326 case FilterOp::kIsNotNull:
327 // Those operations can't be binary searched so we fall back on not
328 // sorted algorithm.
329 break;
330 }
331 }
332 return RangeOrBitVector(LinearSearch(op, sql_val, search_range));
333 }
334
IndexSearchValidated(FilterOp op,SqlValue sql_val,Indices & indices) const335 void StringStorage::ChainImpl::IndexSearchValidated(FilterOp op,
336 SqlValue sql_val,
337 Indices& indices) const {
338 PERFETTO_DCHECK(indices.tokens.size() <= size());
339 PERFETTO_TP_TRACE(
340 metatrace::Category::DB, "StringStorage::ChainImpl::IndexSearch",
341 [&indices, op](metatrace::Record* r) {
342 r->AddArg("Count", std::to_string(indices.tokens.size()));
343 r->AddArg("Op", std::to_string(static_cast<uint32_t>(op)));
344 });
345
346 StringPool::Id val =
347 (op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
348 ? StringPool::Id::Null()
349 : string_pool_->InternString(base::StringView(sql_val.AsString()));
350 const StringPool::Id* start = data_->data();
351 switch (op) {
352 case FilterOp::kEq:
353 utils::IndexSearchWithComparator(val, start, indices, std::equal_to<>());
354 break;
355 case FilterOp::kNe:
356 utils::IndexSearchWithComparator(val, start, indices, NotEqual());
357 break;
358 case FilterOp::kLe:
359 utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
360 LessEqual{string_pool_});
361 break;
362 case FilterOp::kLt:
363 utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
364 Less{string_pool_});
365 break;
366 case FilterOp::kGt:
367 utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
368 Greater{string_pool_});
369 break;
370 case FilterOp::kGe:
371 utils::IndexSearchWithComparator(string_pool_->Get(val), start, indices,
372 GreaterEqual{string_pool_});
373 break;
374 case FilterOp::kGlob: {
375 util::GlobMatcher matcher =
376 util::GlobMatcher::FromPattern(sql_val.AsString());
377 if (matcher.IsEquality()) {
378 utils::IndexSearchWithComparator(val, start, indices,
379 std::equal_to<>());
380 break;
381 }
382 utils::IndexSearchWithComparator(std::move(matcher), start, indices,
383 Glob{string_pool_});
384 break;
385 }
386 case FilterOp::kRegex: {
387 base::StatusOr<regex::Regex> regex =
388 regex::Regex::Create(sql_val.AsString());
389 utils::IndexSearchWithComparator(std::move(regex.value()), start, indices,
390 Regex{string_pool_});
391 break;
392 }
393 case FilterOp::kIsNull:
394 utils::IndexSearchWithComparator(val, start, indices, IsNull());
395 break;
396 case FilterOp::kIsNotNull:
397 utils::IndexSearchWithComparator(val, start, indices, IsNotNull());
398 break;
399 }
400 }
401
LinearSearch(FilterOp op,SqlValue sql_val,Range range) const402 BitVector StringStorage::ChainImpl::LinearSearch(FilterOp op,
403 SqlValue sql_val,
404 Range range) const {
405 StringPool::Id val =
406 (op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
407 ? StringPool::Id::Null()
408 : string_pool_->InternString(base::StringView(sql_val.AsString()));
409
410 const StringPool::Id* start = data_->data() + range.start;
411
412 BitVector::Builder builder(range.end, range.start);
413 switch (op) {
414 case FilterOp::kEq:
415 utils::LinearSearchWithComparator(val, start, std::equal_to<>(), builder);
416 break;
417 case FilterOp::kNe:
418 utils::LinearSearchWithComparator(val, start, NotEqual(), builder);
419 break;
420 case FilterOp::kLe:
421 utils::LinearSearchWithComparator(string_pool_->Get(val), start,
422 LessEqual{string_pool_}, builder);
423 break;
424 case FilterOp::kLt:
425 utils::LinearSearchWithComparator(string_pool_->Get(val), start,
426 Less{string_pool_}, builder);
427 break;
428 case FilterOp::kGt:
429 utils::LinearSearchWithComparator(string_pool_->Get(val), start,
430 Greater{string_pool_}, builder);
431 break;
432 case FilterOp::kGe:
433 utils::LinearSearchWithComparator(string_pool_->Get(val), start,
434 GreaterEqual{string_pool_}, builder);
435 break;
436 case FilterOp::kGlob: {
437 util::GlobMatcher matcher =
438 util::GlobMatcher::FromPattern(sql_val.AsString());
439
440 // If glob pattern doesn't involve any special characters, the function
441 // called should be equality.
442 if (matcher.IsEquality()) {
443 utils::LinearSearchWithComparator(val, start, std::equal_to<>(),
444 builder);
445 break;
446 }
447
448 // For very big string pools (or small ranges) or pools with large strings
449 // run a standard glob function.
450 if (range.size() < string_pool_->size() ||
451 string_pool_->HasLargeString()) {
452 utils::LinearSearchWithComparator(std::move(matcher), start,
453 Glob{string_pool_}, builder);
454 break;
455 }
456
457 utils::LinearSearchWithComparator(
458 StringPool::Id::Null(), start,
459 GlobFullStringPool{string_pool_, matcher}, builder);
460 break;
461 }
462 case FilterOp::kRegex: {
463 // Caller should ensure that the regex is valid.
464 base::StatusOr<regex::Regex> regex =
465 regex::Regex::Create(sql_val.AsString());
466 PERFETTO_CHECK(regex.status().ok());
467
468 // For very big string pools (or small ranges) or pools with large
469 // strings run a standard regex function.
470 if (range.size() < string_pool_->size() ||
471 string_pool_->HasLargeString()) {
472 utils::LinearSearchWithComparator(std::move(regex.value()), start,
473 Regex{string_pool_}, builder);
474 break;
475 }
476 utils::LinearSearchWithComparator(
477 StringPool::Id::Null(), start,
478 RegexFullStringPool{string_pool_, regex.value()}, builder);
479 break;
480 }
481 case FilterOp::kIsNull:
482 utils::LinearSearchWithComparator(val, start, IsNull(), builder);
483 break;
484 case FilterOp::kIsNotNull:
485 utils::LinearSearchWithComparator(val, start, IsNotNull(), builder);
486 }
487
488 return std::move(builder).Build();
489 }
490
BinarySearchIntrinsic(FilterOp op,SqlValue sql_val,Range search_range) const491 Range StringStorage::ChainImpl::BinarySearchIntrinsic(
492 FilterOp op,
493 SqlValue sql_val,
494 Range search_range) const {
495 StringPool::Id val =
496 (op == FilterOp::kIsNull || op == FilterOp::kIsNotNull)
497 ? StringPool::Id::Null()
498 : string_pool_->InternString(base::StringView(sql_val.AsString()));
499 NullTermStringView val_str = string_pool_->Get(val);
500
501 switch (op) {
502 case FilterOp::kEq:
503 return {LowerBoundIntrinsic(string_pool_, data_->data(), val_str,
504 search_range),
505 UpperBoundIntrinsic(string_pool_, data_->data(), val_str,
506 search_range)};
507 case FilterOp::kLe:
508 return {search_range.start,
509 UpperBoundIntrinsic(string_pool_, data_->data(), val_str,
510 search_range)};
511 case FilterOp::kLt:
512 return {search_range.start,
513 LowerBoundIntrinsic(string_pool_, data_->data(), val_str,
514 search_range)};
515 case FilterOp::kGe:
516 return {LowerBoundIntrinsic(string_pool_, data_->data(), val_str,
517 search_range),
518 search_range.end};
519 case FilterOp::kGt:
520 return {UpperBoundIntrinsic(string_pool_, data_->data(), val_str,
521 search_range),
522 search_range.end};
523 case FilterOp::kNe:
524 case FilterOp::kIsNull:
525 case FilterOp::kIsNotNull:
526 case FilterOp::kGlob:
527 case FilterOp::kRegex:
528 PERFETTO_FATAL("Shouldn't be called");
529 }
530 PERFETTO_FATAL("For GCC");
531 }
532
StableSort(SortToken * start,SortToken * end,SortDirection direction) const533 void StringStorage::ChainImpl::StableSort(SortToken* start,
534 SortToken* end,
535 SortDirection direction) const {
536 PERFETTO_TP_TRACE(metatrace::Category::DB,
537 "StringStorage::ChainImpl::StableSort");
538 switch (direction) {
539 case SortDirection::kAscending: {
540 std::stable_sort(start, end,
541 [this](const SortToken& lhs, const SortToken& rhs) {
542 // If RHS is NULL, we know that LHS is not less than
543 // NULL, as nothing is less then null. This check is
544 // only required to keep the stability of the sort.
545 if ((*data_)[rhs.index] == StringPool::Id::Null()) {
546 return false;
547 }
548
549 // If LHS is NULL, it will always be smaller than any
550 // RHS value.
551 if ((*data_)[lhs.index] == StringPool::Id::Null()) {
552 return true;
553 }
554
555 // If neither LHS or RHS are NULL, we have to simply
556 // check which string is smaller.
557 return string_pool_->Get((*data_)[lhs.index]) <
558 string_pool_->Get((*data_)[rhs.index]);
559 });
560 return;
561 }
562 case SortDirection::kDescending: {
563 std::stable_sort(start, end,
564 [this](const SortToken& lhs, const SortToken& rhs) {
565 // If LHS is NULL, we know that it's not greater than
566 // any RHS. This check is only required to keep the
567 // stability of the sort.
568 if ((*data_)[lhs.index] == StringPool::Id::Null()) {
569 return false;
570 }
571
572 // If RHS is NULL, everything will be greater from it.
573 if ((*data_)[rhs.index] == StringPool::Id::Null()) {
574 return true;
575 }
576
577 // If neither LHS or RHS are NULL, we have to simply
578 // check which string is smaller.
579 return string_pool_->Get((*data_)[lhs.index]) >
580 string_pool_->Get((*data_)[rhs.index]);
581 });
582 return;
583 }
584 }
585 PERFETTO_FATAL("For GCC");
586 }
587
Distinct(Indices & indices) const588 void StringStorage::ChainImpl::Distinct(Indices& indices) const {
589 PERFETTO_TP_TRACE(metatrace::Category::DB,
590 "StringStorage::ChainImpl::Distinct");
591 std::unordered_set<StringPool::Id> s;
592 indices.tokens.erase(
593 std::remove_if(indices.tokens.begin(), indices.tokens.end(),
594 [&s, this](const Token& idx) {
595 return !s.insert((*data_)[idx.index]).second;
596 }),
597 indices.tokens.end());
598 }
599
MaxElement(Indices & indices) const600 std::optional<Token> StringStorage::ChainImpl::MaxElement(
601 Indices& indices) const {
602 PERFETTO_TP_TRACE(metatrace::Category::DB,
603 "StringStorage::ChainImpl::MaxElement");
604 auto tok = std::max_element(indices.tokens.begin(), indices.tokens.end(),
605 [this](const Token& lhs, const Token& rhs) {
606 return LessForTokens(lhs, rhs);
607 });
608 if (tok == indices.tokens.end()) {
609 return std::nullopt;
610 }
611
612 return *tok;
613 }
614
MinElement(Indices & indices) const615 std::optional<Token> StringStorage::ChainImpl::MinElement(
616 Indices& indices) const {
617 PERFETTO_TP_TRACE(metatrace::Category::DB,
618 "StringStorage::ChainImpl::MinElement");
619 auto tok = std::min_element(indices.tokens.begin(), indices.tokens.end(),
620 [this](const Token& lhs, const Token& rhs) {
621 return LessForTokens(lhs, rhs);
622 });
623 if (tok == indices.tokens.end()) {
624 return std::nullopt;
625 }
626
627 return *tok;
628 }
629
Get_AvoidUsingBecauseSlow(uint32_t index) const630 SqlValue StringStorage::ChainImpl::Get_AvoidUsingBecauseSlow(
631 uint32_t index) const {
632 StringPool::Id id = (*data_)[index];
633 return id == StringPool::Id::Null()
634 ? SqlValue()
635 : SqlValue::String(string_pool_->Get(id).c_str());
636 }
637
Serialize(StorageProto * msg) const638 void StringStorage::ChainImpl::Serialize(StorageProto* msg) const {
639 auto* string_storage_msg = msg->set_string_storage();
640 string_storage_msg->set_is_sorted(is_sorted_);
641
642 string_storage_msg->set_values(
643 reinterpret_cast<const uint8_t*>(data_->data()),
644 sizeof(StringPool::Id) * size());
645 }
646
647 } // namespace perfetto::trace_processor::column
648