1 //------------------------------------------------------------------------------
2 // GB_unjumble: unjumble the vectors of a matrix
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
GB_unjumble(GrB_Matrix A,GB_Context Context)12 GrB_Info GB_unjumble // unjumble a matrix
13 (
14 GrB_Matrix A, // matrix to unjumble
15 GB_Context Context
16 )
17 {
18
19 //--------------------------------------------------------------------------
20 // check inputs
21 //--------------------------------------------------------------------------
22
23 ASSERT_MATRIX_OK (A, "A to unjumble", GB0) ;
24 ASSERT (!GB_ZOMBIES (A)) ; // zombies must be killed first
25 ASSERT (GB_PENDING_OK (A)) ; // pending tuples are not modified
26
27 if (!A->jumbled)
28 {
29 // nothing to do
30 return (GrB_SUCCESS) ;
31 }
32
33 // full and bitmap matrices are never jumbled
34 ASSERT (!GB_IS_FULL (A)) ;
35 ASSERT (!GB_IS_BITMAP (A)) ;
36 ASSERT (GB_IS_SPARSE (A) || GB_IS_HYPERSPARSE (A)) ;
37
38 //--------------------------------------------------------------------------
39 // get A
40 //--------------------------------------------------------------------------
41
42 const int64_t anvec = A->nvec ;
43 const int64_t anz = GB_NNZ (A) ;
44 const int64_t *restrict Ap = A->p ;
45 int64_t *restrict Ai = A->i ;
46 const size_t asize = A->type->size ;
47
48 GB_void *Ax = (GB_void *) A->x ;
49 uint8_t *Ax1 = (uint8_t *) A->x ;
50 uint16_t *Ax2 = (uint16_t *) A->x ;
51 uint32_t *Ax4 = (uint32_t *) A->x ;
52 uint64_t *Ax8 = (uint64_t *) A->x ;
53 GB_blob16 *Ax16 = (GB_blob16 *) A->x ;
54
55 //--------------------------------------------------------------------------
56 // determine the number of threads to use
57 //--------------------------------------------------------------------------
58
59 GB_GET_NTHREADS_MAX (nthreads_max, chunk, Context) ;
60 int nthreads = GB_nthreads (anz + anvec, chunk, nthreads_max) ;
61 int ntasks = (nthreads == 1) ? 1 : (32 * nthreads) ;
62 ntasks = GB_IMIN (ntasks, anvec) ;
63 ntasks = GB_IMAX (ntasks, 1) ;
64
65 //--------------------------------------------------------------------------
66 // slice the work
67 //--------------------------------------------------------------------------
68
69 GB_WERK_DECLARE (A_slice, int64_t) ;
70 GB_WERK_PUSH (A_slice, ntasks + 1, int64_t) ;
71 if (A_slice == NULL)
72 {
73 // out of memory
74 return (GrB_OUT_OF_MEMORY) ;
75 }
76 GB_pslice (A_slice, Ap, anvec, ntasks, false) ;
77
78 //--------------------------------------------------------------------------
79 // sort the vectors
80 //--------------------------------------------------------------------------
81
82 switch (asize)
83 {
84 case 1 :
85 // GrB_BOOL, GrB_UINT8, GrB_INT8, and user defined types of size 1
86 #define GB_QSORT \
87 GB_qsort_1b_size1 (Ai+pA_start, Ax1+pA_start, aknz) ;
88 #include "GB_unjumbled_template.c"
89 break ;
90
91 case 2 :
92 // GrB_UINT16, GrB_INT16, and user-defined types of size 2
93 #define GB_QSORT \
94 GB_qsort_1b_size2 (Ai+pA_start, Ax2+pA_start, aknz) ;
95 #include "GB_unjumbled_template.c"
96 break ;
97
98 case 4 :
99 // GrB_UINT32, GrB_INT32, GrB_FP32, and user-defined types of size 4
100 #define GB_QSORT \
101 GB_qsort_1b_size4 (Ai+pA_start, Ax4+pA_start, aknz) ;
102 #include "GB_unjumbled_template.c"
103 break ;
104
105 case 8 :
106 // GrB_UINT64, GrB_INT64, GrB_FP64, GxB_FC32, and user-defined
107 // types of size 8
108 #define GB_QSORT \
109 GB_qsort_1b_size8 (Ai+pA_start, Ax8+pA_start, aknz) ;
110 #include "GB_unjumbled_template.c"
111 break ;
112
113 case 16 :
114 // GxB_FC64, and user-defined types of size 16
115 #define GB_QSORT \
116 GB_qsort_1b_size16 (Ai+pA_start, Ax16+pA_start, aknz) ;
117 #include "GB_unjumbled_template.c"
118 break ;
119
120 default :
121 // user-defined types of arbitrary size
122 #define GB_QSORT \
123 GB_qsort_1b (Ai+pA_start, Ax+pA_start*asize, asize, aknz) ;
124 #include "GB_unjumbled_template.c"
125 break ;
126 }
127
128 //--------------------------------------------------------------------------
129 // free workspace and return result
130 //--------------------------------------------------------------------------
131
132 GB_WERK_POP (A_slice, int64_t) ;
133 A->jumbled = false ; // A has been unjumbled
134 ASSERT_MATRIX_OK (A, "A unjumbled", GB0) ;
135 return (GrB_SUCCESS) ;
136 }
137
138