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

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

Definition at line 38 of file graphcycles_test.cc.

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

Definition at line 42 of file graphcycles_test.cc.

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

Definition at line 33 of file graphcycles_test.cc.

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

Definition at line 39 of file graphcycles_test.cc.

Function Documentation

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.

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.

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

static

Definition at line 161 of file graphcycles_test.cc.

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.

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

Definition at line 125 of file create_thread_identity.cc.

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

static

Definition at line 181 of file graphcycles_test.cc.

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

static

Definition at line 358 of file graphcycles.cc.

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.

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

static

Definition at line 43 of file graphcycles_test.cc.

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

inline

Definition at line 42 of file create_thread_identity.h.

GraphId absl::synchronization_internal::InvalidGraphId ( )

inline

Definition at line 55 of file graphcycles.h.

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.

static void absl::synchronization_internal::MaybeBecomeIdle ( )

static

Definition at line 54 of file waiter.cc.

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.

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

static

Definition at line 94 of file create_thread_identity.cc.

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

static

Definition at line 66 of file graphcycles_test.cc.

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

static

Definition at line 76 of file graphcycles_test.cc.

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

static

Definition at line 101 of file graphcycles_test.cc.

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

static

Definition at line 88 of file graphcycles_test.cc.

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

static

Definition at line 175 of file graphcycles_test.cc.

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

static

Definition at line 168 of file graphcycles_test.cc.

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

static

Definition at line 39 of file create_thread_identity.cc.

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

static

Definition at line 580 of file graphcycles.cc.

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

static

Definition at line 70 of file create_thread_identity.cc.

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

static

Definition at line 66 of file create_thread_identity.cc.

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

static

Definition at line 601 of file graphcycles.cc.

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

Definition at line 190 of file graphcycles_test.cc.

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

Definition at line 405 of file graphcycles_test.cc.

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

Definition at line 410 of file graphcycles_test.cc.

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

Definition at line 417 of file graphcycles_test.cc.

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

Definition at line 426 of file graphcycles_test.cc.

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

Definition at line 437 of file graphcycles_test.cc.

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

Definition at line 447 of file graphcycles_test.cc.

Variable Documentation

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

static

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

Function Documentation

Variable Documentation