graphcycles.h

Go to the documentation of this file.

// 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 implemenation uses O(|V|+|E|) space.

#include <cstdint>

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