1 //------------------------------------------------------------------------------
2 // GB_AxB_saxpy3_coarseHash_phase5:
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 {
11 
12     //--------------------------------------------------------------------------
13     // phase 5: coarse hash task, C=A*B
14     //--------------------------------------------------------------------------
15 
16     // Initially, Hf [...] < mark for all of Hf.
17     // Let f = Hf [hash] and h = Hi [hash]
18 
19     // f < mark          : unoccupied.
20     // h == i, f == mark : occupied with C(i,j)
21 
22     for (int64_t kk = kfirst ; kk <= klast ; kk++)
23     {
24         int64_t pC = Cp [kk] ;
25         int64_t cjnz = Cp [kk+1] - pC ;
26         if (cjnz == 0) continue ;   // nothing to do
27         GB_GET_B_j ;                // get B(:,j)
28 
29         #ifdef GB_CHECK_MASK_ij
30 
31             // The mask M is packed (full, bitmap, or sparse/hyper and not
32             // jumbled with all entries present in the entire matrix).
33             GB_GET_M_j                  // get M(:,j)
34             #ifdef GB_MASK_IS_BITMAP_AND_STRUCTURAL
35             // Mjb is the M(:,j) vector, if M is bitmap and structural
36             const int8_t *restrict Mjb = Mb + pM_start ;
37             #endif
38 
39         #else
40 
41             // M is not present
42             if (bjnz == 1 && (A_is_sparse || A_is_hyper))
43             {
44                 // C(:,j) = A(:,k)*B(k,j), no mask
45                 GB_COMPUTE_C_j_WHEN_NNZ_B_j_IS_ONE ;
46                 continue ;
47             }
48 
49         #endif
50 
51         mark++ ;
52         for ( ; pB < pB_end ; pB++)     // scan B(:,j)
53         {
54             GB_GET_B_kj_INDEX ;         // get index k of B(k,j)
55             GB_GET_A_k ;                // get A(:,k)
56             if (aknz == 0) continue ;
57             GB_GET_B_kj ;               // bkj = B(k,j)
58             // scan A(:,k)
59             for (int64_t pA = pA_start ; pA < pA_end ; pA++)
60             {
61                 GB_GET_A_ik_INDEX ;     // get index i of A(i,j)
62                 #ifdef GB_CHECK_MASK_ij
63                 // check mask condition and skip if C(i,j) is protected by the
64                 // mask
65                 GB_CHECK_MASK_ij ;
66                 #endif
67                 GB_MULT_A_ik_B_kj ;     // t = A(i,k)*B(k,j)
68                 for (GB_HASH (i))   // find i in hash table
69                 {
70                     if (Hf [hash] == mark)
71                     {
72                         // hash entry is occupied
73                         if (Hi [hash] == i)
74                         {
75                             // i already in the hash table
76                             // Hx [hash] += t ;
77                             GB_HX_UPDATE (hash, t) ;
78                             break ;
79                         }
80                     }
81                     else
82                     {
83                         // hash entry is not occupied
84                         Hf [hash] = mark ;
85                         Hi [hash] = i ;
86                         GB_HX_WRITE (hash, t) ;// Hx[hash]=t
87                         Ci [pC++] = i ;
88                         break ;
89                     }
90                 }
91             }
92         }
93         GB_SORT_AND_GATHER_HASHED_C_j (mark) ;  // gather into C(:,j)
94     }
95 }
96 
97 #undef GB_MASK_IS_BITMAP_AND_STRUCTURAL
98 
99