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