8.3
general documentation
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-2024 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#include "cs_defs.h"
31
32/*----------------------------------------------------------------------------
33 * Standard C library headers
34 *----------------------------------------------------------------------------*/
35
36#include <stdio.h>
37
38/*----------------------------------------------------------------------------
39 * Local headers
40 *----------------------------------------------------------------------------*/
41
42#include "fvm_box.h"
43
44/*----------------------------------------------------------------------------*/
45
47
48/*============================================================================
49 * Macro definitions
50 *============================================================================*/
51
52/*============================================================================
53 * Type definitions
54 *============================================================================*/
55
56typedef struct _fvm_box_tree_t fvm_box_tree_t;
57
58typedef enum {
59
60 FVM_BOX_TREE_ASYNC_LEVEL, /* Boxes are placed according to tree parameters,
61 and potentially at different levels */
62 FVM_BOX_TREE_SYNC_LEVEL /* All boxes are placed for all ranks at the
63 same level */
64
66
67/*============================================================================
68 * Public function definitions
69 *============================================================================*/
70
71/*----------------------------------------------------------------------------
72 * Create a fvm_box_tree_t structure and initialize it.
73 *
74 * parameters:
75 * max_level <-- max possible level
76 * threshold <-- max number of boxes linked to an octant if
77 * max_level is not reached
78 * max_box_ratio <-- max n_linked_boxes / n_boxes ratio
79 *
80 * returns:
81 * pointer to an empty fvm_box_tree_t structure.
82 *----------------------------------------------------------------------------*/
83
85fvm_box_tree_create(int max_level,
86 int threshold,
87 float max_box_ratio);
88
89/*----------------------------------------------------------------------------
90 * Destroy a fvm_box_tree_t structure.
91 *
92 * parameters:
93 * bt <-- pointer to pointer to fvm_box_tree_t structure to destroy
94 *----------------------------------------------------------------------------*/
95
96void
98
99/*----------------------------------------------------------------------------
100 * Get the deepest level allowed by the tree structure.
101 *
102 * parameters:
103 * bt <-- pointer to fvm_box_tree_t structure.
104 *
105 * returns:
106 * deepest allowed level of the tree
107 *----------------------------------------------------------------------------*/
108
109int
111
112/*----------------------------------------------------------------------------
113 * Assign a set of boxes to an empty fvm_box_tree_t structure.
114 *
115 * The box tree structure must have been created using to fvm_tree_create().
116 *
117 * The depth of the tree is adjusted so that a maximum of max_n_elts boxes
118 * will be assigned to each leaf, unless this would require going beyond
119 * the tree's maximum level.
120 *
121 * If max_level = -1, the highest level reachable is FVM_TREE_MAX_LEVEL but
122 * there is no defined target level.
123 *
124 * parameters:
125 * bt <-> pointer to fvm_box_tree_t structure.
126 * boxes <-- pointer to the associated box set structure
127 * build_type <-- layout variant for building the tree structure
128 *----------------------------------------------------------------------------*/
129
130void
132 const fvm_box_set_t *boxes,
133 fvm_box_tree_sync_t build_type);
134
135#if defined(HAVE_MPI)
136
137/*----------------------------------------------------------------------------
138 * Compute an index based on Morton encoding to ensure a good distribution
139 * of boxes among the participating ranks.
140 *
141 * parameters:
142 * bt <-> pointer to fvm_box_tree_t structure.
143 * boxes <-- pointer to the associated box set structure
144 *
145 * returns:
146 * pointer to newly created fvm_box_distrib_t structure.
147 *----------------------------------------------------------------------------*/
148
150fvm_box_tree_get_distrib(fvm_box_tree_t *bt,
151 const fvm_box_set_t *boxes);
152
153#endif /* defined(HAVE_MPI) */
154
155/*----------------------------------------------------------------------------
156 * Build an indexed list on boxes to list intersections.
157 *
158 * The index and box_g_num arrays are allocated by this function,
159 * and it is the caller's responsibility to free them.
160 *
161 * Upon return, box_index[i] points to the first position in box_g_num
162 * relative to boxes intersecting box i of the boxes set, while
163 * box_g_num contains the global numbers associated with those boxes.
164 *
165 * parameters:
166 * bt <-- pointer to box tree structure to query
167 * boxes <-- pointer to a associated box set
168 * box_index --> pointer to the index array on bounding boxes
169 * box_g_num --> pointer to the list of intersecting bounding boxes
170 *----------------------------------------------------------------------------*/
171
172void
174 const fvm_box_set_t *boxes,
175 cs_lnum_t *box_index[],
176 cs_gnum_t *box_g_num[]);
177
178/*----------------------------------------------------------------------------
179 * Get global box tree statistics.
180 *
181 * All fields returned are optional: if their argument is set to NULL,
182 * the corresponding information will not be returned.
183 *
184 * For each field not set to NULL, 3 values are always returned:
185 * the mean on all ranks (rounded to the closest integer), the minimum,
186 * and the maximum value respectively.
187 *
188 * In serial mode, the mean, minimum, and maximum will be identical for most
189 * fields, but all 3 values are returned nonetheless.
190 *
191 * Note that the theoretical memory use includes that of the associated
192 * box set.
193 *
194 * parameters:
195 * bt <-- pointer to box tree structure
196 * depth --> tree depth (max level used)
197 * n_leaves --> number of leaves in the tree
198 * n_boxes --> number of boxes in the tree
199 * n_threshold_leaves --> number of leaves where n_boxes > threshold
200 * n_leaf_boxes --> number of boxes for a leaf
201 * mem_used --> theoretical used memory
202 * mem_allocated --> theoretical allocated memory
203 *
204 * returns:
205 * the spatial dimension associated with the box tree layout (3, 2, or 1)
206 *----------------------------------------------------------------------------*/
207
208int
210 int depth[3],
211 cs_lnum_t n_leaves[3],
212 cs_lnum_t n_boxes[3],
213 cs_lnum_t n_threshold_leaves[3],
214 cs_lnum_t n_leaf_boxes[3],
215 size_t mem_used[3],
216 size_t mem_allocated[3]);
217
218/*----------------------------------------------------------------------------
219 * Display local statistics about a fvm_box_tree_t structure.
220 *
221 * parameters:
222 * bt <-- pointer to box tree structure
223 *----------------------------------------------------------------------------*/
224
225void
227
228/*----------------------------------------------------------------------------
229 * Dump an fvm_box_tree_t structure.
230 *
231 * parameters:
232 * bt <-- pointer to box tree structure
233 *----------------------------------------------------------------------------*/
234
235void
237
238/*----------------------------------------------------------------------------*/
239
241
242#endif /* __FVM_BOX_TREE_H__ */
#define BEGIN_C_DECLS
Definition: cs_defs.h:542
uint64_t cs_gnum_t
global mesh entity number
Definition: cs_defs.h:325
#define END_C_DECLS
Definition: cs_defs.h:543
int cs_lnum_t
local mesh entity id
Definition: cs_defs.h:335
struct _fvm_box_distrib_t fvm_box_distrib_t
Definition: fvm_box.h:53
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.cpp:2345
fvm_box_tree_sync_t
Definition: fvm_box_tree.h:58
@ FVM_BOX_TREE_ASYNC_LEVEL
Definition: fvm_box_tree.h:60
@ FVM_BOX_TREE_SYNC_LEVEL
Definition: fvm_box_tree.h:62
fvm_box_tree_t * fvm_box_tree_create(int max_level, int threshold, float max_box_ratio)
Definition: fvm_box_tree.cpp:1961
void fvm_box_tree_dump(fvm_box_tree_t *bt)
Definition: fvm_box_tree.cpp:2739
void fvm_box_tree_destroy(fvm_box_tree_t **bt)
Definition: fvm_box_tree.cpp:2029
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.cpp:2430
int fvm_box_tree_get_max_level(const fvm_box_tree_t *bt)
Definition: fvm_box_tree.cpp:2055
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.cpp:2079
struct _fvm_box_tree_t fvm_box_tree_t
Definition: fvm_box_tree.h:56
void fvm_box_tree_dump_statistics(const fvm_box_tree_t *bt)
Definition: fvm_box_tree.cpp:2601