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 { operatorExtentLess38 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 Extent ExtentForBytes(uint64_t block_size, 45 uint64_t start_bytes, 46 uint64_t size_bytes); 47 48 class ExtentRanges { 49 public: 50 typedef std::set<Extent, ExtentLess> ExtentSet; 51 ExtentRanges()52 ExtentRanges() : blocks_(0) {} 53 void AddBlock(uint64_t block); 54 void SubtractBlock(uint64_t block); 55 void AddExtent(Extent extent); 56 void SubtractExtent(const Extent& extent); 57 void AddExtents(const std::vector<Extent>& extents); 58 void SubtractExtents(const std::vector<Extent>& extents); 59 void AddRepeatedExtents( 60 const ::google::protobuf::RepeatedPtrField<Extent>& exts); 61 void SubtractRepeatedExtents( 62 const ::google::protobuf::RepeatedPtrField<Extent>& exts); 63 void AddRanges(const ExtentRanges& ranges); 64 void SubtractRanges(const ExtentRanges& ranges); 65 66 // Returns whether the block |block| is in this ExtentRange. 67 bool ContainsBlock(uint64_t block) const; 68 69 static bool ExtentsOverlapOrTouch(const Extent& a, const Extent& b); 70 static bool ExtentsOverlap(const Extent& a, const Extent& b); 71 72 // Dumps contents to the log file. Useful for debugging. 73 void Dump() const; 74 blocks()75 uint64_t blocks() const { return blocks_; } extent_set()76 const ExtentSet& extent_set() const { return extent_set_; } 77 78 // Returns an ordered vector of extents for |count| blocks, 79 // using extents in extent_set_. The returned extents are not 80 // removed from extent_set_. |count| must be less than or equal to 81 // the number of blocks in this extent set. 82 std::vector<Extent> GetExtentsForBlockCount(uint64_t count) const; 83 84 private: 85 ExtentSet extent_set_; 86 uint64_t blocks_; 87 }; 88 89 // Filters out from the passed list of extents |extents| all the blocks in the 90 // ExtentRanges set. Note that the order of the blocks in |extents| is preserved 91 // omitting blocks present in the ExtentRanges |ranges|. 92 std::vector<Extent> FilterExtentRanges(const std::vector<Extent>& extents, 93 const ExtentRanges& ranges); 94 95 } // namespace chromeos_update_engine 96 97 #endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_ 98