Line data Source code
1 : //-----------------------------------------------------------------------------
2 : // LAGraph/src/test/test_Sort.c: test LG_msort* methods
3 : //-----------------------------------------------------------------------------
4 :
5 : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
6 : // SPDX-License-Identifier: BSD-2-Clause
7 : //
8 : // For additional details (including references to third party source code and
9 : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
10 : // Contributors.txt for a full list of contributors. Created, in part, with
11 : // funding and support from the U.S. Government (see Acknowledgments.txt file).
12 : // DM22-0790
13 :
14 : // Contributed by Timothy A. Davis, Texas A&M University
15 :
16 : //-----------------------------------------------------------------------------
17 :
18 : #include "LAGraph_test.h"
19 : #include "LG_internal.h"
20 :
21 : char msg [LAGRAPH_MSG_LEN] ;
22 :
23 : //-----------------------------------------------------------------------------
24 : // test_sort1
25 : //-----------------------------------------------------------------------------
26 :
27 1 : void test_sort1 (void)
28 : {
29 1 : OK (LAGraph_Init (msg)) ;
30 1 : OK (LAGraph_SetNumThreads (1, 4, msg)) ;
31 :
32 3 : for (int trial = 0 ; trial <= 1 ; trial++)
33 : {
34 2 : int64_t n = (trial == 0) ? 1024 : (256 * 1024) ;
35 :
36 : int64_t *A0 ;
37 2 : OK (LAGraph_Malloc ((void **) &A0, n, sizeof (int64_t), msg)) ;
38 :
39 2 : uint64_t seed = 1 ;
40 263170 : for (int k = 0 ; k < n ; k++)
41 : {
42 263168 : A0 [k] = (int64_t) LG_Random15 (&seed) ;
43 : }
44 :
45 2 : OK (LG_msort1 (A0, n, msg)) ;
46 :
47 263168 : for (int k = 1 ; k < n ; k++)
48 : {
49 263166 : TEST_CHECK (A0 [k-1] <= A0 [k]) ;
50 : }
51 :
52 263170 : for (int k = 0 ; k < n ; k++)
53 : {
54 263168 : A0 [k] = (int64_t) (LG_Random15 (&seed) % 4) ;
55 : }
56 :
57 2 : OK (LG_msort1 (A0, n, msg)) ;
58 :
59 263168 : for (int k = 1 ; k < n ; k++)
60 : {
61 263166 : TEST_CHECK (A0 [k-1] <= A0 [k]) ;
62 : }
63 :
64 2 : LAGraph_Free ((void **) &A0, NULL) ;
65 : }
66 :
67 1 : OK (LAGraph_Finalize (msg)) ;
68 1 : }
69 :
70 : //-----------------------------------------------------------------------------
71 : // test_sort2
72 : //-----------------------------------------------------------------------------
73 :
74 1 : void test_sort2 (void)
75 : {
76 1 : OK (LAGraph_Init (msg)) ;
77 1 : OK (LAGraph_SetNumThreads (1, 4, msg)) ;
78 :
79 1 : int64_t n = 256 * 1024 ;
80 :
81 : int64_t *A0, *A1 ;
82 1 : OK (LAGraph_Malloc ((void **) &A0, n, sizeof (int64_t), msg)) ;
83 1 : OK (LAGraph_Malloc ((void **) &A1, n, sizeof (int64_t), msg)) ;
84 :
85 1 : uint64_t seed = 1 ;
86 262145 : for (int k = 0 ; k < n ; k++)
87 : {
88 262144 : A0 [k] = (int64_t) LG_Random15 (&seed) ;
89 262144 : A1 [k] = (int64_t) LG_Random60 (&seed) ;
90 : }
91 :
92 1 : OK (LG_msort2 (A0, A1, n, msg)) ;
93 :
94 262144 : for (int k = 1 ; k < n ; k++)
95 : {
96 262143 : TEST_CHECK (LG_lt_2 (A0, A1, k-1, A0, A1, k)
97 : || (A0 [k-1] == A0 [k] && A1 [k-1] == A1 [k])) ;
98 : }
99 :
100 262145 : for (int k = 0 ; k < n ; k++)
101 : {
102 262144 : A0 [k] = 0 ;
103 262144 : A1 [k] = (int64_t) (LG_Random15 (&seed) % 4) ;
104 : }
105 :
106 1 : OK (LG_msort2 (A0, A1, n, msg)) ;
107 :
108 262144 : for (int k = 1 ; k < n ; k++)
109 : {
110 262143 : TEST_CHECK (LG_lt_2 (A0, A1, k-1, A0, A1, k)
111 : || (A0 [k-1] == A0 [k] && A1 [k-1] == A1 [k])) ;
112 : }
113 :
114 1 : LAGraph_Free ((void **) &A0, NULL) ;
115 1 : LAGraph_Free ((void **) &A1, NULL) ;
116 :
117 1 : OK (LAGraph_Finalize (msg)) ;
118 1 : }
119 :
120 : //-----------------------------------------------------------------------------
121 : // test_sort3
122 : //-----------------------------------------------------------------------------
123 :
124 1 : void test_sort3 (void)
125 : {
126 1 : OK (LAGraph_Init (msg)) ;
127 1 : OK (LAGraph_SetNumThreads (1, 4, msg)) ;
128 :
129 1 : int64_t n = 256 * 1024 ;
130 1 : printf ("test sort3\n") ;
131 :
132 : int64_t *A0, *A1, *A2 ;
133 1 : OK (LAGraph_Malloc ((void **) &A0, n, sizeof (int64_t), msg)) ;
134 1 : OK (LAGraph_Malloc ((void **) &A1, n, sizeof (int64_t), msg)) ;
135 1 : OK (LAGraph_Malloc ((void **) &A2, n, sizeof (int64_t), msg)) ;
136 :
137 1 : uint64_t seed = 1 ;
138 262145 : for (int k = 0 ; k < n ; k++)
139 : {
140 262144 : A0 [k] = (int64_t) LG_Random15 (&seed) ;
141 262144 : A1 [k] = (int64_t) LG_Random60 (&seed) ;
142 262144 : A2 [k] = (int64_t) LG_Random60 (&seed) ;
143 : }
144 :
145 1 : OK (LG_msort3 (A0, A1, A2, n, msg)) ;
146 :
147 262144 : for (int k = 1 ; k < n ; k++)
148 : {
149 262143 : TEST_CHECK (LG_lt_3 (A0, A1, A2, k-1, A0, A1, A2, k)
150 : || (A0 [k-1] == A0 [k] &&
151 : A1 [k-1] == A1 [k] &&
152 : A2 [k-1] == A2 [k])) ;
153 : }
154 :
155 262145 : for (int k = 0 ; k < n ; k++)
156 : {
157 262144 : A0 [k] = 0 ;
158 262144 : A1 [k] = (int64_t) (LG_Random15 (&seed) % 4) ;
159 262144 : A2 [k] = (int64_t) (LG_Random15 (&seed) % 4) ;
160 : }
161 :
162 1 : OK (LG_msort3 (A0, A1, A2, n, msg)) ;
163 :
164 262144 : for (int k = 1 ; k < n ; k++)
165 : {
166 262143 : TEST_CHECK (LG_lt_3 (A0, A1, A2, k-1, A0, A1, A2, k)
167 : || (A0 [k-1] == A0 [k] &&
168 : A1 [k-1] == A1 [k] &&
169 : A2 [k-1] == A2 [k])) ;
170 : }
171 :
172 1 : LAGraph_Free ((void **) &A0, NULL) ;
173 1 : LAGraph_Free ((void **) &A1, NULL) ;
174 1 : LAGraph_Free ((void **) &A2, NULL) ;
175 :
176 1 : OK (LAGraph_Finalize (msg)) ;
177 1 : }
178 :
179 : //-----------------------------------------------------------------------------
180 : // test_sort1_brutal
181 : //-----------------------------------------------------------------------------
182 :
183 : #if LAGRAPH_SUITESPARSE
184 1 : void test_sort1_brutal (void)
185 : {
186 1 : OK (LG_brutal_setup (msg)) ;
187 1 : OK (LAGraph_SetNumThreads (1, 4, msg)) ;
188 :
189 3 : for (int trial = 0 ; trial <= 1 ; trial++)
190 : {
191 2 : int64_t n = (trial == 0) ? 1024 : (256 * 1024) ;
192 :
193 : int64_t *A0 ;
194 2 : OK (LAGraph_Malloc ((void **) &A0, n, sizeof (int64_t), msg)) ;
195 :
196 2 : uint64_t seed = 1 ;
197 263170 : for (int k = 0 ; k < n ; k++)
198 : {
199 263168 : A0 [k] = (int64_t) LG_Random15 (&seed) ;
200 : }
201 :
202 3 : LG_BRUTAL (LG_msort1 (A0, n, msg)) ;
203 :
204 263168 : for (int k = 1 ; k < n ; k++)
205 : {
206 263166 : TEST_CHECK (A0 [k-1] <= A0 [k]) ;
207 : }
208 :
209 263170 : for (int k = 0 ; k < n ; k++)
210 : {
211 263168 : A0 [k] = (int64_t) (LG_Random15 (&seed) % 4) ;
212 : }
213 :
214 3 : LG_BRUTAL (LG_msort1 (A0, n, msg)) ;
215 :
216 263168 : for (int k = 1 ; k < n ; k++)
217 : {
218 263166 : TEST_CHECK (A0 [k-1] <= A0 [k]) ;
219 : }
220 :
221 2 : LAGraph_Free ((void **) &A0, NULL) ;
222 : }
223 :
224 1 : OK (LG_brutal_teardown (msg)) ;
225 1 : }
226 : #endif
227 :
228 : //-----------------------------------------------------------------------------
229 : // test_sort2_brutal
230 : //-----------------------------------------------------------------------------
231 :
232 : #if LAGRAPH_SUITESPARSE
233 1 : void test_sort2_brutal (void)
234 : {
235 1 : OK (LG_brutal_setup (msg)) ;
236 1 : OK (LAGraph_SetNumThreads (1, 4, msg)) ;
237 :
238 1 : int64_t n = 256 * 1024 ;
239 :
240 : int64_t *A0, *A1 ;
241 1 : OK (LAGraph_Malloc ((void **) &A0, n, sizeof (int64_t), msg)) ;
242 1 : OK (LAGraph_Malloc ((void **) &A1, n, sizeof (int64_t), msg)) ;
243 :
244 1 : uint64_t seed = 1 ;
245 262145 : for (int k = 0 ; k < n ; k++)
246 : {
247 262144 : A0 [k] = (int64_t) LG_Random15 (&seed) ;
248 262144 : A1 [k] = (int64_t) LG_Random60 (&seed) ;
249 : }
250 :
251 2 : LG_BRUTAL (LG_msort2 (A0, A1, n, msg)) ;
252 :
253 262144 : for (int k = 1 ; k < n ; k++)
254 : {
255 262143 : TEST_CHECK (LG_lt_2 (A0, A1, k-1, A0, A1, k)
256 : || (A0 [k-1] == A0 [k] && A1 [k-1] == A1 [k])) ;
257 : }
258 :
259 262145 : for (int k = 0 ; k < n ; k++)
260 : {
261 262144 : A0 [k] = 0 ;
262 262144 : A1 [k] = (int64_t) (LG_Random15 (&seed) % 4) ;
263 : }
264 :
265 2 : LG_BRUTAL (LG_msort2 (A0, A1, n, msg)) ;
266 :
267 262144 : for (int k = 1 ; k < n ; k++)
268 : {
269 262143 : TEST_CHECK (LG_lt_2 (A0, A1, k-1, A0, A1, k)
270 : || (A0 [k-1] == A0 [k] && A1 [k-1] == A1 [k])) ;
271 : }
272 :
273 1 : LAGraph_Free ((void **) &A0, NULL) ;
274 1 : LAGraph_Free ((void **) &A1, NULL) ;
275 :
276 1 : OK (LG_brutal_teardown (msg)) ;
277 1 : }
278 : #endif
279 :
280 : //-----------------------------------------------------------------------------
281 : // test_sort3_brutal
282 : //-----------------------------------------------------------------------------
283 :
284 1 : void test_sort3_brutal (void)
285 : {
286 1 : OK (LG_brutal_setup (msg)) ;
287 1 : OK (LAGraph_SetNumThreads (1, 4, msg)) ;
288 :
289 1 : int64_t n = 256 * 1024 ;
290 1 : printf ("test sort3\n") ;
291 :
292 : int64_t *A0, *A1, *A2 ;
293 1 : OK (LAGraph_Malloc ((void **) &A0, n, sizeof (int64_t), msg)) ;
294 1 : OK (LAGraph_Malloc ((void **) &A1, n, sizeof (int64_t), msg)) ;
295 1 : OK (LAGraph_Malloc ((void **) &A2, n, sizeof (int64_t), msg)) ;
296 :
297 1 : uint64_t seed = 1 ;
298 262145 : for (int k = 0 ; k < n ; k++)
299 : {
300 262144 : A0 [k] = (int64_t) LG_Random15 (&seed) ;
301 262144 : A1 [k] = (int64_t) LG_Random60 (&seed) ;
302 262144 : A2 [k] = (int64_t) LG_Random60 (&seed) ;
303 : }
304 :
305 2 : LG_BRUTAL (LG_msort3 (A0, A1, A2, n, msg)) ;
306 :
307 262144 : for (int k = 1 ; k < n ; k++)
308 : {
309 262143 : TEST_CHECK (LG_lt_3 (A0, A1, A2, k-1, A0, A1, A2, k)
310 : || (A0 [k-1] == A0 [k] &&
311 : A1 [k-1] == A1 [k] &&
312 : A2 [k-1] == A2 [k])) ;
313 : }
314 :
315 262145 : for (int k = 0 ; k < n ; k++)
316 : {
317 262144 : A0 [k] = 0 ;
318 262144 : A1 [k] = (int64_t) (LG_Random15 (&seed) % 4) ;
319 262144 : A2 [k] = (int64_t) (LG_Random15 (&seed) % 4) ;
320 : }
321 :
322 2 : LG_BRUTAL (LG_msort3 (A0, A1, A2, n, msg)) ;
323 :
324 262144 : for (int k = 1 ; k < n ; k++)
325 : {
326 262143 : TEST_CHECK (LG_lt_3 (A0, A1, A2, k-1, A0, A1, A2, k)
327 : || (A0 [k-1] == A0 [k] &&
328 : A1 [k-1] == A1 [k] &&
329 : A2 [k-1] == A2 [k])) ;
330 : }
331 :
332 1 : LAGraph_Free ((void **) &A0, NULL) ;
333 1 : LAGraph_Free ((void **) &A1, NULL) ;
334 1 : LAGraph_Free ((void **) &A2, NULL) ;
335 :
336 1 : OK (LG_brutal_teardown (msg)) ;
337 1 : }
338 :
339 :
340 : //-----------------------------------------------------------------------------
341 : // TEST_LIST: the list of tasks for this entire test
342 : //-----------------------------------------------------------------------------
343 :
344 : TEST_LIST = {
345 : {"test_sort1", test_sort1},
346 : {"test_sort2", test_sort2},
347 : {"test_sort3", test_sort3},
348 : #if LAGRAPH_SUITESPARSE
349 : {"test_sort1_brutal", test_sort1_brutal},
350 : {"test_sort2_brutal", test_sort2_brutal},
351 : {"test_sort3_brutal", test_sort3_brutal},
352 : #endif
353 : {NULL, NULL}
354 : };
|
