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 true if the input extent overlaps with the current ExtentRanges. 67 bool OverlapsWithExtent(const Extent& extent) const; 68 69 // Returns whether the block |block| is in this ExtentRange. 70 bool ContainsBlock(uint64_t block) const; 71 72 static bool ExtentsOverlapOrTouch(const Extent& a, const Extent& b); 73 static bool ExtentsOverlap(const Extent& a, const Extent& b); 74 75 // Dumps contents to the log file. Useful for debugging. 76 void Dump() const; 77 blocks()78 uint64_t blocks() const { return blocks_; } extent_set()79 const ExtentSet& extent_set() const { return extent_set_; } 80 81 // Returns an ordered vector of extents for |count| blocks, 82 // using extents in extent_set_. The returned extents are not 83 // removed from extent_set_. |count| must be less than or equal to 84 // the number of blocks in this extent set. 85 std::vector<Extent> GetExtentsForBlockCount(uint64_t count) const; 86 87 private: 88 ExtentSet extent_set_; 89 uint64_t blocks_; 90 }; 91 92 // Filters out from the passed list of extents |extents| all the blocks in the 93 // ExtentRanges set. Note that the order of the blocks in |extents| is preserved 94 // omitting blocks present in the ExtentRanges |ranges|. 95 std::vector<Extent> FilterExtentRanges(const std::vector<Extent>& extents, 96 const ExtentRanges& ranges); 97 98 } // namespace chromeos_update_engine 99 100 #endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_ 101