graph_types.h revision aea4c1cea20dda7ae7e85fc8924a2d784f70d806 
1//
2// Copyright (C) 2009 The Android Open Source Project
3//
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at
7//
8//      http://www.apache.org/licenses/LICENSE-2.0
9//
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15//
16
17#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
18#define UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
19
20#include <map>
21#include <set>
22#include <string>
23#include <utility>
24#include <vector>
25
26#include <base/macros.h>
27
28#include "update_engine/payload_generator/annotated_operation.h"
29#include "update_engine/payload_generator/extent_utils.h"
30#include "update_engine/update_metadata.pb.h"
31
32// A few classes that help in generating delta images use these types
33// for the graph work.
34
35namespace chromeos_update_engine {
36
37struct EdgeProperties {
38  // Read-before extents. I.e., blocks in |extents| must be read by the
39  // node pointed to before the pointing node runs (presumably b/c it
40  // overwrites these blocks).
41  std::vector<Extent> extents;
42
43  // Write before extents. I.e., blocks in |write_extents| must be written
44  // by the node pointed to before the pointing node runs (presumably
45  // b/c it reads the data written by the other node).
46  std::vector<Extent> write_extents;
47
48  bool operator==(const EdgeProperties& that) const {
49    return extents == that.extents && write_extents == that.write_extents;
50  }
51};
52
53struct Vertex {
54  Vertex() :
55      valid(true),
56      index(-1),
57      lowlink(-1) {}
58  bool valid;
59
60  typedef std::map<std::vector<Vertex>::size_type, EdgeProperties> EdgeMap;
61  EdgeMap out_edges;
62
63  // We sometimes wish to consider a subgraph of a graph. A subgraph would have
64  // a subset of the vertices from the graph and a subset of the edges.
65  // When considering this vertex within a subgraph, subgraph_edges stores
66  // the out-edges.
67  typedef std::set<std::vector<Vertex>::size_type> SubgraphEdgeMap;
68  SubgraphEdgeMap subgraph_edges;
69
70  // For Tarjan's algorithm:
71  std::vector<Vertex>::size_type index;
72  std::vector<Vertex>::size_type lowlink;
73
74  // Other Vertex properties:
75  AnnotatedOperation aop;
76
77  typedef std::vector<Vertex>::size_type Index;
78  static const Vertex::Index kInvalidIndex;
79};
80
81typedef std::vector<Vertex> Graph;
82
83typedef std::pair<Vertex::Index, Vertex::Index> Edge;
84
85const uint64_t kTempBlockStart = 1ULL << 60;
86COMPILE_ASSERT(kTempBlockStart != 0, kTempBlockStart_invalid);
87
88}  // namespace chromeos_update_engine
89
90#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
91