graph_types.h revision 9b244df41f1bdaddd87b7dbd8e1559556059ed1b 
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 UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
6#define UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
7
8#include <map>
9#include <set>
10#include <string>
11#include <utility>
12#include <vector>
13
14#include <base/macros.h>
15
16#include "update_engine/update_metadata.pb.h"
17
18// A few classes that help in generating delta images use these types
19// for the graph work.
20
21namespace chromeos_update_engine {
22
23bool operator==(const Extent& a, const Extent& b);
24
25struct EdgeProperties {
26  // Read-before extents. I.e., blocks in |extents| must be read by the
27  // node pointed to before the pointing node runs (presumably b/c it
28  // overwrites these blocks).
29  std::vector<Extent> extents;
30
31  // Write before extents. I.e., blocks in |write_extents| must be written
32  // by the node pointed to before the pointing node runs (presumably
33  // b/c it reads the data written by the other node).
34  std::vector<Extent> write_extents;
35
36  bool operator==(const EdgeProperties& that) const {
37    return extents == that.extents && write_extents == that.write_extents;
38  }
39};
40
41struct Vertex {
42  Vertex() :
43      valid(true),
44      index(-1),
45      lowlink(-1),
46      chunk_offset(0),
47      chunk_size(-1) {}
48  bool valid;
49
50  typedef std::map<std::vector<Vertex>::size_type, EdgeProperties> EdgeMap;
51  EdgeMap out_edges;
52
53  // We sometimes wish to consider a subgraph of a graph. A subgraph would have
54  // a subset of the vertices from the graph and a subset of the edges.
55  // When considering this vertex within a subgraph, subgraph_edges stores
56  // the out-edges.
57  typedef std::set<std::vector<Vertex>::size_type> SubgraphEdgeMap;
58  SubgraphEdgeMap subgraph_edges;
59
60  // For Tarjan's algorithm:
61  std::vector<Vertex>::size_type index;
62  std::vector<Vertex>::size_type lowlink;
63
64  // Other Vertex properties:
65  DeltaArchiveManifest_InstallOperation op;
66  std::string file_name;
67  off_t chunk_offset;
68  off_t chunk_size;
69
70  typedef std::vector<Vertex>::size_type Index;
71  static const Vertex::Index kInvalidIndex;
72};
73
74typedef std::vector<Vertex> Graph;
75
76typedef std::pair<Vertex::Index, Vertex::Index> Edge;
77
78const uint64_t kTempBlockStart = 1ULL << 60;
79COMPILE_ASSERT(kTempBlockStart != 0, kTempBlockStart_invalid);
80
81}  // namespace chromeos_update_engine
82
83#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
84