1 //------------------------------------------------------------------------------
2 // GB_setElement: C(row,col) = scalar
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 // Sets the value of single scalar, C(row,col) = scalar, typecasting from the
11 // type of scalar to the type of C, as needed. Not user-callable; does the
12 // work for all GrB_*_setElement* functions.
13
14 // If C(row,col) is already present in the matrix, its value is overwritten
15 // with the scalar. Otherwise, if the mode determined by GrB_init is
16 // non-blocking, the tuple (i,j,scalar) is appended to a list of pending tuples
17 // to C. When calling GrB_Matrix_wait, these pending tuples are assembled.
18 // They are also assembled if the mode is blocking.
19
20 // GrB_setElement is the same as GrB_*assign with an implied SECOND accum
21 // operator whose ztype, xtype, and ytype are the same as C, with I=i, J=1, a
22 // 1-by-1 dense matrix A (where nnz (A) == 1), no mask, mask not complemented,
23 // C_replace effectively false (its value is ignored), and A transpose
24 // effectively false (since transposing a scalar has no effect).
25
26 // Compare this function with GrB_*_extractElement_*
27
28 #include "GB_Pending.h"
29
30 #define GB_FREE_ALL ;
31
GB_setElement(GrB_Matrix C,void * scalar,const GrB_Index row,const GrB_Index col,const GB_Type_code scalar_code,GB_Context Context)32 GrB_Info GB_setElement // set a single entry, C(row,col) = scalar
33 (
34 GrB_Matrix C, // matrix to modify
35 void *scalar, // scalar to set
36 const GrB_Index row, // row index
37 const GrB_Index col, // column index
38 const GB_Type_code scalar_code, // type of the scalar
39 GB_Context Context
40 )
41 {
42
43 //--------------------------------------------------------------------------
44 // check inputs
45 //--------------------------------------------------------------------------
46
47 GrB_Info info ;
48 ASSERT (C != NULL) ;
49 GB_RETURN_IF_NULL (scalar) ;
50
51 if (row >= GB_NROWS (C))
52 {
53 GB_ERROR (GrB_INVALID_INDEX,
54 "Row index " GBu " out of range; must be < " GBd,
55 row, GB_NROWS (C)) ;
56 }
57 if (col >= GB_NCOLS (C))
58 {
59 GB_ERROR (GrB_INVALID_INDEX,
60 "Column index " GBu " out of range; must be < " GBd,
61 col, GB_NCOLS (C)) ;
62 }
63
64 ASSERT (scalar_code <= GB_UDT_code) ;
65
66 GrB_Type ctype = C->type ;
67 GB_Type_code ccode = ctype->code ;
68
69 // scalar_code and C must be compatible
70 if (!GB_code_compatible (scalar_code, ccode))
71 {
72 GB_ERROR (GrB_DOMAIN_MISMATCH,
73 "Input scalar of type [%s]\n"
74 "cannot be typecast to entry of type [%s]",
75 GB_code_string (scalar_code), ctype->name) ;
76 }
77
78 // pending tuples and zombies are expected, and C might be jumbled too
79 ASSERT (GB_JUMBLED_OK (C)) ;
80 ASSERT (GB_PENDING_OK (C)) ;
81 ASSERT (GB_ZOMBIES_OK (C)) ;
82
83 #if GB_BURBLE
84 bool burble = GB_Global_burble_get ( ) ;
85 double t_burble = 0 ;
86 // do not burble when waiting on scalars or empty matrices
87 burble = burble && ((C->vlen > 1) || (C->vdim > 1)) ;
88 #endif
89
90 //--------------------------------------------------------------------------
91 // sort C if needed; do not assemble pending tuples or kill zombies yet
92 //--------------------------------------------------------------------------
93
94 GB_MATRIX_WAIT_IF_JUMBLED (C) ;
95
96 // zombies and pending tuples are still OK, but C is no longer jumbled
97 ASSERT (!GB_JUMBLED (C)) ;
98 ASSERT (GB_PENDING_OK (C)) ;
99 ASSERT (GB_ZOMBIES_OK (C)) ;
100
101 //--------------------------------------------------------------------------
102 // handle the CSR/CSC format
103 //--------------------------------------------------------------------------
104
105 int64_t i, j ;
106 if (C->is_csc)
107 {
108 // set entry with index i in vector j
109 i = row ;
110 j = col ;
111 }
112 else
113 {
114 // set entry with index j in vector i
115 i = col ;
116 j = row ;
117 }
118
119 int64_t pleft ;
120 bool found ;
121 bool is_zombie ;
122 bool C_is_bitmap = GB_IS_BITMAP (C) ;
123
124 if (GB_IS_FULL (C) || C_is_bitmap)
125 {
126
127 //----------------------------------------------------------------------
128 // C is bitmap or full
129 //----------------------------------------------------------------------
130
131 pleft = i + j * C->vlen ;
132 found = true ;
133 is_zombie = false ;
134 }
135 else
136 {
137
138 //----------------------------------------------------------------------
139 // binary search in C->h for vector j, or O(1)-time lookup if sparse
140 //----------------------------------------------------------------------
141
142 int64_t pC_start, pC_end, pright = C->nvec - 1 ;
143 pleft = 0 ;
144 found = GB_lookup (C->h != NULL, C->h, C->p, C->vlen, &pleft,
145 pright, j, &pC_start, &pC_end) ;
146
147 //----------------------------------------------------------------------
148 // binary search in kth vector for index i
149 //----------------------------------------------------------------------
150
151 if (found)
152 {
153 // vector j has been found; now look for index i
154 pleft = pC_start ;
155 pright = pC_end - 1 ;
156
157 // Time taken for this step is at most O(log(nnz(C(:,j))).
158 const int64_t *restrict Ci = C->i ;
159 GB_BINARY_SEARCH_ZOMBIE (i, Ci, pleft, pright, found, C->nzombies,
160 is_zombie) ;
161 }
162 }
163
164 //--------------------------------------------------------------------------
165 // set the element
166 //--------------------------------------------------------------------------
167
168 if (found)
169 {
170
171 //----------------------------------------------------------------------
172 // C (i,j) found
173 //----------------------------------------------------------------------
174
175 // if not zombie: action: ( =A ): copy A into C
176 // else action: ( undelete ): bring a zombie back to life
177
178 // found C (i,j), assign its value
179 size_t csize = ctype->size ;
180
181 // typecast or copy the scalar into C
182 GB_cast_array (((GB_void *) C->x) +(pleft*csize), ccode,
183 (GB_void *) scalar, scalar_code, NULL, csize, 1, 1) ;
184
185 if (is_zombie)
186 {
187 // bring the zombie back to life
188 C->i [pleft] = i ;
189 C->nzombies-- ;
190 }
191 else if (C_is_bitmap)
192 {
193 // set the entry in the C bitmap
194 int8_t cb = C->b [pleft] ;
195 C->nvals += (cb == 0) ;
196 C->b [pleft] = 1 ;
197 }
198
199 // the check is fine but just costly even when debugging
200 // ASSERT_MATRIX_OK (C, "did C for setElement (found)", GB0) ;
201 return (GrB_SUCCESS) ;
202 }
203 else
204 {
205 //----------------------------------------------------------------------
206 // C (i,j) not found: add a pending tuple
207 //----------------------------------------------------------------------
208
209 // action: ( insert )
210
211 // No typecasting can be done. The new pending tuple must either be
212 // the first pending tuple, or its type must match the prior pending
213 // tuples. See GB_subassign_methods.h for a complete description.
214
215 // stype is the type of this scalar
216 GrB_Type stype = GB_code_type (scalar_code, ctype) ;
217
218 bool wait = false ;
219
220 if (C->Pending == NULL)
221 {
222 // the new pending tuple is the first one, so it will define
223 // C->type-pending = stype. No need to wait.
224 wait = false ;
225 }
226 else
227 {
228 if (stype != C->Pending->type)
229 {
230 // the scalar type (stype) must match the type of the
231 // prior pending tuples. If the type is different, prior
232 // pending tuples must be assembled first.
233 wait = true ;
234 }
235 else if (!GB_op_is_second (C->Pending->op, ctype))
236 {
237 // prior op is not SECOND: setElement uses an implicit
238 // SECOND_Ctype operator, which must match the operator of the
239 // prior pending tuples. If it doesn't match, prior pending
240 // tuples must be assembled first.
241 wait = true ;
242 }
243 }
244
245 if (wait)
246 {
247 // Pending tuples exist. Either the pending operator is not
248 // SECOND_ctype (implicit or explicit), or the type of prior
249 // pending tuples is not the same as the type of the scalar. This
250 // new tuple requires both conditions to hold. All prior tuples
251 // must be assembled before this new one can be added.
252
253 #if GB_BURBLE
254 if (burble)
255 {
256 GBURBLE (" [ *_setElement ") ;
257 #if defined ( _OPENMP )
258 t_burble = GB_OPENMP_GET_WTIME ;
259 #endif
260 }
261 #endif
262
263 // delete any lingering zombies and assemble the pending tuples
264 GB_OK (GB_Matrix_wait (C, "C", Context)) ;
265
266 #if GB_BURBLE
267 if (burble)
268 {
269 GB_BURBLE_END ;
270 }
271 #endif
272
273 ASSERT (C->Pending == NULL) ;
274
275 // repeat the search since the C(i,j) entry may have been in
276 // the list of pending tuples. There are no longer any pending
277 // tuples, so this recursion will only happen once. The
278 // pending operator will become the implicit SECOND_ctype,
279 // and the type of the pending tuples will become ctype.
280 return (GB_setElement (C, scalar, row, col, scalar_code, Context)) ;
281 }
282
283 // the new tuple is now compatible with prior tuples, if any
284 ASSERT (GB_PENDING_OK (C)) ;
285 ASSERT (GB_ZOMBIES_OK (C)) ;
286
287 // C (i,j) must be added to the list of pending tuples.
288 // If this is the first pending tuple, then the type of pending tuples
289 // becomes the type of this scalar, and the pending operator becomes
290 // NULL, which is the implicit SECOND_ctype operator.
291
292 if (!GB_Pending_add (&(C->Pending), (GB_void *)scalar,
293 stype, NULL, i, j, C->vdim > 1, Context))
294 {
295 // out of memory
296 GB_phbix_free (C) ;
297 return (GrB_OUT_OF_MEMORY) ;
298 }
299
300 ASSERT (GB_PENDING (C)) ;
301
302 // if this was the first tuple, then the pending operator and
303 // pending type have been defined
304 ASSERT (GB_op_is_second (C->Pending->op, ctype)) ;
305 ASSERT (C->Pending->type == stype) ;
306 ASSERT (C->Pending->size == stype->size) ;
307
308 // this assert is fine, just costly even when debugging
309 // ASSERT_MATRIX_OK (C, "did C for setElement (not found)", GB0) ;
310
311 #if GB_BURBLE
312 // only burble if GB_Matrix_wait will be called
313 burble = (burble && GB_shall_block (C)) ;
314 if (burble)
315 {
316 GBURBLE (" [ *_setElement ") ;
317 #if defined ( _OPENMP )
318 t_burble = GB_OPENMP_GET_WTIME ;
319 #endif
320 }
321 #endif
322
323 info = GB_block (C, Context) ;
324
325 #if GB_BURBLE
326 if (burble)
327 {
328 GB_BURBLE_END ;
329 }
330 #endif
331
332 return (info) ;
333 }
334 }
335
336