From c2e754829628d1e9b7a16b3389cfdace76950fdf Mon Sep 17 00:00:00 2001 From: misterg Date: Tue, 19 Sep 2017 16:54:40 -0400 Subject: Initial Commit --- absl/synchronization/internal/graphcycles.h | 136 ++++++++++++++++++++++++++++ 1 file changed, 136 insertions(+) create mode 100644 absl/synchronization/internal/graphcycles.h (limited to 'absl/synchronization/internal/graphcycles.h') diff --git a/absl/synchronization/internal/graphcycles.h b/absl/synchronization/internal/graphcycles.h new file mode 100644 index 0000000..53474b7 --- /dev/null +++ b/absl/synchronization/internal/graphcycles.h @@ -0,0 +1,136 @@ +// 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 +// +// http://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 ABSL_SYNCHRONIZATION_INTERNAL_GRAPHCYCLES_H_ +#define 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 implemenation uses O(|V|+|E|) space. + +#include + +namespace absl { +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; + + // ---------------------------------------------------- + struct Rep; + private: + Rep *rep_; // opaque representation + GraphCycles(const GraphCycles&) = delete; + GraphCycles& operator=(const GraphCycles&) = delete; +}; + +} // namespace synchronization_internal +} // namespace absl +#endif -- cgit v1.2.3