1 //------------------------------------------------------------------------------ 2 // GB_AxB_saxpy3_coarseHash_phase1: symbolic coarse Hash, optional dense mask 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 // phase1: coarse hash task, C=A*B, or C<#M>=A*B if M is dense 14 //-------------------------------------------------------------------------- 15 16 // Initially, Hf [...] < mark for all of Hf. 17 // Let f = Hf [hash] and h = Hi [hash] 18 19 // f < mark : unoccupied. 20 // h == i, f == mark : occupied with C(i,j) 21 22 // The mask M can be optionally checked, if it is packed (full, bitmap, or 23 // sparse/hyper with all entries present and not jumbled) and checked in 24 // place. This method is not used if M is present and sparse. 25 26 for (int64_t kk = kfirst ; kk <= klast ; kk++) 27 { 28 GB_GET_B_j ; // get B(:,j) 29 Cp [kk] = 0 ; 30 31 //---------------------------------------------------------------------- 32 // special case when B(:,j) is empty 33 //---------------------------------------------------------------------- 34 35 #if ( GB_B_IS_SPARSE || GB_B_IS_HYPER ) 36 if (bjnz == 0) continue ; 37 #endif 38 39 //---------------------------------------------------------------------- 40 // get M(:,j), or handle the case when B(:,j) has one entry 41 //---------------------------------------------------------------------- 42 43 #ifdef GB_CHECK_MASK_ij 44 45 // The mask M is packed (full, bitmap, or sparse/hyper and not 46 // jumbled, with all entries present in the entire matrix). Get 47 // pointers Mjb and Mjx into the M(:,j) vector. 48 GB_GET_M_j 49 const M_TYPE *restrict Mjx = Mask_struct ? NULL : 50 ((M_TYPE *) Mx) + (M_SIZE * pM_start) ; 51 const int8_t *restrict Mjb = M_is_bitmap ? (Mb+pM_start) : NULL ; 52 53 #else 54 55 // M is not present 56 #if ( GB_A_IS_SPARSE || GB_A_IS_HYPER ) 57 if (bjnz == 1) 58 { 59 GB_GET_B_kj_INDEX ; // get index k of B(k,j) 60 GB_GET_A_k ; // get A(:,k) 61 Cp [kk] = aknz ; 62 continue ; 63 } 64 #endif 65 66 #endif 67 68 mark++ ; 69 70 //---------------------------------------------------------------------- 71 // count nnz in C(:,j) 72 //---------------------------------------------------------------------- 73 74 int64_t cjnz = 0 ; 75 for ( ; pB < pB_end ; pB++) // scan B(:,j) 76 { 77 GB_GET_B_kj_INDEX ; // get index k of B(k,j) 78 GB_GET_A_k ; // get A(:,k) 79 // scan A(:,k) 80 for (int64_t pA = pA_start ; pA < pA_end ; pA++) 81 { 82 GB_GET_A_ik_INDEX ; // get index i of A(i,k) 83 #ifdef GB_CHECK_MASK_ij 84 // check mask condition and skip if C(i,j) is protected by 85 // the mask 86 GB_CHECK_MASK_ij ; 87 #endif 88 int64_t hash ; 89 bool marked = false ; 90 bool done = false ; 91 for (hash = GB_HASHF (i) ; ; GB_REHASH (hash, i)) 92 { 93 // if the hash entry is marked then it is occuppied with 94 // some row index in the current C(:,j). 95 marked = (Hf [hash] == mark) ; 96 // if found, then the hash entry holds the row index i. 97 bool found = marked && (Hi [hash] == i) ; 98 // if the hash entry is unmarked, then it is empty, and i 99 // is not in the hash table. In this case, C(i,j) is a new 100 // entry. The search terminates if either i is found, or 101 // if an empty (unmarked) slot is found. 102 if (found || !marked) break ; 103 } 104 if (!marked) 105 { 106 // empty slot found, insert C(i,j) 107 Hf [hash] = mark ; 108 Hi [hash] = i ; 109 cjnz++ ; // C(i,j) is a new entry 110 } 111 } 112 } 113 Cp [kk] = cjnz ; // count the entries in C(:,j) 114 } 115 } 116 117