graph_types.h revision 3b2c7d0e6d859e6fc75c82b3417f87cf5968a49d
1// Copyright (c) 2009 The Chromium OS Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_ 6#define UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_ 7 8#include <map> 9#include <set> 10#include <string> 11#include <utility> 12#include <vector> 13 14#include <base/macros.h> 15 16#include "update_engine/payload_generator/annotated_operation.h" 17#include "update_engine/payload_generator/extent_utils.h" 18#include "update_engine/update_metadata.pb.h" 19 20// A few classes that help in generating delta images use these types 21// for the graph work. 22 23namespace chromeos_update_engine { 24 25struct EdgeProperties { 26 // Read-before extents. I.e., blocks in |extents| must be read by the 27 // node pointed to before the pointing node runs (presumably b/c it 28 // overwrites these blocks). 29 std::vector<Extent> extents; 30 31 // Write before extents. I.e., blocks in |write_extents| must be written 32 // by the node pointed to before the pointing node runs (presumably 33 // b/c it reads the data written by the other node). 34 std::vector<Extent> write_extents; 35 36 bool operator==(const EdgeProperties& that) const { 37 return extents == that.extents && write_extents == that.write_extents; 38 } 39}; 40 41struct Vertex { 42 Vertex() : 43 valid(true), 44 index(-1), 45 lowlink(-1) {} 46 bool valid; 47 48 typedef std::map<std::vector<Vertex>::size_type, EdgeProperties> EdgeMap; 49 EdgeMap out_edges; 50 51 // We sometimes wish to consider a subgraph of a graph. A subgraph would have 52 // a subset of the vertices from the graph and a subset of the edges. 53 // When considering this vertex within a subgraph, subgraph_edges stores 54 // the out-edges. 55 typedef std::set<std::vector<Vertex>::size_type> SubgraphEdgeMap; 56 SubgraphEdgeMap subgraph_edges; 57 58 // For Tarjan's algorithm: 59 std::vector<Vertex>::size_type index; 60 std::vector<Vertex>::size_type lowlink; 61 62 // Other Vertex properties: 63 AnnotatedOperation aop; 64 65 typedef std::vector<Vertex>::size_type Index; 66 static const Vertex::Index kInvalidIndex; 67}; 68 69typedef std::vector<Vertex> Graph; 70 71typedef std::pair<Vertex::Index, Vertex::Index> Edge; 72 73const uint64_t kTempBlockStart = 1ULL << 60; 74COMPILE_ASSERT(kTempBlockStart != 0, kTempBlockStart_invalid); 75 76} // namespace chromeos_update_engine 77 78#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_ 79