Code_Saturne
CFD tool
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
fvm_morton.h
Go to the documentation of this file.
1 #ifndef __FVM_MORTON_H__
2 #define __FVM_MORTON_H__
3 
4 /*============================================================================
5  * Morton encoding for 2D or 3D coordinates.
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 #include <stdio.h>
31 
32 #if defined(HAVE_MPI)
33 #include <mpi.h>
34 #endif
35 
36 /*----------------------------------------------------------------------------
37  * Local headers
38  *----------------------------------------------------------------------------*/
39 
40 #include "fvm_defs.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 and type definitions
53  *============================================================================*/
54 
55 typedef enum {
56 
60 
62 
63 typedef unsigned int fvm_morton_int_t;
64 
65 typedef struct {
66 
67  fvm_morton_int_t L; /* Level in the tree structure */
68  fvm_morton_int_t X[3]; /* X, Y, Z coordinates in Cartesian grid */
69 
71 
72 /*============================================================================
73  * Public function definitions
74  *============================================================================*/
75 
76 /*----------------------------------------------------------------------------
77  * Determine the global extents associated with a set of coordinates
78  *
79  * parameters:
80  * dim <-- spatial dimension
81  * n_coords <-- local number of coordinates
82  * coords <-- entity coordinates; size: n_entities*dim (interlaced)
83  * g_extents --> global extents (size: dim*2)
84  * comm <-- associated MPI communicator
85  *---------------------------------------------------------------------------*/
86 
87 #if defined(HAVE_MPI)
88 
89 void
91  size_t n_coords,
92  const cs_coord_t coords[],
93  cs_coord_t g_extents[],
94  MPI_Comm comm);
95 
96 #else
97 
98 void
100  size_t n_coords,
101  const cs_coord_t coords[],
102  cs_coord_t g_extents[]);
103 
104 #endif
105 
106 /*----------------------------------------------------------------------------
107  * Determine the global extents associated with a set of local extents
108  *
109  * parameters:
110  * dim <-- spatial dimension
111  * n_extents <-- local number of coordinates
112  * extents <-- entity coordinates; size: n_entities*dim*2 (interlaced)
113  * g_extents --> global extents (size: dim*2)
114  * comm <-- associated MPI communicator
115  *---------------------------------------------------------------------------*/
116 
117 #if defined(HAVE_MPI)
118 
119 void
121  size_t n_extents,
122  const cs_coord_t extents[],
123  cs_coord_t g_extents[],
124  MPI_Comm comm);
125 
126 #else
127 
128 void
130  size_t n_extents,
131  const cs_coord_t extents[],
132  cs_coord_t g_extents[]);
133 
134 #endif
135 
136 /*----------------------------------------------------------------------------
137  * Build a Morton code according to the level in an octree grid and its
138  * coordinates in the grid.
139  *
140  * parameters:
141  * dim <-- 1D, 2D or 3D
142  * level <-- level in the grid
143  * coords <-- coordinates in the grid (normalized)
144  *
145  * returns:
146  * a Morton code
147  *----------------------------------------------------------------------------*/
148 
150 fvm_morton_encode(int dim,
151  fvm_morton_int_t level,
152  const cs_coord_t coords[]);
153 
154 /*----------------------------------------------------------------------------
155  * Encode an array of coordinates.
156  *
157  * The caller is responsible for freeing the returned array once it is
158  * no longer useful.
159  *
160  * parameters:
161  * dim <-- 1D, 2D or 3D
162  * level <-- level in the grid
163  * extents <-- coordinate extents for normalization (size: dim*2)
164  * n_coords <-- nomber of coordinates in array
165  * coords <-- coordinates in the grid (interlaced, not normalized)
166  * m_code --> array of corresponding Morton codes
167  *----------------------------------------------------------------------------*/
168 
169 void
171  fvm_morton_int_t level,
172  const cs_coord_t extents[],
173  size_t n_coords,
174  const cs_coord_t coords[],
175  fvm_morton_code_t m_code[]);
176 
177 /*----------------------------------------------------------------------------
178  * Given a Morton code in the grid, compute the Morton codes of its
179  * children when refining the grid by one level.
180  *
181  * parameters:
182  * dim <-- 1D, 2D or 3D
183  * parent <-- Morton code associated with parent
184  * children --> array of children Morton codes
185  * (size: 8 in 3D, 4 in 2D, 2 in 1D)
186  *----------------------------------------------------------------------------*/
187 
188 void
190  fvm_morton_code_t parent,
191  fvm_morton_code_t children[]);
192 
193 /*----------------------------------------------------------------------------
194  * Compare two Morton encoding and check if these two codes are equal,
195  * different or shared the same anchor.
196  *
197  * parameters:
198  * dim <-- 2D or 3D
199  * code_a <-- first Morton code to compare
200  * code_b <-- second Morton code to compare
201  *
202  * returns:
203  * a type on the kind of relation between the two Morton encodings.
204  *----------------------------------------------------------------------------*/
205 
207 fvm_morton_compare(int dim,
208  fvm_morton_code_t code_a,
209  fvm_morton_code_t code_b);
210 
211 /*----------------------------------------------------------------------------
212  * Locally order a list of Morton ids.
213  *
214  * parameters:
215  * n_codes <-- number of Morton ids to order
216  * morton_codes <-- array of Morton ids to order
217  * order --> pointer to pre-allocated ordering table
218  *----------------------------------------------------------------------------*/
219 
220 void
222  const fvm_morton_code_t morton_codes[],
223  cs_lnum_t order[]);
224 
225 /*----------------------------------------------------------------------------
226  * Locally sort a list of Morton ids.
227  *
228  * parameters:
229  * n_codes <-- number of Morton ids to order
230  * morton_codes <-> array of Morton ids to sort
231  *----------------------------------------------------------------------------*/
232 
233 void
235  fvm_morton_code_t morton_codes[]);
236 
237 /*----------------------------------------------------------------------------
238  * Test if Morton code "a" is greater than Morton code "b"
239  *
240  * parameters:
241  * code_a <-- first Morton code to compare
242  * code_b <-- second Morton code to compare
243  *
244  * returns:
245  * true or false
246  *----------------------------------------------------------------------------*/
247 
248 _Bool
251 
252 /*----------------------------------------------------------------------------
253  * Test if Morton code "a" is greater or equal to Morton code "b"
254  *
255  * parameters:
256  * code_a <-- first Morton code to compare
257  * code_b <-- second Morton code to compare
258  *
259  * returns:
260  * true or false
261  *----------------------------------------------------------------------------*/
262 
263 _Bool
266 
267 /*----------------------------------------------------------------------------
268  * Get the index associated to a Morton code using a binary search.
269  *
270  * No check is done to ensure that the code is present in the array.
271  *
272  * parameters:
273  * size <-- size of the array
274  * code <-- code we are searching for
275  * codes <-- array of Morton codes
276  *
277  * returns:
278  * id associated to the given code in the codes array.
279  *----------------------------------------------------------------------------*/
280 
281 int
283  fvm_morton_code_t code,
284  fvm_morton_code_t *codes);
285 
286 /*----------------------------------------------------------------------------
287  * Get the quantile associated to a Morton code using a binary search.
288  *
289  * No check is done to ensure that the code is present in the quantiles.
290  *
291  * parameters:
292  * n_quantiles <-- number of quantiles
293  * code <-- code we are searching for
294  * quantile_start <-- first Morton code in each quantile (size: n_quantiles)
295  *
296  * returns:
297  * id associated to the given code in the codes array.
298  *----------------------------------------------------------------------------*/
299 
300 size_t
301 fvm_morton_quantile_search(size_t n_quantiles,
302  fvm_morton_code_t code,
303  fvm_morton_code_t *quantile_start);
304 
305 #if defined(HAVE_MPI)
306 
307 /*----------------------------------------------------------------------------
308  * Build a global Morton encoding rank index.
309  *
310  * The rank_index[i] contains the first Morton code assigned to rank [i].
311  *
312  * parameters:
313  * dim <-- 1D, 2D or 3D
314  * gmax_level <-- level in octree used to build the Morton encoding
315  * n_codes <-- number of Morton codes to be indexed
316  * morton_code <-- array of Morton codes to be indexed
317  * weight <-- weighting related to each code
318  * order <-- ordering array
319  * rank_index <-> pointer to the global Morton encoding rank index
320  * comm <-- MPI communicator on which we build the global index
321  *
322  * returns:
323  * the fit related to the Morton encoding distribution (lower is better).
324  *----------------------------------------------------------------------------*/
325 
326 double
327 fvm_morton_build_rank_index(int dim,
328  int gmax_level,
329  cs_gnum_t n_codes,
330  const fvm_morton_code_t code[],
331  const cs_lnum_t weight[],
332  const cs_lnum_t order[],
333  fvm_morton_code_t rank_index[],
334  MPI_Comm comm);
335 
336 #endif /* if HAVE_MPI */
337 
338 /*----------------------------------------------------------------------------
339  * Dump a Morton to standard output or to a file.
340  *
341  * parameters:
342  * dim <-- 2D or 3D
343  * code <-- Morton code to dump
344  *----------------------------------------------------------------------------*/
345 
346 void
347 fvm_morton_dump(int dim,
348  fvm_morton_code_t code);
349 
350 /*----------------------------------------------------------------------------*/
351 
352 #ifdef __cplusplus
353 }
354 #endif /* __cplusplus */
355 
356 #endif /* __FVM_MORTON_H__ */
Definition: cs_ventil.c:117
void fvm_morton_local_sort(cs_lnum_t n_codes, fvm_morton_code_t morton_codes[])
Definition: fvm_morton.c:1175
fvm_morton_compare_t fvm_morton_compare(int dim, fvm_morton_code_t code_a, fvm_morton_code_t code_b)
Definition: fvm_morton.c:1223
void fvm_morton_local_order(cs_lnum_t n_codes, const fvm_morton_code_t morton_codes[], cs_lnum_t order[])
Definition: fvm_morton.c:1126
_Bool fvm_morton_a_gt_b(fvm_morton_code_t a, fvm_morton_code_t b)
Definition: fvm_morton.c:1277
void fvm_morton_get_coord_extents(int dim, size_t n_coords, const cs_coord_t coords[], cs_coord_t g_extents[])
Definition: fvm_morton.c:857
int fvm_morton_binary_search(cs_lnum_t size, fvm_morton_code_t code, fvm_morton_code_t *codes)
Definition: fvm_morton.c:1316
void fvm_morton_get_children(int dim, fvm_morton_code_t parent, fvm_morton_code_t children[])
Definition: fvm_morton.c:1068
double cs_coord_t
Definition: cs_defs.h:261
void fvm_morton_get_global_extents(int dim, size_t n_extents, const cs_coord_t extents[], cs_coord_t g_extents[])
Definition: fvm_morton.c:909
Definition: fvm_morton.h:58
fvm_morton_compare_t
Definition: fvm_morton.h:55
Definition: fvm_morton.h:65
int cs_lnum_t
Definition: cs_defs.h:260
unsigned int fvm_morton_int_t
Definition: fvm_morton.h:63
Definition: fvm_morton.h:57
unsigned cs_gnum_t
Definition: cs_defs.h:255
fvm_morton_code_t fvm_morton_encode(int dim, fvm_morton_int_t level, const cs_coord_t coords[])
Definition: fvm_morton.c:955
void fvm_morton_encode_coords(int dim, fvm_morton_int_t level, const cs_coord_t extents[], size_t n_coords, const cs_coord_t coords[], fvm_morton_code_t m_code[])
Definition: fvm_morton.c:993
size_t fvm_morton_quantile_search(size_t n_quantiles, fvm_morton_code_t code, fvm_morton_code_t *quantile_start)
Definition: fvm_morton.c:1351
_Bool fvm_morton_a_ge_b(fvm_morton_code_t a, fvm_morton_code_t b)
Definition: fvm_morton.c:1295
#define _Bool
Definition: cs_defs.h:154
Definition: fvm_morton.h:59
void fvm_morton_dump(int dim, fvm_morton_code_t code)
Definition: fvm_morton.c:1481
fvm_morton_int_t L
Definition: fvm_morton.h:67