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