1 //------------------------------------------------------------------------------
2 // GB_subassign_01: C(I,J) = scalar ; using S
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 // Method 01: C(I,J) = scalar ; using S
11
12 // M: NULL
13 // Mask_comp: false
14 // C_replace: false
15 // accum: NULL
16 // A: scalar
17 // S: constructed
18
19 // C: not bitmap
20
21 #include "GB_subassign_methods.h"
22
GB_subassign_01(GrB_Matrix C,const GrB_Index * I,const int64_t ni,const int64_t nI,const int Ikind,const int64_t Icolon[3],const GrB_Index * J,const int64_t nj,const int64_t nJ,const int Jkind,const int64_t Jcolon[3],const void * scalar,const GrB_Type atype,GB_Context Context)23 GrB_Info GB_subassign_01
24 (
25 GrB_Matrix C,
26 // input:
27 const GrB_Index *I,
28 const int64_t ni,
29 const int64_t nI,
30 const int Ikind,
31 const int64_t Icolon [3],
32 const GrB_Index *J,
33 const int64_t nj,
34 const int64_t nJ,
35 const int Jkind,
36 const int64_t Jcolon [3],
37 const void *scalar,
38 const GrB_Type atype,
39 GB_Context Context
40 )
41 {
42
43 //--------------------------------------------------------------------------
44 // check inputs
45 //--------------------------------------------------------------------------
46
47 ASSERT (!GB_IS_BITMAP (C)) ;
48
49 //--------------------------------------------------------------------------
50 // S = C(I,J)
51 //--------------------------------------------------------------------------
52
53 GB_EMPTY_TASKLIST ;
54 GB_OK (GB_subassign_symbolic (S, C, I, ni, J, nj, true, Context)) ;
55
56 //--------------------------------------------------------------------------
57 // get inputs
58 //--------------------------------------------------------------------------
59
60 GB_GET_C ; // C must not be bitmap
61 const int64_t *restrict Ch = C->h ;
62 const int64_t *restrict Cp = C->p ;
63 const bool C_is_hyper = (Ch != NULL) ;
64 const int64_t Cnvec = C->nvec ;
65 GB_GET_SCALAR ;
66 GB_GET_S ;
67 GrB_BinaryOp accum = NULL ;
68
69 //--------------------------------------------------------------------------
70 // Method 01: C(I,J) = scalar ; using S
71 //--------------------------------------------------------------------------
72
73 // Time: Optimal; must visit all IxJ, so Omega(|I|*|J|) is required.
74
75 // Entries in S are found and the corresponding entry in C replaced with
76 // the scalar. The traversal of S is identical to the traversal of M in
77 // Method 4.
78
79 // Method 01 and Method 03 are very similar.
80
81 //--------------------------------------------------------------------------
82 // Parallel: all IxJ (Methods 01, 03, 13, 15, 17, 19)
83 //--------------------------------------------------------------------------
84
85 GB_SUBASSIGN_IXJ_SLICE ;
86
87 //--------------------------------------------------------------------------
88 // phase 1: create zombies, update entries, and count pending tuples
89 //--------------------------------------------------------------------------
90
91 #pragma omp parallel for num_threads(nthreads) schedule(dynamic,1) \
92 reduction(+:nzombies)
93 for (taskid = 0 ; taskid < ntasks ; taskid++)
94 {
95
96 //----------------------------------------------------------------------
97 // get the task descriptor
98 //----------------------------------------------------------------------
99
100 GB_GET_IXJ_TASK_DESCRIPTOR_PHASE1 (iA_start, iA_end) ;
101
102 //----------------------------------------------------------------------
103 // compute all vectors in this task
104 //----------------------------------------------------------------------
105
106 for (int64_t j = kfirst ; j <= klast ; j++)
107 {
108
109 //------------------------------------------------------------------
110 // get jC, the corresponding vector of C
111 //------------------------------------------------------------------
112
113 int64_t jC = GB_ijlist (J, j, Jkind, Jcolon) ;
114
115 //------------------------------------------------------------------
116 // get S(iA_start:end,j)
117 //------------------------------------------------------------------
118
119 GB_GET_VECTOR_FOR_IXJ (S, iA_start) ;
120
121 //------------------------------------------------------------------
122 // C(I(iA_start,iA_end-1),jC) = scalar
123 //------------------------------------------------------------------
124
125 for (int64_t iA = iA_start ; iA < iA_end ; iA++)
126 {
127 bool found = (pS < pS_end) && (GBI (Si, pS, Svlen) == iA) ;
128 if (!found)
129 {
130 // ----[. A 1]----------------------------------------------
131 // S (i,j) is not present, the scalar is present
132 // [. A 1]: action: ( insert )
133 task_pending++ ;
134 }
135 else
136 {
137 // ----[C A 1] or [X A 1]-----------------------------------
138 // both S (i,j) and A (i,j) present
139 // [C A 1]: action: ( =A ): scalar to C, no accum
140 // [X A 1]: action: ( undelete ): zombie lives
141 GB_C_S_LOOKUP ;
142 GB_noaccum_C_A_1_scalar ;
143 GB_NEXT (S) ;
144 }
145 }
146 }
147
148 GB_PHASE1_TASK_WRAPUP ;
149 }
150
151 //--------------------------------------------------------------------------
152 // phase 2: insert pending tuples
153 //--------------------------------------------------------------------------
154
155 GB_PENDING_CUMSUM ;
156
157 #pragma omp parallel for num_threads(nthreads) schedule(dynamic,1) \
158 reduction(&&:pending_sorted)
159 for (taskid = 0 ; taskid < ntasks ; taskid++)
160 {
161
162 //----------------------------------------------------------------------
163 // get the task descriptor
164 //----------------------------------------------------------------------
165
166 GB_GET_IXJ_TASK_DESCRIPTOR_PHASE2 (iA_start, iA_end) ;
167
168 //----------------------------------------------------------------------
169 // compute all vectors in this task
170 //----------------------------------------------------------------------
171
172 for (int64_t j = kfirst ; j <= klast ; j++)
173 {
174
175 //------------------------------------------------------------------
176 // get jC, the corresponding vector of C
177 //------------------------------------------------------------------
178
179 int64_t jC = GB_ijlist (J, j, Jkind, Jcolon) ;
180
181 //------------------------------------------------------------------
182 // get S(iA_start:end,j)
183 //------------------------------------------------------------------
184
185 GB_GET_VECTOR_FOR_IXJ (S, iA_start) ;
186
187 //------------------------------------------------------------------
188 // C(I(iA_start,iA_end-1),jC) = scalar
189 //------------------------------------------------------------------
190
191 for (int64_t iA = iA_start ; iA < iA_end ; iA++)
192 {
193 bool found = (pS < pS_end) && (GBI (Si, pS, Svlen) == iA) ;
194 if (!found)
195 {
196 // ----[. A 1]----------------------------------------------
197 // S (i,j) is not present, the scalar is present
198 // [. A 1]: action: ( insert )
199 int64_t iC = GB_ijlist (I, iA, Ikind, Icolon) ;
200 GB_PENDING_INSERT (scalar) ;
201 }
202 else
203 {
204 // both S (i,j) and A (i,j) present
205 GB_NEXT (S) ;
206 }
207 }
208 }
209
210 GB_PHASE2_TASK_WRAPUP ;
211 }
212
213 //--------------------------------------------------------------------------
214 // finalize the matrix and return result
215 //--------------------------------------------------------------------------
216
217 GB_SUBASSIGN_WRAPUP ;
218 }
219
220