1 //------------------------------------------------------------------------------
2 // GB_transplant: replace contents of one matrix with another
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 // Transplant A into C, and then free A. If any part of A is shallow, or if A
11 // must be typecasted, a deep copy is made into C. Prior content of C is
12 // ignored. Then A is freed, except for any shallow components of A which are
13 // left untouched (after unlinking them from A). The resulting matrix C is not
14 // shallow. This function is not user-callable. The new type of C (ctype)
15 // must be compatible with A->type.
16
17 // C->hyper_switch, C->bitmap_switch, C->sparsity, and C->static_header are
18 // not modified by the transplant.
19
20 #include "GB.h"
21
GB_transplant(GrB_Matrix C,const GrB_Type ctype,GrB_Matrix * Ahandle,GB_Context Context)22 GrB_Info GB_transplant // transplant one matrix into another
23 (
24 GrB_Matrix C, // output matrix to overwrite with A
25 const GrB_Type ctype, // new type of C
26 GrB_Matrix *Ahandle, // input matrix to copy from and free
27 GB_Context Context
28 )
29 {
30
31 //--------------------------------------------------------------------------
32 // check inputs
33 //--------------------------------------------------------------------------
34
35 ASSERT (Ahandle != NULL) ;
36 GrB_Matrix A = *Ahandle ;
37 ASSERT (!GB_aliased (C, A)) ;
38
39 ASSERT_MATRIX_OK (A, "A before transplant", GB0) ;
40 ASSERT (GB_ZOMBIES_OK (A)) ; // zombies in A transplanted into C
41 ASSERT (GB_JUMBLED_OK (A)) ; // if A is jumbled, then C is jumbled
42 ASSERT (GB_PENDING_OK (A)) ; // pending tuples n A transplanted into C
43
44 // C is about to be cleared, any pending work is OK
45 ASSERT (C != NULL) ;
46 ASSERT_TYPE_OK (ctype, "new type for C", GB0) ;
47 ASSERT (GB_PENDING_OK (C)) ;
48 ASSERT (GB_ZOMBIES_OK (C)) ;
49 ASSERT (GB_JUMBLED_OK (C)) ;
50
51 // the ctype and A->type must be compatible. C->type is ignored
52 ASSERT (GB_Type_compatible (ctype, A->type)) ;
53
54 int64_t avdim = A->vdim ;
55 int64_t avlen = A->vlen ;
56
57 //--------------------------------------------------------------------------
58 // determine the number of threads to use
59 //--------------------------------------------------------------------------
60
61 int64_t anz = GB_NNZ_HELD (A) ;
62 int64_t anvec = A->nvec ;
63
64 GB_GET_NTHREADS_MAX (nthreads_max, chunk, Context) ;
65 int nthreads = GB_nthreads (anz + anvec, chunk, nthreads_max) ;
66
67 //--------------------------------------------------------------------------
68 // clear C and transplant the type, size, format, and pending tuples
69 //--------------------------------------------------------------------------
70
71 // free all content of C
72 GB_phbix_free (C) ;
73
74 ASSERT (!GB_PENDING (C)) ;
75 ASSERT (!GB_ZOMBIES (C)) ;
76 ASSERT (!GB_JUMBLED (C)) ;
77 ASSERT (C->nzmax == 0) ;
78
79 // It is now safe to change the type and dimension of C
80 C->type = ctype ;
81 C->is_csc = A->is_csc ;
82 C->vlen = avlen ;
83 C->vdim = avdim ;
84 C->nvec_nonempty = A->nvec_nonempty ;
85
86 // C is not shallow, and has no content yet
87 ASSERT (!GB_is_shallow (C)) ;
88 ASSERT (C->p == NULL) ;
89 ASSERT (C->h == NULL) ;
90 ASSERT (C->b == NULL) ;
91 ASSERT (C->i == NULL) ;
92 ASSERT (C->x == NULL) ;
93 ASSERT (C->Pending == NULL) ;
94
95 // determine if C should be constructed as a bitmap or full matrix
96 bool C_is_bitmap = GB_IS_BITMAP (A) ;
97 bool C_is_full = GB_as_if_full (A) && !C_is_bitmap ;
98
99 //--------------------------------------------------------------------------
100 // transplant pending tuples from A to C
101 //--------------------------------------------------------------------------
102
103 C->Pending = A->Pending ;
104 A->Pending = NULL ;
105
106 //--------------------------------------------------------------------------
107 // transplant A->p vector pointers and A->h hyperlist
108 //--------------------------------------------------------------------------
109
110 if (C_is_full || C_is_bitmap)
111 {
112
113 //----------------------------------------------------------------------
114 // C is full or bitmap: C->p and C->h do not exist
115 //----------------------------------------------------------------------
116
117 C->plen = -1 ;
118 C->nvec = avdim ;
119
120 // free any non-shallow A->p and A->h content of A
121 GB_ph_free (A) ;
122
123 }
124 else if (A->p_shallow || A->h_shallow)
125 {
126
127 //----------------------------------------------------------------------
128 // A->p or A->h are shallow copies another matrix; make a deep copy
129 //----------------------------------------------------------------------
130
131 int nth = GB_nthreads (anvec, chunk, nthreads_max) ;
132
133 if (A->h != NULL)
134 {
135 // A is hypersparse, create new C->p and C->h
136 C->plen = anvec ;
137 C->nvec = anvec ;
138 C->p = GB_MALLOC (C->plen+1, int64_t, &(C->p_size)) ;
139 C->h = GB_MALLOC (C->plen , int64_t, &(C->h_size)) ;
140 if (C->p == NULL || C->h == NULL)
141 {
142 // out of memory
143 GB_phbix_free (C) ;
144 GB_Matrix_free (Ahandle) ;
145 return (GrB_OUT_OF_MEMORY) ;
146 }
147
148 // copy A->p and A->h into the newly created C->p and C->h
149 GB_memcpy (C->p, A->p, (anvec+1) * sizeof (int64_t), nth) ;
150 GB_memcpy (C->h, A->h, anvec * sizeof (int64_t), nth) ;
151 }
152 else
153 {
154 // A is sparse, create new C->p
155 C->plen = avdim ;
156 C->nvec = avdim ;
157 C->p = GB_MALLOC (C->plen+1, int64_t, &(C->p_size)) ;
158 if (C->p == NULL)
159 {
160 // out of memory
161 GB_phbix_free (C) ;
162 GB_Matrix_free (Ahandle) ;
163 return (GrB_OUT_OF_MEMORY) ;
164 }
165
166 // copy A->p into the newly created C->p
167 GB_memcpy (C->p, A->p, (avdim+1) * sizeof (int64_t), nth) ;
168 }
169
170 // free any non-shallow A->p and A->h content of A
171 GB_ph_free (A) ;
172
173 }
174 else
175 {
176
177 //----------------------------------------------------------------------
178 // both A->p and A->h are not shallow: quick transplant into C
179 //----------------------------------------------------------------------
180
181 // Quick transplant of A->p and A->h into C. This works for both
182 // sparse and hypersparse cases.
183 ASSERT (C->p == NULL) ;
184 ASSERT (C->h == NULL) ;
185 C->p = A->p ; C->p_size = A->p_size ;
186 C->h = A->h ; C->h_size = A->h_size ;
187 C->plen = A->plen ;
188 C->nvec = anvec ;
189 }
190
191 // A->p and A->h have been freed or removed from A
192 A->p = NULL ;
193 A->h = NULL ;
194 A->p_shallow = false ;
195 A->h_shallow = false ;
196 C->p_shallow = false ;
197 C->h_shallow = false ;
198
199 C->magic = GB_MAGIC ; // C is now initialized
200
201 if (anz == 0)
202 {
203 // quick return if A has no entries
204 ASSERT_MATRIX_OK (C, "C empty transplant", GB0) ;
205 GB_Matrix_free (Ahandle) ;
206 return (GrB_SUCCESS) ;
207 }
208
209 //--------------------------------------------------------------------------
210 // allocate new space for C->b, C->i, and C->x if A is shallow
211 //--------------------------------------------------------------------------
212
213 // get C->nzmax: if C->b, C->i, or C->x must be allocated, then C->nzmax
214 // is set to their minimum size. Otherwise, if C->b, C->i, and C->x can
215 // be transplanted from A, then they inherit the nzmax of A.
216
217 // C->b is allocated only if A->b exists and is shallow.
218 // C->i is not allocated if C is full or bitmap.
219 // C->x is allocated if A->x is shallow, or if the type is changing
220
221 ASSERT (C->b == NULL && C->i == NULL && C->x == NULL) ;
222 bool allocate_Cb = (A->b_shallow) && (C_is_bitmap) ;
223 bool allocate_Ci = (A->i_shallow) && (!(C_is_full || C_is_bitmap)) ;
224 bool allocate_Cx = (A->x_shallow || C->type != A->type) ;
225 C->nzmax = (allocate_Cb || allocate_Ci || allocate_Cx) ? anz : A->nzmax ;
226 C->nzmax = GB_IMAX (C->nzmax, 1) ;
227
228 // allocate new components if needed
229 bool ok = true ;
230
231 if (allocate_Cb)
232 {
233 // allocate new C->b component
234 C->b = GB_MALLOC (C->nzmax, int8_t, &(C->b_size)) ;
235 ok = ok && (C->b != NULL) ;
236 }
237
238 if (allocate_Ci)
239 {
240 // allocate new C->i component
241 C->i = GB_MALLOC (C->nzmax, int64_t, &(C->i_size)) ;
242 ok = ok && (C->i != NULL) ;
243 }
244
245 if (allocate_Cx)
246 {
247 // allocate new C->x component
248 C->x = GB_MALLOC (C->nzmax * C->type->size, GB_void, &(C->x_size)) ;
249 ok = ok && (C->x != NULL) ;
250 }
251
252 if (!ok)
253 {
254 // out of memory
255 GB_phbix_free (C) ;
256 GB_Matrix_free (Ahandle) ;
257 return (GrB_OUT_OF_MEMORY) ;
258 }
259
260 //--------------------------------------------------------------------------
261 // transplant or copy A->x numerical values
262 //--------------------------------------------------------------------------
263
264 // Note that A may contain zombies, and the values of these zombies may be
265 // uninitialized values in A->x. All entries are typecasted or memcpy'ed
266 // from A->x to C->x, both zombies and live entries alike. valgrind may
267 // complain about typecasting these uninitialized values, but these
268 // warnings are false positives. The output of the typecasting is itself a
269 // zombie, and the values of all zombies are ignored.
270
271 ASSERT_TYPE_OK (C->type, "target C->type for values", GB0) ;
272 ASSERT_TYPE_OK (A->type, "source A->type for values", GB0) ;
273
274 if (C->type == A->type)
275 {
276 // types match
277 if (A->x_shallow)
278 {
279 // A is shallow so make a deep copy; no typecast needed
280 // TODO handle the bitmap better for valgrind: do not use memcpy
281 GB_memcpy (C->x, A->x, anz * C->type->size, nthreads) ;
282 A->x = NULL ;
283 }
284 else
285 {
286 // OK to move pointers instead
287 C->x = A->x ; C->x_size = A->x_size ;
288 A->x = NULL ;
289 }
290 }
291 else
292 {
293 // types differ, must typecast from A to C.
294 GB_void *restrict Cx = (GB_void *) C->x ;
295 GB_void *restrict Ax = (GB_void *) A->x ;
296 GB_cast_array (Cx, C->type->code,
297 Ax, A->type->code, A->b, A->type->size, anz, nthreads) ;
298 if (!A->x_shallow)
299 {
300 GB_FREE (&(A->x), A->x_size) ;
301 }
302 A->x = NULL ;
303 }
304
305 ASSERT (A->x == NULL) ; // has been freed or removed
306 A->x_shallow = false ;
307
308 ASSERT (C->x != NULL) ;
309 C->x_shallow = false ;
310
311 //--------------------------------------------------------------------------
312 // transplant or copy A->i row indices
313 //--------------------------------------------------------------------------
314
315 if (C_is_full || C_is_bitmap)
316 {
317
318 //----------------------------------------------------------------------
319 // C is full or bitmap
320 //----------------------------------------------------------------------
321
322 // C is full or bitmap; C->i stays NULL
323 C->i = NULL ;
324
325 }
326 else if (A->i_shallow)
327 {
328
329 //----------------------------------------------------------------------
330 // A->i is a shallow copy of another matrix, so we need a deep copy
331 //----------------------------------------------------------------------
332
333 // copy A->i into C->i
334 GB_memcpy (C->i, A->i, anz * sizeof (int64_t), nthreads) ;
335 A->i = NULL ;
336 A->i_shallow = false ;
337
338 }
339 else
340 {
341
342 //----------------------------------------------------------------------
343 // A->i is not shallow, so just transplant the pointer from A to C
344 //----------------------------------------------------------------------
345
346 C->i = A->i ; C->i_size = A->i_size ;
347 A->i = NULL ;
348 A->i_shallow = false ;
349 }
350
351 C->i_shallow = false ;
352 C->nzombies = A->nzombies ; // zombies may have been transplanted into C
353 C->jumbled = A->jumbled ; // C is jumbled if A is jumbled
354
355 //--------------------------------------------------------------------------
356 // transplant or copy A->b bitmap
357 //--------------------------------------------------------------------------
358
359 if (!C_is_bitmap)
360 {
361
362 //----------------------------------------------------------------------
363 // A is not bitmap; A->b does not exist
364 //----------------------------------------------------------------------
365
366 // C is not bitmap; C->b stays NULL
367 C->b = NULL ;
368
369 }
370 else if (A->b_shallow)
371 {
372
373 //----------------------------------------------------------------------
374 // A->b is a shallow copy of another matrix, so we need a deep copy
375 //----------------------------------------------------------------------
376
377 // copy A->b into C->b
378 GB_memcpy (C->b, A->b, anz * sizeof (int8_t), nthreads) ;
379 A->b = NULL ;
380 A->b_shallow = false ;
381
382 }
383 else
384 {
385
386 //----------------------------------------------------------------------
387 // A->b is not shallow, so just transplant the pointer from A to C
388 //----------------------------------------------------------------------
389
390 C->b = A->b ; C->b_size = A->b_size ;
391 A->b = NULL ;
392 A->b_shallow = false ;
393 }
394
395 C->b_shallow = false ;
396 C->nvals = A->nvals ;
397
398 //--------------------------------------------------------------------------
399 // free A and return result
400 //--------------------------------------------------------------------------
401
402 GB_Matrix_free (Ahandle) ;
403 ASSERT_MATRIX_OK (C, "C after transplant", GB0) ;
404 return (GrB_SUCCESS) ;
405 }
406
407