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 
35 namespace chromeos_update_engine {
36 
37 struct 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 
53 struct Vertex {
VertexVertex54   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 
81 typedef std::vector<Vertex> Graph;
82 
83 typedef std::pair<Vertex::Index, Vertex::Index> Edge;
84 
85 const uint64_t kTempBlockStart = 1ULL << 60;
86 static_assert(kTempBlockStart != 0, "kTempBlockStart invalid");
87 
88 }  // namespace chromeos_update_engine
89 
90 #endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
91