1
#ifndef __FVM_BOX_TREE_H__
2
#define __FVM_BOX_TREE_H__
4
/*============================================================================
5
* Search octrees and quadtrees of boxes.
6
*============================================================================*/
9
This file is part of Code_Saturne, a general-purpose CFD tool.
11
Copyright (C) 1998-2011 EDF S.A.
13
This program is free software; you can redistribute it and/or modify it under
14
the terms of the GNU General Public License as published by the Free Software
15
Foundation; either version 2 of the License, or (at your option) any later
18
This program is distributed in the hope that it will be useful, but WITHOUT
19
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
20
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
23
You should have received a copy of the GNU General Public License along with
24
this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
25
Street, Fifth Floor, Boston, MA 02110-1301, USA.
28
/*----------------------------------------------------------------------------*/
30
/*----------------------------------------------------------------------------
31
* Standard C library headers
32
*----------------------------------------------------------------------------*/
36
/*----------------------------------------------------------------------------
38
*----------------------------------------------------------------------------*/
42
/*----------------------------------------------------------------------------*/
49
#endif /* __cplusplus */
51
/*============================================================================
53
*============================================================================*/
55
/*============================================================================
57
*============================================================================*/
59
typedef struct _fvm_box_tree_t fvm_box_tree_t;
63
FVM_BOX_TREE_ASYNC_LEVEL, /* Boxes are placed according to tree parameters,
64
and potentially at different levels */
65
FVM_BOX_TREE_SYNC_LEVEL /* All boxes are placed for all ranks at the
68
} fvm_box_tree_sync_t;
70
/*============================================================================
71
* Public function definitions
72
*============================================================================*/
74
/*----------------------------------------------------------------------------
75
* Create a fvm_box_tree_t structure and initialize it.
78
* max_level <-- max possible level
79
* threshold <-- max number of boxes linked to an octant if
80
* max_level is not reached
81
* max_box_ratio <-- max n_linked_boxes / n_boxes ratio
84
* pointer to an empty fvm_box_tree_t structure.
85
*----------------------------------------------------------------------------*/
88
fvm_box_tree_create(int max_level,
92
/*----------------------------------------------------------------------------
93
* Destroy a fvm_box_tree_t structure.
96
* bt <-- pointer to pointer to fvm_box_tree_t structure to destroy
97
*----------------------------------------------------------------------------*/
100
fvm_box_tree_destroy(fvm_box_tree_t **bt);
102
/*----------------------------------------------------------------------------
103
* Get the deepest level allowed by the tree structure.
106
* bt <-- pointer to fvm_box_tree_t structure.
109
* deepest allowed level of the tree
110
*----------------------------------------------------------------------------*/
113
fvm_box_tree_get_max_level(const fvm_box_tree_t *bt);
115
/*----------------------------------------------------------------------------
116
* Assign a set of boxes to an empty fvm_box_tree_t structure.
118
* The box tree structure must have been created using to fvm_tree_create().
120
* The depth of the tree is adjusted so that a maximum of max_n_elts boxes
121
* will be assigned to each leaf, unless this would require going beyond
122
* the tree's maximum level.
124
* If max_level = -1, the highest level reachable is FVM_TREE_MAX_LEVEL but
125
* there is no defined target level.
128
* bt <-> pointer to fvm_box_tree_t structure.
129
* boxes <-- pointer to the associated box set structure
130
* build_type <-- layout variant for building the tree structure
131
*----------------------------------------------------------------------------*/
134
fvm_box_tree_set_boxes(fvm_box_tree_t *bt,
135
const fvm_box_set_t *boxes,
136
fvm_box_tree_sync_t build_type);
138
#if defined(HAVE_MPI)
140
/*----------------------------------------------------------------------------
141
* Compute an index based on Morton encoding to ensure a good distribution
142
* of boxes among the participating ranks.
145
* bt <-> pointer to fvm_box_tree_t structure.
146
* boxes <-- pointer to the associated box set structure
149
* pointer to newly created fvm_box_distrib_t structure.
150
*----------------------------------------------------------------------------*/
153
fvm_box_tree_get_distrib(fvm_box_tree_t *bt,
154
const fvm_box_set_t *boxes);
156
#endif /* defined(HAVE_MPI) */
158
/*----------------------------------------------------------------------------
159
* Build an indexed list on boxes to list intersections.
161
* The index and box_g_num arrays are allocated by this function,
162
* and it is the caller's responsibility to free them.
164
* Upon return, box_index[i] points to the first position in box_g_num
165
* relative to boxes intersecting box i of the boxes set, while
166
* box_g_num contains the global numbers associated with those boxes.
169
* bt <-- pointer to box tree structure to query
170
* boxes <-- pointer to a associated box set
171
* box_index --> pointer to the index array on bounding boxes
172
* box_g_num --> pointer to the list of intersecting bounding boxes
173
*----------------------------------------------------------------------------*/
176
fvm_box_tree_get_intersects(fvm_box_tree_t *bt,
177
const fvm_box_set_t *boxes,
178
fvm_lnum_t *box_index[],
179
fvm_gnum_t *box_g_num[]);
181
/*----------------------------------------------------------------------------
182
* Get global box tree statistics.
184
* All fields returned are optional: if their argument is set to NULL,
185
* the corresponding information will not be returned.
187
* For each field not set to NULL, 3 values are always returned:
188
* the mean on all ranks (rounded to the closest integer), the minimum,
189
* and the maximum value respectively.
191
* In serial mode, the mean, minimum, and maximum will be identical for most
192
* fields, but all 3 values are returned nonetheless.
194
* Note that the theoretical memory use includes that of the associated
198
* bt <-- pointer to box tree structure
199
* depth --> tree depth (max level used)
200
* n_leaves --> number of leaves in the tree
201
* n_boxes --> number of boxes in the tree
202
* n_threshold_leaves --> number of leaves where n_boxes > threshold
203
* n_leaf_boxes --> number of boxes for a leaf
204
* mem_used --> theoretical used memory
205
* mem_allocated --> theoretical allocated memory
208
* the spatial dimension associated with the box tree layout (3, 2, or 1)
209
*----------------------------------------------------------------------------*/
212
fvm_box_tree_get_stats(const fvm_box_tree_t *bt,
214
fvm_lnum_t n_leaves[3],
215
fvm_lnum_t n_boxes[3],
216
fvm_lnum_t n_threshold_leaves[3],
217
fvm_lnum_t n_leaf_boxes[3],
219
size_t mem_allocated[3]);
221
/*----------------------------------------------------------------------------
222
* Display local statistics about a fvm_box_tree_t structure.
225
* bt <-- pointer to box tree structure
226
*----------------------------------------------------------------------------*/
229
fvm_box_tree_dump_statistics(const fvm_box_tree_t *bt);
231
/*----------------------------------------------------------------------------
232
* Dump an fvm_box_tree_t structure.
235
* bt <-- pointer to box tree structure
236
*----------------------------------------------------------------------------*/
239
fvm_box_tree_dump(fvm_box_tree_t *bt);
241
/*----------------------------------------------------------------------------*/
245
#endif /* __cplusplus */
247
#endif /* __FVM_BOX_TREE_H__ */