Classes
struct	Edge

class	Futex

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	CheckEdges (Nodes nodes, Edges edges, const IdMap &id, GraphCycles *gc)

static void	CheckInvariants (const 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 Node *	FindNode (GraphCycles::Rep *rep, GraphId id)

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

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 void	MaybeBecomeIdle ()

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

static base_internal::ThreadIdentity *	NewThreadIdentity ()

static void	PrintEdges (Edges *edges)

static void	PrintGCEdges (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 int	RandomEdge (RandomEngine rng, Edges edges)

static int	RandomNode (RandomEngine rng, Nodes nodes)

static void	ReclaimThreadIdentity (void *v)

static void	Reorder (GraphCycles::Rep *r)

static void	ResetThreadIdentity (base_internal::ThreadIdentity *identity)

static intptr_t	RoundUp (intptr_t addr, intptr_t align)

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

	TEST (GraphCycles, RandomizedTest)

	TEST_F (GraphCyclesTest, NoCycle)

	TEST_F (GraphCyclesTest, SimpleCycle)

	TEST_F (GraphCyclesTest, IndirectCycle)

	TEST_F (GraphCyclesTest, LongPath)

	TEST_F (GraphCyclesTest, RemoveNode)

	TEST_F (GraphCyclesTest, ManyEdges)

Variables
static base_internal::SpinLock	freelist_lock (base_internal::kLinkerInitialized)

static base_internal::ThreadIdentity *	thread_identity_freelist

Typedef Documentation

◆ Edges

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

Definition at line 38 of file graphcycles_test.cc.

◆ IdMap

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

Definition at line 42 of file graphcycles_test.cc.

◆ Nodes

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

Definition at line 33 of file graphcycles_test.cc.

◆ RandomEngine

using absl::synchronization_internal::RandomEngine = typedef std::mt19937_64

Definition at line 39 of file graphcycles_test.cc.

Function Documentation

◆ BackwardDFS()

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

static

Definition at line 558 of file graphcycles.cc.

◆ CheckEdges()

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

static

Definition at line 135 of file graphcycles_test.cc.

◆ CheckInvariants()

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

static

Definition at line 161 of file graphcycles_test.cc.

◆ CheckTransitiveClosure()

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

static

Definition at line 114 of file graphcycles_test.cc.

◆ CreateThreadIdentity()

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

Definition at line 125 of file create_thread_identity.cc.

◆ EdgeIndex()

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

static

Definition at line 181 of file graphcycles_test.cc.

◆ FindNode()

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

static

Definition at line 358 of file graphcycles.cc.

◆ ForwardDFS()

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

static

Definition at line 530 of file graphcycles.cc.

◆ Get()

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

static

Definition at line 43 of file graphcycles_test.cc.

◆ GetOrCreateCurrentThreadIdentity()

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

inline

Definition at line 42 of file create_thread_identity.h.

◆ InvalidGraphId()

GraphId absl::synchronization_internal::InvalidGraphId ( )

inline

Definition at line 55 of file graphcycles.h.

◆ IsReachable()

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

static

Definition at line 49 of file graphcycles_test.cc.

◆ MaybeBecomeIdle()

static void absl::synchronization_internal::MaybeBecomeIdle ( )

static

Definition at line 54 of file waiter.cc.

◆ MoveToList()

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

static

Definition at line 613 of file graphcycles.cc.

◆ NewThreadIdentity()

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

static

Definition at line 94 of file create_thread_identity.cc.

◆ PrintEdges()

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

static

Definition at line 66 of file graphcycles_test.cc.

◆ PrintGCEdges()

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

static

Definition at line 76 of file graphcycles_test.cc.

◆ PrintGCTransitiveClosure()

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

static

Definition at line 101 of file graphcycles_test.cc.

◆ PrintTransitiveClosure()

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

static

Definition at line 88 of file graphcycles_test.cc.

◆ RandomEdge()

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

static

Definition at line 175 of file graphcycles_test.cc.

◆ RandomNode()

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

static

Definition at line 168 of file graphcycles_test.cc.

◆ ReclaimThreadIdentity()

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

static

Definition at line 39 of file create_thread_identity.cc.

◆ Reorder()

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

static

Definition at line 580 of file graphcycles.cc.

◆ ResetThreadIdentity()

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

static

Definition at line 70 of file create_thread_identity.cc.

◆ RoundUp()

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

static

Definition at line 66 of file create_thread_identity.cc.

◆ Sort()

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

static

Definition at line 601 of file graphcycles.cc.

◆ TEST()

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

Definition at line 190 of file graphcycles_test.cc.

◆ TEST_F() [1/6]

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

Definition at line 405 of file graphcycles_test.cc.

◆ TEST_F() [2/6]

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

Definition at line 410 of file graphcycles_test.cc.

◆ TEST_F() [3/6]

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

Definition at line 417 of file graphcycles_test.cc.

◆ TEST_F() [4/6]

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

Definition at line 426 of file graphcycles_test.cc.

◆ TEST_F() [5/6]

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

Definition at line 437 of file graphcycles_test.cc.

◆ TEST_F() [6/6]

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

Definition at line 447 of file graphcycles_test.cc.

Variable Documentation

◆ freelist_lock

base_internal::SpinLock absl::synchronization_internal::freelist_lock(base_internal::kLinkerInitialized)

static

◆ thread_identity_freelist

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

static

Definition at line 35 of file create_thread_identity.cc.

Classes

Typedefs

Functions

Variables

Typedef Documentation

◆ Edges

◆ IdMap

◆ Nodes

◆ RandomEngine

Function Documentation

◆ BackwardDFS()

◆ CheckEdges()

◆ CheckInvariants()

◆ CheckTransitiveClosure()

◆ CreateThreadIdentity()

◆ EdgeIndex()

◆ FindNode()

◆ ForwardDFS()

◆ Get()

◆ GetOrCreateCurrentThreadIdentity()

◆ InvalidGraphId()

◆ IsReachable()

◆ MaybeBecomeIdle()

◆ MoveToList()

◆ NewThreadIdentity()

◆ PrintEdges()

◆ PrintGCEdges()

◆ PrintGCTransitiveClosure()

◆ PrintTransitiveClosure()

◆ RandomEdge()

◆ RandomNode()

◆ ReclaimThreadIdentity()

◆ Reorder()

◆ ResetThreadIdentity()

◆ RoundUp()

◆ Sort()

◆ 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

◆ freelist_lock

◆ thread_identity_freelist