graph_utils.h revision 161c4a132743f15fc4757112b673085c2a7a7f29 
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#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
6#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
7
8#include <vector>
9
10#include <base/basictypes.h>
11
12#include "update_engine/payload_generator/graph_types.h"
13#include "update_engine/update_metadata.pb.h"
14
15// A few utility functions for graphs
16
17namespace chromeos_update_engine {
18
19namespace graph_utils {
20
21// Returns the number of blocks represented by all extents in the edge.
22uint64_t EdgeWeight(const Graph& graph, const Edge& edge);
23
24// These add a read-before dependency from graph[src] -> graph[dst]. If the dep
25// already exists, the block/s is/are added to the existing edge.
26void AddReadBeforeDep(Vertex* src,
27                      Vertex::Index dst,
28                      uint64_t block);
29void AddReadBeforeDepExtents(Vertex* src,
30                             Vertex::Index dst,
31                             const std::vector<Extent>& extents);
32
33void DropWriteBeforeDeps(Vertex::EdgeMap* edge_map);
34
35// For each node N in graph, drop all edges N->|index|.
36void DropIncomingEdgesTo(Graph* graph, Vertex::Index index);
37
38// block must either be the next block in the last extent or a block
39// in the next extent. This function will not handle inserting block
40// into an arbitrary place in the extents.
41void AppendBlockToExtents(std::vector<Extent>* extents, uint64_t block);
42
43// Get/SetElement are intentionally overloaded so that templated functions
44// can accept either type of collection of Extents.
45Extent GetElement(const std::vector<Extent>& collection, size_t index);
46Extent GetElement(
47    const google::protobuf::RepeatedPtrField<Extent>& collection,
48    size_t index);
49
50template<typename T>
51uint64_t BlocksInExtents(const T& collection) {
52  uint64_t ret = 0;
53  for (size_t i = 0; i < static_cast<size_t>(collection.size()); ++i) {
54    ret += GetElement(collection, i).num_blocks();
55  }
56  return ret;
57}
58
59void DumpGraph(const Graph& graph);
60
61}  // namespace graph_utils
62
63}  // namespace chromeos_update_engine
64
65#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
66