Home | History | Annotate | Download | only in trace_processor 
      1 /*
      2  * Copyright (C) 2018 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/filtered_row_index.h"
     18 
     19 #include <numeric>
     20 
     21 namespace perfetto {
     22 namespace trace_processor {
     23 
     24 FilteredRowIndex::FilteredRowIndex(uint32_t start_row, uint32_t end_row)
     25     : mode_(Mode::kAllRows), start_row_(start_row), end_row_(end_row) {}
     26 
     27 void FilteredRowIndex::IntersectRows(std::vector<uint32_t> rows) {
     28   PERFETTO_DCHECK(error_.empty());
     29 
     30   // Sort the rows so all branches below make sense.
     31   std::sort(rows.begin(), rows.end());
     32 
     33   if (mode_ == kAllRows) {
     34     mode_ = Mode::kRowVector;
     35     // Yes you're reading this code correctly. We use lower_bound in both cases.
     36     // Yes this is very intentional and has to do with |end_row_| already being
     37     // one greater than the value we are searching for so we need the first
     38     // iterator which is *geq* the |end_row_|.
     39     auto begin = std::lower_bound(rows.begin(), rows.end(), start_row_);
     40     auto end = std::lower_bound(begin, rows.end(), end_row_);
     41     rows_.insert(rows_.end(), begin, end);
     42     return;
     43   } else if (mode_ == kRowVector) {
     44     std::vector<uint32_t> intersected;
     45     std::set_intersection(rows_.begin(), rows_.end(), rows.begin(), rows.end(),
     46                           std::back_inserter(intersected));
     47     rows_ = std::move(intersected);
     48     return;
     49   }
     50 
     51   // Initialise start to the beginning of the vector.
     52   auto start = row_filter_.begin();
     53 
     54   // Skip directly to the rows in range of start and end.
     55   size_t i = 0;
     56   for (; i < rows.size() && rows[i] < start_row_; i++) {
     57   }
     58   for (; i < rows.size() && rows[i] < end_row_; i++) {
     59     // Unset all bits between the start iterator and the iterator pointing
     60     // to the current row. That is, this loop sets all elements not pointed
     61     // to by rows to false. It does not touch the rows themselves which
     62     // means if they were already false (i.e. not returned) then they won't
     63     // be returned now and if they were true (i.e. returned) they will still
     64     // be returned.
     65     auto row = rows[i];
     66     auto end = row_filter_.begin() + static_cast<ptrdiff_t>(row - start_row_);
     67     std::fill(start, end, false);
     68     start = end + 1;
     69   }
     70   std::fill(start, row_filter_.end(), false);
     71 }
     72 
     73 std::vector<uint32_t> FilteredRowIndex::ToRowVector() {
     74   PERFETTO_DCHECK(error_.empty());
     75 
     76   switch (mode_) {
     77     case Mode::kAllRows:
     78       mode_ = Mode::kRowVector;
     79       rows_.resize(end_row_ - start_row_);
     80       std::iota(rows_.begin(), rows_.end(), start_row_);
     81       break;
     82     case Mode::kBitVector:
     83       ConvertBitVectorToRowVector();
     84       break;
     85     case Mode::kRowVector:
     86       // Nothing to do.
     87       break;
     88   }
     89   return TakeRowVector();
     90 }
     91 
     92 void FilteredRowIndex::ConvertBitVectorToRowVector() {
     93   PERFETTO_DCHECK(error_.empty());
     94 
     95   mode_ = Mode::kRowVector;
     96 
     97   auto b = row_filter_.begin();
     98   auto e = row_filter_.end();
     99   using std::find;
    100   for (auto it = find(b, e, true); it != e; it = find(it + 1, e, true)) {
    101     auto filter_idx = static_cast<uint32_t>(std::distance(b, it));
    102     rows_.emplace_back(filter_idx + start_row_);
    103   }
    104   row_filter_.clear();
    105 }
    106 
    107 std::unique_ptr<RowIterator> FilteredRowIndex::ToRowIterator(bool desc) {
    108   PERFETTO_DCHECK(error_.empty());
    109 
    110   switch (mode_) {
    111     case Mode::kAllRows:
    112       return std::unique_ptr<RangeRowIterator>(
    113           new RangeRowIterator(start_row_, end_row_, desc));
    114     case Mode::kBitVector: {
    115       return std::unique_ptr<RangeRowIterator>(
    116           new RangeRowIterator(start_row_, desc, TakeBitVector()));
    117     }
    118     case Mode::kRowVector: {
    119       auto vector = TakeRowVector();
    120       if (desc)
    121         std::reverse(vector.begin(), vector.end());
    122       return std::unique_ptr<VectorRowIterator>(
    123           new VectorRowIterator(std::move(vector)));
    124     }
    125   }
    126   PERFETTO_FATAL("For GCC");
    127 }
    128 
    129 std::vector<uint32_t> FilteredRowIndex::TakeRowVector() {
    130   PERFETTO_DCHECK(error_.empty());
    131 
    132   PERFETTO_DCHECK(mode_ == Mode::kRowVector);
    133   auto vector = std::move(rows_);
    134   rows_.clear();
    135   mode_ = Mode::kAllRows;
    136   return vector;
    137 }
    138 
    139 std::vector<bool> FilteredRowIndex::TakeBitVector() {
    140   PERFETTO_DCHECK(error_.empty());
    141 
    142   PERFETTO_DCHECK(mode_ == Mode::kBitVector);
    143   auto filter = std::move(row_filter_);
    144   row_filter_.clear();
    145   mode_ = Mode::kAllRows;
    146   return filter;
    147 }
    148 
    149 }  // namespace trace_processor
    150 }  // namespace perfetto
    151