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