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 { 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 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
