about summary refs log tree commit diff
path: root/third_party/abseil_cpp/absl/synchronization/internal/graphcycles.h
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/abseil_cpp/absl/synchronization/internal/graphcycles.h')
-rw-r--r--third_party/abseil_cpp/absl/synchronization/internal/graphcycles.h141
1 files changed, 0 insertions, 141 deletions
diff --git a/third_party/abseil_cpp/absl/synchronization/internal/graphcycles.h b/third_party/abseil_cpp/absl/synchronization/internal/graphcycles.h
deleted file mode 100644
index ceba33e4de89..000000000000
--- a/third_party/abseil_cpp/absl/synchronization/internal/graphcycles.h
+++ /dev/null
@@ -1,141 +0,0 @@
-// 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 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 implementation uses O(|V|+|E|) space.
-
-#include <cstdint>
-
-#include "absl/base/config.h"
-
-namespace absl {
-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;
-
-  // ----------------------------------------------------
-  struct Rep;
- private:
-  Rep *rep_;      // opaque representation
-  GraphCycles(const GraphCycles&) = delete;
-  GraphCycles& operator=(const GraphCycles&) = delete;
-};
-
-}  // namespace synchronization_internal
-ABSL_NAMESPACE_END
-}  // namespace absl
-
-#endif