1 /* 2 * Copyright (C) 2019 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_CONTAINERS_NULLABLE_VECTOR_H_ 18 #define SRC_TRACE_PROCESSOR_CONTAINERS_NULLABLE_VECTOR_H_ 19 20 #include <stdint.h> 21 22 #include <deque> 23 #include <optional> 24 25 #include "perfetto/base/logging.h" 26 #include "src/trace_processor/containers/row_map.h" 27 28 namespace perfetto { 29 namespace trace_processor { 30 31 // A data structure which compactly stores a list of possibly nullable data. 32 // 33 // Internally, this class is implemented using a combination of a std::deque 34 // with a BitVector used to store whether each index is null or not. 35 // By default, for each null value, it only uses a single bit inside the 36 // BitVector at a slight cost (searching the BitVector to find the index into 37 // the std::deque) when looking up the data. 38 template <typename T> 39 class NullableVector { 40 private: 41 enum class Mode { 42 // Sparse mode is the default mode and ensures that nulls are stored using 43 // only 44 // a single bit (at the cost of making setting null entries to non-null 45 // O(n)). 46 kSparse, 47 48 // Dense mode forces the reservation of space for null entries which 49 // increases 50 // memory usage but allows for O(1) set operations. 51 kDense, 52 }; 53 54 public: 55 // Creates an empty NullableVector. NullableVector()56 NullableVector() : NullableVector<T>(Mode::kSparse) {} 57 58 NullableVector(const NullableVector&) = delete; 59 NullableVector& operator=(const NullableVector&) = delete; 60 61 NullableVector(NullableVector&&) = default; 62 NullableVector& operator=(NullableVector&&) noexcept = default; 63 64 // Creates a sparse nullable vector Sparse()65 static NullableVector<T> Sparse() { return NullableVector<T>(Mode::kSparse); } 66 67 // Creates a dense nullable vector Dense()68 static NullableVector<T> Dense() { return NullableVector<T>(Mode::kDense); } 69 70 // Returns the optional value at |idx| or std::nullopt if the value is null. Get(uint32_t idx)71 std::optional<T> Get(uint32_t idx) const { 72 bool contains = valid_.IsSet(idx); 73 if (mode_ == Mode::kDense) 74 return contains ? std::make_optional(data_[idx]) : std::nullopt; 75 76 return contains ? std::make_optional(data_[valid_.CountSetBits(idx)]) 77 : std::nullopt; 78 } 79 80 // Adds the given value to the NullableVector. Append(T val)81 void Append(T val) { 82 data_.emplace_back(val); 83 valid_.AppendTrue(); 84 } 85 86 // Adds the given optional value to the NullableVector. Append(std::optional<T> val)87 void Append(std::optional<T> val) { 88 if (val) { 89 Append(*val); 90 } else { 91 AppendNull(); 92 } 93 } 94 95 // Sets the value at |idx| to the given |val|. Set(uint32_t idx,T val)96 void Set(uint32_t idx, T val) { 97 if (mode_ == Mode::kDense) { 98 valid_.Set(idx); 99 data_[idx] = val; 100 } else { 101 // Generally, we will be setting a null row to non-null so optimize for 102 // that path. 103 uint32_t row = valid_.CountSetBits(idx); 104 bool was_set = valid_.Set(idx); 105 if (PERFETTO_UNLIKELY(was_set)) { 106 data_[row] = val; 107 } else { 108 data_.insert(data_.begin() + static_cast<ptrdiff_t>(row), val); 109 } 110 } 111 } 112 113 // Requests the removal of unused capacity. 114 // Matches the semantics of std::vector::shrink_to_fit. ShrinkToFit()115 void ShrinkToFit() { 116 data_.shrink_to_fit(); 117 valid_.ShrinkToFit(); 118 } 119 120 // Returns the size of the NullableVector; this includes any null values. size()121 uint32_t size() const { return valid_.size(); } 122 123 // Returns whether data in this NullableVector is stored densely. IsDense()124 bool IsDense() const { return mode_ == Mode::kDense; } 125 non_null_vector()126 const std::vector<T>& non_null_vector() const { return data_; } non_null_bit_vector()127 const BitVector& non_null_bit_vector() const { return valid_; } 128 129 private: NullableVector(Mode mode)130 explicit NullableVector(Mode mode) : mode_(mode) {} 131 AppendNull()132 void AppendNull() { 133 if (mode_ == Mode::kDense) { 134 data_.emplace_back(); 135 } 136 valid_.AppendFalse(); 137 } 138 139 Mode mode_ = Mode::kSparse; 140 141 std::vector<T> data_; 142 BitVector valid_; 143 }; 144 145 } // namespace trace_processor 146 } // namespace perfetto 147 148 #endif // SRC_TRACE_PROCESSOR_CONTAINERS_NULLABLE_VECTOR_H_ 149