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