Code_Saturne
CFD tool
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
fvm_box_tree.h
Go to the documentation of this file.
1 #ifndef __FVM_BOX_TREE_H__
2 #define __FVM_BOX_TREE_H__
3 
4 /*============================================================================
5  * Search octrees and quadtrees of boxes.
6  *============================================================================*/
7 
8 /*
9  This file is part of Code_Saturne, a general-purpose CFD tool.
10 
11  Copyright (C) 1998-2012 EDF S.A.
12 
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
16  version.
17 
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
21  details.
22 
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.
26 */
27 
28 /*----------------------------------------------------------------------------*/
29 
30 /*----------------------------------------------------------------------------
31  * Standard C library headers
32  *----------------------------------------------------------------------------*/
33 
34 #include <stdio.h>
35 
36 /*----------------------------------------------------------------------------
37  * FVM library headers
38  *----------------------------------------------------------------------------*/
39 
40 #include "fvm_box.h"
41 
42 /*----------------------------------------------------------------------------*/
43 
44 #ifdef __cplusplus
45 extern "C" {
46 #if 0
47 } /* Fake brace to */
48 #endif
49 #endif /* __cplusplus */
50 
51 /*============================================================================
52  * Macro definitions
53  *============================================================================*/
54 
55 /*============================================================================
56  * Type definitions
57  *============================================================================*/
58 
60 
61 typedef enum {
62 
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
66  same level */
67 
69 
70 /*============================================================================
71  * Public function definitions
72  *============================================================================*/
73 
74 /*----------------------------------------------------------------------------
75  * Create a fvm_box_tree_t structure and initialize it.
76  *
77  * parameters:
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
82  *
83  * returns:
84  * pointer to an empty fvm_box_tree_t structure.
85  *----------------------------------------------------------------------------*/
86 
89  int threshold,
90  float max_box_ratio);
91 
92 /*----------------------------------------------------------------------------
93  * Destroy a fvm_box_tree_t structure.
94  *
95  * parameters:
96  * bt <-- pointer to pointer to fvm_box_tree_t structure to destroy
97  *----------------------------------------------------------------------------*/
98 
99 void
101 
102 /*----------------------------------------------------------------------------
103  * Get the deepest level allowed by the tree structure.
104  *
105  * parameters:
106  * bt <-- pointer to fvm_box_tree_t structure.
107  *
108  * returns:
109  * deepest allowed level of the tree
110  *----------------------------------------------------------------------------*/
111 
112 int
114 
115 /*----------------------------------------------------------------------------
116  * Assign a set of boxes to an empty fvm_box_tree_t structure.
117  *
118  * The box tree structure must have been created using to fvm_tree_create().
119  *
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.
123  *
124  * If max_level = -1, the highest level reachable is FVM_TREE_MAX_LEVEL but
125  * there is no defined target level.
126  *
127  * parameters:
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  *----------------------------------------------------------------------------*/
132 
133 void
135  const fvm_box_set_t *boxes,
136  fvm_box_tree_sync_t build_type);
137 
138 #if defined(HAVE_MPI)
139 
140 /*----------------------------------------------------------------------------
141  * Compute an index based on Morton encoding to ensure a good distribution
142  * of boxes among the participating ranks.
143  *
144  * parameters:
145  * bt <-> pointer to fvm_box_tree_t structure.
146  * boxes <-- pointer to the associated box set structure
147  *
148  * returns:
149  * pointer to newly created fvm_box_distrib_t structure.
150  *----------------------------------------------------------------------------*/
151 
153 fvm_box_tree_get_distrib(fvm_box_tree_t *bt,
154  const fvm_box_set_t *boxes);
155 
156 #endif /* defined(HAVE_MPI) */
157 
158 /*----------------------------------------------------------------------------
159  * Build an indexed list on boxes to list intersections.
160  *
161  * The index and box_g_num arrays are allocated by this function,
162  * and it is the caller's responsibility to free them.
163  *
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.
167  *
168  * parameters:
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  *----------------------------------------------------------------------------*/
174 
175 void
177  const fvm_box_set_t *boxes,
178  cs_lnum_t *box_index[],
179  cs_gnum_t *box_g_num[]);
180 
181 /*----------------------------------------------------------------------------
182  * Get global box tree statistics.
183  *
184  * All fields returned are optional: if their argument is set to NULL,
185  * the corresponding information will not be returned.
186  *
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.
190  *
191  * In serial mode, the mean, minimum, and maximum will be identical for most
192  * fields, but all 3 values are returned nonetheless.
193  *
194  * Note that the theoretical memory use includes that of the associated
195  * box set.
196  *
197  * parameters:
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
206  *
207  * returns:
208  * the spatial dimension associated with the box tree layout (3, 2, or 1)
209  *----------------------------------------------------------------------------*/
210 
211 int
213  int depth[3],
214  cs_lnum_t n_leaves[3],
215  cs_lnum_t n_boxes[3],
216  cs_lnum_t n_threshold_leaves[3],
217  cs_lnum_t n_leaf_boxes[3],
218  size_t mem_used[3],
219  size_t mem_allocated[3]);
220 
221 /*----------------------------------------------------------------------------
222  * Display local statistics about a fvm_box_tree_t structure.
223  *
224  * parameters:
225  * bt <-- pointer to box tree structure
226  *----------------------------------------------------------------------------*/
227 
228 void
230 
231 /*----------------------------------------------------------------------------
232  * Dump an fvm_box_tree_t structure.
233  *
234  * parameters:
235  * bt <-- pointer to box tree structure
236  *----------------------------------------------------------------------------*/
237 
238 void
240 
241 /*----------------------------------------------------------------------------*/
242 
243 #ifdef __cplusplus
244 }
245 #endif /* __cplusplus */
246 
247 #endif /* __FVM_BOX_TREE_H__ */
void fvm_box_tree_destroy(fvm_box_tree_t **bt)
Definition: fvm_box_tree.c:2033
fvm_box_tree_t * fvm_box_tree_create(int max_level, int threshold, float max_box_ratio)
Definition: fvm_box_tree.c:1965
void fvm_box_tree_get_intersects(fvm_box_tree_t *bt, const fvm_box_set_t *boxes, cs_lnum_t *box_index[], cs_gnum_t *box_g_num[])
Definition: fvm_box_tree.c:2349
int fvm_box_tree_get_stats(const fvm_box_tree_t *bt, int depth[3], cs_lnum_t n_leaves[3], cs_lnum_t n_boxes[3], cs_lnum_t n_threshold_leaves[3], cs_lnum_t n_leaf_boxes[3], size_t mem_used[3], size_t mem_allocated[3])
Definition: fvm_box_tree.c:2434
struct _fvm_box_distrib_t fvm_box_distrib_t
Definition: fvm_box.h:56
Definition: fvm_box_tree.h:63
void fvm_box_tree_dump_statistics(const fvm_box_tree_t *bt)
Definition: fvm_box_tree.c:2605
int max_level
Definition: fvm_box_tree.c:118
int cs_lnum_t
Definition: cs_defs.h:260
void fvm_box_tree_set_boxes(fvm_box_tree_t *bt, const fvm_box_set_t *boxes, fvm_box_tree_sync_t build_type)
Definition: fvm_box_tree.c:2083
unsigned cs_gnum_t
Definition: cs_defs.h:255
fvm_box_tree_sync_t
Definition: fvm_box_tree.h:61
Definition: fvm_box_priv.h:81
cs_lnum_t threshold
Definition: fvm_box_tree.c:119
void fvm_box_tree_dump(fvm_box_tree_t *bt)
Definition: fvm_box_tree.c:2743
Definition: fvm_box_tree.c:114
Definition: fvm_box_tree.h:65
int fvm_box_tree_get_max_level(const fvm_box_tree_t *bt)
Definition: fvm_box_tree.c:2059
float max_box_ratio
Definition: fvm_box_tree.c:121