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