tor-browser

graphcycles.h (5472B)

---

// 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