chromium/third_party/abseil-cpp/absl/synchronization/internal/graphcycles.cc

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

// GraphCycles provides incremental cycle detection on a dynamic
// graph using the following algorithm:
//
// A dynamic topological sort algorithm for directed acyclic graphs
// David J. Pearce, Paul H. J. Kelly
// Journal of Experimental Algorithmics (JEA) JEA Homepage archive
// Volume 11, 2006, Article No. 1.7
//
// Brief summary of the algorithm:
//
// (1) Maintain a rank for each node that is consistent
//     with the topological sort of the graph. I.e., path from x to y
//     implies rank[x] < rank[y].
// (2) When a new edge (x->y) is inserted, do nothing if rank[x] < rank[y].
// (3) Otherwise: adjust ranks in the neighborhood of x and y.

#include "absl/base/attributes.h"
// This file is a no-op if the required LowLevelAlloc support is missing.
#include "absl/base/internal/low_level_alloc.h"
#ifndef ABSL_LOW_LEVEL_ALLOC_MISSING

#include "absl/synchronization/internal/graphcycles.h"

#include <algorithm>
#include <array>
#include <cinttypes>
#include <limits>
#include "absl/base/internal/hide_ptr.h"
#include "absl/base/internal/raw_logging.h"
#include "absl/base/internal/spinlock.h"

// Do not use STL.   This module does not use standard memory allocation.

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace synchronization_internal {

namespace {

// Avoid LowLevelAlloc's default arena since it calls malloc hooks in
// which people are doing things like acquiring Mutexes.
ABSL_CONST_INIT static absl::base_internal::SpinLock arena_mu(
    absl::kConstInit, base_internal::SCHEDULE_KERNEL_ONLY);
ABSL_CONST_INIT static base_internal::LowLevelAlloc::Arena* arena;

static void InitArenaIfNecessary() { … }

// Number of inlined elements in Vec.  Hash table implementation
// relies on this being a power of two.
static const uint32_t kInline = …;

// A simple LowLevelAlloc based resizable vector with inlined storage
// for a few elements.  T must be a plain type since constructor
// and destructor are not run on elements of type T managed by Vec.
template <typename T>
class Vec { … };

// A hash set of non-negative int32_t that uses Vec for its underlying storage.
class NodeSet { … };

// We encode a node index and a node version in GraphId.  The version
// number is incremented when the GraphId is freed which automatically
// invalidates all copies of the GraphId.

inline GraphId MakeId(int32_t index, uint32_t version) { … }

inline int32_t NodeIndex(GraphId id) { … }

inline uint32_t NodeVersion(GraphId id) { … }

struct Node { … };

// Hash table for pointer to node index lookups.
class PointerMap { … };

}  // namespace

struct GraphCycles::Rep { … };

static Node* FindNode(GraphCycles::Rep* rep, GraphId id) { … }

void GraphCycles::TestOnlyAddNodes(uint32_t n) { … }

GraphCycles::GraphCycles() { … }

GraphCycles::~GraphCycles() { … }

bool GraphCycles::CheckInvariants() const { … }

GraphId GraphCycles::GetId(void* ptr) { … }

void GraphCycles::RemoveNode(void* ptr) { … }

void* GraphCycles::Ptr(GraphId id) { … }

bool GraphCycles::HasNode(GraphId node) { … }

bool GraphCycles::HasEdge(GraphId x, GraphId y) const { … }

void GraphCycles::RemoveEdge(GraphId x, GraphId y) { … }

static bool ForwardDFS(GraphCycles::Rep* r, int32_t n, int32_t upper_bound);
static void BackwardDFS(GraphCycles::Rep* r, int32_t n, int32_t lower_bound);
static void Reorder(GraphCycles::Rep* r);
static void Sort(const Vec<Node*>&, Vec<int32_t>* delta);
static void MoveToList(
    GraphCycles::Rep* r, Vec<int32_t>* src, Vec<int32_t>* dst);

bool GraphCycles::InsertEdge(GraphId idx, GraphId idy) { … }

static bool ForwardDFS(GraphCycles::Rep* r, int32_t n, int32_t upper_bound) { … }

static void BackwardDFS(GraphCycles::Rep* r, int32_t n, int32_t lower_bound) { … }

static void Reorder(GraphCycles::Rep* r) { … }

static void Sort(const Vec<Node*>& nodes, Vec<int32_t>* delta) { … }

static void MoveToList(
    GraphCycles::Rep* r, Vec<int32_t>* src, Vec<int32_t>* dst) { … }

int GraphCycles::FindPath(GraphId idx, GraphId idy, int max_path_len,
                          GraphId path[]) const { … }

bool GraphCycles::IsReachable(GraphId x, GraphId y) const { … }

void GraphCycles::UpdateStackTrace(GraphId id, int priority,
                                   int (*get_stack_trace)(void** stack, int)) { … }

int GraphCycles::GetStackTrace(GraphId id, void*** ptr) { … }

}  // namespace synchronization_internal
ABSL_NAMESPACE_END
}  // namespace absl

#endif  // ABSL_LOW_LEVEL_ALLOC_MISSING