1 //------------------------------------------------------------------------------
2 // GB_AxB_saxpy3_coarseHash_notM_phase1: symbolic coarse hash method, with !M
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     // Initially, Hf [...] < mark for all of Hf.
12     // Let h = Hi [hash] and f = Hf [hash].
13 
14     // f < mark: unoccupied, M(i,j)=0, and C(i,j) not yet seen.
15     // h == i, f == mark   : M(i,j)=1. C(i,j) ignored.
16     // h == i, f == mark+1 : M(i,j)=0, and C(i,j) has been seen.
17 
18     for (int64_t kk = kfirst ; kk <= klast ; kk++)
19     {
20         GB_GET_B_j ;            // get B(:,j)
21         Cp [kk] = 0 ;
22 
23         //----------------------------------------------------------------------
24         // special case when B(:,j) is empty
25         //----------------------------------------------------------------------
26 
27         #if ( GB_B_IS_SPARSE || GB_B_IS_HYPER )
28         if (bjnz == 0) continue ;
29         #endif
30 
31         //----------------------------------------------------------------------
32         // get M(:,j) and scatter it into the Hf workspace
33         //----------------------------------------------------------------------
34 
35         GB_GET_M_j ;            // get M(:,j)
36         mark += 2 ;
37         int64_t mark1 = mark+1 ;
38         GB_HASH_M_j ;           // hash M(:,j)
39 
40         //----------------------------------------------------------------------
41         // count nnz in C(:,j)
42         //----------------------------------------------------------------------
43 
44         int64_t cjnz = 0 ;
45         for ( ; pB < pB_end ; pB++)     // scan B(:,j)
46         {
47             GB_GET_B_kj_INDEX ;         // get index k of B(k,j)
48             GB_GET_A_k ;                // get A(:,k)
49             // scan A(:,k)
50             for (int64_t pA = pA_start ; pA < pA_end ; pA++)
51             {
52                 GB_GET_A_ik_INDEX ;     // get index i of A(i,k)
53                 for (GB_HASH (i))       // find i in hash
54                 {
55                     if (Hf [hash] < mark)   // if true, i is new
56                     {
57                         Hf [hash] = mark1 ; // mark C(i,j) seen
58                         Hi [hash] = i ;
59                         cjnz++ ;        // C(i,j) is a new entry
60                         break ;
61                     }
62                     if (Hi [hash] == i) break ;
63                 }
64             }
65         }
66         Cp [kk] = cjnz ;                // count the entries in C(:,j)
67     }
68 }
69 
70