1 //------------------------------------------------------------------------------ 2 // GB_AxB_saxpy3_fineHash_M_phase2: C<M>=A*B, fine Hash, phase2 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 // phase2: fine hash task, C(:,j)<M(:,j)>=A*B(:,j) 13 //-------------------------------------------------------------------------- 14 15 // M is sparse and scattered into Hf 16 17 // Given Hf [hash] split into (h,f) 18 19 // h == 0 , f == 0 : unlocked, unoccupied. C(i,j) ignored 20 // h == i+1, f == 1 : unlocked, occupied by M(i,j)=1. 21 // C(i,j) has not been seen. 22 // Hx is not initialized. 23 // h == i+1, f == 2 : unlocked, occupied by C(i,j), M(i,j)=1 24 // Hx is initialized. 25 // h == ..., f == 3 : locked. 26 27 // 0 -> 0 : to ignore, if M(i,j)=0 28 // 1 -> 3 : to lock, if i seen for first time 29 // 2 -> 3 : to lock, if i seen already 30 // 3 -> 2 : to unlock; now i has been seen 31 32 GB_GET_M_j_RANGE (16) ; // get first and last in M(:,j) 33 for ( ; pB < pB_end ; pB++) // scan B(:,j) 34 { 35 GB_GET_B_kj_INDEX ; // get index k of B(k,j) 36 GB_GET_A_k ; // get A(:,k) 37 if (aknz == 0) continue ; 38 GB_GET_B_kj ; // bkj = B(k,j) 39 #define GB_IKJ \ 40 { \ 41 GB_MULT_A_ik_B_kj ; /* t = A(i,k) * B(k,j) */ \ 42 int64_t i1 = i + 1 ; /* i1 = one-based index */ \ 43 int64_t i_unlocked = (i1 << 2) + 2 ; /* (i+1,2) */ \ 44 for (GB_HASH (i)) /* find i in hash table */ \ 45 { \ 46 int64_t hf ; \ 47 GB_ATOMIC_READ \ 48 hf = Hf [hash] ; /* grab the entry */ \ 49 if (GB_HAS_ATOMIC && (hf == i_unlocked)) \ 50 { \ 51 /* Hx [hash] += t */ \ 52 GB_ATOMIC_UPDATE_HX (hash, t) ; \ 53 break ; /* C(i,j) has been updated */ \ 54 } \ 55 if (hf == 0) break ; /* M(i,j)=0; ignore Cij */ \ 56 if ((hf >> 2) == i1) /* if true, i found */ \ 57 { \ 58 do /* lock the entry */ \ 59 { \ 60 /* do this atomically: */ \ 61 /* { hf = Hf [hash] ; Hf [hash] |= 3 ; }*/ \ 62 GB_ATOMIC_CAPTURE_INT64_OR (hf,Hf[hash],3);\ 63 } while ((hf & 3) == 3) ; /* own: f=1,2 */ \ 64 if ((hf & 3) == 1) /* f == 1 */ \ 65 { \ 66 /* C(i,j) is a new entry in C(:,j) */ \ 67 /* Hx [hash] = t */ \ 68 GB_ATOMIC_WRITE_HX (hash, t) ; \ 69 } \ 70 else /* f == 2 */ \ 71 { \ 72 /* C(i,j) already appears in C(:,j) */ \ 73 /* Hx [hash] += t */ \ 74 GB_ATOMIC_UPDATE_HX (hash, t) ; \ 75 } \ 76 GB_ATOMIC_WRITE \ 77 Hf [hash] = i_unlocked ; /* unlock entry */ \ 78 break ; \ 79 } \ 80 } \ 81 } 82 GB_SCAN_M_j_OR_A_k (A_ok_for_binary_search) ; 83 #undef GB_IKJ 84 } 85 } 86 87