1 //------------------------------------------------------------------------------
2 // GB_assign_zombie3: delete entries in C(:,j) 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>=any must delete all
11 // entries C(i,j) outside of C(I,j), if the mask M(i,0) (or its complement) is
12 // zero. This step is not done for GxB_*_subassign, since that method does not
13 // modify anything outside IxJ.
14
15 // GB_assign_zombie3 and GB_assign_zombie4 are transposes of each other.
16
17 // C must be sparse or hypersparse.
18 // M can have any sparsity structure: hypersparse, sparse, bitmap, or full
19
20 #include "GB_assign.h"
21 #include "GB_assign_zombie.h"
22 #include "GB_subassign_methods.h"
23
GB_assign_zombie3(GrB_Matrix C,const GrB_Matrix M,const bool Mask_comp,const bool Mask_struct,const int64_t j,const GrB_Index * I,const int64_t nI,const int Ikind,const int64_t Icolon[3],GB_Context Context)24 void GB_assign_zombie3
25 (
26 GrB_Matrix C, // the matrix C, or a copy
27 const GrB_Matrix M,
28 const bool Mask_comp,
29 const bool Mask_struct,
30 const int64_t j, // vector index with entries to delete
31 const GrB_Index *I,
32 const int64_t nI,
33 const int Ikind,
34 const int64_t Icolon [3],
35 GB_Context Context
36 )
37 {
38
39 //--------------------------------------------------------------------------
40 // check inputs
41 //--------------------------------------------------------------------------
42
43 ASSERT (!GB_IS_FULL (C)) ;
44 ASSERT (!GB_IS_BITMAP (C)) ;
45 ASSERT (GB_ZOMBIES_OK (C)) ;
46 ASSERT (GB_JUMBLED_OK (C)) ;
47 ASSERT (!GB_PENDING (C)) ;
48 ASSERT (!GB_ZOMBIES (M)) ;
49 ASSERT (!GB_JUMBLED (M)) ; // binary search on M
50 ASSERT (!GB_PENDING (M)) ;
51 ASSERT (!GB_aliased (C, M)) ; // NO ALIAS of C==M
52
53 //--------------------------------------------------------------------------
54 // get C (:,j)
55 //--------------------------------------------------------------------------
56
57 const int64_t *restrict Ch = C->h ;
58 const int64_t *restrict Cp = C->p ;
59 int64_t *restrict Ci = C->i ;
60 int64_t pC_start, pC_end, pleft = 0, pright = C->nvec-1 ;
61 GB_lookup (C->h != NULL, Ch, Cp, C->vlen, &pleft, pright, j,
62 &pC_start, &pC_end) ;
63 int64_t nzombies = C->nzombies ;
64 const int64_t zjnz = pC_end - pC_start ;
65
66 //--------------------------------------------------------------------------
67 // get M(:,0)
68 //--------------------------------------------------------------------------
69
70 const int64_t *restrict Mp = M->p ;
71 const int8_t *restrict Mb = M->b ;
72 const int64_t *restrict Mi = M->i ;
73 const GB_void *restrict Mx = (GB_void *) (Mask_struct ? NULL : (M->x)) ;
74 const size_t msize = M->type->size ;
75 const int64_t Mvlen = M->vlen ;
76 int64_t pM_start = 0 ; // Mp [0]
77 int64_t pM_end = GBP (Mp, 1, Mvlen) ;
78 const bool M_is_bitmap = GB_IS_BITMAP (M) ;
79 const bool mjdense = (pM_end - pM_start) == Mvlen ;
80
81 //--------------------------------------------------------------------------
82 // determine the number of threads to use
83 //--------------------------------------------------------------------------
84
85 GB_GET_NTHREADS_MAX (nthreads_max, chunk, Context) ;
86 int nthreads = GB_nthreads (zjnz, chunk, nthreads_max) ;
87 int ntasks = (nthreads == 1) ? 1 : (64 * nthreads) ;
88
89 //--------------------------------------------------------------------------
90 // delete entries from C(:,j) that are outside I, if the mask M allows it
91 //--------------------------------------------------------------------------
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 p1, p2 ;
99 GB_PARTITION (p1, p2, zjnz, taskid, ntasks) ;
100 for (int64_t pC = pC_start + p1 ; pC < pC_start + p2 ; pC++)
101 {
102
103 //------------------------------------------------------------------
104 // get C(i,j)
105 //------------------------------------------------------------------
106
107 int64_t i = Ci [pC] ;
108 if (!GB_IS_ZOMBIE (i))
109 {
110
111 //--------------------------------------------------------------
112 // C(i,j) is outside C(I,j) if i is not in the list I
113 //--------------------------------------------------------------
114
115 bool i_outside = !GB_ij_is_in_list (I, nI, i, Ikind, Icolon) ;
116 if (i_outside)
117 {
118
119 //----------------------------------------------------------
120 // C(i,j) is a live entry not in the C(I,J) submatrix
121 //----------------------------------------------------------
122
123 // Check the mask M to see if it should be deleted.
124 GB_MIJ_BINARY_SEARCH_OR_DENSE_LOOKUP (i) ;
125 if (Mask_comp)
126 {
127 // negate the mask if Mask_comp is true
128 mij = !mij ;
129 }
130 if (!mij)
131 {
132 // delete C(i,j) by marking it as a zombie
133 nzombies++ ;
134 Ci [pC] = GB_FLIP (i) ;
135 }
136 }
137 }
138 }
139 }
140
141 //--------------------------------------------------------------------------
142 // return result
143 //--------------------------------------------------------------------------
144
145 C->nzombies = nzombies ;
146 }
147
148