extent_ranges.h revision aea4c1cea20dda7ae7e85fc8924a2d784f70d806 
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
35namespace chromeos_update_engine {
36
37struct ExtentLess {
38  bool operator()(const Extent& x, const Extent& y) const {
39    return x.start_block() < y.start_block();
40  }
41};
42
43Extent ExtentForRange(uint64_t start_block, uint64_t num_blocks);
44
45class 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|.
89std::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