IOSS 2.0

Ioss_Sort.h
Go to the documentation of this file.
1 // Copyright(C) 1999-2017 National Technology & Engineering Solutions
2 // of Sandia, LLC (NTESS). Under the terms of Contract DE-NA0003525 with
3 // NTESS, the U.S. Government retains certain rights in this software.
4 //
5 // Redistribution and use in source and binary forms, with or without
6 // modification, are permitted provided that the following conditions are
7 // met:
8 //
9 // * Redistributions of source code must retain the above copyright
10 // notice, this list of conditions and the following disclaimer.
11 //
12 // * Redistributions in binary form must reproduce the above
13 // copyright notice, this list of conditions and the following
14 // disclaimer in the documentation and/or other materials provided
15 // with the distribution.
16 //
17 // * Neither the name of NTESS nor the names of its
18 // contributors may be used to endorse or promote products derived
19 // from this software without specific prior written permission.
20 //
21 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32
33 #ifndef IOSS_Ioss_Sort_h
34 #define IOSS_Ioss_Sort_h
35
36 #include <cstddef>
37 #include <vector>
38
39 // This is used instead of the std::sort since we were having issues
40 // with the std::sort on some compiler versions with certain options
41 // enabled (-fopenmp). If this shows up as a hotspot in performance
42 // measurements, then we can use std::sort on most platforms and just
43 // use this version where there are compiler issues.
44
45 // Using Explicit Template Instantiation with the types:
46 //
47 // std::vector<int>, std::vector<int64_t>, std::vector<std::pair<int64_t,int64_t>>
48 //
49 // Update in Ioss_Sort.C if other types are needed.
50
51 namespace {
52 const int QSORT_CUTOFF = 12;
53
54 template <typename INT> void SWAP(INT *V, size_t I, size_t J) { std::swap(V[I], V[J]); }
55
56 template <typename INT> void order3(INT v[], size_t left, size_t center, size_t right)
57 {
58 if (v[left] > v[center]) {
59 SWAP(v, left, center);
60 }
61 if (v[left] > v[right]) {
62 SWAP(v, left, right);
63 }
64 if (v[center] > v[right]) {
65 SWAP(v, center, right);
66 }
67 }
68
69 template <typename INT> size_t median3(INT v[], size_t left, size_t right)
70 {
71 size_t center = (left + right) / 2;
72 size_t pl = left;
73 size_t pm = center;
74 size_t pr = right;
75
76 if (right - left > 40) {
77 size_t s = (right - left) / 8;
78 order3(v, left, left + s, left + 2 * s);
79 order3(v, center - s, center, center + s);
80 order3(v, right - 2 * s, right - s, right);
81
82 // Now set up to get median of the 3 medians...
83 pl = left + s;
84 pm = center;
85 pr = right - s;
86 }
87 order3(v, pl, pm, pr);
88
89 SWAP(v, center, right - 1);
90 return right - 1;
91 }
92
93 template <typename INT> void qsort_int(INT v[], size_t left, size_t right)
94 {
95 size_t pivot;
96 size_t i, j;
97
98 if (left + QSORT_CUTOFF < right) {
99 pivot = median3(v, left, right);
100 i = left;
101 j = right - 1;
102
103 for (;;) {
104 while (v[++i] < v[pivot]) {
105 ;
106 }
107 while (v[--j] > v[pivot]) {
108 ;
109 }
110 if (i < j) {
111 SWAP(v, i, j);
112 }
113 else {
114 break;
115 }
116 }
117
118 SWAP(v, i, right - 1);
119 qsort_int(v, left, i - 1);
120 qsort_int(v, i + 1, right);
121 }
122 }
123
124 template <typename INT> void isort_int(INT v[], size_t N)
125 {
126 size_t i, j;
127 size_t ndx = 0;
128 INT small;
129 INT tmp;
130
131 if (N <= 1) {
132 return;
133 }
134 small = v[0];
135 for (i = 1; i < N; i++) {
136 if (v[i] < small) {
137 small = v[i];
138 ndx = i;
139 }
140 }
141 /* Put smallest value in slot 0 */
142 SWAP(v, 0, ndx);
143
144 for (i = 1; i < N; i++) {
145 tmp = v[i];
146 for (j = i; tmp < v[j - 1]; j--) {
147 v[j] = v[j - 1];
148 }
149 v[j] = tmp;
150 }
151 }
152 } // namespace
153
154 namespace Ioss {
155 template <typename INT> void qsort(std::vector<INT> &v)
156 {
157 if (v.size() <= 1) {
158 return;
159 }
160 qsort_int(v.data(), 0, v.size() - 1);
161 isort_int(v.data(), v.size());
162 }
163 } // namespace Ioss
164
165 #endif
Ioss::qsort
void qsort(std::vector< INT > &v)
Definition: Ioss_Sort.h:155
Ioss
The main namespace for the Ioss library.
Definition: Ioad_DatabaseIO.C:66
INT
int INT
Definition: Ioss_StructuredBlock.h:53
anonymous_namespace{Ioss_Sort.h}::qsort_int
void qsort_int(INT v[], size_t left, size_t right)
Definition: Ioss_Sort.h:93
anonymous_namespace{Ioss_Sort.h}::median3
size_t median3(INT v[], size_t left, size_t right)
Definition: Ioss_Sort.h:69
anonymous_namespace{Ioss_Sort.h}::isort_int
void isort_int(INT v[], size_t N)
Definition: Ioss_Sort.h:124
anonymous_namespace{Ioss_Sort.h}::order3
void order3(INT v[], size_t left, size_t center, size_t right)
Definition: Ioss_Sort.h:56
anonymous_namespace{Ioss_Sort.h}::SWAP
void SWAP(INT *V, size_t I, size_t J)
Definition: Ioss_Sort.h:54
anonymous_namespace{Ioss_Sort.h}::QSORT_CUTOFF
const int QSORT_CUTOFF
Definition: Ioss_Sort.h:52