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_Random64 (&seed) & 0x7FFF) ;
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_Random64 (&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_Random64 (&seed) & 0x7FFF) ;
89 262144 : A1 [k] = (int64_t) LG_Random64 (&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_Random64 (&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 = 9 ;
138 :
139 262145 : for (int k = 0 ; k < n ; k++)
140 : {
141 262144 : A0 [k] = (int64_t) (LG_Random64 (&seed) & 0x7FFF) ;
142 262144 : A1 [k] = (int64_t) LG_Random64 (&seed) ;
143 262144 : A2 [k] = (int64_t) LG_Random64 (&seed) ;
144 : }
145 :
146 1 : OK (LG_msort3 (A0, A1, A2, n, msg)) ;
147 :
148 262144 : for (int k = 1 ; k < n ; k++)
149 : {
150 262143 : TEST_CHECK (LG_lt_3 (A0, A1, A2, k-1, A0, A1, A2, k)
151 : || (A0 [k-1] == A0 [k] &&
152 : A1 [k-1] == A1 [k] &&
153 : A2 [k-1] == A2 [k])) ;
154 : }
155 :
156 262145 : for (int k = 0 ; k < n ; k++)
157 : {
158 262144 : A0 [k] = 0 ;
159 262144 : A1 [k] = (int64_t) (LG_Random64 (&seed) % 4) ;
160 262144 : A2 [k] = (int64_t) (LG_Random64 (&seed) % 4) ;
161 : }
162 :
163 1 : OK (LG_msort3 (A0, A1, A2, n, msg)) ;
164 :
165 262144 : for (int k = 1 ; k < n ; k++)
166 : {
167 262143 : TEST_CHECK (LG_lt_3 (A0, A1, A2, k-1, A0, A1, A2, k)
168 : || (A0 [k-1] == A0 [k] &&
169 : A1 [k-1] == A1 [k] &&
170 : A2 [k-1] == A2 [k])) ;
171 : }
172 :
173 1 : LAGraph_Free ((void **) &A0, NULL) ;
174 1 : LAGraph_Free ((void **) &A1, NULL) ;
175 1 : LAGraph_Free ((void **) &A2, NULL) ;
176 :
177 1 : OK (LAGraph_Finalize (msg)) ;
178 1 : }
179 :
180 : //-----------------------------------------------------------------------------
181 : // test_sort1_brutal
182 : //-----------------------------------------------------------------------------
183 :
184 : #if LG_BRUTAL_TESTS
185 1 : void test_sort1_brutal (void)
186 : {
187 1 : OK (LG_brutal_setup (msg)) ;
188 1 : OK (LAGraph_SetNumThreads (1, 4, msg)) ;
189 :
190 3 : for (int trial = 0 ; trial <= 1 ; trial++)
191 : {
192 2 : int64_t n = (trial == 0) ? 1024 : (256 * 1024) ;
193 :
194 : int64_t *A0 ;
195 2 : OK (LAGraph_Malloc ((void **) &A0, n, sizeof (int64_t), msg)) ;
196 :
197 2 : uint64_t seed = 1 ;
198 263170 : for (int k = 0 ; k < n ; k++)
199 : {
200 263168 : A0 [k] = (int64_t) (LG_Random64 (&seed) & 0x7FFF) ;
201 : }
202 :
203 3 : LG_BRUTAL (LG_msort1 (A0, n, msg)) ;
204 :
205 263168 : for (int k = 1 ; k < n ; k++)
206 : {
207 263166 : TEST_CHECK (A0 [k-1] <= A0 [k]) ;
208 : }
209 :
210 263170 : for (int k = 0 ; k < n ; k++)
211 : {
212 263168 : A0 [k] = (int64_t) (LG_Random64 (&seed) % 4) ;
213 : }
214 :
215 3 : LG_BRUTAL (LG_msort1 (A0, n, msg)) ;
216 :
217 263168 : for (int k = 1 ; k < n ; k++)
218 : {
219 263166 : TEST_CHECK (A0 [k-1] <= A0 [k]) ;
220 : }
221 :
222 2 : LAGraph_Free ((void **) &A0, NULL) ;
223 : }
224 :
225 1 : OK (LG_brutal_teardown (msg)) ;
226 1 : }
227 : #endif
228 :
229 : //-----------------------------------------------------------------------------
230 : // test_sort2_brutal
231 : //-----------------------------------------------------------------------------
232 :
233 : #if LG_BRUTAL_TESTS
234 1 : void test_sort2_brutal (void)
235 : {
236 1 : OK (LG_brutal_setup (msg)) ;
237 1 : OK (LAGraph_SetNumThreads (1, 4, msg)) ;
238 :
239 1 : int64_t n = 256 * 1024 ;
240 :
241 : int64_t *A0, *A1 ;
242 1 : OK (LAGraph_Malloc ((void **) &A0, n, sizeof (int64_t), msg)) ;
243 1 : OK (LAGraph_Malloc ((void **) &A1, n, sizeof (int64_t), msg)) ;
244 :
245 1 : uint64_t seed = 1 ;
246 262145 : for (int k = 0 ; k < n ; k++)
247 : {
248 262144 : A0 [k] = (int64_t) (LG_Random64 (&seed) & 0x7FFF) ;
249 262144 : A1 [k] = (int64_t) LG_Random64 (&seed) ;
250 : }
251 :
252 2 : LG_BRUTAL (LG_msort2 (A0, A1, n, msg)) ;
253 :
254 262144 : for (int k = 1 ; k < n ; k++)
255 : {
256 262143 : TEST_CHECK (LG_lt_2 (A0, A1, k-1, A0, A1, k)
257 : || (A0 [k-1] == A0 [k] && A1 [k-1] == A1 [k])) ;
258 : }
259 :
260 262145 : for (int k = 0 ; k < n ; k++)
261 : {
262 262144 : A0 [k] = 0 ;
263 262144 : A1 [k] = (int64_t) (LG_Random64 (&seed) % 4) ;
264 : }
265 :
266 2 : LG_BRUTAL (LG_msort2 (A0, A1, n, msg)) ;
267 :
268 262144 : for (int k = 1 ; k < n ; k++)
269 : {
270 262143 : TEST_CHECK (LG_lt_2 (A0, A1, k-1, A0, A1, k)
271 : || (A0 [k-1] == A0 [k] && A1 [k-1] == A1 [k])) ;
272 : }
273 :
274 1 : LAGraph_Free ((void **) &A0, NULL) ;
275 1 : LAGraph_Free ((void **) &A1, NULL) ;
276 :
277 1 : OK (LG_brutal_teardown (msg)) ;
278 1 : }
279 : #endif
280 :
281 : //-----------------------------------------------------------------------------
282 : // test_sort3_brutal
283 : //-----------------------------------------------------------------------------
284 :
285 : #if LG_BRUTAL_TESTS
286 1 : void test_sort3_brutal (void)
287 : {
288 1 : OK (LG_brutal_setup (msg)) ;
289 1 : OK (LAGraph_SetNumThreads (1, 4, msg)) ;
290 :
291 1 : int64_t n = 256 * 1024 ;
292 1 : printf ("test sort3\n") ;
293 :
294 : int64_t *A0, *A1, *A2 ;
295 1 : OK (LAGraph_Malloc ((void **) &A0, n, sizeof (int64_t), msg)) ;
296 1 : OK (LAGraph_Malloc ((void **) &A1, n, sizeof (int64_t), msg)) ;
297 1 : OK (LAGraph_Malloc ((void **) &A2, n, sizeof (int64_t), msg)) ;
298 :
299 1 : uint64_t seed = 1 ;
300 262145 : for (int k = 0 ; k < n ; k++)
301 : {
302 262144 : A0 [k] = (int64_t) (LG_Random64 (&seed) & 0x7FFF) ;
303 262144 : A1 [k] = (int64_t) LG_Random64 (&seed) ;
304 262144 : A2 [k] = (int64_t) LG_Random64 (&seed) ;
305 : }
306 :
307 2 : LG_BRUTAL (LG_msort3 (A0, A1, A2, n, msg)) ;
308 :
309 262144 : for (int k = 1 ; k < n ; k++)
310 : {
311 262143 : TEST_CHECK (LG_lt_3 (A0, A1, A2, k-1, A0, A1, A2, k)
312 : || (A0 [k-1] == A0 [k] &&
313 : A1 [k-1] == A1 [k] &&
314 : A2 [k-1] == A2 [k])) ;
315 : }
316 :
317 262145 : for (int k = 0 ; k < n ; k++)
318 : {
319 262144 : A0 [k] = 0 ;
320 262144 : A1 [k] = (int64_t) (LG_Random64 (&seed) % 4) ;
321 262144 : A2 [k] = (int64_t) (LG_Random64 (&seed) % 4) ;
322 : }
323 :
324 2 : LG_BRUTAL (LG_msort3 (A0, A1, A2, n, msg)) ;
325 :
326 262144 : for (int k = 1 ; k < n ; k++)
327 : {
328 262143 : TEST_CHECK (LG_lt_3 (A0, A1, A2, k-1, A0, A1, A2, k)
329 : || (A0 [k-1] == A0 [k] &&
330 : A1 [k-1] == A1 [k] &&
331 : A2 [k-1] == A2 [k])) ;
332 : }
333 :
334 1 : LAGraph_Free ((void **) &A0, NULL) ;
335 1 : LAGraph_Free ((void **) &A1, NULL) ;
336 1 : LAGraph_Free ((void **) &A2, NULL) ;
337 :
338 1 : OK (LG_brutal_teardown (msg)) ;
339 1 : }
340 : #endif
341 :
342 :
343 : //-----------------------------------------------------------------------------
344 : // TEST_LIST: the list of tasks for this entire test
345 : //-----------------------------------------------------------------------------
346 :
347 : TEST_LIST = {
348 : {"test_sort1", test_sort1},
349 : {"test_sort2", test_sort2},
350 : {"test_sort3", test_sort3},
351 : #if LG_BRUTAL_TESTS
352 : {"test_sort1_brutal", test_sort1_brutal},
353 : {"test_sort2_brutal", test_sort2_brutal},
354 : {"test_sort3_brutal", test_sort3_brutal},
355 : #endif
356 : {NULL, NULL}
357 : };
|
