extent_utils.cc revision 52490e776a9d34a94fb18ab1fe7d416425e94dda 
1// Copyright (c) 2009 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#include "update_engine/payload_generator/extent_utils.h"
6
7#include <string>
8#include <utility>
9#include <vector>
10
11#include <base/logging.h>
12#include <base/macros.h>
13
14#include "update_engine/extent_ranges.h"
15#include "update_engine/payload_constants.h"
16#include "update_engine/payload_generator/annotated_operation.h"
17
18using std::string;
19using std::vector;
20
21namespace chromeos_update_engine {
22
23void AppendBlockToExtents(vector<Extent>* extents, uint64_t block) {
24  // First try to extend the last extent in |extents|, if any.
25  if (!extents->empty()) {
26    Extent& extent = extents->back();
27    uint64_t next_block = extent.start_block() == kSparseHole ?
28        kSparseHole : extent.start_block() + extent.num_blocks();
29    if (next_block == block) {
30      extent.set_num_blocks(extent.num_blocks() + 1);
31      return;
32    }
33  }
34  // If unable to extend the last extent, append a new single-block extent.
35  Extent new_extent;
36  new_extent.set_start_block(block);
37  new_extent.set_num_blocks(1);
38  extents->push_back(new_extent);
39}
40
41Extent GetElement(const vector<Extent>& collection, size_t index) {
42  return collection[index];
43}
44Extent GetElement(
45    const google::protobuf::RepeatedPtrField<Extent>& collection,
46    size_t index) {
47  return collection.Get(index);
48}
49
50void NormalizeExtents(vector<Extent>* extents) {
51  vector<Extent> new_extents;
52  for (const Extent& curr_ext : *extents) {
53    if (new_extents.empty()) {
54      new_extents.push_back(curr_ext);
55      continue;
56    }
57    Extent& last_ext = new_extents.back();
58    if (last_ext.start_block() + last_ext.num_blocks() ==
59        curr_ext.start_block()) {
60      // If the extents are touching, we want to combine them.
61      last_ext.set_num_blocks(last_ext.num_blocks() + curr_ext.num_blocks());
62    } else {
63      // Otherwise just include the extent as is.
64      new_extents.push_back(curr_ext);
65    }
66  }
67  *extents = new_extents;
68}
69
70vector<Extent> ExtentsSublist(const vector<Extent>& extents,
71                              uint64_t block_offset, uint64_t block_count) {
72  vector<Extent> result;
73  uint64_t scanned_blocks = 0;
74  if (block_count == 0)
75    return result;
76  uint64_t end_block_offset = block_offset + block_count;
77  for (const Extent& extent : extents) {
78    // The loop invariant is that if |extents| has enough blocks, there's
79    // still some extent to add to |result|. This implies that at the beginning
80    // of the loop scanned_blocks < block_offset + block_count.
81    if (scanned_blocks + extent.num_blocks() > block_offset) {
82      // This case implies that |extent| has some overlapping with the requested
83      // subsequence.
84      uint64_t new_start = extent.start_block();
85      uint64_t new_num_blocks = extent.num_blocks();
86      if (scanned_blocks + new_num_blocks > end_block_offset) {
87        // Cut the end part of the extent.
88        new_num_blocks = end_block_offset - scanned_blocks;
89      }
90      if (block_offset > scanned_blocks) {
91        // Cut the begin part of the extent.
92        new_num_blocks -= block_offset - scanned_blocks;
93        new_start += block_offset - scanned_blocks;
94      }
95      result.push_back(ExtentForRange(new_start, new_num_blocks));
96    }
97    scanned_blocks += extent.num_blocks();
98    if (scanned_blocks >= end_block_offset)
99      break;
100  }
101  return result;
102}
103
104bool operator==(const Extent& a, const Extent& b) {
105  return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks();
106}
107
108}  // namespace chromeos_update_engine
109