1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
|
//------------------------------------------------------------------------------
// GB_qsort_1b: sort a 2-by-n list, using A [0][ ] as the sort key
//------------------------------------------------------------------------------
// SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2025, All Rights Reserved.
// SPDX-License-Identifier: Apache-2.0
//------------------------------------------------------------------------------
#include "sort/GB_sort.h"
// returns true if A [a] < B [b]
#define GB_lt(A,a,B,b) GB_lt_1 (A ## _0, a, B ## _0, b)
// Each entry has a single key: a 32-bit or 64-bit unsigned integer
#define GB_K 1
//------------------------------------------------------------------------------
// GB_qsort_1b_32_generic: generic method for any data type, A0 is 32bit
//------------------------------------------------------------------------------
#define GB_A0_t uint32_t
#define GB_A1_t GB_void
#define GB_partition GB_partition_1b_32_generic
#define GB_quicksort GB_quicksort_1b_32_generic
// argument list for calling a function
#define GB_arg(A) \
A ## _0, A ## _1, xsize
// argument list for calling a function, with offset
#define GB_arg_offset(A,x) \
A ## _0 + (x), A ## _1 + (x)*xsize, xsize
// argument list for defining a function
#define GB_args(A) \
GB_A0_t *restrict A ## _0, \
GB_A1_t *restrict A ## _1, \
size_t xsize
// swap A [a] and A [b]
#define GB_swap(A,a,b) \
{ \
GB_A0_t t0 = A ## _0 [a] ; A ## _0 [a] = A ## _0 [b] ; A ## _0 [b] = t0 ; \
GB_A1_t t1 [GB_VLA(xsize)] ; \
memcpy (t1, A ## _1 + (a)*xsize, xsize) ; \
memcpy (A ## _1 + (a)*xsize, A ## _1 + (b)*xsize, xsize) ; \
memcpy (A ## _1 + (b)*xsize, t1, xsize) ; \
}
#include "sort/template/GB_qsort_template.c"
void GB_qsort_1b_32_generic // sort array A of size 2-by-n, using A0: 32
(
GB_A0_t *restrict A_0, // size n array
GB_A1_t *restrict A_1, // size n array
const size_t xsize, // size of entries in A_1
const int64_t n
)
{
uint64_t seed = n ;
GB_quicksort (GB_arg (A), n, &seed) ;
}
//------------------------------------------------------------------------------
// GB_qsort_1b_64_generic: generic method for any data type, A0 is 64bit
//------------------------------------------------------------------------------
#undef GB_A0_t
#undef GB_partition
#undef GB_quicksort
#define GB_A0_t uint64_t
#define GB_partition GB_partition_1b_64_generic
#define GB_quicksort GB_quicksort_1b_64_generic
#include "sort/template/GB_qsort_template.c"
void GB_qsort_1b_64_generic // sort array A of size 2-by-n, using A0: 64
(
GB_A0_t *restrict A_0, // size n array
GB_A1_t *restrict A_1, // size n array
const size_t xsize, // size of entries in A_1
const int64_t n
)
{
uint64_t seed = n ;
GB_quicksort (GB_arg (A), n, &seed) ;
}
//------------------------------------------------------------------------------
// GB_qsort_1b_32_size1: quicksort, A_1 of type that has sizeof 1, A0: 32bit
//------------------------------------------------------------------------------
#undef GB_A0_t
#undef GB_A1_t
#undef GB_partition
#undef GB_quicksort
#define GB_A0_t uint32_t
#define GB_A1_t uint8_t
#define GB_partition GB_partition_1b_32_size1
#define GB_quicksort GB_quicksort_1b_32_size1
// argument list for calling a function
#undef GB_arg
#define GB_arg(A) \
A ## _0, A ## _1
// argument list for calling a function, with offset
#undef GB_arg_offset
#define GB_arg_offset(A,x) \
A ## _0 + (x), A ## _1 + (x)
// argument list for defining a function
#undef GB_args
#define GB_args(A) \
GB_A0_t *restrict A ## _0, \
GB_A1_t *restrict A ## _1 \
// swap A [a] and A [b]
#undef GB_swap
#define GB_swap(A,a,b) \
{ \
GB_A0_t t0 = A ## _0 [a] ; A ## _0 [a] = A ## _0 [b] ; A ## _0 [b] = t0 ; \
GB_A1_t t1 = A ## _1 [a] ; A ## _1 [a] = A ## _1 [b] ; A ## _1 [b] = t1 ; \
}
#include "sort/template/GB_qsort_template.c"
void GB_qsort_1b_32_size1 // GB_qsort_1b, A_1 with sizeof = 1, A0: 32 bit
(
GB_A0_t *restrict A_0, // size n array
GB_A1_t *restrict A_1, // size n array
const int64_t n
)
{
uint64_t seed = n ;
GB_quicksort (GB_arg (A), n, &seed) ;
}
//------------------------------------------------------------------------------
// GB_qsort_1b_64_size1: quicksort, A_1 of type that has sizeof 1, A0: 64bit
//------------------------------------------------------------------------------
#undef GB_A0_t
#undef GB_partition
#undef GB_quicksort
#define GB_A0_t uint64_t
#define GB_partition GB_partition_1b_64_size1
#define GB_quicksort GB_quicksort_1b_64_size1
#include "sort/template/GB_qsort_template.c"
void GB_qsort_1b_64_size1 // GB_qsort_1b with A_1 with sizeof = 1, A0: 64
(
GB_A0_t *restrict A_0, // size n array
GB_A1_t *restrict A_1, // size n array
const int64_t n
)
{
uint64_t seed = n ;
GB_quicksort (GB_arg (A), n, &seed) ;
}
//------------------------------------------------------------------------------
// GB_qsort_1b_32_size2: quicksort: A_1 of type with sizeof 2, A0: 32 bit
//------------------------------------------------------------------------------
#undef GB_A0_t
#undef GB_A1_t
#undef GB_partition
#undef GB_quicksort
#define GB_A0_t uint32_t
#define GB_A1_t uint16_t
#define GB_partition GB_partition_1b_32_size2
#define GB_quicksort GB_quicksort_1b_32_size2
#include "sort/template/GB_qsort_template.c"
void GB_qsort_1b_32_size2 // GB_qsort_1b, A_1 with sizeof = 2, A0: 32 bit
(
GB_A0_t *restrict A_0, // size n array
GB_A1_t *restrict A_1, // size n array
const int64_t n
)
{
uint64_t seed = n ;
GB_quicksort (GB_arg (A), n, &seed) ;
}
//------------------------------------------------------------------------------
// GB_qsort_1b_64_size2: quicksort: A_1 of type with sizeof 2, A0: 64 bit
//------------------------------------------------------------------------------
#undef GB_A0_t
#undef GB_partition
#undef GB_quicksort
#define GB_A0_t uint64_t
#define GB_partition GB_partition_1b_64_size2
#define GB_quicksort GB_quicksort_1b_64_size2
#include "sort/template/GB_qsort_template.c"
void GB_qsort_1b_64_size2 // GB_qsort_1b, A_1 with sizeof = 2, A0: 64 bit
(
GB_A0_t *restrict A_0, // size n array
GB_A1_t *restrict A_1, // size n array
const int64_t n
)
{
uint64_t seed = n ;
GB_quicksort (GB_arg (A), n, &seed) ;
}
//------------------------------------------------------------------------------
// GB_qsort_1b_32_size4: quicksort, A_1 of type that has sizeof 4, A0: 32 bit
//------------------------------------------------------------------------------
#undef GB_A0_t
#undef GB_A1_t
#undef GB_partition
#undef GB_quicksort
#define GB_A0_t uint32_t
#define GB_A1_t uint32_t
#define GB_partition GB_partition_1b_32_size4
#define GB_quicksort GB_quicksort_1b_32_size4
#include "sort/template/GB_qsort_template.c"
void GB_qsort_1b_32_size4 // GB_qsort_1b A_1 with sizeof = 4, A0: 32 bit
(
GB_A0_t *restrict A_0, // size n array
GB_A1_t *restrict A_1, // size n array
const int64_t n
)
{
uint64_t seed = n ;
GB_quicksort (GB_arg (A), n, &seed) ;
}
//------------------------------------------------------------------------------
// GB_qsort_1b_64_size4: quicksort, A_1 of type that has sizeof 4, A0: 64 bit
//------------------------------------------------------------------------------
#undef GB_A0_t
#undef GB_partition
#undef GB_quicksort
#define GB_A0_t uint64_t
#define GB_partition GB_partition_1b_64_size4
#define GB_quicksort GB_quicksort_1b_64_size4
#include "sort/template/GB_qsort_template.c"
void GB_qsort_1b_64_size4 // GB_qsort_1b A_1 with sizeof = 4, A0: 64 bit
(
GB_A0_t *restrict A_0, // size n array
GB_A1_t *restrict A_1, // size n array
const int64_t n
)
{
uint64_t seed = n ;
GB_quicksort (GB_arg (A), n, &seed) ;
}
//------------------------------------------------------------------------------
// GB_qsort_1b_32_size8: quicksort, A_1 of type that has sizeof 8, A0: 32 bit
//------------------------------------------------------------------------------
#undef GB_A0_t
#undef GB_A1_t
#undef GB_partition
#undef GB_quicksort
#define GB_A0_t uint32_t
#define GB_A1_t uint64_t
#define GB_partition GB_partition_1b_32_size8
#define GB_quicksort GB_quicksort_1b_32_size8
#include "sort/template/GB_qsort_template.c"
void GB_qsort_1b_32_size8 // GB_qsort_1b, A_1 with sizeof = 8, A0: 32 bit
(
GB_A0_t *restrict A_0, // size n array
GB_A1_t *restrict A_1, // size n array
const int64_t n
)
{
uint64_t seed = n ;
GB_quicksort (GB_arg (A), n, &seed) ;
}
//------------------------------------------------------------------------------
// GB_qsort_1b_64_size8: quicksort, A_1 of type that has sizeof 8, A0: 64 bit
//------------------------------------------------------------------------------
#undef GB_A0_t
#undef GB_partition
#undef GB_quicksort
#define GB_A0_t uint64_t
#define GB_partition GB_partition_1b_64_size8
#define GB_quicksort GB_quicksort_1b_64_size8
#include "sort/template/GB_qsort_template.c"
void GB_qsort_1b_64_size8 // GB_qsort_1b, A_1 with sizeof = 8, A0: 64 bit
(
GB_A0_t *restrict A_0, // size n array
GB_A1_t *restrict A_1, // size n array
const int64_t n
)
{
uint64_t seed = n ;
GB_quicksort (GB_arg (A), n, &seed) ;
}
//------------------------------------------------------------------------------
// GB_qsort_1b_32_size16: quicksort, A_1 of type that has sizeof 16, A0: 32 bit
//------------------------------------------------------------------------------
#undef GB_A0_t
#undef GB_A1_t
#undef GB_partition
#undef GB_quicksort
#define GB_A0_t uint32_t
#define GB_A1_t GB_blob16
#define GB_partition GB_partition_1b_32_size16
#define GB_quicksort GB_quicksort_1b_32_size16
#include "sort/template/GB_qsort_template.c"
void GB_qsort_1b_32_size16 // GB_qsort_1b, A_1 with sizeof = 16, A0: 32 bit
(
GB_A0_t *restrict A_0, // size n array
GB_A1_t *restrict A_1, // size n array
const int64_t n
)
{
uint64_t seed = n ;
GB_quicksort (GB_arg (A), n, &seed) ;
}
//------------------------------------------------------------------------------
// GB_qsort_1b_64_size16: quicksort, A_1 of type that has sizeof 16, A0: 64 bit
//------------------------------------------------------------------------------
#undef GB_A0_t
#undef GB_partition
#undef GB_quicksort
#define GB_A0_t uint64_t
#define GB_partition GB_partition_1b_64_size16
#define GB_quicksort GB_quicksort_1b_64_size16
#include "sort/template/GB_qsort_template.c"
void GB_qsort_1b_64_size16 // GB_qsort_1b, A_1 with sizeof = 16, A0: 64 bit
(
GB_A0_t *restrict A_0, // size n array
GB_A1_t *restrict A_1, // size n array
const int64_t n
)
{
uint64_t seed = n ;
GB_quicksort (GB_arg (A), n, &seed) ;
}
|
