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 if (ExtentRanges::ExtentsOverlap(ext, extent)) { 60 LOG(WARNING) << "Looking up a partially intersecting extent isn't " 61 "supported by " 62 "this data structure. Querying extent: " 63 << extent << ", partial match in map: " << ext; 64 } 65 } 66 return {}; 67 } 68 return {it->second}; 69 } 70 71 // Return a set of extents that are contained in this extent map. 72 // If |extent| is completely covered by this extent map, a vector of itself 73 // will be returned. 74 // If only a subset of |extent| is covered by this extent map, a vector of 75 // parts in this map will be returned. 76 // If |extent| has no intersection with this map, an empty vector will be 77 // returned. 78 // E.g. extent map contains [0,5] and [10,15], GetIntersectingExtents([3, 12]) 79 // would return [3,5] and [10,12] GetIntersectingExtents(const Extent & extent)80 std::vector<Extent> GetIntersectingExtents(const Extent& extent) const { 81 return set_.GetIntersectingExtents(extent); 82 } 83 84 // Complement of |GetIntersectingExtents|, return vector of extents which are 85 // part of |extent| but not covered by this map. GetNonIntersectingExtents(const Extent & extent)86 std::vector<Extent> GetNonIntersectingExtents(const Extent& extent) const { 87 return FilterExtentRanges({extent}, set_); 88 } 89 90 private: 91 // Get a range of exents that potentially intersect with parameter |extent| 92 std::map<Extent, T, Comparator> map_; 93 ExtentRanges set_{false}; 94 }; 95 } // namespace chromeos_update_engine 96 97 #endif // UPDATE_ENGINE_PAYLOAD_CONSUMER_EXTENT_MAP_H_ 98