EIC code displayed by LXR master/​include/​absl/​synchronization/​internal/​graphcycles.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2025-01-30 09:31:55

 // 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;
 
   // Test-only method to add more nodes. The nodes will not be valid, and this
   // method should only be used to test the behavior of the graph when it is
   // very full.
   void TestOnlyAddNodes(uint32_t n);
 
   // ----------------------------------------------------
   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

This page was automatically generated by the 2.3.7 LXR engine. The LXR team