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