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 
24 #include "perfetto/base/logging.h"
25 #include "perfetto/ext/base/optional.h"
26 #include "src/trace_processor/containers/row_map.h"
27 
28 namespace perfetto {
29 namespace trace_processor {
30 
31 // Base class for NullableVector which allows type erasure to be implemented
32 // (e.g. allows for std::unique_ptr<NullableVectorBase>).
33 class NullableVectorBase {
34  public:
35   NullableVectorBase() = default;
36   virtual ~NullableVectorBase();
37 
38   NullableVectorBase(const NullableVectorBase&) = delete;
39   NullableVectorBase& operator=(const NullableVectorBase&) = delete;
40 
41   NullableVectorBase(NullableVectorBase&&) = default;
42   NullableVectorBase& operator=(NullableVectorBase&&) noexcept = default;
43 };
44 
45 // A data structure which compactly stores a list of possibly nullable data.
46 //
47 // Internally, this class is implemented using a combination of a std::deque
48 // with a BitVector used to store whether each index is null or not.
49 // By default, for each null value, it only uses a single bit inside the
50 // BitVector at a slight cost (searching the BitVector to find the index into
51 // the std::deque) when looking up the data.
52 template <typename T>
53 class NullableVector : public NullableVectorBase {
54  private:
55   enum class Mode {
56     // Sparse mode is the default mode and ensures that nulls are stored using
57     // only
58     // a single bit (at the cost of making setting null entries to non-null
59     // O(n)).
60     kSparse,
61 
62     // Dense mode forces the reservation of space for null entries which
63     // increases
64     // memory usage but allows for O(1) set operations.
65     kDense,
66   };
67 
68  public:
69   // Creates an empty NullableVector.
NullableVector()70   NullableVector() : NullableVector<T>(Mode::kSparse) {}
71   ~NullableVector() override = default;
72 
73   explicit NullableVector(const NullableVector&) = delete;
74   NullableVector& operator=(const NullableVector&) = delete;
75 
76   NullableVector(NullableVector&&) = default;
77   NullableVector& operator=(NullableVector&&) noexcept = default;
78 
79   // Creates a sparse nullable vector
Sparse()80   static NullableVector<T> Sparse() { return NullableVector<T>(Mode::kSparse); }
81 
82   // Creates a dense nullable vector
Dense()83   static NullableVector<T> Dense() { return NullableVector<T>(Mode::kDense); }
84 
85   // Returns the optional value at |idx| or base::nullopt if the value is null.
Get(uint32_t idx)86   base::Optional<T> Get(uint32_t idx) const {
87     if (mode_ == Mode::kDense) {
88       bool contains = valid_.Contains(idx);
89       return contains ? base::Optional<T>(data_[idx]) : base::nullopt;
90     } else {
91       auto opt_idx = valid_.IndexOf(idx);
92       return opt_idx ? base::Optional<T>(data_[*opt_idx]) : base::nullopt;
93     }
94   }
95 
96   // Returns the non-null value at |ordinal| where |ordinal| gives the index
97   // of the entry in-terms of non-null entries only.
98   //
99   // For example:
100   // this = [0, null, 2, null, 4]
101   //
102   // GetNonNull(0) = 0
103   // GetNonNull(1) = 2
104   // GetNonNull(2) = 4
105   // ...
GetNonNull(uint32_t ordinal)106   T GetNonNull(uint32_t ordinal) const {
107     if (mode_ == Mode::kDense) {
108       return data_[valid_.Get(ordinal)];
109     } else {
110       PERFETTO_DCHECK(ordinal < data_.size());
111       return data_[ordinal];
112     }
113   }
114 
115   // Adds the given value to the NullableVector.
Append(T val)116   void Append(T val) {
117     data_.emplace_back(val);
118     valid_.Insert(size_++);
119   }
120 
121   // Adds a null value to the NullableVector.
AppendNull()122   void AppendNull() {
123     if (mode_ == Mode::kDense) {
124       data_.emplace_back();
125     }
126     size_++;
127   }
128 
129   // Adds the given optional value to the NullableVector.
Append(base::Optional<T> val)130   void Append(base::Optional<T> val) {
131     if (val) {
132       Append(*val);
133     } else {
134       AppendNull();
135     }
136   }
137 
138   // Sets the value at |idx| to the given |val|.
Set(uint32_t idx,T val)139   void Set(uint32_t idx, T val) {
140     if (mode_ == Mode::kDense) {
141       if (!valid_.Contains(idx)) {
142         valid_.Insert(idx);
143       }
144       data_[idx] = val;
145     } else {
146       auto opt_idx = valid_.IndexOf(idx);
147 
148       // Generally, we will be setting a null row to non-null so optimize for
149       // that path.
150       if (PERFETTO_UNLIKELY(opt_idx)) {
151         data_[*opt_idx] = val;
152       } else {
153         valid_.Insert(idx);
154 
155         opt_idx = valid_.IndexOf(idx);
156         PERFETTO_DCHECK(opt_idx);
157         data_.insert(data_.begin() + static_cast<ptrdiff_t>(*opt_idx), val);
158       }
159     }
160   }
161 
162   // Returns the size of the NullableVector; this includes any null values.
size()163   uint32_t size() const { return size_; }
164 
165   // Returns whether data in this NullableVector is stored densely.
IsDense()166   bool IsDense() const { return mode_ == Mode::kDense; }
167 
168  private:
NullableVector(Mode mode)169   NullableVector(Mode mode) : mode_(mode) {}
170 
171   Mode mode_ = Mode::kSparse;
172 
173   std::deque<T> data_;
174   RowMap valid_;
175   uint32_t size_ = 0;
176 };
177 
178 }  // namespace trace_processor
179 }  // namespace perfetto
180 
181 #endif  // SRC_TRACE_PROCESSOR_CONTAINERS_NULLABLE_VECTOR_H_
182