| // |
| // Copyright (C) 2009 The Android Open Source Project |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| // |
| |
| #ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_ |
| #define UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_ |
| |
| #include <map> |
| #include <set> |
| #include <string> |
| #include <utility> |
| #include <vector> |
| |
| #include <base/macros.h> |
| |
| #include "update_engine/payload_generator/annotated_operation.h" |
| #include "update_engine/payload_generator/extent_utils.h" |
| #include "update_engine/update_metadata.pb.h" |
| |
| // A few classes that help in generating delta images use these types |
| // for the graph work. |
| |
| namespace chromeos_update_engine { |
| |
| struct EdgeProperties { |
| // Read-before extents. I.e., blocks in |extents| must be read by the |
| // node pointed to before the pointing node runs (presumably b/c it |
| // overwrites these blocks). |
| std::vector<Extent> extents; |
| |
| // Write before extents. I.e., blocks in |write_extents| must be written |
| // by the node pointed to before the pointing node runs (presumably |
| // b/c it reads the data written by the other node). |
| std::vector<Extent> write_extents; |
| |
| bool operator==(const EdgeProperties& that) const { |
| return extents == that.extents && write_extents == that.write_extents; |
| } |
| }; |
| |
| struct Vertex { |
| Vertex() : |
| valid(true), |
| index(-1), |
| lowlink(-1) {} |
| bool valid; |
| |
| typedef std::map<std::vector<Vertex>::size_type, EdgeProperties> EdgeMap; |
| EdgeMap out_edges; |
| |
| // We sometimes wish to consider a subgraph of a graph. A subgraph would have |
| // a subset of the vertices from the graph and a subset of the edges. |
| // When considering this vertex within a subgraph, subgraph_edges stores |
| // the out-edges. |
| typedef std::set<std::vector<Vertex>::size_type> SubgraphEdgeMap; |
| SubgraphEdgeMap subgraph_edges; |
| |
| // For Tarjan's algorithm: |
| std::vector<Vertex>::size_type index; |
| std::vector<Vertex>::size_type lowlink; |
| |
| // Other Vertex properties: |
| AnnotatedOperation aop; |
| |
| typedef std::vector<Vertex>::size_type Index; |
| static const Vertex::Index kInvalidIndex; |
| }; |
| |
| typedef std::vector<Vertex> Graph; |
| |
| typedef std::pair<Vertex::Index, Vertex::Index> Edge; |
| |
| const uint64_t kTempBlockStart = 1ULL << 60; |
| static_assert(kTempBlockStart != 0, "kTempBlockStart invalid"); |
| |
| } // namespace chromeos_update_engine |
| |
| #endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_ |