1 // 2 // Copyright (C) 2010 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_GENERATOR_EXTENT_RANGES_H_ 18 #define UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_ 19 20 #include <map> 21 #include <set> 22 #include <vector> 23 24 #include <base/macros.h> 25 26 #include "update_engine/update_metadata.pb.h" 27 28 // An ExtentRanges object represents an unordered collection of extents (and 29 // therefore blocks). Such an object may be modified by adding or subtracting 30 // blocks (think: set addition or set subtraction). Note that ExtentRanges 31 // ignores sparse hole extents mostly to avoid confusion between extending a 32 // sparse hole range vs. set addition but also to ensure that the delta 33 // generator doesn't use sparse holes as scratch space. 34 35 namespace chromeos_update_engine { 36 37 struct ExtentLess { 38 bool operator()(const Extent& x, const Extent& y) const { 39 return x.start_block() < y.start_block(); 40 } 41 }; 42 43 Extent ExtentForRange(uint64_t start_block, uint64_t num_blocks); 44 45 class ExtentRanges { 46 public: 47 typedef std::set<Extent, ExtentLess> ExtentSet; 48 49 ExtentRanges() : blocks_(0) {} 50 void AddBlock(uint64_t block); 51 void SubtractBlock(uint64_t block); 52 void AddExtent(Extent extent); 53 void SubtractExtent(const Extent& extent); 54 void AddExtents(const std::vector<Extent>& extents); 55 void SubtractExtents(const std::vector<Extent>& extents); 56 void AddRepeatedExtents( 57 const ::google::protobuf::RepeatedPtrField<Extent> &exts); 58 void SubtractRepeatedExtents( 59 const ::google::protobuf::RepeatedPtrField<Extent> &exts); 60 void AddRanges(const ExtentRanges& ranges); 61 void SubtractRanges(const ExtentRanges& ranges); 62 63 // Returns whether the block |block| is in this ExtentRange. 64 bool ContainsBlock(uint64_t block) const; 65 66 static bool ExtentsOverlapOrTouch(const Extent& a, const Extent& b); 67 static bool ExtentsOverlap(const Extent& a, const Extent& b); 68 69 // Dumps contents to the log file. Useful for debugging. 70 void Dump() const; 71 72 uint64_t blocks() const { return blocks_; } 73 const ExtentSet& extent_set() const { return extent_set_; } 74 75 // Returns an ordered vector of extents for |count| blocks, 76 // using extents in extent_set_. The returned extents are not 77 // removed from extent_set_. |count| must be less than or equal to 78 // the number of blocks in this extent set. 79 std::vector<Extent> GetExtentsForBlockCount(uint64_t count) const; 80 81 private: 82 ExtentSet extent_set_; 83 uint64_t blocks_; 84 }; 85 86 // Filters out from the passed list of extents |extents| all the blocks in the 87 // ExtentRanges set. Note that the order of the blocks in |extents| is preserved 88 // omitting blocks present in the ExtentRanges |ranges|. 89 std::vector<Extent> FilterExtentRanges(const std::vector<Extent>& extents, 90 const ExtentRanges& ranges); 91 92 } // namespace chromeos_update_engine 93 94 #endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_ 95
