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