extent_utils.h revision 14158570d3995008dc93a628004118b87a6bca01 
1// Copyright 2015 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_UTILS_H_
6#define UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_UTILS_H_
7
8#include <vector>
9
10#include "update_engine/payload_constants.h"
11#include "update_engine/update_metadata.pb.h"
12
13// Utility functions for manipulating Extents and lists of blocks.
14
15namespace chromeos_update_engine {
16
17// |block| must either be the next block in the last extent or a block
18// in the next extent. This function will not handle inserting block
19// into an arbitrary place in the extents.
20void AppendBlockToExtents(std::vector<Extent>* extents, uint64_t block);
21
22// Get/SetElement are intentionally overloaded so that templated functions
23// can accept either type of collection of Extents.
24Extent GetElement(const std::vector<Extent>& collection, size_t index);
25Extent GetElement(
26    const google::protobuf::RepeatedPtrField<Extent>& collection,
27    size_t index);
28
29// Return the total number of blocks in a collection (vector or
30// RepeatedPtrField) of Extents.
31template<typename T>
32uint64_t BlocksInExtents(const T& collection) {
33  uint64_t ret = 0;
34  for (size_t i = 0; i < static_cast<size_t>(collection.size()); ++i) {
35    ret += GetElement(collection, i).num_blocks();
36  }
37  return ret;
38}
39
40// Takes a collection (vector or RepeatedPtrField) of Extent and
41// returns a vector of the blocks referenced, in order.
42template<typename T>
43std::vector<uint64_t> ExpandExtents(const T& extents) {
44  std::vector<uint64_t> ret;
45  for (size_t i = 0, e = static_cast<size_t>(extents.size()); i != e; ++i) {
46    const Extent extent = GetElement(extents, i);
47    if (extent.start_block() == kSparseHole) {
48      ret.resize(ret.size() + extent.num_blocks(), kSparseHole);
49    } else {
50      for (uint64_t block = extent.start_block();
51           block < (extent.start_block() + extent.num_blocks()); block++) {
52        ret.push_back(block);
53      }
54    }
55  }
56  return ret;
57}
58
59// Stores all Extents in 'extents' into 'out'.
60void StoreExtents(const std::vector<Extent>& extents,
61                  google::protobuf::RepeatedPtrField<Extent>* out);
62
63// Stores all extents in |extents| into |out_vector|.
64void ExtentsToVector(const google::protobuf::RepeatedPtrField<Extent>& extents,
65                     std::vector<Extent>* out_vector);
66
67// Takes a pointer to extents |extents| and extents |extents_to_add|, and
68// merges them by adding |extents_to_add| to |extents| and normalizing.
69void ExtendExtents(
70  google::protobuf::RepeatedPtrField<Extent>* extents,
71  const google::protobuf::RepeatedPtrField<Extent>& extents_to_add);
72
73// Takes a vector of extents and normalizes those extents. Expects the extents
74// to be sorted by start block. E.g. if |extents| is [(1, 2), (3, 5), (10, 2)]
75// then |extents| will be changed to [(1, 7), (10, 2)].
76void NormalizeExtents(std::vector<Extent>* extents);
77
78// Return a subsequence of the list of blocks passed. Both the passed list of
79// blocks |extents| and the return value are expressed as a list of Extent, not
80// blocks. The returned list skips the first |block_offset| blocks from the
81// |extents| and cotains |block_count| blocks (or less if |extents| is shorter).
82std::vector<Extent> ExtentsSublist(const std::vector<Extent>& extents,
83                                   uint64_t block_offset, uint64_t block_count);
84
85bool operator==(const Extent& a, const Extent& b);
86
87}  // namespace chromeos_update_engine
88
89#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_UTILS_H_
90