From 5aa5d282eac56a21e74611c1cdbaa97bb5db2dca Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Tue, 8 Feb 2022 02:05:36 +0300 Subject: chore(3p/abseil_cpp): unvendor abseil_cpp we weren't actually using these sources anymore, okay? Change-Id: If701571d9716de308d3512e1eb22c35db0877a66 Reviewed-on: https://cl.tvl.fyi/c/depot/+/5248 Tested-by: BuildkiteCI Reviewed-by: grfn Autosubmit: tazjin --- .../absl/synchronization/internal/graphcycles.h | 141 --------------------- 1 file changed, 141 deletions(-) delete mode 100644 third_party/abseil_cpp/absl/synchronization/internal/graphcycles.h (limited to 'third_party/abseil_cpp/absl/synchronization/internal/graphcycles.h') 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 - -#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 -- cgit 1.4.1