Classes
struct	Edge

class	GraphCycles

class	GraphCyclesTest

struct	GraphId

class	KernelTimeout

class	PerThreadSem

class	PerThreadSemTest

class	SimpleSemaphore

struct	ThreadData

class	ThreadPool

class	Waiter

Typedefs
using	Edges = std::vector< Edge >

typedef std::map< int, GraphId >	IdMap

using	Nodes = std::vector< int >

using	RandomEngine = std::mt19937_64

Functions
static void	BackwardDFS (GraphCycles::Rep *r, int32_t n, int32_t lower_bound)

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

static void	CheckEdges (Nodes nodes, Edges edges, const IdMap &id, GraphCycles *gc)

static void	CheckEdges (Nodes nodes, Edges edges, const IdMap &id, GraphCycles *gc)

static void	CheckInvariants (const GraphCycles &gc)

static void	CheckInvariants (const GraphCycles &gc)

static void	CheckTransitiveClosure (Nodes nodes, Edges edges, const IdMap &id, GraphCycles *gc)

static void	CheckTransitiveClosure (Nodes nodes, Edges edges, const IdMap &id, GraphCycles *gc)

base_internal::ThreadIdentity *	CreateThreadIdentity ()

static int	EdgeIndex (Edges *edges, int from, int to)

static int	EdgeIndex (Edges *edges, int from, int to)

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

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

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

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

static ABSL_CONST_INIT base_internal::SpinLock	freelist_lock (absl::kConstInit, base_internal::SCHEDULE_KERNEL_ONLY)

static ABSL_CONST_INIT base_internal::SpinLock	freelist_lock (absl::kConstInit, base_internal::SCHEDULE_KERNEL_ONLY)

static GraphId	Get (const IdMap &id, int num)

static GraphId	Get (const IdMap &id, int num)

base_internal::ThreadIdentity *	GetOrCreateCurrentThreadIdentity ()

GraphId	InvalidGraphId ()

static bool	IsReachable (Edges edges, int from, int to, std::unordered_set< int > seen)

static bool	IsReachable (Edges edges, int from, int to, std::unordered_set< int > seen)

static void	MaybeBecomeIdle ()

static void	MaybeBecomeIdle ()

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

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

int	MutexDelay (int32_t c, int mode)

static base_internal::ThreadIdentity *	NewThreadIdentity ()

static base_internal::ThreadIdentity *	NewThreadIdentity ()

void	OneTimeInitThreadIdentity (base_internal::ThreadIdentity *identity)

static void	PrintEdges (Edges *edges)

static void	PrintEdges (Edges *edges)

static void	PrintGCEdges (Nodes nodes, const IdMap &id, GraphCycles gc)

static void	PrintGCEdges (Nodes nodes, const IdMap &id, GraphCycles gc)

static void	PrintGCTransitiveClosure (Nodes nodes, const IdMap &id, GraphCycles gc)

static void	PrintGCTransitiveClosure (Nodes nodes, const IdMap &id, GraphCycles gc)

static void	PrintTransitiveClosure (Nodes nodes, Edges edges)

static void	PrintTransitiveClosure (Nodes nodes, Edges edges)

static int	RandomEdge (RandomEngine rng, Edges edges)

static int	RandomEdge (RandomEngine rng, Edges edges)

static int	RandomNode (RandomEngine rng, Nodes nodes)

static int	RandomNode (RandomEngine rng, Nodes nodes)

static void	ReclaimThreadIdentity (void *v)

static void	Reorder (GraphCycles::Rep *r)

static void	Reorder (GraphCycles::Rep *r)

static void	ResetThreadIdentity (base_internal::ThreadIdentity *identity)

static void	ResetThreadIdentityBetweenReuse (base_internal::ThreadIdentity *identity)

static intptr_t	RoundUp (intptr_t addr, intptr_t align)

static intptr_t	RoundUp (intptr_t addr, intptr_t align)

static void	Sort (const Vec< Node * > &, Vec< int32_t > *delta)

static void	Sort (const Vec< Node * > &, Vec< int32_t > *delta)

	TEST (GraphCycles, RandomizedTest)

	TEST_F (GraphCyclesTest, IndirectCycle)

	TEST_F (GraphCyclesTest, LongPath)

	TEST_F (GraphCyclesTest, ManyEdges)

	TEST_F (GraphCyclesTest, NoCycle)

	TEST_F (GraphCyclesTest, RemoveNode)

	TEST_F (GraphCyclesTest, SimpleCycle)

Variables
static ABSL_CONST_INIT base_internal::ThreadIdentity *	thread_identity_freelist

static ABSL_CONST_INIT base_internal::ThreadIdentity *	thread_identity_freelist

Typedef Documentation

◆ Edges

typedef std::vector< Edge > absl::synchronization_internal::Edges

Definition at line 39 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ IdMap

typedef std::map< int, GraphId > absl::synchronization_internal::IdMap

Definition at line 43 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ Nodes

typedef std::vector< int > absl::synchronization_internal::Nodes

Definition at line 34 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ RandomEngine

typedef std::mt19937_64 absl::synchronization_internal::RandomEngine

Definition at line 40 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

Function Documentation

◆ BackwardDFS() [1/2]

static void absl::synchronization_internal::BackwardDFS	(	GraphCycles::Rep *	r,
		int32_t	n,
		int32_t	lower_bound
	)

static

Definition at line 560 of file abseil-cpp/absl/synchronization/internal/graphcycles.cc.

◆ BackwardDFS() [2/2]

static void absl::synchronization_internal::BackwardDFS	(	GraphCycles::Rep *	r,
		int32_t	n,
		int32_t	lower_bound
	)

static

Definition at line 560 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles.cc.

◆ CheckEdges() [1/2]

static void absl::synchronization_internal::CheckEdges	(	Nodes *	nodes,
		Edges *	edges,
		const IdMap &	id,
		GraphCycles *	gc
	)

static

Definition at line 136 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ CheckEdges() [2/2]

static void absl::synchronization_internal::CheckEdges	(	Nodes *	nodes,
		Edges *	edges,
		const IdMap &	id,
		GraphCycles *	gc
	)

static

Definition at line 136 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ CheckInvariants() [1/2]

static void absl::synchronization_internal::CheckInvariants ( const GraphCycles & gc )

static

Definition at line 162 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ CheckInvariants() [2/2]

static void absl::synchronization_internal::CheckInvariants ( const GraphCycles & gc )

static

Definition at line 162 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ CheckTransitiveClosure() [1/2]

static void absl::synchronization_internal::CheckTransitiveClosure	(	Nodes *	nodes,
		Edges *	edges,
		const IdMap &	id,
		GraphCycles *	gc
	)

static

Definition at line 115 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ CheckTransitiveClosure() [2/2]

static void absl::synchronization_internal::CheckTransitiveClosure	(	Nodes *	nodes,
		Edges *	edges,
		const IdMap &	id,
		GraphCycles *	gc
	)

static

Definition at line 115 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ CreateThreadIdentity()

base_internal::ThreadIdentity * absl::synchronization_internal::CreateThreadIdentity ( )

Definition at line 132 of file abseil-cpp/absl/synchronization/internal/create_thread_identity.cc.

◆ EdgeIndex() [1/2]

static int absl::synchronization_internal::EdgeIndex	(	Edges *	edges,
		int	from,
		int	to
	)

static

Definition at line 182 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ EdgeIndex() [2/2]

static int absl::synchronization_internal::EdgeIndex	(	Edges *	edges,
		int	from,
		int	to
	)

static

Definition at line 182 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ FindNode() [1/2]

static Node* absl::synchronization_internal::FindNode	(	GraphCycles::Rep *	rep,
		GraphId	id
	)

static

Definition at line 360 of file abseil-cpp/absl/synchronization/internal/graphcycles.cc.

◆ FindNode() [2/2]

static Node* absl::synchronization_internal::FindNode	(	GraphCycles::Rep *	rep,
		GraphId	id
	)

static

Definition at line 360 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles.cc.

◆ ForwardDFS() [1/2]

static bool absl::synchronization_internal::ForwardDFS	(	GraphCycles::Rep *	r,
		int32_t	n,
		int32_t	upper_bound
	)

static

Definition at line 532 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles.cc.

◆ ForwardDFS() [2/2]

static bool absl::synchronization_internal::ForwardDFS	(	GraphCycles::Rep *	r,
		int32_t	n,
		int32_t	upper_bound
	)

static

Definition at line 532 of file abseil-cpp/absl/synchronization/internal/graphcycles.cc.

◆ freelist_lock() [1/2]

static ABSL_CONST_INIT base_internal::SpinLock absl::synchronization_internal::freelist_lock	(	absl::kConstInit	,
		base_internal::SCHEDULE_KERNEL_ONLY
	)

static

◆ freelist_lock() [2/2]

static ABSL_CONST_INIT base_internal::SpinLock absl::synchronization_internal::freelist_lock	(	absl::kConstInit	,
		base_internal::SCHEDULE_KERNEL_ONLY
	)

static

◆ Get() [1/2]

static GraphId absl::synchronization_internal::Get	(	const IdMap &	id,
		int	num
	)

static

Definition at line 44 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ Get() [2/2]

static GraphId absl::synchronization_internal::Get	(	const IdMap &	id,
		int	num
	)

static

Definition at line 44 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ GetOrCreateCurrentThreadIdentity()

base_internal::ThreadIdentity * absl::synchronization_internal::GetOrCreateCurrentThreadIdentity ( )

inline

Definition at line 43 of file abseil-cpp/absl/synchronization/internal/create_thread_identity.h.

◆ InvalidGraphId()

GraphId absl::synchronization_internal::InvalidGraphId ( )

inline

Definition at line 58 of file abseil-cpp/absl/synchronization/internal/graphcycles.h.

◆ IsReachable() [1/2]

static bool absl::synchronization_internal::IsReachable	(	Edges *	edges,
		int	from,
		int	to,
		std::unordered_set< int > *	seen
	)

static

Definition at line 50 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ IsReachable() [2/2]

static bool absl::synchronization_internal::IsReachable	(	Edges *	edges,
		int	from,
		int	to,
		std::unordered_set< int > *	seen
	)

static

Definition at line 50 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ MaybeBecomeIdle() [1/2]

static void absl::synchronization_internal::MaybeBecomeIdle ( )

static

Definition at line 56 of file abseil-cpp/absl/synchronization/internal/waiter.cc.

◆ MaybeBecomeIdle() [2/2]

static void absl::synchronization_internal::MaybeBecomeIdle ( )

static

Definition at line 56 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/waiter.cc.

◆ MoveToList() [1/2]

static void absl::synchronization_internal::MoveToList	(	GraphCycles::Rep *	r,
		Vec< int32_t > *	src,
		Vec< int32_t > *	dst
	)

static

Definition at line 615 of file abseil-cpp/absl/synchronization/internal/graphcycles.cc.

◆ MoveToList() [2/2]

static void absl::synchronization_internal::MoveToList	(	GraphCycles::Rep *	r,
		Vec< int32_t > *	src,
		Vec< int32_t > *	dst
	)

static

Definition at line 615 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles.cc.

◆ MutexDelay()

int absl::synchronization_internal::MutexDelay	(	int32_t	c,
		int	mode
	)

Definition at line 165 of file abseil-cpp/absl/synchronization/mutex.cc.

◆ NewThreadIdentity() [1/2]

static base_internal::ThreadIdentity* absl::synchronization_internal::NewThreadIdentity ( )

static

Definition at line 97 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/create_thread_identity.cc.

◆ NewThreadIdentity() [2/2]

static base_internal::ThreadIdentity* absl::synchronization_internal::NewThreadIdentity ( )

static

Definition at line 100 of file abseil-cpp/absl/synchronization/internal/create_thread_identity.cc.

◆ OneTimeInitThreadIdentity()

void absl::synchronization_internal::OneTimeInitThreadIdentity ( base_internal::ThreadIdentity * identity )

Definition at line 72 of file abseil-cpp/absl/synchronization/internal/create_thread_identity.cc.

◆ PrintEdges() [1/2]

static void absl::synchronization_internal::PrintEdges ( Edges * edges )

static

Definition at line 67 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ PrintEdges() [2/2]

static void absl::synchronization_internal::PrintEdges ( Edges * edges )

static

Definition at line 67 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ PrintGCEdges() [1/2]

static void absl::synchronization_internal::PrintGCEdges	(	Nodes *	nodes,
		const IdMap &	id,
		GraphCycles *	gc
	)

static

Definition at line 77 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ PrintGCEdges() [2/2]

static void absl::synchronization_internal::PrintGCEdges	(	Nodes *	nodes,
		const IdMap &	id,
		GraphCycles *	gc
	)

static

Definition at line 77 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ PrintGCTransitiveClosure() [1/2]

static void absl::synchronization_internal::PrintGCTransitiveClosure	(	Nodes *	nodes,
		const IdMap &	id,
		GraphCycles *	gc
	)

static

Definition at line 102 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ PrintGCTransitiveClosure() [2/2]

static void absl::synchronization_internal::PrintGCTransitiveClosure	(	Nodes *	nodes,
		const IdMap &	id,
		GraphCycles *	gc
	)

static

Definition at line 102 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ PrintTransitiveClosure() [1/2]

static void absl::synchronization_internal::PrintTransitiveClosure	(	Nodes *	nodes,
		Edges *	edges
	)

static

Definition at line 89 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ PrintTransitiveClosure() [2/2]

static void absl::synchronization_internal::PrintTransitiveClosure	(	Nodes *	nodes,
		Edges *	edges
	)

static

Definition at line 89 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ RandomEdge() [1/2]

static int absl::synchronization_internal::RandomEdge	(	RandomEngine *	rng,
		Edges *	edges
	)

static

Definition at line 176 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ RandomEdge() [2/2]

static int absl::synchronization_internal::RandomEdge	(	RandomEngine *	rng,
		Edges *	edges
	)

static

Definition at line 176 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ RandomNode() [1/2]

static int absl::synchronization_internal::RandomNode	(	RandomEngine *	rng,
		Nodes *	nodes
	)

static

Definition at line 169 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ RandomNode() [2/2]

static int absl::synchronization_internal::RandomNode	(	RandomEngine *	rng,
		Nodes *	nodes
	)

static

Definition at line 169 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ ReclaimThreadIdentity()

void absl::synchronization_internal::ReclaimThreadIdentity ( void * v )

static

Definition at line 41 of file abseil-cpp/absl/synchronization/internal/create_thread_identity.cc.

◆ Reorder() [1/2]

static void absl::synchronization_internal::Reorder ( GraphCycles::Rep * r )

static

Definition at line 582 of file abseil-cpp/absl/synchronization/internal/graphcycles.cc.

◆ Reorder() [2/2]

static void absl::synchronization_internal::Reorder ( GraphCycles::Rep * r )

static

Definition at line 582 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles.cc.

◆ ResetThreadIdentity()

static void absl::synchronization_internal::ResetThreadIdentity ( base_internal::ThreadIdentity * identity )

static

Definition at line 74 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/create_thread_identity.cc.

◆ ResetThreadIdentityBetweenReuse()

static void absl::synchronization_internal::ResetThreadIdentityBetweenReuse ( base_internal::ThreadIdentity * identity )

static

Definition at line 76 of file abseil-cpp/absl/synchronization/internal/create_thread_identity.cc.

◆ RoundUp() [1/2]

static intptr_t absl::synchronization_internal::RoundUp	(	intptr_t	addr,
		intptr_t	align
	)

static

Definition at line 68 of file abseil-cpp/absl/synchronization/internal/create_thread_identity.cc.

◆ RoundUp() [2/2]

static intptr_t absl::synchronization_internal::RoundUp	(	intptr_t	addr,
		intptr_t	align
	)

static

Definition at line 70 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/create_thread_identity.cc.

◆ Sort() [1/2]

static void absl::synchronization_internal::Sort	(	const Vec< Node * > &	nodes,
		Vec< int32_t > *	delta
	)

static

Definition at line 603 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/graphcycles.cc.

◆ Sort() [2/2]

static void absl::synchronization_internal::Sort	(	const Vec< Node * > &	nodes,
		Vec< int32_t > *	delta
	)

static

Definition at line 603 of file abseil-cpp/absl/synchronization/internal/graphcycles.cc.

◆ TEST()

absl::synchronization_internal::TEST	(	GraphCycles	,
		RandomizedTest
	)

Definition at line 191 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ TEST_F() [1/6]

absl::synchronization_internal::TEST_F	(	GraphCyclesTest	,
		IndirectCycle
	)

Definition at line 418 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ TEST_F() [2/6]

absl::synchronization_internal::TEST_F	(	GraphCyclesTest	,
		LongPath
	)

Definition at line 427 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ TEST_F() [3/6]

absl::synchronization_internal::TEST_F	(	GraphCyclesTest	,
		ManyEdges
	)

Definition at line 448 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ TEST_F() [4/6]

absl::synchronization_internal::TEST_F	(	GraphCyclesTest	,
		NoCycle
	)

Definition at line 406 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ TEST_F() [5/6]

absl::synchronization_internal::TEST_F	(	GraphCyclesTest	,
		RemoveNode
	)

Definition at line 438 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

◆ TEST_F() [6/6]

absl::synchronization_internal::TEST_F	(	GraphCyclesTest	,
		SimpleCycle
	)

Definition at line 411 of file abseil-cpp/absl/synchronization/internal/graphcycles_test.cc.

Variable Documentation

◆ thread_identity_freelist [1/2]

ABSL_CONST_INIT base_internal::ThreadIdentity* absl::synchronization_internal::thread_identity_freelist

static

Definition at line 37 of file abseil-cpp/absl/synchronization/internal/create_thread_identity.cc.

◆ thread_identity_freelist [2/2]

ABSL_CONST_INIT base_internal::ThreadIdentity* absl::synchronization_internal::thread_identity_freelist

static

Definition at line 37 of file bloaty/third_party/abseil-cpp/absl/synchronization/internal/create_thread_identity.cc.

Classes

Typedefs

Functions

Variables

Typedef Documentation

◆ Edges

◆ IdMap

◆ Nodes

◆ RandomEngine

Function Documentation

◆ BackwardDFS() [1/2]

◆ BackwardDFS() [2/2]

◆ CheckEdges() [1/2]

◆ CheckEdges() [2/2]

◆ CheckInvariants() [1/2]

◆ CheckInvariants() [2/2]

◆ CheckTransitiveClosure() [1/2]

◆ CheckTransitiveClosure() [2/2]

◆ CreateThreadIdentity()

◆ EdgeIndex() [1/2]

◆ EdgeIndex() [2/2]

◆ FindNode() [1/2]

◆ FindNode() [2/2]

◆ ForwardDFS() [1/2]

◆ ForwardDFS() [2/2]

◆ freelist_lock() [1/2]

◆ freelist_lock() [2/2]

◆ Get() [1/2]

◆ Get() [2/2]

◆ GetOrCreateCurrentThreadIdentity()

◆ InvalidGraphId()

◆ IsReachable() [1/2]

◆ IsReachable() [2/2]

◆ MaybeBecomeIdle() [1/2]

◆ MaybeBecomeIdle() [2/2]

◆ MoveToList() [1/2]

◆ MoveToList() [2/2]

◆ MutexDelay()

◆ NewThreadIdentity() [1/2]

◆ NewThreadIdentity() [2/2]

◆ OneTimeInitThreadIdentity()

◆ PrintEdges() [1/2]

◆ PrintEdges() [2/2]

◆ PrintGCEdges() [1/2]

◆ PrintGCEdges() [2/2]

◆ PrintGCTransitiveClosure() [1/2]

◆ PrintGCTransitiveClosure() [2/2]

◆ PrintTransitiveClosure() [1/2]

◆ PrintTransitiveClosure() [2/2]

◆ RandomEdge() [1/2]

◆ RandomEdge() [2/2]

◆ RandomNode() [1/2]

◆ RandomNode() [2/2]

◆ ReclaimThreadIdentity()

◆ Reorder() [1/2]

◆ Reorder() [2/2]

◆ ResetThreadIdentity()

◆ ResetThreadIdentityBetweenReuse()

◆ RoundUp() [1/2]

◆ RoundUp() [2/2]

◆ Sort() [1/2]

◆ Sort() [2/2]

◆ TEST()

◆ TEST_F() [1/6]

◆ TEST_F() [2/6]

◆ TEST_F() [3/6]

◆ TEST_F() [4/6]

◆ TEST_F() [5/6]

◆ TEST_F() [6/6]

Variable Documentation

◆ thread_identity_freelist [1/2]

◆ thread_identity_freelist [2/2]