row_map.cc | Explore in Territory

/*
 * Copyright (C) 2019 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "src/trace_processor/containers/row_map.h"

#include <algorithm>
#include <cstdint>
#include <unordered_set>
#include <utility>
#include <variant>
#include <vector>

#include "perfetto/base/logging.h"
#include "src/trace_processor/containers/bit_vector.h"
#include "src/trace_processor/containers/row_map_algorithms.h"

namespace perfetto {
namespace trace_processor {

namespace {

Range;
OutputIndex;
Variant;

RowMap Select(Range range, Range selector) { … }

RowMap Select(Range range, const BitVector& selector) { … }

RowMap Select(Range range, const std::vector<OutputIndex>& selector) { … }

RowMap Select(const BitVector& bv, Range selector) { … }

RowMap Select(const BitVector& bv, const BitVector& selector) { … }

RowMap Select(const BitVector& bv, const std::vector<uint32_t>& selector) { … }

RowMap Select(const std::vector<uint32_t>& iv, Range selector) { … }

RowMap Select(const std::vector<uint32_t>& iv, const BitVector& selector) { … }

RowMap Select(const std::vector<uint32_t>& iv,
              const std::vector<uint32_t>& selector) { … }

// O(N), but 64 times faster than doing it bit by bit, as we compare words in
// BitVectors.
Variant IntersectInternal(BitVector& first, const BitVector& second) { … }

// O(1) complexity.
Variant IntersectInternal(Range first, Range second) { … }

// O(N + k) complexity, where N is the size of |second| and k is the number of
// elements that have to be removed from |first|.
Variant IntersectInternal(std::vector<OutputIndex>& first,
                          const std::vector<OutputIndex>& second) { … }

// O(1) complexity.
Variant IntersectInternal(Range range, const BitVector& bv) { … }

Variant IntersectInternal(BitVector& bv, Range range) { … }

Variant IntersectInternal(const std::vector<OutputIndex>& index_vec,
                          const BitVector& bv) { … }

Variant IntersectInternal(const BitVector& bv,
                          const std::vector<OutputIndex>& index_vec) { … }

Variant IntersectInternal(Range range,
                          const std::vector<OutputIndex>& index_vec) { … }

Variant IntersectInternal(const std::vector<OutputIndex>& index_vec,
                          Range range) { … }

}  // namespace

RowMap::RowMap() : … { … }

RowMap::RowMap(uint32_t start, uint32_t end) : … { … }

RowMap::RowMap(Variant def) : … { … }

RowMap::RowMap(Range r) : … { … }

// Creates a RowMap backed by a BitVector.
RowMap::RowMap(BitVector bit_vector) : … { … }

// Creates a RowMap backed by an std::vector<uint32_t>.
RowMap::RowMap(IndexVector vec) : … { … }

RowMap RowMap::Copy() const { … }

OutputIndex RowMap::Max() const { … }

RowMap RowMap::SelectRowsSlow(const RowMap& selector) const { … }

void RowMap::Intersect(const RowMap& second) { … }

RowMap::Iterator::Iterator(const RowMap* rm) : … { … }

}  // namespace trace_processor
}  // namespace perfetto
chromium/third_party/perfetto/src/trace_processor/containers/row_map.cc
