1 //------------------------------------------------------------------------------
2 // GB_convert_sparse_to_bitmap: convert from sparse/hypersparse to bitmap
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_ek_slice.h"
11 #ifndef GBCOMPACT
12 #include "GB_type__include.h"
13 #endif
14
15 #define GB_FREE_WORK \
16 { \
17 GB_WERK_POP (A_ek_slicing, int64_t) ; \
18 }
19
20 #define GB_FREE_ALL \
21 { \
22 GB_FREE_WORK ; \
23 if (!in_place) GB_FREE (&Ax_new, Ax_new_size) ; \
24 GB_FREE (&Ab, Ab_size) ; \
25 }
26
GB_convert_sparse_to_bitmap(GrB_Matrix A,GB_Context Context)27 GrB_Info GB_convert_sparse_to_bitmap // convert sparse/hypersparse to bitmap
28 (
29 GrB_Matrix A, // matrix to convert from sparse to bitmap
30 GB_Context Context
31 )
32 {
33
34 //--------------------------------------------------------------------------
35 // check inputs
36 //--------------------------------------------------------------------------
37
38 GrB_Info info ;
39 GB_WERK_DECLARE (A_ek_slicing, int64_t) ;
40 int8_t *restrict Ab = NULL ; size_t Ab_size = 0 ;
41 GB_void *restrict Ax_new = NULL ; size_t Ax_new_size = 0 ;
42
43 ASSERT_MATRIX_OK (A, "A converting sparse/hypersparse to bitmap", GB0) ;
44 ASSERT (!GB_IS_FULL (A)) ;
45 ASSERT (!GB_IS_BITMAP (A)) ;
46 ASSERT (GB_IS_SPARSE (A) || GB_IS_HYPERSPARSE (A)) ;
47 ASSERT (!GB_PENDING (A)) ;
48 ASSERT (GB_JUMBLED_OK (A)) ; // A can be jumbled on input
49 ASSERT (GB_ZOMBIES_OK (A)) ; // A can have zombies on input
50 GBURBLE ("(sparse to bitmap) ") ;
51
52 //--------------------------------------------------------------------------
53 // determine the maximum number of threads to use
54 //--------------------------------------------------------------------------
55
56 GB_GET_NTHREADS_MAX (nthreads_max, chunk, Context) ;
57
58 //--------------------------------------------------------------------------
59 // determine if the conversion can be done in-place
60 //--------------------------------------------------------------------------
61
62 // if in_place is true, then A->x does not change if A is as-if-full
63 bool in_place = GB_as_if_full (A) ;
64
65 //--------------------------------------------------------------------------
66 // allocate A->b
67 //--------------------------------------------------------------------------
68
69 const int64_t anz = GB_NNZ (A) ;
70 const int64_t avdim = A->vdim ;
71 const int64_t avlen = A->vlen ;
72 const int64_t anvec = A->nvec ;
73 int64_t anzmax ;
74 if (!GB_Index_multiply ((GrB_Index *) &anzmax, avdim, avlen))
75 {
76 // problem too large
77 return (GrB_OUT_OF_MEMORY) ;
78 }
79 anzmax = GB_IMAX (anzmax, 1) ;
80
81 if (in_place || anz > 0)
82 {
83 // if any entries exist, use malloc since all of Ab will be set below.
84 Ab = GB_MALLOC (anzmax, int8_t, &Ab_size) ;
85 }
86 else
87 {
88 // calloc Ab so all bitmap entries are zero; no need to touch them.
89 // This case occurs when setting the GxB_SPARSITY_CONTROL of a new
90 // matrix to GxB_BITMAP, with no entries.
91 Ab = GB_CALLOC (anzmax, int8_t, &Ab_size) ;
92 }
93
94 if (Ab == NULL)
95 {
96 // out of memory
97 return (GrB_OUT_OF_MEMORY) ;
98 }
99
100 //--------------------------------------------------------------------------
101 // allocate the new A->x
102 //--------------------------------------------------------------------------
103
104 const size_t asize = A->type->size ;
105 bool Ax_shallow ;
106
107 if (in_place)
108 {
109 // keep the existing A->x
110 Ax_new = (GB_void *) A->x ;
111 Ax_shallow = A->x_shallow ;
112 Ax_new_size = A->x_size ;
113 }
114 else
115 {
116 // A->x must be modified to fit the bitmap structure
117 Ax_new = GB_MALLOC (anzmax * asize, GB_void, &Ax_new_size) ;
118 Ax_shallow = false ;
119 if (Ax_new == NULL)
120 {
121 // out of memory
122 GB_FREE_ALL ;
123 return (GrB_OUT_OF_MEMORY) ;
124 }
125 }
126
127 //--------------------------------------------------------------------------
128 // scatter the pattern and values into the new bitmap
129 //--------------------------------------------------------------------------
130
131 int64_t nzombies = A->nzombies ;
132 if (in_place)
133 {
134
135 //----------------------------------------------------------------------
136 // the sparse A has all entries: convert in-place
137 //----------------------------------------------------------------------
138
139 ASSERT (nzombies == 0) ;
140 // set all of Ab [0..anz-1] to 1, in parallel
141 GB_memset (Ab, 1, anz, nthreads_max) ;
142
143 }
144 else if (anz > 0)
145 {
146
147 //----------------------------------------------------------------------
148 // set all of Ab to zero
149 //----------------------------------------------------------------------
150
151 GB_memset (Ab, 0, anzmax, nthreads_max) ;
152
153 //----------------------------------------------------------------------
154 // scatter the values and pattern of A into the bitmap
155 //----------------------------------------------------------------------
156
157 int A_nthreads, A_ntasks ;
158 GB_SLICE_MATRIX (A, 8, chunk) ;
159 bool done = false ;
160
161 #ifndef GBCOMPACT
162
163 //------------------------------------------------------------------
164 // define the worker for the switch factory
165 //------------------------------------------------------------------
166
167 #define GB_convert_s2b_(cname) GB (_convert_s2b_ ## cname)
168 #define GB_WORKER(cname) \
169 { \
170 info = GB_convert_s2b_(cname) (A, Ax_new, Ab, \
171 A_ek_slicing, A_ntasks, A_nthreads) ; \
172 done = (info != GrB_NO_VALUE) ; \
173 } \
174 break ;
175
176 //------------------------------------------------------------------
177 // launch the switch factory
178 //------------------------------------------------------------------
179
180 GB_Type_code acode = A->type->code ;
181 if (acode < GB_UDT_code)
182 {
183 switch (acode)
184 {
185 case GB_BOOL_code : GB_WORKER (_bool )
186 case GB_INT8_code : GB_WORKER (_int8 )
187 case GB_INT16_code : GB_WORKER (_int16 )
188 case GB_INT32_code : GB_WORKER (_int32 )
189 case GB_INT64_code : GB_WORKER (_int64 )
190 case GB_UINT8_code : GB_WORKER (_uint8 )
191 case GB_UINT16_code : GB_WORKER (_uint16)
192 case GB_UINT32_code : GB_WORKER (_uint32)
193 case GB_UINT64_code : GB_WORKER (_uint64)
194 case GB_FP32_code : GB_WORKER (_fp32 )
195 case GB_FP64_code : GB_WORKER (_fp64 )
196 case GB_FC32_code : GB_WORKER (_fc32 )
197 case GB_FC64_code : GB_WORKER (_fc64 )
198 default: ;
199 }
200 }
201
202 #endif
203
204 if (!done)
205 {
206 // Ax_new [pnew] = Ax [p]
207 #define GB_COPY_A_TO_C(Ax_new,pnew,Ax,p) \
208 memcpy (Ax_new +(pnew)*asize, Ax +(p)*asize, asize)
209 #define GB_ATYPE GB_void
210 #include "GB_convert_sparse_to_bitmap_template.c"
211 }
212 }
213
214 //--------------------------------------------------------------------------
215 // free prior content of A and transplant the new content
216 //--------------------------------------------------------------------------
217
218 if (in_place)
219 {
220 // if done in-place, remove A->x from A so it is not freed
221 A->x = NULL ;
222 A->x_shallow = false ;
223 }
224
225 GB_phbix_free (A) ;
226
227 A->b = Ab ; A->b_size = Ab_size ;
228 A->b_shallow = false ;
229 Ab = NULL ;
230
231 A->x = Ax_new ; A->x_size = Ax_new_size ;
232 A->x_shallow = Ax_shallow ;
233 Ax_new = NULL ;
234
235 A->nzmax = anzmax ;
236 A->nvals = anz - nzombies ;
237 ASSERT (A->nzombies == 0) ;
238
239 A->plen = -1 ;
240 A->nvec = avdim ;
241 A->nvec_nonempty = (avlen == 0) ? 0 : avdim ;
242
243 A->magic = GB_MAGIC ;
244
245 //--------------------------------------------------------------------------
246 // free workspace and return result
247 //--------------------------------------------------------------------------
248
249 GB_FREE_WORK ;
250 ASSERT_MATRIX_OK (A, "A converted from sparse to bitmap", GB0) ;
251 ASSERT (GB_IS_BITMAP (A)) ;
252 ASSERT (!GB_ZOMBIES (A)) ;
253 ASSERT (!GB_JUMBLED (A)) ;
254 ASSERT (!GB_PENDING (A)) ;
255 return (GrB_SUCCESS) ;
256 }
257
258