• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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() : valid(true), index(-1), lowlink(-1) {}
55   bool valid;
56 
57   typedef std::map<std::vector<Vertex>::size_type, EdgeProperties> EdgeMap;
58   EdgeMap out_edges;
59 
60   // We sometimes wish to consider a subgraph of a graph. A subgraph would have
61   // a subset of the vertices from the graph and a subset of the edges.
62   // When considering this vertex within a subgraph, subgraph_edges stores
63   // the out-edges.
64   typedef std::set<std::vector<Vertex>::size_type> SubgraphEdgeMap;
65   SubgraphEdgeMap subgraph_edges;
66 
67   // For Tarjan's algorithm:
68   std::vector<Vertex>::size_type index;
69   std::vector<Vertex>::size_type lowlink;
70 
71   // Other Vertex properties:
72   AnnotatedOperation aop;
73 
74   typedef std::vector<Vertex>::size_type Index;
75   static const Vertex::Index kInvalidIndex;
76 };
77 
78 typedef std::vector<Vertex> Graph;
79 
80 typedef std::pair<Vertex::Index, Vertex::Index> Edge;
81 
82 const uint64_t kTempBlockStart = 1ULL << 60;
83 static_assert(kTempBlockStart != 0, "kTempBlockStart invalid");
84 
85 }  // namespace chromeos_update_engine
86 
87 #endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
88