1 //
2 // Copyright (C) 2021 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 UPDATE_ENGINE_PAYLOAD_CONSUMER_EXTENT_MAP_H_
18 #define UPDATE_ENGINE_PAYLOAD_CONSUMER_EXTENT_MAP_H_
19 
20 #include <map>
21 #include <utility>
22 #include <vector>
23 
24 #include "update_engine/common/utils.h"
25 #include "update_engine/payload_generator/extent_ranges.h"
26 #include "update_engine/payload_generator/extent_utils.h"
27 #include "update_engine/update_metadata.pb.h"
28 
29 namespace chromeos_update_engine {
30 
31 // Data structure for storing a disjoint set of extents.
32 // Currently the only usecase is for VABCPartitionWriter to keep track of which
33 // block belongs to which merge operation. Therefore this class only contains
34 // the minimal set of functions needed.
35 template <typename T, typename Comparator = ExtentLess>
36 class ExtentMap {
37  public:
AddExtent(const Extent & extent,T && value)38   bool AddExtent(const Extent& extent, T&& value) {
39     if (set_.OverlapsWithExtent(extent)) {
40       return false;
41     }
42     const auto& [it, inserted] = map_.insert({extent, std::forward<T>(value)});
43     if (inserted) {
44       set_.AddExtent(extent);
45     }
46     return inserted;
47   }
48 
size()49   size_t size() const { return map_.size(); }
50 
51   // Return a pointer to entry which is intersecting |extent|. If T is already
52   // a pointer type, return T on success. This function always return
53   // |nullptr| on failure. Therefore you cannot store nullptr as an entry.
Get(const Extent & extent)54   std::optional<T> Get(const Extent& extent) const {
55     const auto it = map_.find(extent);
56     if (it == map_.end()) {
57       for (const auto& ext : set_.GetCandidateRange(extent)) {
58         // Sometimes there are operations like
59         // map.AddExtent({0, 5}, 42);
60         // map.Get({2, 1})
61         // If the querying extent is completely covered within the key, we still
62         // consdier this to be a valid query.
63 
64         if (ExtentContains(ext, extent)) {
65           return map_.at(ext);
66         }
67         if (ExtentRanges::ExtentsOverlap(ext, extent)) {
68           LOG(WARNING) << "Looking up a partially intersecting extent isn't "
69                           "supported by "
70                           "this data structure. Querying extent: "
71                        << extent << ", partial match in map: " << ext;
72         }
73       }
74       return {};
75     }
76     return {it->second};
77   }
78 
79   // Return a set of extents that are contained in this extent map.
80   // If |extent| is completely covered by this extent map, a vector of itself
81   // will be returned.
82   // If only a subset of |extent| is covered by this extent map, a vector of
83   // parts in this map will be returned.
84   // If |extent| has no intersection with this map, an empty vector will be
85   // returned.
86   // E.g. extent map contains [0,5] and [10,15], GetIntersectingExtents([3, 12])
87   // would return [3,5] and [10,12]
GetIntersectingExtents(const Extent & extent)88   std::vector<Extent> GetIntersectingExtents(const Extent& extent) const {
89     return set_.GetIntersectingExtents(extent);
90   }
91 
92   // Complement of |GetIntersectingExtents|, return vector of extents which are
93   // part of |extent| but not covered by this map.
GetNonIntersectingExtents(const Extent & extent)94   std::vector<Extent> GetNonIntersectingExtents(const Extent& extent) const {
95     return FilterExtentRanges({extent}, set_);
96   }
97 
98  private:
99   // Get a range of exents that potentially intersect with parameter |extent|
100   std::map<Extent, T, Comparator> map_;
101   ExtentRanges set_{false};
102 };
103 }  // namespace chromeos_update_engine
104 
105 #endif  // UPDATE_ENGINE_PAYLOAD_CONSUMER_EXTENT_MAP_H_
106