1 /*============================================================================
2 * \file Functions related to the ordering of local arrays.
3 *============================================================================*/
4
5 /*
6 This file is part of Code_Saturne, a general-purpose CFD tool.
7
8 Copyright (C) 1998-2021 EDF S.A.
9
10 This program is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free Software
12 Foundation; either version 2 of the License, or (at your option) any later
13 version.
14
15 This program is distributed in the hope that it will be useful, but WITHOUT
16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
18 details.
19
20 You should have received a copy of the GNU General Public License along with
21 this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
22 Street, Fifth Floor, Boston, MA 02110-1301, USA.
23 */
24
25 /*----------------------------------------------------------------------------*/
26
27 #include "cs_defs.h"
28
29 /*----------------------------------------------------------------------------
30 * Standard C library headers
31 *----------------------------------------------------------------------------*/
32
33 #include <assert.h>
34 #include <stdio.h>
35 #include <string.h>
36
37 /*----------------------------------------------------------------------------
38 * Local headers
39 *----------------------------------------------------------------------------*/
40
41 #include "bft_mem.h"
42 #include "bft_printf.h"
43
44 /*----------------------------------------------------------------------------
45 * Header for the current file
46 *----------------------------------------------------------------------------*/
47
48 #include "cs_order.h"
49
50 /*----------------------------------------------------------------------------*/
51
52 BEGIN_C_DECLS
53
54 /*! \cond DOXYGEN_SHOULD_SKIP_THIS */
55
56 /*============================================================================
57 * Local structure definitions
58 *============================================================================*/
59
60 /*=============================================================================
61 * Private function definitions
62 *============================================================================*/
63
64 /*----------------------------------------------------------------------------
65 * Descend binary tree for the ordering of a cs_gnum_t (integer) array.
66 *
67 * parameters:
68 * number <-- pointer to numbers of entities that should be ordered.
69 * (if NULL, a default 1 to n numbering is considered)
70 * level <-- level of the binary tree to descend
71 * nb_ent <-- number of entities in the binary tree to descend
72 * order <-> ordering array
73 *----------------------------------------------------------------------------*/
74
75 inline static void
_order_gnum_descend_tree(const cs_gnum_t number[],size_t level,const size_t nb_ent,cs_lnum_t order[])76 _order_gnum_descend_tree(const cs_gnum_t number[],
77 size_t level,
78 const size_t nb_ent,
79 cs_lnum_t order[])
80 {
81 size_t i_save, i1, i2, lv_cur;
82
83 i_save = (size_t)(order[level]);
84
85 while (level <= (nb_ent/2)) {
86
87 lv_cur = (2*level) + 1;
88
89 if (lv_cur < nb_ent - 1) {
90
91 i1 = (size_t)(order[lv_cur+1]);
92 i2 = (size_t)(order[lv_cur]);
93
94 if (number[i1] > number[i2]) lv_cur++;
95 }
96
97 if (lv_cur >= nb_ent) break;
98
99 i1 = i_save;
100 i2 = (size_t)(order[lv_cur]);
101
102 if (number[i1] >= number[i2]) break;
103
104 order[level] = order[lv_cur];
105 level = lv_cur;
106
107 }
108
109 order[level] = i_save;
110 }
111
112 /*----------------------------------------------------------------------------
113 * Order an array of global numbers.
114 *
115 * parameters:
116 * number <-- array of entity numbers (if NULL, a default 1 to n
117 * numbering is considered)
118 * order <-- pre-allocated ordering table
119 * nb_ent <-- number of entities considered
120 *----------------------------------------------------------------------------*/
121
122 static void
_order_gnum(const cs_gnum_t number[],cs_lnum_t order[],const size_t nb_ent)123 _order_gnum(const cs_gnum_t number[],
124 cs_lnum_t order[],
125 const size_t nb_ent)
126 {
127 size_t i;
128 cs_lnum_t o_save;
129
130 /* Initialize ordering array */
131
132 for (i = 0 ; i < nb_ent ; i++)
133 order[i] = i;
134
135 if (nb_ent < 2)
136 return;
137
138 /* Create binary tree */
139
140 i = (nb_ent / 2) ;
141 do {
142 i--;
143 _order_gnum_descend_tree(number, i, nb_ent, order);
144 } while (i > 0);
145
146 /* Sort binary tree */
147
148 for (i = nb_ent - 1 ; i > 0 ; i--) {
149 o_save = order[0];
150 order[0] = order[i];
151 order[i] = o_save;
152 _order_gnum_descend_tree(number, 0, i, order);
153 }
154 }
155
156 /*----------------------------------------------------------------------------
157 * Descend binary tree for the lexicographical ordering of a strided
158 * cs_gnum_t array.
159 *
160 * parameters:
161 * number <-- pointer to numbers of entities that should be ordered.
162 * (if NULL, a default 1 to n numbering is considered)
163 * stride <-- stride of array (number of values to compare)
164 * level <-- level of the binary tree to descend
165 * nb_ent <-- number of entities in the binary tree to descend
166 * order <-> ordering array
167 *----------------------------------------------------------------------------*/
168
169 inline static void
_order_gnum_descend_tree_s(const cs_gnum_t number[],size_t stride,size_t level,const size_t nb_ent,cs_lnum_t order[])170 _order_gnum_descend_tree_s(const cs_gnum_t number[],
171 size_t stride,
172 size_t level,
173 const size_t nb_ent,
174 cs_lnum_t order[])
175 {
176 size_t i_save, i1, i2, j, lv_cur;
177
178 i_save = (size_t)(order[level]);
179
180 while (level <= (nb_ent/2)) {
181
182 lv_cur = (2*level) + 1;
183
184 if (lv_cur < nb_ent - 1) {
185
186 i1 = (size_t)(order[lv_cur+1]);
187 i2 = (size_t)(order[lv_cur]);
188
189 for (j = 0; j < stride; j++) {
190 if (number[i1*stride + j] != number[i2*stride + j])
191 break;
192 }
193
194 if (j < stride) {
195 if (number[i1*stride + j] > number[i2*stride + j])
196 lv_cur++;
197 }
198
199 }
200
201 if (lv_cur >= nb_ent) break;
202
203 i1 = i_save;
204 i2 = (size_t)(order[lv_cur]);
205
206 for (j = 0; j < stride; j++) {
207 if (number[i1*stride + j] != number[i2*stride + j])
208 break;
209 }
210
211 if (j == stride) break;
212 if (number[i1*stride + j] >= number[i2*stride + j]) break;
213
214 order[level] = order[lv_cur];
215 level = lv_cur;
216
217 }
218
219 order[level] = i_save;
220 }
221
222 /*----------------------------------------------------------------------------
223 * Order a strided array of global numbers lexicographically.
224 *
225 * parameters:
226 * number <-- array of entity numbers (if NULL, a default 1 to n
227 * numbering is considered)
228 * stride <-- stride of array (number of values to compare)
229 * order --> pre-allocated ordering table
230 * nb_ent <-- number of entities considered
231 *----------------------------------------------------------------------------*/
232
233 static void
_order_gnum_s(const cs_gnum_t number[],size_t stride,cs_lnum_t order[],const size_t nb_ent)234 _order_gnum_s(const cs_gnum_t number[],
235 size_t stride,
236 cs_lnum_t order[],
237 const size_t nb_ent)
238 {
239 size_t i;
240 cs_lnum_t o_save;
241
242 /* Initialize ordering array */
243
244 for (i = 0 ; i < nb_ent ; i++)
245 order[i] = i;
246
247 if (nb_ent < 2)
248 return;
249
250 /* Create binary tree */
251
252 i = (nb_ent / 2) ;
253 do {
254 i--;
255 _order_gnum_descend_tree_s(number, stride, i, nb_ent, order);
256 } while (i > 0);
257
258 /* Sort binary tree */
259
260 for (i = nb_ent - 1 ; i > 0 ; i--) {
261 o_save = order[0];
262 order[0] = order[i];
263 order[i] = o_save;
264 _order_gnum_descend_tree_s(number, stride, 0, i, order);
265 }
266 }
267
268 /*----------------------------------------------------------------------------
269 * Indicate if element i1 from an indexed list is lexicographically
270 * greater than or equal to element i2.
271 *
272 * parameters:
273 * i1 <-- position in index for the first element
274 * i2 <-- position in index for the second element
275 * index <-- number of values to compare for each entity
276 * number <-- pointer to numbers of entities that should be ordered.
277 * (if NULL, a default 1 to n numbering is considered)
278 *
279 * returns:
280 * true if element i1 is greater or equal than element i2, false otherwise
281 *----------------------------------------------------------------------------*/
282
283 inline static bool
_indexed_is_greater_or_equal(size_t i1,size_t i2,const cs_lnum_t index[],const cs_gnum_t number[])284 _indexed_is_greater_or_equal(size_t i1,
285 size_t i2,
286 const cs_lnum_t index[],
287 const cs_gnum_t number[])
288 {
289 cs_lnum_t i;
290
291 cs_lnum_t i1_s = index[i1], i1_e = index[i1+1], s1 = i1_e - i1_s;
292 cs_lnum_t i2_s = index[i2], i2_e = index[i2+1], s2 = i2_e - i2_s;
293
294 if (s1 >= s2) {
295
296 for (i = 0; i < s2; i++) {
297 if (number[i1_s + i] > number[i2_s + i])
298 return true;
299 else if (number[i1_s + i] < number[i2_s + i])
300 return false;
301 }
302
303 return true;
304 }
305 else { /* s1 < s2 */
306
307 for (i = 0; i < s1; i++) {
308 if (number[i1_s + i] > number[i2_s + i])
309 return true;
310 else if (number[i1_s + i] < number[i2_s + i])
311 return false;
312 }
313
314 return false;
315 }
316
317 }
318
319 /*----------------------------------------------------------------------------
320 * Indicate if element i1 from an indexed list is lexicographically
321 * strictly greater than element i2.
322 *
323 * parameters:
324 * i1 <-- position in index for the first element
325 * i2 <-- position in index for the second element
326 * index <-- number of values to compare for each entity
327 * number <-- pointer to numbers of entities that should be ordered.
328 * (if NULL, a default 1 to n numbering is considered)
329 *
330 * returns:
331 * true if element i1 is strictly greater than element i2, false otherwise
332 *----------------------------------------------------------------------------*/
333
334 inline static bool
_indexed_is_greater(size_t i1,size_t i2,const cs_lnum_t index[],const cs_gnum_t number[])335 _indexed_is_greater(size_t i1,
336 size_t i2,
337 const cs_lnum_t index[],
338 const cs_gnum_t number[])
339 {
340 cs_lnum_t i;
341
342 cs_lnum_t i1_s = index[i1], i1_e = index[i1+1], s1 = i1_e - i1_s;
343 cs_lnum_t i2_s = index[i2], i2_e = index[i2+1], s2 = i2_e - i2_s;
344
345 if (s1 > s2) {
346
347 for (i = 0; i < s2; i++) {
348 if (number[i1_s + i] > number[i2_s + i])
349 return true;
350 else if (number[i1_s + i] < number[i2_s + i])
351 return false;
352 }
353
354 return true;
355 }
356 else { /* s1 <= s2 */
357
358 for (i = 0; i < s1; i++) {
359 if (number[i1_s + i] > number[i2_s + i])
360 return true;
361 else if (number[i1_s + i] < number[i2_s + i])
362 return false;
363 }
364
365 return false;
366 }
367
368 }
369
370 /*----------------------------------------------------------------------------
371 * Descend binary tree for the lexicographical ordering of an indexed
372 * array of global numbers.
373 *
374 * parameters:
375 * number <-- pointer to numbers of entities that should be ordered.
376 * (if NULL, a default 1 to n numbering is considered)
377 * index <-- number of values to compare for each entity
378 * level <-- level of the binary tree to descend
379 * nb_ent <-- number of entities in the binary tree to descend
380 * order <-> ordering array
381 *----------------------------------------------------------------------------*/
382
383 inline static void
_order_gnum_descend_tree_i(const cs_gnum_t number[],const cs_lnum_t index[],size_t level,const size_t nb_ent,cs_lnum_t order[])384 _order_gnum_descend_tree_i(const cs_gnum_t number[],
385 const cs_lnum_t index[],
386 size_t level,
387 const size_t nb_ent,
388 cs_lnum_t order[])
389 {
390 size_t i_save, i1, i2, lv_cur;
391
392 i_save = (size_t)(order[level]);
393
394 while (level <= (nb_ent/2)) {
395
396 lv_cur = (2*level) + 1;
397
398 if (lv_cur < nb_ent - 1) {
399
400 i1 = (size_t)(order[lv_cur+1]);
401 i2 = (size_t)(order[lv_cur]);
402
403 /* Test if element in position i1 is greater than element in
404 position i2 */
405
406 if (_indexed_is_greater(i1, i2, index, number))
407 lv_cur++;
408
409 }
410
411 if (lv_cur >= nb_ent) break;
412
413 i1 = i_save;
414 i2 = (size_t)(order[lv_cur]);
415
416 if (_indexed_is_greater_or_equal(i1, i2, index, number))
417 break;
418
419 order[level] = order[lv_cur];
420 level = lv_cur;
421
422 }
423
424 order[level] = i_save;
425 }
426
427 /*----------------------------------------------------------------------------
428 * Order an indexed array of global numbers lexicographically.
429 *
430 * parameters:
431 * number <-- array of entity numbers (if NULL, a default 1 to n
432 * numbering is considered)
433 * index <-- number of values to compare for each entity
434 * order --> pre-allocated ordering table
435 * nb_ent <-- number of entities considered
436 *----------------------------------------------------------------------------*/
437
438 static void
_order_gnum_i(const cs_gnum_t number[],const cs_lnum_t index[],cs_lnum_t order[],const size_t nb_ent)439 _order_gnum_i(const cs_gnum_t number[],
440 const cs_lnum_t index[],
441 cs_lnum_t order[],
442 const size_t nb_ent)
443 {
444 size_t i;
445 cs_lnum_t o_save;
446
447 /* Initialize ordering array */
448
449 for (i = 0 ; i < nb_ent ; i++)
450 order[i] = i;
451
452 if (nb_ent < 2)
453 return;
454
455 /* Create binary tree */
456
457 i = (nb_ent / 2);
458 do {
459 i--;
460 _order_gnum_descend_tree_i(number, index, i, nb_ent, order);
461 } while (i > 0);
462
463
464 /* Sort binary tree */
465
466 for (i = nb_ent - 1 ; i > 0 ; i--) {
467 o_save = order[0];
468 order[0] = order[i];
469 order[i] = o_save;
470 _order_gnum_descend_tree_i(number, index, 0, i, order);
471 }
472
473 }
474
475 /*----------------------------------------------------------------------------
476 * Descend binary tree for the ordering of a cs_lnum_t (integer) array.
477 *
478 * parameters:
479 * number <-- pointer to numbers of entities that should be ordered.
480 * (if NULL, a default 1 to n numbering is considered)
481 * level <-- level of the binary tree to descend
482 * nb_ent <-- number of entities in the binary tree to descend
483 * order <-> ordering array
484 *----------------------------------------------------------------------------*/
485
486 inline static void
_order_lnum_descend_tree(const cs_lnum_t number[],size_t level,const size_t nb_ent,cs_lnum_t order[])487 _order_lnum_descend_tree(const cs_lnum_t number[],
488 size_t level,
489 const size_t nb_ent,
490 cs_lnum_t order[])
491 {
492 size_t i_save, i1, i2, lv_cur;
493
494 i_save = (size_t)(order[level]);
495
496 while (level <= (nb_ent/2)) {
497
498 lv_cur = (2*level) + 1;
499
500 if (lv_cur < nb_ent - 1) {
501
502 i1 = (size_t)(order[lv_cur+1]);
503 i2 = (size_t)(order[lv_cur]);
504
505 if (number[i1] > number[i2]) lv_cur++;
506 }
507
508 if (lv_cur >= nb_ent) break;
509
510 i1 = i_save;
511 i2 = (size_t)(order[lv_cur]);
512
513 if (number[i1] >= number[i2]) break;
514
515 order[level] = order[lv_cur];
516 level = lv_cur;
517
518 }
519
520 order[level] = i_save;
521 }
522
523 /*----------------------------------------------------------------------------
524 * Order an array of local numbers.
525 *
526 * parameters:
527 * number <-- array of entity numbers (if NULL, a default 1 to n
528 * numbering is considered)
529 * order <-- pre-allocated ordering table
530 * nb_ent <-- number of entities considered
531 *----------------------------------------------------------------------------*/
532
533 static void
_order_lnum(const cs_lnum_t number[],cs_lnum_t order[],const size_t nb_ent)534 _order_lnum(const cs_lnum_t number[],
535 cs_lnum_t order[],
536 const size_t nb_ent)
537 {
538 size_t i;
539 cs_lnum_t o_save;
540
541 /* Initialize ordering array */
542
543 for (i = 0 ; i < nb_ent ; i++)
544 order[i] = i;
545
546 if (nb_ent < 2)
547 return;
548
549 /* Create binary tree */
550
551 i = (nb_ent / 2) ;
552 do {
553 i--;
554 _order_lnum_descend_tree(number, i, nb_ent, order);
555 } while (i > 0);
556
557 /* Sort binary tree */
558
559 for (i = nb_ent - 1 ; i > 0 ; i--) {
560 o_save = order[0];
561 order[0] = order[i];
562 order[i] = o_save;
563 _order_lnum_descend_tree(number, 0, i, order);
564 }
565 }
566
567 /*----------------------------------------------------------------------------
568 * Descend binary tree for the lexicographical ordering of a strided
569 * cs_lnum_t array.
570 *
571 * parameters:
572 * number <-- pointer to numbers of entities that should be ordered.
573 * (if NULL, a default 1 to n numbering is considered)
574 * stride <-- stride of array (number of values to compare)
575 * level <-- level of the binary tree to descend
576 * nb_ent <-- number of entities in the binary tree to descend
577 * order <-> ordering array
578 *----------------------------------------------------------------------------*/
579
580 inline static void
_order_lnum_descend_tree_s(const cs_lnum_t number[],size_t stride,size_t level,const size_t nb_ent,cs_lnum_t order[])581 _order_lnum_descend_tree_s(const cs_lnum_t number[],
582 size_t stride,
583 size_t level,
584 const size_t nb_ent,
585 cs_lnum_t order[])
586 {
587 size_t i_save, i1, i2, j, lv_cur;
588
589 i_save = (size_t)(order[level]);
590
591 while (level <= (nb_ent/2)) {
592
593 lv_cur = (2*level) + 1;
594
595 if (lv_cur < nb_ent - 1) {
596
597 i1 = (size_t)(order[lv_cur+1]);
598 i2 = (size_t)(order[lv_cur]);
599
600 for (j = 0; j < stride; j++) {
601 if (number[i1*stride + j] != number[i2*stride + j])
602 break;
603 }
604
605 if (j < stride) {
606 if (number[i1*stride + j] > number[i2*stride + j])
607 lv_cur++;
608 }
609
610 }
611
612 if (lv_cur >= nb_ent) break;
613
614 i1 = i_save;
615 i2 = (size_t)(order[lv_cur]);
616
617 for (j = 0; j < stride; j++) {
618 if (number[i1*stride + j] != number[i2*stride + j])
619 break;
620 }
621
622 if (j == stride) break;
623 if (number[i1*stride + j] >= number[i2*stride + j]) break;
624
625 order[level] = order[lv_cur];
626 level = lv_cur;
627
628 }
629
630 order[level] = i_save;
631 }
632
633 /*----------------------------------------------------------------------------
634 * Order a strided array of global numbers lexicographically.
635 *
636 * parameters:
637 * number <-- array of entity numbers (if NULL, a default 1 to n
638 * numbering is considered)
639 * stride <-- stride of array (number of values to compare)
640 * order --> pre-allocated ordering table
641 * nb_ent <-- number of entities considered
642 *----------------------------------------------------------------------------*/
643
644 static void
_order_lnum_s(const cs_lnum_t number[],size_t stride,cs_lnum_t order[],const size_t nb_ent)645 _order_lnum_s(const cs_lnum_t number[],
646 size_t stride,
647 cs_lnum_t order[],
648 const size_t nb_ent)
649 {
650 size_t i;
651 cs_lnum_t o_save;
652
653 /* Initialize ordering array */
654
655 for (i = 0 ; i < nb_ent ; i++)
656 order[i] = i;
657
658 if (nb_ent < 2)
659 return;
660
661 /* Create binary tree */
662
663 i = (nb_ent / 2) ;
664 do {
665 i--;
666 _order_lnum_descend_tree_s(number, stride, i, nb_ent, order);
667 } while (i > 0);
668
669 /* Sort binary tree */
670
671 for (i = nb_ent - 1 ; i > 0 ; i--) {
672 o_save = order[0];
673 order[0] = order[i];
674 order[i] = o_save;
675 _order_lnum_descend_tree_s(number, stride, 0, i, order);
676 }
677 }
678
679 /*----------------------------------------------------------------------------
680 * Descend binary tree for the ordering of a cs_real_t array.
681 *
682 * parameters:
683 * value <-- pointer to values of entities that should be ordered.
684 * level <-- level of the binary tree to descend
685 * nb_ent <-- number of entities in the binary tree to descend
686 * order <-> ordering array
687 *----------------------------------------------------------------------------*/
688
689 inline static void
_order_real_descend_tree(const cs_real_t value[],size_t level,const size_t nb_ent,cs_lnum_t order[])690 _order_real_descend_tree(const cs_real_t value[],
691 size_t level,
692 const size_t nb_ent,
693 cs_lnum_t order[])
694 {
695 size_t i_save, i1, i2, lv_cur;
696
697 i_save = (size_t)(order[level]);
698
699 while (level <= (nb_ent/2)) {
700
701 lv_cur = (2*level) + 1;
702
703 if (lv_cur < nb_ent - 1) {
704
705 i1 = (size_t)(order[lv_cur+1]);
706 i2 = (size_t)(order[lv_cur]);
707
708 if (value[i1] > value[i2]) lv_cur++;
709 }
710
711 if (lv_cur >= nb_ent) break;
712
713 i1 = i_save;
714 i2 = (size_t)(order[lv_cur]);
715
716 if (value[i1] >= value[i2]) break;
717
718 order[level] = order[lv_cur];
719 level = lv_cur;
720
721 }
722
723 order[level] = i_save;
724 }
725
726 /*----------------------------------------------------------------------------
727 * Order an array of local values.
728 *
729 * parameters:
730 * value <-- array of entity values
731 * order <-- pre-allocated ordering table
732 * nb_ent <-- number of entities considered
733 *----------------------------------------------------------------------------*/
734
735 static void
_order_real(const cs_real_t value[],cs_lnum_t order[],const size_t nb_ent)736 _order_real(const cs_real_t value[],
737 cs_lnum_t order[],
738 const size_t nb_ent)
739 {
740 size_t i;
741 cs_lnum_t o_save;
742
743 /* Initialize ordering array */
744
745 for (i = 0 ; i < nb_ent ; i++)
746 order[i] = i;
747
748 if (nb_ent < 2)
749 return;
750
751 /* Create binary tree */
752
753 i = (nb_ent / 2) ;
754 do {
755 i--;
756 _order_real_descend_tree(value, i, nb_ent, order);
757 } while (i > 0);
758
759 /* Sort binary tree */
760
761 for (i = nb_ent - 1 ; i > 0 ; i--) {
762 o_save = order[0];
763 order[0] = order[i];
764 order[i] = o_save;
765 _order_real_descend_tree(value, 0, i, order);
766 }
767 }
768
769 /*! (DOXYGEN_SHOULD_SKIP_THIS) \endcond */
770
771 /*=============================================================================
772 * Public function definitions
773 *============================================================================*/
774
775 /*----------------------------------------------------------------------------*/
776 /*!
777 * \brief Test if an array of global numbers is ordered.
778 *
779 * \param[in] list optional list (1 to n numbering) of selected entities
780 * (or NULL if all nb_ent are selected). This list may
781 * contain element numbers in any order
782 * \param[in] number array of all entity numbers (number of entity i given
783 * by number[i] or number[list[i] - 1]) if list exists
784 * (if NULL, a default 1 to n numbering is considered)
785 * \param[in] nb_ent number of entities considered
786 *
787 * \return 1 if ordered, 0 otherwise.
788 */
789 /*----------------------------------------------------------------------------*/
790
791 int
cs_order_gnum_test(const cs_lnum_t list[],const cs_gnum_t number[],size_t nb_ent)792 cs_order_gnum_test(const cs_lnum_t list[],
793 const cs_gnum_t number[],
794 size_t nb_ent)
795 {
796 size_t i = 0;
797
798 /* If numbering is explicit */
799
800 if (number != NULL) {
801
802 if (list != NULL) {
803 for (i = 1 ; i < nb_ent ; i++) {
804 if (number[list[i] - 1] < number[list[i-1] - 1])
805 break;
806 }
807 }
808 else {
809 for (i = 1 ; i < nb_ent ; i++) {
810 if (number[i] < number[i-1])
811 break;
812 }
813 }
814
815 /* If numbering is implicit */
816
817 }
818 else {
819
820 if (list != NULL) {
821 for (i = 1 ; i < nb_ent ; i++) {
822 if (list[i] < list[i-1])
823 break;
824 }
825 }
826 else
827 i = nb_ent;
828 }
829
830 if (i == nb_ent || nb_ent == 0)
831 return 1;
832 else
833 return 0;
834 }
835
836 /*----------------------------------------------------------------------------*/
837 /*!
838 * \brief Return an ordering table associated with an array of global numbers.
839 *
840 * \param[in] list optional list (1 to n numbering) of selected entities
841 * (or NULL if all nb_ent are selected). This list may
842 * contain element numbers in any order
843 * \param[in] number array of all entity numbers (number of entity i given
844 * by number[i] or number[list[i] - 1]) if list exists
845 * (if NULL, a default 1 to n numbering is considered)
846 * \param[in] nb_ent number of entities considered
847 *
848 * \return pointer to list of nb_ent entities (0 to n-1 numbering) ordered by
849 * increasing associated number. The calling code is responsible for
850 * freeing this array when it is not needed anymore.
851 */
852 /*----------------------------------------------------------------------------*/
853
854 cs_lnum_t *
cs_order_gnum(const cs_lnum_t list[],const cs_gnum_t number[],size_t nb_ent)855 cs_order_gnum(const cs_lnum_t list[],
856 const cs_gnum_t number[],
857 size_t nb_ent)
858 {
859 cs_lnum_t *order;
860
861 BFT_MALLOC(order, nb_ent, cs_lnum_t);
862
863 cs_order_gnum_allocated(list,
864 number,
865 order,
866 nb_ent);
867
868 return order;
869 }
870
871 /*----------------------------------------------------------------------------*/
872 /*!
873 * \brief Return a lexicographical ordering table associated with a strided
874 * array of global numbers.
875 *
876 * \param[in] list optional list (1 to n numbering) of selected entities
877 * (or NULL if all nb_ent are selected). This list may
878 * contain element numbers in any order
879 * \param[in] number array of all entity numbers (number of entity i
880 * given by number[i] or number[list[i] - 1]) if list
881 * exists (if NULL, a default 1 to n numbering is
882 * considered)
883 * \param[in] stride stride of number array (number of values to compare)
884 * \param[in] nb_ent number of entities considered
885 *
886 * \return pointer to list of nb_ent entities (0 to n-1 numbering) ordered by
887 * increasing associated number. The calling code is responsible for
888 * freeing this array when it is not needed anymore.
889 */
890 /*----------------------------------------------------------------------------*/
891
892 cs_lnum_t *
cs_order_gnum_s(const cs_lnum_t list[],const cs_gnum_t number[],size_t stride,size_t nb_ent)893 cs_order_gnum_s(const cs_lnum_t list[],
894 const cs_gnum_t number[],
895 size_t stride,
896 size_t nb_ent)
897 {
898 cs_lnum_t *order;
899
900 BFT_MALLOC(order, nb_ent, cs_lnum_t);
901
902 cs_order_gnum_allocated_s(list,
903 number,
904 stride,
905 order,
906 nb_ent);
907
908 return order;
909 }
910
911 /*----------------------------------------------------------------------------*/
912 /*!
913 * \brief Return a lexicographical ordering table associated with an indexed
914 * array of global numbers.
915 *
916 * \param[in] list optional list (1 to n numbering) of selected entities
917 * (or NULL if all nb_ent are selected). This list may
918 * contain element numbers in any order
919 * \param[in] number array of all entity numbers (numbers of entity i start
920 * at index[i] or _index[i] (reduced index) if list exists).
921 * If list = NULL, a default 1 to n numbering is considered)
922 * \param[in] index number of values to compare for each entity
923 * \param[in] nb_ent number of entities considered
924 *
925 * \return pointer to list of nb_ent entities (0 to n-1 numbering) ordered by
926 * increasing associated number. The calling code is responsible for
927 * freeing this array when it is not needed anymore.
928 */
929 /*----------------------------------------------------------------------------*/
930
931 cs_lnum_t *
cs_order_gnum_i(const cs_lnum_t list[],const cs_gnum_t number[],const cs_lnum_t index[],size_t nb_ent)932 cs_order_gnum_i(const cs_lnum_t list[],
933 const cs_gnum_t number[],
934 const cs_lnum_t index[],
935 size_t nb_ent)
936 {
937 cs_lnum_t *order = NULL;
938
939 BFT_MALLOC(order, nb_ent, cs_lnum_t);
940
941 cs_order_gnum_allocated_i(list, number, index, order, nb_ent);
942
943 return order;
944 }
945
946 /*----------------------------------------------------------------------------*/
947 /*!
948 * \brief Compute an ordering table associated with an array of global numbers.
949 *
950 * \param[in] list optional list (1 to n numbering) of selected entities
951 * (or NULL if all nb_ent are selected). This list may
952 * contain element numbers in any order
953 * \param[in] number array of all entity numbers (number of entity i given
954 * by number[i] or number[list[i] - 1]) if list exists
955 * (if NULL, a default 1 to n numbering is considered)
956 * \param[out] order pointer to pre-allocated ordering table
957 * \param[in] nb_ent number of entities considered
958 */
959 /*----------------------------------------------------------------------------*/
960
961 void
cs_order_gnum_allocated(const cs_lnum_t list[],const cs_gnum_t number[],cs_lnum_t order[],size_t nb_ent)962 cs_order_gnum_allocated(const cs_lnum_t list[],
963 const cs_gnum_t number[],
964 cs_lnum_t order[],
965 size_t nb_ent)
966 {
967 size_t i;
968 cs_gnum_t *number_list;
969
970 /* Explicit numbering */
971
972 if (number != NULL) {
973
974 if (list != NULL) {
975 BFT_MALLOC(number_list, nb_ent, cs_gnum_t);
976 for (i = 0 ; i < nb_ent ; i++)
977 number_list[i] = number[list[i] - 1];
978 _order_gnum(number_list, order, nb_ent);
979 BFT_FREE(number_list);
980 }
981 else
982 _order_gnum(number,
983 order,
984 nb_ent);
985
986 }
987
988 /* Implicit numbering */
989
990 else {
991
992 if (list != NULL) {
993 BFT_MALLOC(number_list, nb_ent, cs_gnum_t);
994 for (i = 0 ; i < nb_ent ; i++)
995 number_list[i] = (cs_gnum_t)(list[i]);
996 _order_gnum(number_list, order, nb_ent);
997 BFT_FREE(number_list);
998 }
999 else {
1000 for (i = 0 ; i < nb_ent ; i++)
1001 order[i] = i;
1002 }
1003
1004 }
1005
1006 }
1007
1008 /*----------------------------------------------------------------------------*/
1009 /*!
1010 * \brief Compute a lexicographical ordering table associated with an array of
1011 * strided global numbers.
1012 *
1013 * \param[in] list optional list (1 to n numbering) of selected entities
1014 * (or NULL if all nb_ent are selected). This list may
1015 * contain element numbers in any order
1016 * \param[in] number array of all entity numbers (numbers of entity i start
1017 * at number[i*stride] or number[(list[i] - 1)*stride])
1018 * if list exists (if NULL, a default 1 to n numbering is
1019 * considered)
1020 * \param[in] stride stride of number array (number of values to compare)
1021 * \param[out] order pointer to pre-allocated ordering table
1022 * \param[in] nb_ent number of entities considered
1023 */
1024 /*----------------------------------------------------------------------------*/
1025
1026 void
cs_order_gnum_allocated_s(const cs_lnum_t list[],const cs_gnum_t number[],size_t stride,cs_lnum_t order[],const size_t nb_ent)1027 cs_order_gnum_allocated_s(const cs_lnum_t list[],
1028 const cs_gnum_t number[],
1029 size_t stride,
1030 cs_lnum_t order[],
1031 const size_t nb_ent)
1032 {
1033 size_t i, j;
1034 cs_gnum_t *number_list;
1035
1036 /* Explicit numbering */
1037
1038 if (number != NULL) {
1039
1040 if (list != NULL) {
1041 BFT_MALLOC(number_list, nb_ent*stride, cs_gnum_t);
1042 for (i = 0 ; i < nb_ent ; i++) {
1043 for (j = 0; j < stride; j++)
1044 number_list[i*stride + j] = number[(list[i] - 1)*stride + j];
1045 }
1046 _order_gnum_s(number_list, stride, order, nb_ent);
1047 BFT_FREE(number_list);
1048 }
1049 else
1050 _order_gnum_s(number, stride, order, nb_ent);
1051
1052 }
1053
1054 /* Implicit numbering */
1055
1056 else
1057
1058 cs_order_gnum_allocated(list, NULL, order, nb_ent);
1059
1060 }
1061
1062 /*----------------------------------------------------------------------------*/
1063 /*!
1064 * \brief Compute a lexicographical ordering table associated with an indexed
1065 * array of global numbers.
1066 *
1067 * \param[in] list optional list (1 to n numbering) of selected entities
1068 * (or NULL if all nb_ent are selected). This list may
1069 * contain element numbers in any order
1070 * \param[in] number array of all entity numbers (numbers of entity i start
1071 * at index[i] or _index[i] (reduced index) if list
1072 * exists). If list = NULL, a default 1 to n numbering
1073 * is considered)
1074 * \param[in] index number of values to compare for each entity (from 0)
1075 * \param[out] order pointer to pre-allocated ordering table
1076 * \param[in] nb_ent number of entities considered
1077 */
1078 /*----------------------------------------------------------------------------*/
1079
1080 void
cs_order_gnum_allocated_i(const cs_lnum_t list[],const cs_gnum_t number[],const cs_lnum_t index[],cs_lnum_t order[],size_t nb_ent)1081 cs_order_gnum_allocated_i(const cs_lnum_t list[],
1082 const cs_gnum_t number[],
1083 const cs_lnum_t index[],
1084 cs_lnum_t order[],
1085 size_t nb_ent)
1086 {
1087 /* Explicit numbering */
1088
1089 if (number != NULL) {
1090
1091 if (list != NULL) {
1092
1093 size_t i, j, k, ent_id, _shift;
1094
1095 cs_lnum_t *_index = NULL;
1096 cs_gnum_t *number_list = NULL;
1097
1098 BFT_MALLOC(_index, nb_ent + 1, cs_lnum_t);
1099
1100 /* Count reduced size */
1101
1102 for (i = 0; i < nb_ent; i++) {
1103 ent_id = list[i]-1;
1104 _index[i+1] = index[ent_id+1] - index[ent_id];
1105 }
1106
1107 _index[0] = 0;
1108 for (i = 0; i < nb_ent; i++)
1109 _index[i+1] += _index[i];
1110
1111 BFT_MALLOC(number_list, _index[nb_ent], cs_gnum_t);
1112
1113 /* Define reduced index and adjacency */
1114
1115 for (i = 0; i < nb_ent; i++) {
1116
1117 ent_id = list[i]-1;
1118 _shift = _index[i];
1119
1120 for (j = index[ent_id], k = 0;
1121 (cs_lnum_t)j < index[ent_id+1]; j++, k++)
1122 number_list[_shift + k] = number[j];
1123
1124 }
1125
1126 /* Local ordering */
1127
1128 _order_gnum_i(number_list, _index, order, nb_ent);
1129
1130 BFT_FREE(_index);
1131 BFT_FREE(number_list);
1132
1133 }
1134 else { /* Local ordering */
1135
1136 _order_gnum_i(number, index, order, nb_ent);
1137
1138 }
1139
1140 } /* number != NULL */
1141
1142 /* Implicit numbering */
1143
1144 else
1145
1146 cs_order_gnum_allocated(list, NULL, order, nb_ent);
1147
1148 }
1149
1150 /*----------------------------------------------------------------------------*/
1151 /*!
1152 * \brief Compute an ordering table associated with an array of local numbers.
1153 *
1154 * \param[in] list optional list (1 to n numbering) of selected entities
1155 * (or NULL if all nb_ent are selected). This list may
1156 * contain element numbers in any order
1157 * \param[in] number array of all entity numbers (number of entity i given
1158 * by number[i] or number[list[i] - 1]) if list exists
1159 * (if NULL, a default 1 to n numbering is considered)
1160 * \param[out] order pointer to pre-allocated ordering table
1161 * \param[in] nb_ent number of entities considered
1162 */
1163 /*----------------------------------------------------------------------------*/
1164
1165 void
cs_order_lnum_allocated(const cs_lnum_t list[],const cs_lnum_t number[],cs_lnum_t order[],size_t nb_ent)1166 cs_order_lnum_allocated(const cs_lnum_t list[],
1167 const cs_lnum_t number[],
1168 cs_lnum_t order[],
1169 size_t nb_ent)
1170 {
1171 size_t i;
1172 cs_lnum_t *number_list;
1173
1174 /* Explicit numbering */
1175
1176 if (number != NULL) {
1177
1178 if (list != NULL) {
1179 BFT_MALLOC(number_list, nb_ent, cs_lnum_t);
1180 for (i = 0 ; i < nb_ent ; i++)
1181 number_list[i] = number[list[i] - 1];
1182 _order_lnum(number_list,
1183 order,
1184 nb_ent);
1185 BFT_FREE(number_list);
1186 }
1187 else
1188 _order_lnum(number,
1189 order,
1190 nb_ent);
1191
1192 }
1193
1194 /* Implicit numbering */
1195
1196 else {
1197
1198 if (list != NULL) {
1199 BFT_MALLOC(number_list, nb_ent, cs_lnum_t);
1200 for (i = 0 ; i < nb_ent ; i++)
1201 number_list[i] = (cs_gnum_t)(list[i]);
1202 _order_lnum(number_list,
1203 order,
1204 nb_ent);
1205 BFT_FREE(number_list);
1206 }
1207 else {
1208 for (i = 0 ; i < nb_ent ; i++)
1209 order[i] = i;
1210 }
1211
1212 }
1213
1214 }
1215
1216 /*----------------------------------------------------------------------------*/
1217 /*!
1218 * \brief Compute a lexicographical ordering table associated with an array of
1219 * strided local numbers.
1220 *
1221 * \param[in] list optional list (1 to n numbering) of selected entities
1222 * (or NULL if all nb_ent are selected). This list may
1223 * contain element numbers in any order
1224 * \param[in] number array of all entity numbers (numbers of entity i start
1225 * at number[i*stride] or number[(list[i] - 1)*stride])
1226 * if list exists (if NULL, a default 1 to n numbering is
1227 * considered)
1228 * \param[in] stride stride of number array (number of values to compare)
1229 * \param[out] order pointer to pre-allocated ordering table
1230 * \param[in] nb_ent number of entities considered
1231 */
1232 /*----------------------------------------------------------------------------*/
1233
1234 void
cs_order_lnum_allocated_s(const cs_lnum_t list[],const cs_lnum_t number[],size_t stride,cs_lnum_t order[],const size_t nb_ent)1235 cs_order_lnum_allocated_s(const cs_lnum_t list[],
1236 const cs_lnum_t number[],
1237 size_t stride,
1238 cs_lnum_t order[],
1239 const size_t nb_ent)
1240 {
1241 size_t i, j;
1242 cs_lnum_t *number_list;
1243
1244 /* Explicit numbering */
1245
1246 if (number != NULL) {
1247
1248 if (list != NULL) {
1249 BFT_MALLOC(number_list, nb_ent*stride, cs_lnum_t);
1250 for (i = 0 ; i < nb_ent ; i++) {
1251 for (j = 0; j < stride; j++)
1252 number_list[i*stride + j] = number[(list[i] - 1)*stride + j];
1253 }
1254 _order_lnum_s(number_list,
1255 stride,
1256 order,
1257 nb_ent);
1258 BFT_FREE(number_list);
1259 }
1260 else
1261 _order_lnum_s(number,
1262 stride,
1263 order,
1264 nb_ent);
1265
1266 }
1267
1268 /* Implicit numbering */
1269
1270 else
1271
1272 cs_order_lnum_allocated(list,
1273 NULL,
1274 order,
1275 nb_ent);
1276
1277 }
1278
1279 /*----------------------------------------------------------------------------*/
1280 /*!
1281 * \brief Compute an ordering table associated with an array of local values.
1282 *
1283 * \param[in] list optional list (1 to n numbering) of selected entities
1284 * (or NULL if all nb_ent are selected). This list may
1285 * contain element numbers in any order
1286 * \param[in] val array of all entity values (value of entity i given
1287 * by value[i] or value[list[i] - 1]) if list exists
1288 * \param[out] order pointer to pre-allocated ordering table
1289 * \param[in] nb_ent number of entities considered
1290 */
1291 /*----------------------------------------------------------------------------*/
1292
1293 void
cs_order_real_allocated(const cs_lnum_t list[],const cs_real_t val[],cs_lnum_t order[],size_t nb_ent)1294 cs_order_real_allocated(const cs_lnum_t list[],
1295 const cs_real_t val[],
1296 cs_lnum_t order[],
1297 size_t nb_ent)
1298 {
1299 size_t i;
1300 cs_real_t *val_list;
1301
1302 /* Explicit numbering */
1303
1304 if (list != NULL) {
1305 BFT_MALLOC(val_list, nb_ent, cs_real_t);
1306 for (i = 0 ; i < nb_ent ; i++)
1307 val_list[i] = val[list[i] - 1];
1308 _order_real(val_list,
1309 order,
1310 nb_ent);
1311 BFT_FREE(val_list);
1312 }
1313 else
1314 _order_real(val,
1315 order,
1316 nb_ent);
1317
1318 }
1319
1320 /*----------------------------------------------------------------------------*/
1321 /*!
1322 * \brief Build local renumbering array based on ordering of entities.
1323 *
1324 * \param[in] order 0 to n-1 ordering of entities by increasing attribute
1325 * \param[in] nb_ent number of entities considered
1326 *
1327 * \return pointer to renumbering array (0 to n-1 numbering) indicating the
1328 * new index of renumbered entities; The calling code is responsible
1329 * for freeing this array when it is not needed anymore.
1330 */
1331 /*----------------------------------------------------------------------------*/
1332
1333 cs_lnum_t *
cs_order_renumbering(const cs_lnum_t order[],size_t nb_ent)1334 cs_order_renumbering(const cs_lnum_t order[],
1335 size_t nb_ent)
1336 {
1337 size_t i;
1338 cs_lnum_t *number;
1339
1340 if (nb_ent < 1)
1341 return NULL;
1342
1343 assert(order != NULL);
1344
1345 BFT_MALLOC(number, nb_ent, cs_lnum_t);
1346
1347 #if defined(DEBUG) && !defined(NDEBUG)
1348 /* Initialize with "impossible" number (so as to have a reproducible
1349 and detectable error in the renumbering array in case of
1350 incorrect order[] values) */
1351 for (i = 0 ; i < nb_ent ; i++)
1352 number[i] = - 1;
1353 #endif
1354
1355 /* Populate renumbering array */
1356
1357 for (i = 0 ; i < nb_ent ; i++)
1358 number[order[i]] = i;
1359
1360 #if defined(DEBUG) && !defined(NDEBUG)
1361 /* Check renumbering array */
1362 for (i = 0 ; i < nb_ent ; i++)
1363 assert(number[i] >= 0);
1364 #endif
1365
1366 return number;
1367 }
1368
1369 /*----------------------------------------------------------------------------*/
1370 /*!
1371 * \brief Reorder data based on ordering array.
1372 *
1373 * \param[in] n_elts number of elements
1374 * \param[in] elt_size element size
1375 * \param[in] order reordering array
1376 * \param[in,out] data data
1377 *
1378 * \return new size of data
1379 */
1380 /*----------------------------------------------------------------------------*/
1381
1382 void
cs_order_reorder_data(cs_lnum_t n_elts,size_t elt_size,const cs_lnum_t order[],void * data)1383 cs_order_reorder_data(cs_lnum_t n_elts,
1384 size_t elt_size,
1385 const cs_lnum_t order[],
1386 void *data)
1387 {
1388 unsigned char *tmp;
1389 unsigned char *_data = data;
1390
1391 BFT_MALLOC(tmp, n_elts*elt_size, unsigned char);
1392
1393 for (cs_lnum_t i = 0; i < n_elts; i++) {
1394 cs_lnum_t j = order[i];
1395 const unsigned char *src = _data + j*elt_size;
1396 unsigned char *dest = tmp + i*elt_size;
1397 for (size_t k = 0; k < elt_size; k++)
1398 dest[k] = src[k];
1399 }
1400 memcpy(data, tmp, n_elts*elt_size);
1401
1402 BFT_FREE(tmp);
1403 }
1404
1405 /*----------------------------------------------------------------------------*/
1406 /*!
1407 * \brief Build a sorted array containing a single occurence of each global
1408 * number in a given array.
1409 *
1410 * Global numbers under a given "base" value are extruded.
1411 *
1412 * The caller is responsible for freeing the returned array.
1413 *
1414 * \param[in] n_ent size of input array
1415 * \param[in] base base id; numbers lower than this are dropped
1416 * \param[in] number array containing of all referenced entity numbers
1417 * \param[out] n_single array number of single occurences >= base
1418 * \param[out] single sorted array of unique numbers >= base
1419 */
1420 /*----------------------------------------------------------------------------*/
1421
1422 void
cs_order_single_gnum(size_t n_ent,const cs_gnum_t base,const cs_gnum_t number[],size_t * n_single,cs_gnum_t * single[])1423 cs_order_single_gnum(size_t n_ent,
1424 const cs_gnum_t base,
1425 const cs_gnum_t number[],
1426 size_t *n_single,
1427 cs_gnum_t *single[])
1428 {
1429 if (n_ent == 0) {
1430 *n_single = 0;
1431 *single = NULL;
1432 return;
1433 }
1434
1435 /* Sort global numbers */
1436
1437 cs_lnum_t *order = cs_order_gnum(NULL, number, n_ent);
1438
1439 /* Count number of distinct global entities */
1440
1441 size_t _n_single = 0;
1442
1443 size_t s_id = 0;
1444 while (s_id < n_ent && _n_single == 0) {
1445 if (number[order[s_id]] >= base)
1446 _n_single = 1;
1447 else
1448 s_id++;
1449 }
1450
1451 for (size_t i = s_id+1; i < n_ent; i++) {
1452 if (number[order[i]] > number[order[i-1]])
1453 _n_single += 1;
1454 }
1455
1456 cs_gnum_t *_single = NULL;
1457
1458 if (_n_single > 0) {
1459
1460 BFT_MALLOC(_single, _n_single, cs_gnum_t);
1461
1462 size_t j = 0;
1463 cs_gnum_t num_c = number[order[s_id]];
1464
1465 _single[j++] = num_c;
1466
1467 cs_gnum_t num_p = num_c;
1468 for (size_t i = s_id+1; i < n_ent; i++) {
1469 num_c = number[order[i]];
1470 if (num_c > num_p) {
1471 _single[j++] = num_c;
1472 num_p = num_c;
1473 }
1474 }
1475
1476 assert(j == _n_single);
1477 }
1478
1479 BFT_FREE(order);
1480
1481 *n_single = _n_single;
1482 *single = _single;
1483 }
1484
1485 /*----------------------------------------------------------------------------*/
1486
1487 END_C_DECLS
1488