PaStiX Handbook: Sorted queue structure

Searching...

No Matches

Data Structures
struct	pastix_queue_item_s
	Queue item structure. More...

struct	pastix_queue_s
	Queue structure. More...

Typedefs
typedef struct pastix_queue_item_s	pastix_queue_item_t
	Queue item structure.

typedef struct pastix_queue_s	pastix_queue_t
	Queue structure.

Functions
int	pqueueInit (pastix_queue_t *q, pastix_int_t size)
	Initialize the queue structure with an initial space to store the elements.

void	pqueueExit (pastix_queue_t *q)
	Free the structure associated to the queue.

pastix_int_t	pqueueSize (const pastix_queue_t *q)
	Return the size of the queue.

void	pqueueClear (pastix_queue_t *q)
	Reset the number of used element to 0.

void	pqueuePush2 (pastix_queue_t *q, pastix_int_t elt, double key1, double key2)
	Insert an element into the sorted queue.

pastix_int_t	pqueueRead (const pastix_queue_t *q)
	Read the first element of the queue.

pastix_int_t	pqueuePop2 (pastix_queue_t q, double key1, double *key2)
	Remove the first element of the queue and return its keys if needed.

void	pqueuePrint (const pastix_queue_t *q)
	Print the queue.

static void	pqueuePush1 (pastix_queue_t *q, pastix_int_t elt, double key1)
	Push an element with a single key.

static pastix_int_t	pqueuePop (pastix_queue_t *q)
	Pop the head of the queue whithout returning the keys.

static pastix_int_t	pqueuePop1 (pastix_queue_t q, double key1)
	Pop the head of the queue and get the associated first key.

static int	pqueueItemComparison (const pastix_queue_item_t item1, const pastix_queue_item_t item2)
	Compare two items of the queue based on the couple (key1, key2).

Detailed Description

This module describes the queue structure used in the analyze part of the solver. The sorting is based on a balanced tree that is partially updated at insertion and suppression.

Data Type Documentation

◆ pastix_queue_item_s

struct pastix_queue_item_s

Queue item structure.

Definition at line 29 of file queue.h.

Data Fields
double	key1	Key 1 of the element
double	key2	Key 2 of the element
pastix_int_t	eltptr	Pointer to the element

◆ pastix_queue_s

struct pastix_queue_s

Queue structure.

Definition at line 38 of file queue.h.

Data Fields
pastix_int_t	size	Allocated memory size
volatile pastix_int_t	used	Number of element in the queue
pastix_queue_item_t *	elttab	Array of the element
pastix_atomic_lock_t	lock	Lock for insertion and removal in shared memory

Function Documentation

◆ pqueueInit()

int pqueueInit	(	pastix_queue_t *	q,
		pastix_int_t	size
	)

Initialize the queue structure with an initial space to store the elements.

Parameters

[in,out]	q	The qallocated pointer to the queue to initialize.
[in]	size	The initial size for the queue.

Return values

PASTIX_SUCCESS	if success.
PASTIX_ERR_OUTOFMEMORY	if malloc failed.

Definition at line 81 of file queue.c.

References pastix_queue_s::elttab, pastix_queue_s::lock, PASTIX_SUCCESS, pastix_queue_s::size, and pastix_queue_s::used.

Referenced by faxCSRAmalgamate(), order_tasks(), orderSupernodes(), propMappSubtree(), simuInit(), thread_cdiag_dynamic(), thread_cgetrf_dynamic(), thread_chetrf_dynamic(), thread_cpotrf_dynamic(), thread_cpxtrf_dynamic(), thread_csytrf_dynamic(), thread_ctrsm_dynamic(), thread_ddiag_dynamic(), thread_dgetrf_dynamic(), thread_dpotrf_dynamic(), thread_dsytrf_dynamic(), thread_dtrsm_dynamic(), thread_sdiag_dynamic(), thread_sgetrf_dynamic(), thread_spotrf_dynamic(), thread_ssytrf_dynamic(), thread_strsm_dynamic(), thread_zdiag_dynamic(), thread_zgetrf_dynamic(), thread_zhetrf_dynamic(), thread_zpotrf_dynamic(), thread_zpxtrf_dynamic(), thread_zsytrf_dynamic(), and thread_ztrsm_dynamic().

◆ pqueueExit()

void pqueueExit ( pastix_queue_t * q )

Free the structure associated to the queue.

Parameters

[in,out] q The pointer to the queue to free.

Definition at line 110 of file queue.c.

References pastix_queue_s::elttab, and pastix_queue_s::size.

Referenced by faxCSRAmalgamate(), order_tasks(), orderSupernodes(), propMappSubtree(), simuExit(), simuRealloc(), thread_cdiag_dynamic(), thread_cgetrf_dynamic(), thread_chetrf_dynamic(), thread_cpotrf_dynamic(), thread_cpxtrf_dynamic(), thread_csytrf_dynamic(), thread_ctrsm_dynamic(), thread_ddiag_dynamic(), thread_dgetrf_dynamic(), thread_dpotrf_dynamic(), thread_dsytrf_dynamic(), thread_dtrsm_dynamic(), thread_sdiag_dynamic(), thread_sgetrf_dynamic(), thread_spotrf_dynamic(), thread_ssytrf_dynamic(), thread_strsm_dynamic(), thread_zdiag_dynamic(), thread_zgetrf_dynamic(), thread_zhetrf_dynamic(), thread_zpotrf_dynamic(), thread_zpxtrf_dynamic(), thread_zsytrf_dynamic(), and thread_ztrsm_dynamic().

◆ pqueueSize()

pastix_int_t pqueueSize ( const pastix_queue_t * q )

Return the size of the queue.

Parameters

[in] q The pointer to the queue.

Returns: The size of the queue.

Definition at line 135 of file queue.c.

References pastix_queue_s::used.

Referenced by faxCSRAmalgamate(), order_tasks(), orderSupernodes(), propMappSubtree(), simu_getNextTaskNextProc(), simu_pushToReadyHeap(), and simuRun().

◆ pqueueClear()

void pqueueClear ( pastix_queue_t * q )

Reset the number of used element to 0.

Parameters

[in,out] q The pointer to the queue.

Definition at line 152 of file queue.c.

References pastix_queue_s::used.

◆ pqueuePush2()

void pqueuePush2	(	pastix_queue_t *	q,
		pastix_int_t	elt,
		double	key1,
		double	key2
	)

Insert an element into the sorted queue.

Parameters

[in,out]	q	The pointer to the queue.
[in]	elt	The element to insert in the queue.
[in]	key1	The first key of the element.
[in]	key2	The second key of the element.

Definition at line 178 of file queue.c.

References pastix_queue_item_s::eltptr, pastix_queue_s::elttab, pastix_queue_item_s::key1, pastix_queue_item_s::key2, pastix_queue_s::lock, pastix_int_t, pqueueItemComparison(), pastix_queue_s::size, and pastix_queue_s::used.

Referenced by pqueuePush1(), propMappSubtree(), simu_pushToReadyHeap(), and simu_putInAllReadyQueues().

◆ pqueueRead()

pastix_int_t pqueueRead ( const pastix_queue_t * q )

Read the first element of the queue.

Parameters

[in] q The pointer to the queue.

Returns: The value of the first element sorted by (key1, key2).

Definition at line 239 of file queue.c.

References pastix_queue_item_s::eltptr, and pastix_queue_s::elttab.

Referenced by simu_getNextTaskNextProc(), and simu_pushToReadyHeap().

◆ pqueuePop2()

pastix_int_t pqueuePop2	(	pastix_queue_t *	q,
		double *	key1,
		double *	key2
	)

Remove the first element of the queue and return its keys if needed.

Parameters

[in,out]	q	The pointer to the queue. On exit, the queue without its head.
[out]	key1	If key1 != NULL, stores the associated key1 to the first element on exit.
[out]	key2	If key2 != NULL, stores the associated key2 to the first element on exit.

Returns: The value of the first element sorted by (key1, key2).

Definition at line 268 of file queue.c.

Referenced by pqueuePop(), pqueuePop1(), and propMappSubtree().

◆ pqueuePrint()

void pqueuePrint ( const pastix_queue_t * q )

Print the queue.

Print the queue elements for debug. They are not printed in a sorted order, but in the order they are stored in the queue.

Parameters

[in] q The pointer to the queue.

Definition at line 334 of file queue.c.

References pastix_queue_item_s::eltptr, pastix_queue_s::elttab, pastix_queue_item_s::key1, pastix_queue_item_s::key2, pastix_int_t, and pastix_queue_s::used.

◆ pqueuePush1()

static void pqueuePush1	(	pastix_queue_t *	q,
		pastix_int_t	elt,
		double	key1
	)

inlinestatic

Push an element with a single key.

Parameters

[in,out]	q	The queue structure.
[in]	elt	The element to insert.
[in]	key1	The first key of the element to insert (the second will be 0.).

Definition at line 64 of file queue.h.

References pqueuePush2().

Referenced by cpucblk_cgetrfsp1dplus(), cpucblk_chetrfsp1dplus(), cpucblk_cpotrfsp1dplus(), cpucblk_cpxtrfsp1dplus(), cpucblk_crelease_deps(), cpucblk_crelease_rhs_bwd_deps(), cpucblk_crelease_rhs_fwd_deps(), cpucblk_csytrfsp1dplus(), cpucblk_dgetrfsp1dplus(), cpucblk_dpotrfsp1dplus(), cpucblk_drelease_deps(), cpucblk_drelease_rhs_bwd_deps(), cpucblk_drelease_rhs_fwd_deps(), cpucblk_dsytrfsp1dplus(), cpucblk_sgetrfsp1dplus(), cpucblk_spotrfsp1dplus(), cpucblk_srelease_deps(), cpucblk_srelease_rhs_bwd_deps(), cpucblk_srelease_rhs_fwd_deps(), cpucblk_ssytrfsp1dplus(), cpucblk_zgetrfsp1dplus(), cpucblk_zhetrfsp1dplus(), cpucblk_zpotrfsp1dplus(), cpucblk_zpxtrfsp1dplus(), cpucblk_zrelease_deps(), cpucblk_zrelease_rhs_bwd_deps(), cpucblk_zrelease_rhs_fwd_deps(), cpucblk_zsytrfsp1dplus(), faxCSRAmalgamate(), order_tasks(), orderSupernodes(), propMappSubtree(), thread_cdiag_dynamic(), thread_cgetrf_dynamic(), thread_chetrf_dynamic(), thread_cpotrf_dynamic(), thread_cpxtrf_dynamic(), thread_csytrf_dynamic(), thread_ctrsm_dynamic(), thread_ddiag_dynamic(), thread_dgetrf_dynamic(), thread_dpotrf_dynamic(), thread_dsytrf_dynamic(), thread_dtrsm_dynamic(), thread_sdiag_dynamic(), thread_sgetrf_dynamic(), thread_spotrf_dynamic(), thread_ssytrf_dynamic(), thread_strsm_dynamic(), thread_zdiag_dynamic(), thread_zgetrf_dynamic(), thread_zhetrf_dynamic(), thread_zpotrf_dynamic(), thread_zpxtrf_dynamic(), thread_zsytrf_dynamic(), and thread_ztrsm_dynamic().

◆ pqueuePop()

static pastix_int_t pqueuePop ( pastix_queue_t * q )

inlinestatic

Pop the head of the queue whithout returning the keys.

Parameters

[in,out] q The queue structure.

Returns: The element at the head of the queue.

Definition at line 75 of file queue.h.

References pqueuePop2().

Referenced by orderSupernodes(), propMappSubtree(), simu_getNextTaskNextProc(), simu_pushToReadyHeap(), stealQueue(), thread_cdiag_dynamic(), thread_cgetrf_dynamic(), thread_chetrf_dynamic(), thread_cpotrf_dynamic(), thread_cpxtrf_dynamic(), thread_csytrf_dynamic(), thread_ctrsm_dynamic(), thread_ddiag_dynamic(), thread_dgetrf_dynamic(), thread_dpotrf_dynamic(), thread_dsytrf_dynamic(), thread_dtrsm_dynamic(), thread_sdiag_dynamic(), thread_sgetrf_dynamic(), thread_spotrf_dynamic(), thread_ssytrf_dynamic(), thread_strsm_dynamic(), thread_zdiag_dynamic(), thread_zgetrf_dynamic(), thread_zhetrf_dynamic(), thread_zpotrf_dynamic(), thread_zpxtrf_dynamic(), thread_zsytrf_dynamic(), and thread_ztrsm_dynamic().

◆ pqueuePop1()

static pastix_int_t pqueuePop1	(	pastix_queue_t *	q,
		double *	key1
	)

inlinestatic

Pop the head of the queue and get the associated first key.

Parameters

[in,out]	q	The queue structure.
[out]	key1	The first key of the element removed from the head of the queue.

Returns: The element at the head of the queue.

Definition at line 88 of file queue.h.

References pqueuePop2().

Referenced by faxCSRAmalgamate(), and order_tasks().

◆ pqueueItemComparison()

static int pqueueItemComparison	(	const pastix_queue_item_t *	item1,
		const pastix_queue_item_t *	item2
	)

inlinestatic

Compare two items of the queue based on the couple (key1, key2).

Parameters

[in]	item1	The first item to compare.
[in]	item2	The second item to compare.

Return values

1	if item1 < item2
0	otherwise

Definition at line 45 of file queue.c.

References pastix_queue_item_s::key1, and pastix_queue_item_s::key2.

Referenced by pqueuePop2(), and pqueuePush2().

Data Structures

Typedefs

Functions

Detailed Description

Data Type Documentation

◆ pastix_queue_item_s

◆ pastix_queue_s

Function Documentation

◆ pqueueInit()

◆ pqueueExit()

◆ pqueueSize()

◆ pqueueClear()

◆ pqueuePush2()

◆ pqueueRead()

◆ pqueuePop2()

◆ pqueuePrint()

◆ pqueuePush1()

◆ pqueuePop()

◆ pqueuePop1()

◆ pqueueItemComparison()