1 //------------------------------------------------------------------------------
2 // GB_resize: change the size 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_select.h"
11
12 #define GB_FREE_ALL \
13 { \
14 GB_FREE (&Ax_new, Ax_new_size) ; \
15 GB_FREE (&Ab_new, Ab_new_size) ; \
16 GB_phbix_free (A) ; \
17 }
18
19 //------------------------------------------------------------------------------
20 // GB_resize: resize a GrB_Matrix
21 //------------------------------------------------------------------------------
22
GB_resize(GrB_Matrix A,const GrB_Index nrows_new,const GrB_Index ncols_new,GB_Context Context)23 GrB_Info GB_resize // change the size of a matrix
24 (
25 GrB_Matrix A, // matrix to modify
26 const GrB_Index nrows_new, // new number of rows in matrix
27 const GrB_Index ncols_new, // new number of columns in matrix
28 GB_Context Context
29 )
30 {
31
32 //--------------------------------------------------------------------------
33 // check inputs
34 //--------------------------------------------------------------------------
35
36 GrB_Info info ;
37 GB_void *restrict Ax_new = NULL ; size_t Ax_new_size = 0 ;
38 int8_t *restrict Ab_new = NULL ; size_t Ab_new_size = 0 ;
39 ASSERT_MATRIX_OK (A, "A to resize", GB0) ;
40
41 //--------------------------------------------------------------------------
42 // handle the CSR/CSC format
43 //--------------------------------------------------------------------------
44
45 int64_t vdim_old = A->vdim ;
46 int64_t vlen_old = A->vlen ;
47 int64_t vlen_new, vdim_new ;
48 if (A->is_csc)
49 {
50 vlen_new = nrows_new ;
51 vdim_new = ncols_new ;
52 }
53 else
54 {
55 vlen_new = ncols_new ;
56 vdim_new = nrows_new ;
57 }
58
59 if (vdim_new == vdim_old && vlen_new == vlen_old)
60 {
61 // nothing to do
62 return (GrB_SUCCESS) ;
63 }
64
65 //--------------------------------------------------------------------------
66 // delete any lingering zombies and assemble any pending tuples
67 //--------------------------------------------------------------------------
68
69 // only do so if either dimension is shrinking, or if pending tuples exist
70 // and vdim_old <= 1 and vdim_new > 1, since in that case, Pending->j has
71 // not been allocated yet, but would be required in the resized matrix.
72 // If A is jumbled, it must be sorted.
73
74 if (vdim_new < vdim_old || vlen_new < vlen_old || A->jumbled ||
75 (GB_PENDING (A) && vdim_old <= 1 && vdim_new > 1))
76 {
77 GB_MATRIX_WAIT (A) ;
78 ASSERT_MATRIX_OK (A, "A to resize, wait", GB0) ;
79 }
80
81 ASSERT (!GB_JUMBLED (A)) ;
82
83 //--------------------------------------------------------------------------
84 // resize the matrix
85 //--------------------------------------------------------------------------
86
87 bool A_is_bitmap = GB_IS_BITMAP (A) ;
88 bool A_is_full = GB_IS_FULL (A) ;
89 bool A_is_shrinking = (vdim_new <= vdim_old && vlen_new <= vlen_old) ;
90
91 if ((A_is_full || A_is_bitmap) && A_is_shrinking)
92 {
93
94 //----------------------------------------------------------------------
95 // A is full or bitmap
96 //----------------------------------------------------------------------
97
98 // get the old and new dimensions
99 int64_t anz_old = vlen_old * vdim_old ;
100 int64_t anz_new = vlen_new * vdim_new ;
101 size_t nzmax_new = GB_IMAX (anz_new, 1) ;
102 size_t nzmax_old = A->nzmax ;
103 bool in_place = A_is_full && (vlen_new == vlen_old || vdim_new <= 1) ;
104 size_t asize = A->type->size ;
105
106 //----------------------------------------------------------------------
107 // allocate or reallocate A->x and A->b
108 //----------------------------------------------------------------------
109
110 bool ok = true ;
111 if (in_place)
112 {
113 // reallocate A->x in-place; no data movement needed
114 GB_REALLOC (A->x, nzmax_new*asize, nzmax_old*asize, GB_void,
115 &(A->x_size), &ok, Context) ;
116 }
117 else
118 {
119 // allocate new space for A->x
120 Ax_new = GB_MALLOC (nzmax_new*asize, GB_void, &Ax_new_size) ;
121 ok = (Ax_new != NULL) ;
122 if (A_is_bitmap)
123 {
124 // allocate new space for A->b
125 Ab_new = GB_MALLOC (nzmax_new*asize, int8_t, &Ab_new_size) ;
126 ok = ok && (Ab_new != NULL) ;
127 }
128 }
129 if (!ok)
130 {
131 // out of memory
132 GB_FREE_ALL ;
133 return (GrB_OUT_OF_MEMORY) ;
134 }
135
136 //----------------------------------------------------------------------
137 // move data if not in-place
138 //----------------------------------------------------------------------
139
140 if (!in_place)
141 {
142
143 //------------------------------------------------------------------
144 // determine number of threads to use
145 //------------------------------------------------------------------
146
147 GB_GET_NTHREADS_MAX (nthreads_max, chunk, Context) ;
148 int nthreads = GB_nthreads (anz_new, chunk, nthreads_max) ;
149
150 //------------------------------------------------------------------
151 // resize Ax
152 //------------------------------------------------------------------
153
154 GB_void *restrict Ax_old = (GB_void *) A->x ;
155
156 int64_t j ;
157 if (vdim_new <= 4*nthreads)
158 {
159 // use all threads for each vector
160 for (j = 0 ; j < vdim_new ; j++)
161 {
162 GB_void *pdest = Ax_new + j * vlen_new * asize ;
163 GB_void *psrc = Ax_old + j * vlen_old * asize ;
164 GB_memcpy (pdest, psrc, vlen_new * asize, nthreads) ;
165 }
166 }
167 else
168 {
169 // use a single thread for each vector
170 #pragma omp parallel for num_threads(nthreads) schedule(static)
171 for (j = 0 ; j < vdim_new ; j++)
172 {
173 GB_void *pdest = Ax_new + j * vlen_new * asize ;
174 GB_void *psrc = Ax_old + j * vlen_old * asize ;
175 memcpy (pdest, psrc, vlen_new * asize) ;
176 }
177 }
178 GB_FREE (&Ax_old, A->x_size) ;
179 A->x = Ax_new ; A->x_size = Ax_new_size ;
180
181 //------------------------------------------------------------------
182 // resize Ab if A is bitmap, and count the # of entries
183 //------------------------------------------------------------------
184
185 if (A_is_bitmap)
186 {
187 int8_t *restrict Ab_old = A->b ;
188 int64_t pnew ;
189 int64_t anvals = 0 ;
190 #pragma omp parallel for num_threads(nthreads) \
191 schedule(static) reduction(+:anvals)
192 for (pnew = 0 ; pnew < anz_new ; pnew++)
193 {
194 int64_t i = pnew % vlen_new ;
195 int64_t j = pnew / vlen_new ;
196 int64_t pold = i + j * vlen_old ;
197 int8_t ab = Ab_old [pold] ;
198 Ab_new [pnew] = ab ;
199 anvals += ab ;
200 }
201 A->nvals = anvals ;
202 GB_FREE (&Ab_old, A->b_size) ;
203 A->b = Ab_new ; A->b_size = Ab_new_size ;
204 }
205 }
206
207 //----------------------------------------------------------------------
208 // adjust dimensions and return result
209 //----------------------------------------------------------------------
210
211 A->vdim = vdim_new ;
212 A->vlen = vlen_new ;
213 A->nzmax = nzmax_new ;
214 A->nvec = vdim_new ;
215 A->nvec_nonempty = (vlen_new == 0) ? 0 : vdim_new ;
216 ASSERT_MATRIX_OK (A, "A bitmap/full shrunk", GB0) ;
217 return (GrB_SUCCESS) ;
218
219 }
220 else
221 {
222
223 //----------------------------------------------------------------------
224 // convert A to hypersparse and resize it
225 //----------------------------------------------------------------------
226
227 // convert to hypersparse
228 GB_OK (GB_convert_any_to_hyper (A, Context)) ;
229 ASSERT (GB_IS_HYPERSPARSE (A)) ;
230
231 // resize the number of sparse vectors
232 int64_t *restrict Ah = A->h ;
233 int64_t *restrict Ap = A->p ;
234 A->vdim = vdim_new ;
235
236 if (vdim_new < A->plen)
237 {
238 // reduce the size of A->p and A->h; this cannot fail
239 info = GB_hyper_realloc (A, vdim_new, Context) ;
240 ASSERT (info == GrB_SUCCESS) ;
241 Ap = A->p ;
242 Ah = A->h ;
243 }
244
245 if (vdim_new < vdim_old)
246 {
247 // descrease A->nvec to delete the vectors outside the range
248 // 0...vdim_new-1.
249 int64_t pleft = 0 ;
250 int64_t pright = GB_IMIN (A->nvec, vdim_new) - 1 ;
251 bool found ;
252 GB_SPLIT_BINARY_SEARCH (vdim_new, Ah, pleft, pright, found) ;
253 A->nvec = pleft ;
254 }
255
256 if (vdim_new < vdim_old)
257 {
258 // number of vectors is decreasing, need to count the new number of
259 // non-empty vectors: done during pruning or by selector, below.
260 A->nvec_nonempty = -1 ; // recomputed just below
261 }
262
263 //----------------------------------------------------------------------
264 // resize the length of each vector
265 //----------------------------------------------------------------------
266
267 // if vlen is shrinking, delete entries outside the new matrix
268 if (vlen_new < vlen_old)
269 {
270 GB_OK (GB_selector (NULL /* A in-place */, GB_RESIZE_opcode, NULL,
271 false, A, vlen_new-1, NULL, Context)) ;
272 }
273
274 //----------------------------------------------------------------------
275 // vlen has been resized
276 //----------------------------------------------------------------------
277
278 A->vlen = vlen_new ;
279 ASSERT_MATRIX_OK (A, "A vlen resized", GB0) ;
280
281 //----------------------------------------------------------------------
282 // conform the matrix to its desired sparsity structure
283 //----------------------------------------------------------------------
284
285 return (GB_conform (A, Context)) ;
286 }
287 }
288
289