1 //------------------------------------------------------------------------------
2 // GB_qsort_1b: sort a 2-by-n list, using A [0][ ] as the sort key
3 //------------------------------------------------------------------------------
4
5 // SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved.
6 // SPDX-License-Identifier: Apache-2.0
7
8 //------------------------------------------------------------------------------
9
10 #include "GB_sort.h"
11
12 // returns true if A [a] < B [b]
13 #define GB_lt(A,a,B,b) GB_lt_1 (A ## _0, a, B ## _0, b)
14
15 // each entry has a single key
16 #define GB_K 1
17
18 //------------------------------------------------------------------------------
19 // GB_qsort_1b: generic method for any data type
20 //------------------------------------------------------------------------------
21
22 // argument list for calling a function
23 #define GB_arg(A) \
24 A ## _0, A ## _1, xsize
25
26 // argument list for calling a function, with offset
27 #define GB_arg_offset(A,x) \
28 A ## _0 + (x), A ## _1 + (x)*xsize, xsize
29
30 // argument list for defining a function
31 #define GB_args(A) \
32 int64_t *restrict A ## _0, \
33 GB_void *restrict A ## _1, \
34 size_t xsize
35
36 // swap A [a] and A [b]
37 #define GB_swap(A,a,b) \
38 { \
39 int64_t t0 = A ## _0 [a] ; A ## _0 [a] = A ## _0 [b] ; A ## _0 [b] = t0 ; \
40 GB_void t1 [GB_VLA(xsize)] ; \
41 memcpy (t1, A ## _1 + (a)*xsize, xsize) ; \
42 memcpy (A ## _1 + (a)*xsize, A ## _1 + (b)*xsize, xsize) ; \
43 memcpy (A ## _1 + (b)*xsize, t1, xsize) ; \
44 }
45
46 #define GB_partition GB_partition_1b
47 #define GB_quicksort GB_quicksort_1b
48
49 #include "GB_qsort_template.c"
50
51 GB_PUBLIC // accessed by the MATLAB tests in GraphBLAS/Test only
GB_qsort_1b(int64_t * restrict A_0,GB_void * restrict A_1,const size_t xsize,const int64_t n)52 void GB_qsort_1b // sort array A of size 2-by-n, using 1 key (A [0][])
53 (
54 int64_t *restrict A_0, // size n array
55 GB_void *restrict A_1, // size n array
56 const size_t xsize, // size of entries in A_1
57 const int64_t n
58 )
59 {
60 uint64_t seed = n ;
61 GB_quicksort (GB_arg (A), n, &seed) ;
62 }
63
64 //------------------------------------------------------------------------------
65 // GB_qsort_1b_size1: quicksort with A_1 of type that has sizeof 1
66 //------------------------------------------------------------------------------
67
68 // for GrB_BOOL, GrB_INT8, GrB_UINT8, and user-defined types with sizeof(...)=1
69
70 #define A1_type uint8_t
71
72 // argument list for calling a function
73 #undef GB_arg
74 #define GB_arg(A) \
75 A ## _0, A ## _1
76
77 // argument list for calling a function, with offset
78 #undef GB_arg_offset
79 #define GB_arg_offset(A,x) \
80 A ## _0 + (x), A ## _1 + (x)
81
82 // argument list for defining a function
83 #undef GB_args
84 #define GB_args(A) \
85 int64_t *restrict A ## _0, \
86 A1_type *restrict A ## _1 \
87
88 // swap A [a] and A [b]
89 #undef GB_swap
90 #define GB_swap(A,a,b) \
91 { \
92 int64_t t0 = A ## _0 [a] ; A ## _0 [a] = A ## _0 [b] ; A ## _0 [b] = t0 ; \
93 A1_type t1 = A ## _1 [a] ; A ## _1 [a] = A ## _1 [b] ; A ## _1 [b] = t1 ; \
94 }
95
96 #undef GB_partition
97 #define GB_partition GB_partition_1b_size1
98 #undef GB_quicksort
99 #define GB_quicksort GB_quicksort_1b_size1
100
101 #include "GB_qsort_template.c"
102
GB_qsort_1b_size1(int64_t * restrict A_0,uint8_t * restrict A_1,const int64_t n)103 void GB_qsort_1b_size1 // GB_qsort_1b with A_1 with sizeof = 1
104 (
105 int64_t *restrict A_0, // size n array
106 uint8_t *restrict A_1, // size n array
107 const int64_t n
108 )
109 {
110 uint64_t seed = n ;
111 GB_quicksort (GB_arg (A), n, &seed) ;
112 }
113
114 //------------------------------------------------------------------------------
115 // GB_qsort_1b_size2: quicksort with A_1 of type that has sizeof 2
116 //------------------------------------------------------------------------------
117
118 // for GrB_INT16, GrB_UINT16, and user-defined types of sizeof(...) = 2
119
120 #undef A1_type
121 #define A1_type uint16_t
122 #undef GB_partition
123 #define GB_partition GB_partition_1b_size2
124 #undef GB_quicksort
125 #define GB_quicksort GB_quicksort_1b_size2
126
127 #include "GB_qsort_template.c"
128
GB_qsort_1b_size2(int64_t * restrict A_0,uint16_t * restrict A_1,const int64_t n)129 void GB_qsort_1b_size2 // GB_qsort_1b with A_1 with sizeof = 2
130 (
131 int64_t *restrict A_0, // size n array
132 uint16_t *restrict A_1, // size n array
133 const int64_t n
134 )
135 {
136 uint64_t seed = n ;
137 GB_quicksort (GB_arg (A), n, &seed) ;
138 }
139
140 //------------------------------------------------------------------------------
141 // GB_qsort_1b_size4: quicksort with A_1 of type that has sizeof 4
142 //------------------------------------------------------------------------------
143
144 // for GrB_INT32, GrB_UINT32, GrB_FP32, and user-defined types with
145 // sizeof(...) = 4.
146
147 #undef A1_type
148 #define A1_type uint32_t
149 #undef GB_partition
150 #define GB_partition GB_partition_1b_size4
151 #undef GB_quicksort
152 #define GB_quicksort GB_quicksort_1b_size4
153
154 #include "GB_qsort_template.c"
155
GB_qsort_1b_size4(int64_t * restrict A_0,uint32_t * restrict A_1,const int64_t n)156 void GB_qsort_1b_size4 // GB_qsort_1b with A_1 with sizeof = 4
157 (
158 int64_t *restrict A_0, // size n array
159 uint32_t *restrict A_1, // size n array
160 const int64_t n
161 )
162 {
163 uint64_t seed = n ;
164 GB_quicksort (GB_arg (A), n, &seed) ;
165 }
166
167 //------------------------------------------------------------------------------
168 // GB_qsort_1b_size8: quicksort with A_1 of type that has sizeof 8
169 //------------------------------------------------------------------------------
170
171 // for GrB_INT64, GrB_UINT64, GrB_FP64, GxB_FC32, and user-defined types
172 // with sizeof(...) = 8.
173
174 #undef A1_type
175 #define A1_type uint64_t
176 #undef GB_partition
177 #define GB_partition GB_partition_1b_size8
178 #undef GB_quicksort
179 #define GB_quicksort GB_quicksort_1b_size8
180
181 #include "GB_qsort_template.c"
182
GB_qsort_1b_size8(int64_t * restrict A_0,uint64_t * restrict A_1,const int64_t n)183 void GB_qsort_1b_size8 // GB_qsort_1b with A_1 with sizeof = 8
184 (
185 int64_t *restrict A_0, // size n array
186 uint64_t *restrict A_1, // size n array
187 const int64_t n
188 )
189 {
190 uint64_t seed = n ;
191 GB_quicksort (GB_arg (A), n, &seed) ;
192 }
193
194 //------------------------------------------------------------------------------
195 // GB_qsort_1b_size16: quicksort with A_1 of type that has sizeof 16
196 //------------------------------------------------------------------------------
197
198 // for GxB_FC64 and user-defined types with sizeof(...) = 16.
199
200 #undef A1_type
201 #define A1_type GB_blob16
202 #undef GB_partition
203 #define GB_partition GB_partition_1b_size16
204 #undef GB_quicksort
205 #define GB_quicksort GB_quicksort_1b_size16
206
207 #include "GB_qsort_template.c"
208
GB_qsort_1b_size16(int64_t * restrict A_0,GB_blob16 * restrict A_1,const int64_t n)209 void GB_qsort_1b_size16 // GB_qsort_1b with A_1 with sizeof = 16
210 (
211 int64_t *restrict A_0, // size n array
212 GB_blob16 *restrict A_1, // size n array
213 const int64_t n
214 )
215 {
216 ASSERT (sizeof (GB_blob16) == 16) ;
217 uint64_t seed = n ;
218 GB_quicksort (GB_arg (A), n, &seed) ;
219 }
220
221