1 /* 2 * Copyright (C) 2022 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 #ifndef SRC_TRACE_PROCESSOR_DB_COLUMN_STORAGE_OVERLAY_H_ 18 #define SRC_TRACE_PROCESSOR_DB_COLUMN_STORAGE_OVERLAY_H_ 19 20 #include <stdint.h> 21 22 #include <optional> 23 #include <utility> 24 #include <vector> 25 26 #include "src/trace_processor/containers/bit_vector.h" 27 #include "src/trace_processor/containers/row_map.h" 28 29 namespace perfetto::trace_processor { 30 31 // Contains indices which can be used to lookup data in one or more 32 // ColumnStorages. 33 // 34 // Implemented as a thin wrapper around RowMap so much of the documentation 35 // from RowMap also applies to this class. 36 class ColumnStorageOverlay { 37 public: 38 // Input type. 39 using InputRow = uint32_t; 40 using OutputIndex = uint32_t; 41 42 // Allows efficient iteration over the rows of a ColumnStorageOverlay. 43 class Iterator { 44 public: Iterator(RowMap::Iterator it)45 explicit Iterator(RowMap::Iterator it) : it_(std::move(it)) {} 46 47 Iterator(Iterator&&) noexcept = default; 48 Iterator& operator=(Iterator&&) = default; 49 50 // Forwards the iterator to the next row of the ColumnStorageOverlay. Next()51 void Next() { return it_.Next(); } 52 53 // Returns if the iterator is still valid. 54 explicit operator bool() const { return bool(it_); } 55 56 // Returns the index pointed to by this iterator. index()57 OutputIndex index() const { return it_.index(); } 58 59 // Returns the row of the index the iterator points to. row()60 InputRow row() const { return it_.row(); } 61 62 private: 63 RowMap::Iterator it_; 64 }; 65 66 // Creates an empty ColumnStorageOverlay. 67 // By default this will be implemented using a range. ColumnStorageOverlay()68 ColumnStorageOverlay() : ColumnStorageOverlay(0) {} 69 70 // Creates a |ColumnStorageOverlay| containing all rows between 0 and |size|. ColumnStorageOverlay(uint32_t size)71 explicit ColumnStorageOverlay(uint32_t size) 72 : ColumnStorageOverlay(0, size) {} 73 74 // Creates a |ColumnStorageOverlay| containing all rows between |start| and 75 // |end|. ColumnStorageOverlay(uint32_t start,uint32_t end)76 explicit ColumnStorageOverlay(uint32_t start, uint32_t end) 77 : ColumnStorageOverlay(RowMap(start, end)) {} 78 79 // Creates a |ColumnStorageOverlay| containing all rows corresponding to set 80 // bits in |bv|. ColumnStorageOverlay(BitVector bv)81 explicit ColumnStorageOverlay(BitVector bv) 82 : ColumnStorageOverlay(RowMap(std::move(bv))) {} 83 84 // Creates a |ColumnStorageOverlay| containing all rows in |rows|. ColumnStorageOverlay(std::vector<uint32_t> rows)85 explicit ColumnStorageOverlay(std::vector<uint32_t> rows) 86 : ColumnStorageOverlay(RowMap(std::move(rows))) {} 87 88 ColumnStorageOverlay(const ColumnStorageOverlay&) noexcept = delete; 89 ColumnStorageOverlay& operator=(const ColumnStorageOverlay&) = delete; 90 91 ColumnStorageOverlay(ColumnStorageOverlay&&) noexcept = default; 92 ColumnStorageOverlay& operator=(ColumnStorageOverlay&&) = default; 93 94 // Creates a copy of the ColumnStorageOverlay. 95 // We have an explicit copy function because ColumnStorageOverlay can hold 96 // onto large chunks of memory and we want to be very explicit when making a 97 // copy to avoid accidental leaks and copies. Copy()98 ColumnStorageOverlay Copy() const { 99 return ColumnStorageOverlay(row_map_.Copy()); 100 } 101 102 // Returns the size of the ColumnStorageOverlay; that is the number of 103 // indices in the ColumnStorageOverlay. size()104 uint32_t size() const { return row_map_.size(); } 105 106 // Returns whether this ColumnStorageOverlay is empty. empty()107 bool empty() const { return size() == 0; } 108 109 // Returns the index at the given |row|. Get(uint32_t row)110 OutputIndex Get(uint32_t row) const { return row_map_.Get(row); } 111 112 // Returns the first row of the given |index| in the ColumnStorageOverlay. RowOf(OutputIndex index)113 std::optional<InputRow> RowOf(OutputIndex index) const { 114 return row_map_.RowOf(index); 115 } 116 117 // Performs an ordered insert of the index into the current 118 // ColumnStorageOverlay (precondition: this ColumnStorageOverlay is ordered 119 // based on the indices it contains). 120 // 121 // See RowMap::Insert for more information on this function. Insert(OutputIndex index)122 void Insert(OutputIndex index) { return row_map_.Insert(index); } 123 124 // Updates this ColumnStorageOverlay by 'picking' the indices given by 125 // |picker|. 126 // 127 // See RowMap::SelectRows for more information on this function. SelectRows(const RowMap & selector)128 ColumnStorageOverlay SelectRows(const RowMap& selector) const { 129 return ColumnStorageOverlay(row_map_.SelectRows(selector)); 130 } 131 132 // Clears this ColumnStorageOverlay by resetting it to a newly constructed 133 // state. Clear()134 void Clear() { *this = ColumnStorageOverlay(); } 135 136 // Returns the iterator over the rows in this ColumnStorageOverlay. IterateRows()137 Iterator IterateRows() const { return Iterator(row_map_.IterateRows()); } 138 row_map()139 const RowMap& row_map() const { return row_map_; } 140 141 private: ColumnStorageOverlay(RowMap rm)142 explicit ColumnStorageOverlay(RowMap rm) : row_map_(std::move(rm)) {} 143 144 RowMap row_map_; 145 }; 146 147 } // namespace perfetto::trace_processor 148 149 #endif // SRC_TRACE_PROCESSOR_DB_COLUMN_STORAGE_OVERLAY_H_ 150