1 //------------------------------------------------------------------------------
2 // GB_AxB_saxpy3_coarseHash_notM_phase5: C<!M>=A*B, coarse Hash, phase 5
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     // phase5: coarse hash task, C<!M>=A*B
13     //--------------------------------------------------------------------------
14 
15     // M is sparse and scattered into Hf
16 
17     // Initially, Hf [...] < mark for all of Hf.
18     // Let h = Hi [hash] and f = Hf [hash].
19 
20     // f < mark: unoccupied, M(i,j)=0, and C(i,j) not yet seen.
21     // h == i, f == mark   : M(i,j)=1. C(i,j) ignored.
22     // h == i, f == mark+1 : M(i,j)=0, and C(i,j) has been seen.
23 
24     for (int64_t kk = kfirst ; kk <= klast ; kk++)
25     {
26         int64_t pC = Cp [kk] ;
27         int64_t cjnz = Cp [kk+1] - pC ;
28         if (cjnz == 0) continue ;   // nothing to do
29         GB_GET_M_j ;                // get M(:,j)
30         mark += 2 ;
31         int64_t mark1 = mark+1 ;
32         GB_HASH_M_j ;               // hash M(:,j)
33         GB_GET_B_j ;                // get B(:,j)
34         for ( ; pB < pB_end ; pB++)     // scan B(:,j)
35         {
36             GB_GET_B_kj_INDEX ;         // get index k of B(k,j)
37             GB_GET_A_k ;                // get A(:,k)
38             if (aknz == 0) continue ;
39             GB_GET_B_kj ;               // bkj = B(k,j)
40             // scan A(:,k)
41             for (int64_t pA = pA_start ; pA < pA_end ; pA++)
42             {
43                 GB_GET_A_ik_INDEX ;     // get index i of A(i,k)
44                 for (GB_HASH (i))       // find i in hash
45                 {
46                     int64_t f = Hf [hash] ;
47                     if (f < mark)   // if true, i is new
48                     {
49                         // C(i,j) is new
50                         Hf [hash] = mark1 ; // mark C(i,j) seen
51                         Hi [hash] = i ;
52                         GB_MULT_A_ik_B_kj ; // t = A(i,k)*B(k,j)
53                         GB_HX_WRITE (hash, t) ; // Hx [hash] = t
54                         Ci [pC++] = i ;
55                         break ;
56                     }
57                     if (Hi [hash] == i)
58                     {
59                         if (f == mark1)
60                         {
61                             // C(i,j) has been seen; update it.
62                             GB_MULT_A_ik_B_kj ;//t=A(i,k)*B(k,j)
63                             GB_HX_UPDATE (hash, t) ;//Hx[ ] += t
64                         }
65                         break ;
66                     }
67                 }
68             }
69         }
70         GB_SORT_AND_GATHER_HASHED_C_j (mark1) ;
71     }
72 }
73 
74