1 //------------------------------------------------------------------------------
2 // GB_sort.h: definitions for sorting functions
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 // All of the GB_qsort_* functions are single-threaded, by design. Both
11 // GB_msort_* functions are parallel. None of these sorting methods are
12 // guaranteed to be stable, but they are always used in GraphBLAS with unique
13 // keys.
14
15 #ifndef GB_SORT_H
16 #define GB_SORT_H
17 #include "GB.h"
18
19 #define GB_BASECASE (64 * 1024)
20
21 GB_PUBLIC // accessed by the MATLAB tests in GraphBLAS/Test only
22 void GB_qsort_1b // sort array A of size 2-by-n, using 1 key (A [0][])
23 (
24 int64_t *restrict A_0, // size n array
25 GB_void *restrict A_1, // size n array
26 const size_t xsize, // size of entries in A_1
27 const int64_t n
28 ) ;
29
30 void GB_qsort_1b_size1 // GB_qsort_1b with A1 with sizeof = 1
31 (
32 int64_t *restrict A_0, // size n array
33 uint8_t *restrict A_1, // size n array
34 const int64_t n
35 ) ;
36
37 void GB_qsort_1b_size2 // GB_qsort_1b with A1 with sizeof = 2
38 (
39 int64_t *restrict A_0, // size n array
40 uint16_t *restrict A_1, // size n array
41 const int64_t n
42 ) ;
43
44 void GB_qsort_1b_size4 // GB_qsort_1b with A1 with sizeof = 4
45 (
46 int64_t *restrict A_0, // size n array
47 uint32_t *restrict A_1, // size n array
48 const int64_t n
49 ) ;
50
51 void GB_qsort_1b_size8 // GB_qsort_1b with A_1 with sizeof = 8
52 (
53 int64_t *restrict A_0, // size n array
54 uint64_t *restrict A_1, // size n array
55 const int64_t n
56 ) ;
57
58 typedef struct
59 {
60 uint8_t stuff [16] ; // not accessed directly
61 }
62 GB_blob16 ; // sizeof (GB_blob16) is 16.
63
64 void GB_qsort_1b_size16 // GB_qsort_1b with A_1 with sizeof = 16
65 (
66 int64_t *restrict A_0, // size n array
67 GB_blob16 *restrict A_1, // size n array
68 const int64_t n
69 ) ;
70
71 GB_PUBLIC // accessed by the MATLAB tests in GraphBLAS/Test only
72 void GB_qsort_1a // sort array A of size 1-by-n
73 (
74 int64_t *restrict A_0, // size n array
75 const int64_t n
76 ) ;
77
78 GB_PUBLIC // accessed by the MATLAB tests in GraphBLAS/Test only
79 void GB_qsort_2 // sort array A of size 2-by-n, using 2 keys (A [0:1][])
80 (
81 int64_t *restrict A_0, // size n array
82 int64_t *restrict A_1, // size n array
83 const int64_t n
84 ) ;
85
86 GB_PUBLIC // accessed by the MATLAB tests in GraphBLAS/Test only
87 void GB_qsort_3 // sort array A of size 3-by-n, using 3 keys (A [0:2][])
88 (
89 int64_t *restrict A_0, // size n array
90 int64_t *restrict A_1, // size n array
91 int64_t *restrict A_2, // size n array
92 const int64_t n
93 ) ;
94
95 GB_PUBLIC // accessed by the MATLAB tests in GraphBLAS/Test only
96 GrB_Info GB_msort_2b // sort array A of size 2-by-n, using 2 keys (A [0:1][])
97 (
98 int64_t *restrict A_0, // size n array
99 int64_t *restrict A_1, // size n array
100 const int64_t n,
101 int nthreads // # of threads to use
102 ) ;
103
104 GB_PUBLIC // accessed by the MATLAB tests in GraphBLAS/Test only
105 GrB_Info GB_msort_3b // sort array A of size 3-by-n, using 3 keys (A [0:2][])
106 (
107 int64_t *restrict A_0, // size n array
108 int64_t *restrict A_1, // size n array
109 int64_t *restrict A_2, // size n array
110 const int64_t n,
111 int nthreads // # of threads to use
112 ) ;
113
114 //------------------------------------------------------------------------------
115 // GB_lt_1: sorting comparator function, one key
116 //------------------------------------------------------------------------------
117
118 // A [a] and B [b] are keys of one integer.
119
120 // GB_lt_1 returns true if A [a] < B [b], for GB_qsort_1b
121
122 #define GB_lt_1(A_0, a, B_0, b) (A_0 [a] < B_0 [b])
123
124 //------------------------------------------------------------------------------
125 // GB_lt_2: sorting comparator function, two keys
126 //------------------------------------------------------------------------------
127
128 // A [a] and B [b] are keys of two integers.
129
130 // GB_lt_2 returns true if A [a] < B [b], for GB_qsort_2 and GB_msort_2b
131
132 #define GB_lt_2(A_0, A_1, a, B_0, B_1, b) \
133 ( \
134 (A_0 [a] < B_0 [b]) ? \
135 ( \
136 true \
137 ) \
138 : \
139 ( \
140 (A_0 [a] == B_0 [b]) ? \
141 ( \
142 /* primary key is the same; tie-break on the 2nd key */ \
143 (A_1 [a] < B_1 [b]) \
144 ) \
145 : \
146 ( \
147 false \
148 ) \
149 ) \
150 )
151
152 //------------------------------------------------------------------------------
153 // GB_lt_3: sorting comparator function, three keys
154 //------------------------------------------------------------------------------
155
156 // A [a] and B [b] are keys of three integers.
157
158 // GB_lt_3 returns true if A [a] < B [b], for GB_qsort_3 and GB_msort_3b
159
160 #define GB_lt_3(A_0, A_1, A_2, a, B_0, B_1, B_2, b) \
161 ( \
162 (A_0 [a] < B_0 [b]) ? \
163 ( \
164 true \
165 ) \
166 : \
167 ( \
168 (A_0 [a] == B_0 [b]) ? \
169 ( \
170 /* primary key is the same; tie-break on the 2nd and 3rd key */ \
171 GB_lt_2 (A_1, A_2, a, B_1, B_2, b) \
172 ) \
173 : \
174 ( \
175 false \
176 ) \
177 ) \
178 )
179
180 //------------------------------------------------------------------------------
181 // GB_eq_*: sorting comparator function, three keys
182 //------------------------------------------------------------------------------
183
184 // A [a] and B [b] are keys of two or three integers.
185 // GB_eq_* returns true if A [a] == B [b]
186
187 #define GB_eq_3(A_0, A_1, A_2, a, B_0, B_1, B_2, b) \
188 ( \
189 (A_0 [a] == B_0 [b]) && \
190 (A_1 [a] == B_1 [b]) && \
191 (A_2 [a] == B_2 [b]) \
192 )
193
194 #define GB_eq_2(A_0, A_1, a, B_0, B_1, b) \
195 ( \
196 (A_0 [a] == B_0 [b]) && \
197 (A_1 [a] == B_1 [b]) \
198 )
199
200 //------------------------------------------------------------------------------
201 // random number generator for quicksort
202 //------------------------------------------------------------------------------
203
204 // return a random GrB_Index, in range 0 to 2^60
205 #define GB_RAND_MAX 32767
206
207 // return a random number between 0 and GB_RAND_MAX
GB_rand15(uint64_t * seed)208 static inline GrB_Index GB_rand15 (uint64_t *seed)
209 {
210 (*seed) = (*seed) * 1103515245 + 12345 ;
211 return (((*seed) / 65536) % (GB_RAND_MAX + 1)) ;
212 }
213
214 // return a random GrB_Index, in range 0 to 2^60
GB_rand(uint64_t * seed)215 static inline GrB_Index GB_rand (uint64_t *seed)
216 {
217 GrB_Index i = GB_rand15 (seed) ;
218 i = GB_RAND_MAX * i + GB_rand15 (seed) ;
219 i = GB_RAND_MAX * i + GB_rand15 (seed) ;
220 i = GB_RAND_MAX * i + GB_rand15 (seed) ;
221 return (i) ;
222 }
223
224 #endif
225
226