/*============================================================================
* Functions related to the ordering of local arrays of global numbers and
* calculation of global ranks in parallel mode.
*============================================================================*/
/*
This file is part of the "Finite Volume Mesh" library, intended to provide
finite volume mesh and associated fields I/O and manipulation services.
Copyright (C) 2004-2005 EDF
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
*/
/*----------------------------------------------------------------------------
* Standard C library headers
*----------------------------------------------------------------------------*/
#include <assert.h>
#include <stdio.h>
/*----------------------------------------------------------------------------
* BFT library headers
*----------------------------------------------------------------------------*/
#include <bft_mem.h>
#include <bft_printf.h>
/*----------------------------------------------------------------------------
* Local headers
*----------------------------------------------------------------------------*/
#include <fvm_config_defs.h>
#include <fvm_defs.h>
#include <fvm_parall.h>
/*----------------------------------------------------------------------------
* Header for the current file
*----------------------------------------------------------------------------*/
#include <fvm_order.h>
/*----------------------------------------------------------------------------*/
#ifdef __cplusplus
extern "C" {
#if 0
} /* Fake brace to force back Emacs auto-indentation back to column 0 */
#endif
#endif /* __cplusplus */
/*============================================================================
* Local structure definitions
*============================================================================*/
/*=============================================================================
* Private function definitions
*============================================================================*/
/*----------------------------------------------------------------------------
* Descend binary tree for the ordering of a fvm_gnum (integer) array.
*
* parameters:
* number <-- pointer to numbers of entities that should be ordered.
* (if NULL, a default 1 to n numbering is considered)
* level <-- level of the binary tree to descend
* nb_ent <-- number of entities in the binary tree to descend
* order <-> ordering array
*----------------------------------------------------------------------------*/
inline static void
_fvm_order_gnum_descend_tree(const fvm_gnum_t number[],
size_t level,
const size_t nb_ent,
fvm_lnum_t order[])
{
size_t i_save, i1, i2, lv_cur;
i_save = (size_t)(order[level]);
while (level <= (nb_ent/2)) {
lv_cur = (2*level) + 1;
if (lv_cur < nb_ent - 1) {
i1 = (size_t)(order[lv_cur+1]);
i2 = (size_t)(order[lv_cur]);
if (number[i1] > number[i2]) lv_cur++;
}
if (lv_cur >= nb_ent) break;
i1 = i_save;
i2 = (size_t)(order[lv_cur]);
if (number[i1] >= number[i2]) break;
order[level] = order[lv_cur];
level = lv_cur;
}
order[level] = i_save;
}
/*----------------------------------------------------------------------------
* Order an array of global numbers.
*
* parameters:
* number <-- array of entity numbers (if NULL, a default 1 to n
* numbering is considered)
* order <-- pre-allocated ordering table
* nb_ent <-- number of entities considered
*----------------------------------------------------------------------------*/
static void
_fvm_order_local(const fvm_gnum_t number[],
fvm_lnum_t order[],
const size_t nb_ent)
{
size_t i;
fvm_lnum_t o_save;
/* Initialize ordering array */
for (i = 0 ; i < nb_ent ; i++)
order[i] = i;
if (nb_ent < 2)
return;
/* Create binary tree */
i = (nb_ent / 2) ;
do {
i--;
_fvm_order_gnum_descend_tree(number, i, nb_ent, order);
} while (i > 0);
/* Sort binary tree */
for (i = nb_ent - 1 ; i > 0 ; i--) {
o_save = order[0];
order[0] = order[i];
order[i] = o_save;
_fvm_order_gnum_descend_tree(number, 0, i, order);
}
}
/*=============================================================================
* Public function definitions
*============================================================================*/
/*----------------------------------------------------------------------------
* Test if an array of global numbers is ordered.
*
* parameters:
* list <-- optional list (1 to n numbering) of selected entities
* (or NULL if all nb_ent are selected). This list may
* contain element numbers in any order
* number <-- array of all entity numbers (number of entity i
* given by number[i] or number[list[i] - 1]) if list exists
* (if NULL, a default 1 to n numbering is considered)
* nb_ent <-- number of entities considered
*
* returns:
* 1 if ordered, 0 otherwise.
*----------------------------------------------------------------------------*/
int
fvm_order_local_test(const fvm_lnum_t list[],
const fvm_gnum_t number[],
const size_t nb_ent)
{
size_t i = 0;
/* If numbering is explicit */
if (number != NULL) {
if (list != NULL) {
for (i = 1 ; i < nb_ent ; i++) {
if (number[list[i] - 1] < number[list[i-1] - 1])
break;
}
}
else {
for (i = 1 ; i < nb_ent ; i++) {
if (number[i] < number[i-1])
break;
}
}
/* If numbering is implicit */
}
else {
if (list != NULL) {
for (i = 1 ; i < nb_ent ; i++) {
if (list[i] < list[i-1])
break;
}
}
else
i = nb_ent;
}
if (i == nb_ent || nb_ent == 0)
return 1;
else
return 0;
}
/*----------------------------------------------------------------------------
* Return an ordering table associated with an array of global numbers.
*
* parameters:
* list <-- optional list (1 to n numbering) of selected entities
* (or NULL if all nb_ent are selected). This list may
* contain element numbers in any order
* number <-- array of all entity numbers (number of entity i
* given by number[i] or number[list[i] - 1]) if list exists
* (if NULL, a default 1 to n numbering is considered)
* nb_ent <-- number of entities considered
*
* returns:
* pointer to list of nb_ent entities (0 to n-1 numbering) ordered by
* increasing associated number. The calling code is responsible for
* freeing this array when it is not needed anymore.
*----------------------------------------------------------------------------*/
fvm_lnum_t *
fvm_order_local(const fvm_lnum_t list[],
const fvm_gnum_t number[],
const size_t nb_ent)
{
fvm_lnum_t *order;
BFT_MALLOC(order, nb_ent, fvm_lnum_t);
fvm_order_local_allocated(list,
number,
order,
nb_ent);
return order;
}
/*----------------------------------------------------------------------------
* Compute an ordering table associated with an array of global numbers.
*
* parameters:
* list <-- optional list (1 to n numbering) of selected entities
* (or NULL if all nb_ent are selected). This list may
* contain element numbers in any order
* number <-- array of all entity numbers (number of entity i
* given by number[i] or number[list[i] - 1]) if list exists
* (if NULL, a default 1 to n numbering is considered)
* order --> pointer to pre-allocated ordering table
* nb_ent <-- number of entities considered
*----------------------------------------------------------------------------*/
void
fvm_order_local_allocated(const fvm_lnum_t list[],
const fvm_gnum_t number[],
fvm_lnum_t order[],
const size_t nb_ent)
{
size_t i;
fvm_gnum_t *number_list;
/* Explicit numbering */
if (number != NULL) {
if (list != NULL) {
BFT_MALLOC(number_list, nb_ent, fvm_gnum_t);
for (i = 0 ; i < nb_ent ; i++)
number_list[i] = number[list[i] - 1];
_fvm_order_local(number_list,
order,
nb_ent);
BFT_FREE(number_list);
}
else
_fvm_order_local(number,
order,
nb_ent);
}
/* Implicit numbering */
else {
BFT_MALLOC(number_list, nb_ent, fvm_gnum_t);
if (list != NULL) {
for (i = 0 ; i < nb_ent ; i++)
number_list[i] = (fvm_gnum_t)(list[i]);
}
else {
for (i = 0 ; i < nb_ent ; i++)
number_list[i] = (fvm_gnum_t)(i + 1);
}
_fvm_order_local(number_list,
order,
nb_ent);
BFT_FREE(number_list);
}
}
/*----------------------------------------------------------------------------
* Build local renumbering array based on ordering of entities.
*
* parameters:
* order <-- 0 to n-1 ordering of entities by increasing attribute
* nb_ent <-- number of entities considered
* base <-- renumbering starting number (typically 0 or 1)
*
* returns:
* pointer to renumbering array (0 to n-1 numbering) indicating the new
* index of renumbered entities; The calling code is responsible for
* freeing this array when it is not needed anymore
*----------------------------------------------------------------------------*/
fvm_lnum_t *
fvm_order_local_renumbering(const fvm_lnum_t order[],
const size_t nb_ent)
{
size_t i;
fvm_lnum_t *number;
if (nb_ent < 1)
return NULL;
assert(order != NULL);
BFT_MALLOC(number, nb_ent, fvm_lnum_t);
#if defined(DEBUG) && !defined(NDEBUG)
/* Initialize with "impossible" number (so as to have a reproducible
and detectable error in the renumbering array in case of
incorrect order[] values) */
for (i = 0 ; i < nb_ent ; i++)
number[i] = - 1;
#endif
/* Populate renumbering array */
for (i = 0 ; i < nb_ent ; i++)
number[order[i]] = i;
#if defined(DEBUG) && !defined(NDEBUG)
/* Check renumbering array */
for (i = 0 ; i < nb_ent ; i++)
assert(number[i] >= 0);
#endif
return number;
}
/*----------------------------------------------------------------------------*/
#ifdef __cplusplus
}
#endif /* __cplusplus */
syntax highlighted by Code2HTML, v. 0.9.1