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