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 <utility> | 11 #include <utility> |
11 #include <vector> | 12 #include <vector> |
12 #include "base/basictypes.h" | 13 #include "base/basictypes.h" |
13 #include "update_engine/update_metadata.pb.h" | 14 #include "update_engine/update_metadata.pb.h" |
14 | 15 |
15 // 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 |
16 // for the graph work. | 17 // for the graph work. |
17 | 18 |
18 namespace chromeos_update_engine { | 19 namespace chromeos_update_engine { |
19 | 20 |
20 struct EdgeProperties { | 21 struct EdgeProperties { |
21 std::vector<Extent> extents; // filesystem extents represented | 22 std::vector<Extent> extents; // filesystem extents represented |
22 }; | 23 }; |
23 | 24 |
24 struct Vertex { | 25 struct Vertex { |
25 Vertex() : index(-1), lowlink(-1), op(NULL) {} | 26 Vertex() : index(-1), lowlink(-1) {} |
26 typedef std::map<std::vector<Vertex>::size_type, EdgeProperties> EdgeMap; | 27 typedef std::map<std::vector<Vertex>::size_type, EdgeProperties> EdgeMap; |
27 EdgeMap out_edges; | 28 EdgeMap out_edges; |
28 | 29 |
29 // We sometimes wish to consider a subgraph of a graph. A subgraph would have | 30 // We sometimes wish to consider a subgraph of a graph. A subgraph would have |
30 // a subset of the vertices from the graph and a subset of the edges. | 31 // a subset of the vertices from the graph and a subset of the edges. |
31 // When considering this vertex within a subgraph, subgraph_edges stores | 32 // When considering this vertex within a subgraph, subgraph_edges stores |
32 // the out-edges. | 33 // the out-edges. |
33 typedef std::set<std::vector<Vertex>::size_type> SubgraphEdgeMap; | 34 typedef std::set<std::vector<Vertex>::size_type> SubgraphEdgeMap; |
34 SubgraphEdgeMap subgraph_edges; | 35 SubgraphEdgeMap subgraph_edges; |
35 | 36 |
36 // For Tarjan's algorithm: | 37 // For Tarjan's algorithm: |
37 std::vector<Vertex>::size_type index; | 38 std::vector<Vertex>::size_type index; |
38 std::vector<Vertex>::size_type lowlink; | 39 std::vector<Vertex>::size_type lowlink; |
39 | 40 |
40 // Other Vertex properties: | 41 // Other Vertex properties: |
41 DeltaArchiveManifest_InstallOperation* op; | 42 DeltaArchiveManifest_InstallOperation op; |
| 43 std::string file_name; |
42 | 44 |
43 typedef std::vector<Vertex>::size_type Index; | 45 typedef std::vector<Vertex>::size_type Index; |
44 static const Vertex::Index kInvalidIndex = -1; | 46 static const Vertex::Index kInvalidIndex = -1; |
45 }; | 47 }; |
46 | 48 |
47 typedef std::vector<Vertex> Graph; | 49 typedef std::vector<Vertex> Graph; |
48 | 50 |
49 typedef std::pair<Vertex::Index, Vertex::Index> Edge; | 51 typedef std::pair<Vertex::Index, Vertex::Index> Edge; |
50 | 52 |
| 53 const uint64 kSparseHole = kuint64max; |
| 54 |
51 } // namespace chromeos_update_engine | 55 } // namespace chromeos_update_engine |
52 | 56 |
53 #endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_TYPES_H__ | 57 #endif // CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_TYPES_H__ |
OLD | NEW |