1 //------------------------------------------------------------------------------
2 // GB_Pending.h: operations for pending tuples
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 #ifndef GB_PENDING_H
11 #define GB_PENDING_H
12 #include "GB.h"
13
14 //------------------------------------------------------------------------------
15 // GB_Pending functions
16 //------------------------------------------------------------------------------
17
18 bool GB_Pending_alloc // create a list of pending tuples
19 (
20 GB_Pending *PHandle, // output
21 GrB_Type type, // type of pending tuples
22 GrB_BinaryOp op, // operator for assembling pending tuples
23 bool is_matrix, // true if Pending->j must be allocated
24 int64_t nmax // # of pending tuples to hold
25 ) ;
26
27 bool GB_Pending_realloc // reallocate a list of pending tuples
28 (
29 GB_Pending *PHandle, // Pending tuple list to reallocate
30 int64_t nnew, // # of new tuples to accomodate
31 GB_Context Context
32 ) ;
33
34 void GB_Pending_free // free a list of pending tuples
35 (
36 GB_Pending *PHandle
37 ) ;
38
39 //------------------------------------------------------------------------------
40 // GB_Pending_ensure: make sure the list of pending tuples is large enough
41 //------------------------------------------------------------------------------
42
43 // create or reallocate a list of pending tuples
44
GB_Pending_ensure(GB_Pending * PHandle,GrB_Type type,GrB_BinaryOp op,bool is_matrix,int64_t nnew,GB_Context Context)45 static inline bool GB_Pending_ensure
46 (
47 GB_Pending *PHandle, // input/output
48 GrB_Type type, // type of pending tuples
49 GrB_BinaryOp op, // operator for assembling pending tuples
50 bool is_matrix, // true if Pending->j must be allocated
51 int64_t nnew, // # of pending tuples to add
52 GB_Context Context
53 )
54 {
55
56 //--------------------------------------------------------------------------
57 // check inputs
58 //--------------------------------------------------------------------------
59
60 ASSERT (PHandle != NULL) ;
61
62 //--------------------------------------------------------------------------
63 // ensure the list of pending tuples is large enough
64 //--------------------------------------------------------------------------
65
66 if ((*PHandle) == NULL)
67 {
68 return (GB_Pending_alloc (PHandle, type, op, is_matrix, nnew)) ;
69 }
70 else
71 {
72 return (GB_Pending_realloc (PHandle, nnew, Context)) ;
73 }
74 }
75
76 //------------------------------------------------------------------------------
77 // GB_Pending_add: add an entry A(i,j) to the list of pending tuples
78 //------------------------------------------------------------------------------
79
GB_Pending_add(GB_Pending * PHandle,const GB_void * scalar,const GrB_Type type,const GrB_BinaryOp op,const int64_t i,const int64_t j,const bool is_matrix,GB_Context Context)80 static inline bool GB_Pending_add // add a tuple to the list
81 (
82 GB_Pending *PHandle, // Pending tuples to create or append
83 const GB_void *scalar, // scalar to add to the pending tuples
84 const GrB_Type type, // scalar type, if list is created
85 const GrB_BinaryOp op, // new Pending->op, if list is created
86 const int64_t i, // index into vector
87 const int64_t j, // vector index
88 const bool is_matrix, // allocate Pending->j, if list is created
89 GB_Context Context
90 )
91 {
92
93 //--------------------------------------------------------------------------
94 // check inputs
95 //--------------------------------------------------------------------------
96
97 ASSERT (PHandle != NULL) ;
98
99 //--------------------------------------------------------------------------
100 // allocate the Pending tuples, or ensure existing list is large enough
101 //--------------------------------------------------------------------------
102
103 if (!GB_Pending_ensure (PHandle, type, op, is_matrix, 1, Context))
104 {
105 return (false) ;
106 }
107 GB_Pending Pending = (*PHandle) ;
108 int64_t n = Pending->n ;
109
110 ASSERT (Pending->type == type) ;
111 ASSERT (Pending->nmax > 0 && n < Pending->nmax) ;
112 ASSERT (Pending->i != NULL && Pending->x != NULL) ;
113 ASSERT ((is_matrix) == (Pending->j != NULL)) ;
114
115 //--------------------------------------------------------------------------
116 // keep track of whether or not the pending tuples are already sorted
117 //--------------------------------------------------------------------------
118
119 int64_t *restrict Pending_i = Pending->i ;
120 int64_t *restrict Pending_j = Pending->j ;
121
122 if (n > 0 && Pending->sorted)
123 {
124 int64_t ilast = Pending_i [n-1] ;
125 int64_t jlast = (Pending_j != NULL) ? Pending_j [n-1] : 0 ;
126 Pending->sorted = (jlast < j) || (jlast == j && ilast <= i) ;
127 }
128
129 //--------------------------------------------------------------------------
130 // add the (i,j,scalar) or just (i,scalar) if Pending->j is NULL
131 //--------------------------------------------------------------------------
132
133 Pending_i [n] = i ;
134 if (Pending_j != NULL)
135 {
136 Pending_j [n] = j ;
137 }
138 size_t size = type->size ;
139 GB_void *restrict Pending_x = Pending->x ;
140 memcpy (Pending_x +(n*size), scalar, size) ;
141 Pending->n++ ;
142
143 return (true) ; // success
144 }
145
146 //------------------------------------------------------------------------------
147 // add (iC,jC,aij) or just (iC,aij) if Pending_j is NULL
148 //------------------------------------------------------------------------------
149
150 // GB_PENDING_INSERT(aij) is used by GB_subassign_* to insert a pending tuple,
151 // in phase 2. The list has already been reallocated after phase 1 to hold all
152 // the new pending tuples, so GB_Pending_realloc is not required.
153
154 #define GB_PENDING_INSERT(aij) \
155 if (task_sorted) \
156 { \
157 if (!((jlast < jC) || (jlast == jC && ilast <= iC))) \
158 { \
159 task_sorted = false ; \
160 } \
161 } \
162 Pending_i [n] = iC ; \
163 if (Pending_j != NULL) Pending_j [n] = jC ; \
164 memcpy (Pending_x +(n*asize), (aij), asize) ; \
165 n++ ; \
166 ilast = iC ; \
167 jlast = jC ;
168
169 //------------------------------------------------------------------------------
170 // GB_shall_block: see if the matrix should be finished
171 //------------------------------------------------------------------------------
172
173 // returns true if GB_Matrix_wait should be done
174
GB_shall_block(GrB_Matrix A)175 static inline bool GB_shall_block
176 (
177 GrB_Matrix A
178 )
179 {
180
181 if (!GB_ANY_PENDING_WORK (A))
182 {
183 // no pending work, so no need to block
184 return (false) ;
185 }
186 double npending = (double) GB_Pending_n (A) ;
187 double anzmax = ((double) A->vlen) * ((double) A->vdim) ;
188 bool many_pending = (npending >= anzmax) ;
189 bool blocking = (GB_Global_mode_get ( ) == GrB_BLOCKING) ;
190 return (many_pending || blocking) ;
191 }
192
193 #endif
194
195