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 implemenation uses O(|V|+|E|) space.
40
41#include <cstdint>
42
43namespace absl {
44namespace synchronization_internal {
45
46// Opaque identifier for a graph node.
47struct GraphId {
48 uint64_t handle;
49
50 bool operator==(const GraphId& x) const { return handle == x.handle; }
51 bool operator!=(const GraphId& x) const { return handle != x.handle; }
52};
53
54// Return an invalid graph id that will never be assigned by GraphCycles.
55inline GraphId InvalidGraphId() {
56 return GraphId{0};
57}
58
59class GraphCycles {
60 public:
61 GraphCycles();
62 ~GraphCycles();
63
64 // Return the id to use for ptr, assigning one if necessary.
65 // Subsequent calls with the same ptr value will return the same id
66 // until Remove().
67 GraphId GetId(void* ptr);
68
69 // Remove "ptr" from the graph. Its corresponding node and all
70 // edges to and from it are removed.
71 void RemoveNode(void* ptr);
72
73 // Return the pointer associated with id, or nullptr if id is not
74 // currently in the graph.
75 void* Ptr(GraphId id);
76
77 // Attempt to insert an edge from source_node to dest_node. If the
78 // edge would introduce a cycle, return false without making any
79 // changes. Otherwise add the edge and return true.
80 bool InsertEdge(GraphId source_node, GraphId dest_node);
81
82 // Remove any edge that exists from source_node to dest_node.
83 void RemoveEdge(GraphId source_node, GraphId dest_node);
84
85 // Return whether node exists in the graph.
86 bool HasNode(GraphId node);
87
88 // Return whether there is an edge directly from source_node to dest_node.
89 bool HasEdge(GraphId source_node, GraphId dest_node) const;
90
91 // Return whether dest_node is reachable from source_node
92 // by following edges.
93 bool IsReachable(GraphId source_node, GraphId dest_node) const;
94
95 // Find a path from "source" to "dest". If such a path exists,
96 // place the nodes on the path in the array path[], and return
97 // the number of nodes on the path. If the path is longer than
98 // max_path_len nodes, only the first max_path_len nodes are placed
99 // in path[]. The client should compare the return value with
100 // max_path_len" to see when this occurs. If no path exists, return
101 // 0. Any valid path stored in path[] will start with "source" and
102 // end with "dest". There is no guarantee that the path is the
103 // shortest, but no node will appear twice in the path, except the
104 // source and destination node if they are identical; therefore, the
105 // return value is at most one greater than the number of nodes in
106 // the graph.
107 int FindPath(GraphId source, GraphId dest, int max_path_len,
108 GraphId path[]) const;
109
110 // Update the stack trace recorded for id with the current stack
111 // trace if the last time it was updated had a smaller priority
112 // than the priority passed on this call.
113 //
114 // *get_stack_trace is called to get the stack trace.
115 void UpdateStackTrace(GraphId id, int priority,
116 int (*get_stack_trace)(void**, int));
117
118 // Set *ptr to the beginning of the array that holds the recorded
119 // stack trace for id and return the depth of the stack trace.
120 int GetStackTrace(GraphId id, void*** ptr);
121
122 // Check internal invariants. Crashes on failure, returns true on success.
123 // Expensive: should only be called from graphcycles_test.cc.
124 bool CheckInvariants() const;
125
126 // ----------------------------------------------------
127 struct Rep;
128 private:
129 Rep *rep_; // opaque representation
130 GraphCycles(const GraphCycles&) = delete;
131 GraphCycles& operator=(const GraphCycles&) = delete;
132};
133
134} // namespace synchronization_internal
135} // namespace absl
136
137#endif
138