1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
// Copyright 2017 The Abseil Authors.
//
// 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
//
// https://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 Y_ABSL_SYNCHRONIZATION_INTERNAL_GRAPHCYCLES_H_
#define Y_ABSL_SYNCHRONIZATION_INTERNAL_GRAPHCYCLES_H_
// GraphCycles detects the introduction of a cycle into a directed
// graph that is being built up incrementally.
//
// Nodes are identified by small integers. It is not possible to
// record multiple edges with the same (source, destination) pair;
// requests to add an edge where one already exists are silently
// ignored.
//
// It is also not possible to introduce a cycle; an attempt to insert
// an edge that would introduce a cycle fails and returns false.
//
// GraphCycles uses no internal locking; calls into it should be
// serialized externally.
// Performance considerations:
// Works well on sparse graphs, poorly on dense graphs.
// Extra information is maintained incrementally to detect cycles quickly.
// InsertEdge() is very fast when the edge already exists, and reasonably fast
// otherwise.
// FindPath() is linear in the size of the graph.
// The current implementation uses O(|V|+|E|) space.
#include <cstdint>
#include "y_absl/base/config.h"
namespace y_absl {
Y_ABSL_NAMESPACE_BEGIN
namespace synchronization_internal {
// Opaque identifier for a graph node.
struct GraphId {
uint64_t handle;
bool operator==(const GraphId& x) const { return handle == x.handle; }
bool operator!=(const GraphId& x) const { return handle != x.handle; }
};
// Return an invalid graph id that will never be assigned by GraphCycles.
inline GraphId InvalidGraphId() {
return GraphId{0};
}
class GraphCycles {
public:
GraphCycles();
~GraphCycles();
// Return the id to use for ptr, assigning one if necessary.
// Subsequent calls with the same ptr value will return the same id
// until Remove().
GraphId GetId(void* ptr);
// Remove "ptr" from the graph. Its corresponding node and all
// edges to and from it are removed.
void RemoveNode(void* ptr);
// Return the pointer associated with id, or nullptr if id is not
// currently in the graph.
void* Ptr(GraphId id);
// Attempt to insert an edge from source_node to dest_node. If the
// edge would introduce a cycle, return false without making any
// changes. Otherwise add the edge and return true.
bool InsertEdge(GraphId source_node, GraphId dest_node);
// Remove any edge that exists from source_node to dest_node.
void RemoveEdge(GraphId source_node, GraphId dest_node);
// Return whether node exists in the graph.
bool HasNode(GraphId node);
// Return whether there is an edge directly from source_node to dest_node.
bool HasEdge(GraphId source_node, GraphId dest_node) const;
// Return whether dest_node is reachable from source_node
// by following edges.
bool IsReachable(GraphId source_node, GraphId dest_node) const;
// Find a path from "source" to "dest". If such a path exists,
// place the nodes on the path in the array path[], and return
// the number of nodes on the path. If the path is longer than
// max_path_len nodes, only the first max_path_len nodes are placed
// in path[]. The client should compare the return value with
// max_path_len" to see when this occurs. If no path exists, return
// 0. Any valid path stored in path[] will start with "source" and
// end with "dest". There is no guarantee that the path is the
// shortest, but no node will appear twice in the path, except the
// source and destination node if they are identical; therefore, the
// return value is at most one greater than the number of nodes in
// the graph.
int FindPath(GraphId source, GraphId dest, int max_path_len,
GraphId path[]) const;
// Update the stack trace recorded for id with the current stack
// trace if the last time it was updated had a smaller priority
// than the priority passed on this call.
//
// *get_stack_trace is called to get the stack trace.
void UpdateStackTrace(GraphId id, int priority,
int (*get_stack_trace)(void**, int));
// Set *ptr to the beginning of the array that holds the recorded
// stack trace for id and return the depth of the stack trace.
int GetStackTrace(GraphId id, void*** ptr);
// Check internal invariants. Crashes on failure, returns true on success.
// Expensive: should only be called from graphcycles_test.cc.
bool CheckInvariants() const;
// Test-only method to add more nodes. The nodes will not be valid, and this
// method should only be used to test the behavior of the graph when it is
// very full.
void TestOnlyAddNodes(uint32_t n);
// ----------------------------------------------------
struct Rep;
private:
Rep *rep_; // opaque representation
GraphCycles(const GraphCycles&) = delete;
GraphCycles& operator=(const GraphCycles&) = delete;
};
} // namespace synchronization_internal
Y_ABSL_NAMESPACE_END
} // namespace y_absl
#endif
|
