graphcycles.h
Go to the documentation of this file.
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 
43 namespace absl {
44 namespace synchronization_internal {
45 
46 // Opaque identifier for a graph node.
47 struct 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.
56  return GraphId{0};
57 }
58 
59 class 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
bool operator!=(const GraphId &x) const
Definition: graphcycles.h:51
Definition: algorithm.h:29
GraphId path[kMaxDeadlockPathLen]
Definition: mutex.cc:1288
char * ptr
int priority
Definition: graphcycles.cc:284
bool operator==(const GraphId &x) const
Definition: graphcycles.h:50
static void CheckInvariants(const GraphCycles &gc)
static bool IsReachable(Edges *edges, int from, int to, std::unordered_set< int > *seen)
ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_NO_TAIL_CALL int GetStackTrace(void **result, int max_depth, int skip_count)
Definition: stacktrace.cc:98


abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:19:56