Routines for managing quadrants as elements of trees and subtrees. More...

#include <p8est_extended.h>

Include dependency graph for p8est_algorithms.h:

Functions
sc_mempool_t *	p8est_quadrant_mempool_new (void)
	Create a memory pool for quadrants that initializes compiler padding. More...

void	p8est_quadrant_init_data (p8est_t p8est, p4est_topidx_t which_tree, p8est_quadrant_t quad, p8est_init_t init_fn)
	Alloc and initialize the user data of a valid quadrant. More...

void	p8est_quadrant_free_data (p8est_t p8est, p8est_quadrant_t quad)
	Free the user data of a valid quadrant. More...

unsigned	p8est_quadrant_checksum (sc_array_t quadrants, sc_array_t checkarray, size_t first_quadrant)
	Computes a machine-independent checksum of a list of quadrants. More...

int	p8est_quadrant_in_range (const p8est_quadrant_t fd, const p8est_quadrant_t ld, const p8est_quadrant_t *quadrant)
	Report whether a quadrant fits into the limits of a quadrant range. More...

int	p8est_tree_is_sorted (p8est_tree_t *tree)
	Test if a tree is sorted in Morton ordering. More...

int	p8est_tree_is_linear (p8est_tree_t *tree)
	Test if a tree is sorted in Morton ordering and linear. More...

int	p8est_tree_is_complete (p8est_tree_t *tree)
	Test if a tree is sorted in Morton ordering and complete. More...

int	p8est_tree_is_almost_sorted (p8est_tree_t *tree, int check_linearity)
	Check if a tree is sorted/linear except across edges or corners. More...

void	p8est_tree_print (int log_priority, p8est_tree_t *tree)
	Print the quadrants in a tree. More...

int	p8est_is_equal (p8est_t p8est1, p8est_t p8est2, int compare_data)
	Locally check forest/connectivity structures for equality. More...

int	p8est_is_valid (p8est_t *p8est)
	Check a forest for validity and allreduce the result. More...

void	p8est_tree_compute_overlap (p8est_t p8est, sc_array_t in, sc_array_t out, p8est_connect_type_t balance, sc_array_t borders, sc_array_t *inseeds)
	Compute the overlap of a number of insulation layers with a tree. More...

void	p8est_tree_uniqify_overlap (sc_array_t *out)
	Gets the reduced representation of the overlap that results from using p8est_tree_compute_overlap_new. More...

size_t	p8est_tree_remove_nonowned (p8est_t *p8est, p4est_topidx_t which_tree)
	Removes quadrants that are outside the owned tree boundaries from a tree. More...

void	p8est_complete_region (p8est_t p8est, const p8est_quadrant_t q1, int include_q1, const p8est_quadrant_t q2, int include_q2, p8est_tree_t tree, p4est_topidx_t which_tree, p8est_init_t init_fn)
	Constructs a minimal linear octree between two octants. More...

void	p8est_complete_subtree (p8est_t *p8est, p4est_topidx_t which_tree, p8est_init_t init_fn)
	Completes a sorted tree within a p8est. More...

void	p8est_balance_subtree (p8est_t *p8est, p8est_connect_type_t btype, p4est_topidx_t which_tree, p8est_init_t init_fn)
	Balances a sorted tree within a p8est. More...

void	p8est_balance_border (p8est_t p8est, p8est_connect_type_t btype, p4est_topidx_t which_tree, p8est_init_t init_fn, p8est_replace_t replace_fn, sc_array_t borders)

size_t	p8est_linearize_tree (p8est_t p8est, p8est_tree_t tree)
	Remove overlaps from a sorted list of quadrants. More...

p4est_locidx_t	p8est_partition_correction (p4est_gloidx_t *partition, int num_procs, int rank, p4est_gloidx_t min_quadrant_id, p4est_gloidx_t max_quadrant_id)
	Compute correction of partition for a process. More...

p4est_gloidx_t	p8est_partition_for_coarsening (p8est_t p8est, p4est_locidx_t num_quadrants_in_proc)
	Correct partition counters to allow one level of coarsening. More...

int	p8est_next_nonempty_process (int rank, int num_procs, p4est_locidx_t *num_quadrants_in_proc)
	Find next non-empty process. More...

p4est_gloidx_t	p8est_partition_given (p8est_t p8est, const p4est_locidx_t num_quadrants_in_proc)
	Partition p8est given the number of quadrants per proc. More...

int	p8est_quadrant_on_face_boundary (p8est_t p4est, p4est_topidx_t treeid, int face, const p8est_quadrant_t q)
	Checks if a quadrant's face is on the boundary of the forest. More...

Detailed Description

Routines for managing quadrants as elements of trees and subtrees.

In addition, some high level algorithms such as p4est_partition_given.

Function Documentation

◆ p8est_balance_subtree()

void p8est_balance_subtree	(	p8est_t *	p8est,
		p8est_connect_type_t	btype,
		p4est_topidx_t	which_tree,
		p8est_init_t	init_fn
	)

Balances a sorted tree within a p8est.

It may have exterior quadrants. The completed tree will have only owned quadrants and no overlap.

Parameters

[in,out]	p8est	The p8est to work on.
[in]	btype	The balance type (face, edge or corner).
[in]	which_tree	The 0-based index of the subtree to balance.
[in]	init_fn	Callback function to initialize the user_data which is already allocated automatically.

◆ p8est_complete_region()

void p8est_complete_region	(	p8est_t *	p8est,
		const p8est_quadrant_t *	q1,
		int	include_q1,
		const p8est_quadrant_t *	q2,
		int	include_q2,
		p8est_tree_t *	tree,
		p4est_topidx_t	which_tree,
		p8est_init_t	init_fn
	)

Constructs a minimal linear octree between two octants.

This is algorithm 2 from H. Sundar, R.S. Sampath and G. Biros with the additional improvements that we do not require sorting and the runtime is O(N).

Precondition: q1 < q2 in the Morton ordering.

Parameters

[in]	p8est	Used for the memory pools and quadrant init.
[in]	q1	First input quadrant. Data init'ed if included.
[in]	include_q1	Flag to specify whether q1 is included.
[in]	q2	Second input quadrant. Data init'ed if included.
[in]	include_q2	Flag to specify whether q2 is included.
[out]	tree	Initialized tree with zero elements.
[in]	which_tree	The 0-based index of tree which is needed for the `p8est_quadrant_init_data` routine.
[in]	init_fn	Callback function to initialize the user_data which is already allocated automatically.

◆ p8est_complete_subtree()

void p8est_complete_subtree	(	p8est_t *	p8est,
		p4est_topidx_t	which_tree,
		p8est_init_t	init_fn
	)

Completes a sorted tree within a p8est.

It may have exterior quadrants. The completed tree will have only owned quadrants and no overlap. Note that the tree's counters (quadrants_per_level, maxlevel) must be correct for the quadrants in the incoming tree.

Parameters

[in,out]	p8est	The p8est to work on.
[in]	which_tree	The 0-based index of the subtree to complete.
[in]	init_fn	Callback function to initialize the user_data which is already allocated automatically.

◆ p8est_is_equal()

int p8est_is_equal	(	p8est_t *	p8est1,
		p8est_t *	p8est2,
		int	compare_data
	)

Locally check forest/connectivity structures for equality.

Parameters

[in]	p8est1	The first forest to be compared.
[in]	p8est2	The second forest to be compared.
[in]	compare_data	Also check if quadrant data are identical.

Returns: Returns true if forests and their connectivities are equal.

◆ p8est_is_valid()

int p8est_is_valid ( p8est_t * p8est )

Check a forest for validity and allreduce the result.

Some properties of a valid forest are: the quadrant counters are consistent all trees are complete all non-local trees are empty This function is collective! It is also relatively expensive, so its use in production should be limited.

Parameters

[in] p8est The forest to be tested. Itself and its connectivity must be non-NULL.

Returns: Returns true if valid, false otherwise.

◆ p8est_linearize_tree()

size_t p8est_linearize_tree	(	p8est_t *	p8est,
		p8est_tree_t *	tree
	)

Remove overlaps from a sorted list of quadrants.

This is algorithm 8 from H. Sundar, R.S. Sampath and G. Biros with the additional improvement that it works in-place.

Parameters

[in]	p8est	used for the memory pool and quadrant free.
[in,out]	tree	A sorted tree to be linearized in-place.

Returns: Returns the number of removed quadrants.

◆ p8est_next_nonempty_process()

int p8est_next_nonempty_process	(	int	rank,
		int	num_procs,
		p4est_locidx_t *	num_quadrants_in_proc
	)

Find next non-empty process.

Finds the next process id >= rank which is not empty according to num_quadrants_in_proc.

Parameters

[in]	rank	process id where search starts
[in]	num_proc	number of processes
[in]	num_quadrants_in_proc	number of quadrants for each process

Returns: process id of a non empty process

◆ p8est_partition_correction()

p4est_locidx_t p8est_partition_correction	(	p4est_gloidx_t *	partition,
		int	num_procs,
		int	rank,
		p4est_gloidx_t	min_quadrant_id,
		p4est_gloidx_t	max_quadrant_id
	)

Compute correction of partition for a process.

The correction denotes how many quadrants the process with id rank takes from (if correction positive) or gives to (if correction negative) the previous process with id rank-1 in order to assign a family of quadrants to one process. The process with the highest number of quadrants of a family gets all quadrants belonging to this family from other processes. If this applies to several processes, then the process with the lowest id gets the quadrants. A process can give more quadrants than it owns, if it passes quadrants from other processes.

Parameters

[in]	partition	first global quadrant index for each process (+1)
[in]	num_procs	number of processes
[in]	rank	process id for which correction is computed
[in]	min_quadrant_id	minimal global quadrant index of family
[in]	max_quadrant_id	maximal global quadrant index of family

Returns: correction for process rank

◆ p8est_partition_for_coarsening()

p4est_gloidx_t p8est_partition_for_coarsening	(	p8est_t *	p8est,
		p4est_locidx_t *	num_quadrants_in_proc
	)

Correct partition counters to allow one level of coarsening.

No quadrants are actually shipped, just the desired number is updated. This function guarantees that empty processors remain empty. This function is collective and acts as a synchronization point.

Parameters

[in]	p8est	forest whose partition is corrected
[in,out]	num_quadrants_in_proc	partition that will be corrected

Returns: total absolute number of moved quadrants. In practice, at most a small number per processor.

◆ p8est_partition_given()

p4est_gloidx_t p8est_partition_given	(	p8est_t *	p8est,
		const p4est_locidx_t *	num_quadrants_in_proc
	)

Partition p8est given the number of quadrants per proc.

Given the desired number of quadrants per proc num_quadrants_in_proc the forest p8est is partitioned.

Parameters

[in,out]	p8est	the forest that is partitioned.
[in]	num_quadrants_in_proc	an integer array of the number of quadrants desired per processor.

Returns: Returns the global count of shipped quadrants.

◆ p8est_quadrant_checksum()

unsigned p8est_quadrant_checksum	(	sc_array_t *	quadrants,
		sc_array_t *	checkarray,
		size_t	first_quadrant
	)

Computes a machine-independent checksum of a list of quadrants.

Parameters

[in]	quadrants	Array of quadrants.
[in,out]	checkarray	Temporary array of elem_size 4. Will be resized to quadrants->elem_count * 3. If it is NULL, will be allocated internally.
[in]	first_quadrant	Index of the quadrant to start with. Can be between 0 and elem_count (inclusive).

◆ p8est_quadrant_free_data()

void p8est_quadrant_free_data	(	p8est_t *	p8est,
		p8est_quadrant_t *	quad
	)

Free the user data of a valid quadrant.

Parameters

[in,out] quad The quadrant whose data shall be freed.

◆ p8est_quadrant_in_range()

int p8est_quadrant_in_range	(	const p8est_quadrant_t *	fd,
		const p8est_quadrant_t *	ld,
		const p8est_quadrant_t *	quadrant
	)

Report whether a quadrant fits into the limits of a quadrant range.

The range's boundaries are determined by its first and last descendant. Such descendants are for example stored in each tree of a p8est_t.

Parameters

[in]	fd	First descendant quadrant of a range. Thus its level must be P8EST_QMAXLEVEL. Must be valid, its data is ignored.
[in]	ld	Last descendant quadrant of a range. Thus it must not be smaller than fd and its level must be P8EST_QMAXLEVEL. Must be valid, its data is ignored.
[in]	quadrant	Quadrant checked to be fully inside the range. Must at least be extended, its data is ignored.

Returns: True if and only if quadrant is contained in range.

See also: p8est_quadrant_is_extended

◆ p8est_quadrant_init_data()

void p8est_quadrant_init_data	(	p8est_t *	p8est,
		p4est_topidx_t	which_tree,
		p8est_quadrant_t *	quad,
		p8est_init_t	init_fn
	)

Alloc and initialize the user data of a valid quadrant.

Parameters

[in]	which_tree	0-based index of this quadrant's tree.
[in,out]	quad	The quadrant to be initialized.
[in]	init_fn	User-supplied callback function to init data.

◆ p8est_quadrant_mempool_new()

sc_mempool_t * p8est_quadrant_mempool_new ( void )

Create a memory pool for quadrants that initializes compiler padding.

Returns: Initialized mempool with zero_and_persist setting.

◆ p8est_quadrant_on_face_boundary()

int p8est_quadrant_on_face_boundary	(	p8est_t *	p4est,
		p4est_topidx_t	treeid,
		int	face,
		const p8est_quadrant_t *	q
	)

Checks if a quadrant's face is on the boundary of the forest.

Parameters

[in]	p8est	The forest in which to search for q
[in]	treeid	The tree to which q belongs.
[in]	q	The quadrant that is in question.
[in]	face	The face of the quadrant that is in question.

Returns: true if the quadrant's face is on the boundary of the forest and false otherwise.

◆ p8est_tree_compute_overlap()

void p8est_tree_compute_overlap	(	p8est_t *	p8est,
		sc_array_t *	in,
		sc_array_t *	out,
		p8est_connect_type_t	balance,
		sc_array_t *	borders,
		sc_array_t *	inseeds
	)

Compute the overlap of a number of insulation layers with a tree.

Every quadrant out of the insulation layer of the quadrants in in except the quadrant itself is checked for overlap of quadrants from all trees that are smaller by at least two levels and thus can cause a split. Those elements that cause a split (as determined by the p8est_balance_*_test routines) create quadrants in out that will reproduce those splits when in is balanced. Note: Use this version if you are using less than full balance.

Parameters

[in]	p4est	The p8est to work on.
[in]	in	A piggy-sorted linear list of quadrants. The piggy2->from_tree member must be set.
[in,out]	out	A piggy-sorted subset of tree->quadrants.
[in]	balance	The type of balance condition that should be enforced.
[in]	borders	Array of arrays of tree border elements: if not NULL, this will be used to fill out.
[in]	inseeds	The seeds that in generates locally.

◆ p8est_tree_is_almost_sorted()

int p8est_tree_is_almost_sorted	(	p8est_tree_t *	tree,
		int	check_linearity
	)

Check if a tree is sorted/linear except across edges or corners.

Parameters

[in] check_linearity Boolean for additional check for linearity.

Returns: Returns true if almost sorted/linear, false otherwise.

◆ p8est_tree_is_complete()

int p8est_tree_is_complete ( p8est_tree_t * tree )

Test if a tree is sorted in Morton ordering and complete.

Returns: Returns true if complete, false otherwise.

Note: Complete means that the tree has no holes and no overlaps.

◆ p8est_tree_is_linear()

int p8est_tree_is_linear ( p8est_tree_t * tree )

Test if a tree is sorted in Morton ordering and linear.

Returns: Returns true if linear, false otherwise.

Note: Linear means that the tree has no overlaps.

◆ p8est_tree_is_sorted()

int p8est_tree_is_sorted ( p8est_tree_t * tree )

Test if a tree is sorted in Morton ordering.

Returns: Returns true if sorted, false otherwise.

Note: Duplicate quadrants are not allowed.

◆ p8est_tree_print()

void p8est_tree_print	(	int	log_priority,
		p8est_tree_t *	tree
	)

Print the quadrants in a tree.

Prints one line per quadrant with x, y, level and a string. The string denotes the relation to the previous quadrant and can be: Fn for the first quadrant in the tree with child id n I for identical quadrants R for a quadrant that with smaller Morton index Cn for child id n Sn for sibling with child id n D for a descendant Nn for a next quadrant in the tree with no holes in between and child id n qn for a general quadrant whose child id is n

Parameters

[in] tree Any (possibly incomplete, unsorted) tree to be printed.

◆ p8est_tree_remove_nonowned()

size_t p8est_tree_remove_nonowned	(	p8est_t *	p8est,
		p4est_topidx_t	which_tree
	)

Removes quadrants that are outside the owned tree boundaries from a tree.

Parameters

[in,out]	p8est	The p8est to work on.
[in]	which_tree	Index to a sorted owned tree in the p8est.

Returns: Returns the number of removed quadrants.

◆ p8est_tree_uniqify_overlap()

void p8est_tree_uniqify_overlap ( sc_array_t * out )

Gets the reduced representation of the overlap that results from using p8est_tree_compute_overlap_new.

Parameters

[in,out] out A piggy-sorted subset of tree->quadrants.

Functions

Detailed Description

Function Documentation

◆ p8est_balance_subtree()

◆ p8est_complete_region()

◆ p8est_complete_subtree()

◆ p8est_is_equal()

◆ p8est_is_valid()

◆ p8est_linearize_tree()

◆ p8est_next_nonempty_process()

◆ p8est_partition_correction()

◆ p8est_partition_for_coarsening()

◆ p8est_partition_given()

◆ p8est_quadrant_checksum()

◆ p8est_quadrant_free_data()

◆ p8est_quadrant_in_range()

◆ p8est_quadrant_init_data()

◆ p8est_quadrant_mempool_new()

◆ p8est_quadrant_on_face_boundary()

◆ p8est_tree_compute_overlap()

◆ p8est_tree_is_almost_sorted()

◆ p8est_tree_is_complete()

◆ p8est_tree_is_linear()

◆ p8est_tree_is_sorted()

◆ p8est_tree_print()

◆ p8est_tree_remove_nonowned()

◆ p8est_tree_uniqify_overlap()