1 //------------------------------------------------------------------------------
2 // GB_assign_zombie4: delete entries in C(i,:) for C_replace_phase
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 // For GrB_Row_assign or GrB_Col_assign, C(i,J)<M,repl>=..., if C_replace is
11 // true, and mask M is present, then any entry C(i,j) outside the list J must
12 // be deleted, if M(0,j)=0.
13
14 // GB_assign_zombie3 and GB_assign_zombie4 are transposes of each other.
15
16 // C must be sparse or hypersparse.
17 // M can have any sparsity structure: hypersparse, sparse, bitmap, or full
18
19 #include "GB_assign.h"
20 #include "GB_assign_zombie.h"
21
GB_assign_zombie4(GrB_Matrix C,const GrB_Matrix M,const bool Mask_comp,const bool Mask_struct,const int64_t i,const GrB_Index * J,const int64_t nJ,const int Jkind,const int64_t Jcolon[3],GB_Context Context)22 void GB_assign_zombie4
23 (
24 GrB_Matrix C, // the matrix C, or a copy
25 const GrB_Matrix M,
26 const bool Mask_comp,
27 const bool Mask_struct,
28 const int64_t i, // index of entries to delete
29 const GrB_Index *J,
30 const int64_t nJ,
31 const int Jkind,
32 const int64_t Jcolon [3],
33 GB_Context Context
34 )
35 {
36
37 //--------------------------------------------------------------------------
38 // check inputs
39 //--------------------------------------------------------------------------
40
41 ASSERT (!GB_IS_FULL (C)) ;
42 ASSERT (!GB_IS_BITMAP (C)) ;
43 ASSERT (GB_ZOMBIES_OK (C)) ;
44 ASSERT (!GB_JUMBLED (C)) ; // binary search on C
45 ASSERT (!GB_PENDING (C)) ;
46 ASSERT (!GB_ZOMBIES (M)) ;
47 ASSERT (!GB_JUMBLED (M)) ;
48 ASSERT (!GB_PENDING (M)) ;
49 ASSERT (!GB_aliased (C, M)) ; // NO ALIAS of C==M
50
51 //--------------------------------------------------------------------------
52 // get C
53 //--------------------------------------------------------------------------
54
55 const int64_t *restrict Ch = C->h ;
56 const int64_t *restrict Cp = C->p ;
57 const int64_t Cnvec = C->nvec ;
58 int64_t *restrict Ci = C->i ;
59 int64_t nzombies = C->nzombies ;
60 const int64_t zorig = nzombies ;
61
62 //--------------------------------------------------------------------------
63 // get M
64 //--------------------------------------------------------------------------
65
66 const int64_t *restrict Mp = M->p ;
67 const int64_t *restrict Mh = M->h ;
68 const int8_t *restrict Mb = M->b ;
69 const GB_void *restrict Mx = (GB_void *) (Mask_struct ? NULL : (M->x)) ;
70 const size_t msize = M->type->size ;
71 const int64_t Mnvec = M->nvec ;
72 const int64_t Mvlen = M->vlen ;
73 ASSERT (Mvlen == 1) ;
74 const bool M_is_hyper = GB_IS_HYPERSPARSE (M) ;
75 const bool M_is_bitmap = GB_IS_BITMAP (M) ;
76 const bool M_is_full = GB_IS_FULL (M) ;
77
78 //--------------------------------------------------------------------------
79 // determine the number of threads to use
80 //--------------------------------------------------------------------------
81
82 GB_GET_NTHREADS_MAX (nthreads_max, chunk, Context) ;
83 int nthreads = GB_nthreads (Cnvec, chunk, nthreads_max) ;
84 int ntasks = (nthreads == 1) ? 1 : (64 * nthreads) ;
85
86 //--------------------------------------------------------------------------
87 // delete entries in C(i,:)
88 //--------------------------------------------------------------------------
89
90 // The entry C(i,j) is deleted if j is not in the J, and if M(0,j)=0 (if
91 // the mask is not complemented) or M(0,j)=1 (if the mask is complemented.
92
93 int taskid ;
94 #pragma omp parallel for num_threads(nthreads) schedule(dynamic,1) \
95 reduction(+:nzombies)
96 for (taskid = 0 ; taskid < ntasks ; taskid++)
97 {
98 int64_t kfirst, klast ;
99 GB_PARTITION (kfirst, klast, Cnvec, taskid, ntasks) ;
100 for (int64_t k = kfirst ; k < klast ; k++)
101 {
102
103 //------------------------------------------------------------------
104 // get C(:,j) and determine if j is outside the list J
105 //------------------------------------------------------------------
106
107 int64_t j = GBH (Ch, k) ;
108 bool j_outside = !GB_ij_is_in_list (J, nJ, j, Jkind, Jcolon) ;
109 if (j_outside)
110 {
111
112 //--------------------------------------------------------------
113 // j is not in J; find C(i,j)
114 //--------------------------------------------------------------
115
116 int64_t pC = Cp [k] ;
117 int64_t pC_end = Cp [k+1] ;
118 int64_t pright = pC_end - 1 ;
119 bool found, is_zombie ;
120 GB_BINARY_SEARCH_ZOMBIE (i, Ci, pC, pright, found, zorig,
121 is_zombie) ;
122
123 //--------------------------------------------------------------
124 // delete C(i,j) if found, not a zombie, and M(0,j) allows it
125 //--------------------------------------------------------------
126
127 if (found && !is_zombie)
128 {
129
130 //----------------------------------------------------------
131 // C(i,j) is a live entry not in the C(I,J) submatrix
132 //----------------------------------------------------------
133
134 // Check the mask M to see if it should be deleted.
135 bool mij = false ;
136
137 if (M_is_bitmap || M_is_full)
138 {
139 // M is bitmap/full, no need for GB_lookup
140 int64_t pM = j ;
141 mij = GBB (Mb, pM) && GB_mcast (Mx, pM, msize) ;
142 }
143 else
144 {
145 // M is sparse or hypersparse
146 int64_t pM, pM_end ;
147 int64_t pleft = 0 ;
148 int64_t pright = Mnvec - 1 ;
149 GB_lookup (M_is_hyper, Mh, Mp, Mvlen, &pleft, pright,
150 j, &pM, &pM_end) ;
151 if (pM < pM_end)
152 {
153 // found it
154 mij = GB_mcast (Mx, pM, msize) ;
155 }
156 }
157
158 if (Mask_comp)
159 {
160 // negate the mask if Mask_comp is true
161 mij = !mij ;
162 }
163 if (!mij)
164 {
165 // delete C(i,j) by marking it as a zombie
166 nzombies++ ;
167 Ci [pC] = GB_FLIP (i) ;
168 }
169 }
170 }
171 }
172 }
173
174 //--------------------------------------------------------------------------
175 // return result
176 //--------------------------------------------------------------------------
177
178 C->nzombies = nzombies ;
179 }
180
181