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