1 //------------------------------------------------------------------------------
2 // GB_Monoid_new: create a GrB_Monoid
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 // Create a monoid with an operator, (optionally) an identity value, and
11 // (optionally) a terminal value. If using a built-in operator, a duplicate
12 // boolean operator is first replaced with its unique equivalent. If the
13 // operator is built-in and corresponds to a known monoid, then the identity
14 // value and terminal value provided on input are silently ignored, and the
15 // known values are used instead. This is to allow the use of the hard-coded
16 // functions for built-in monoids.
17
18 // User-defined monoids may have a NULL terminal value, which denotes that the
19 // monoid does not have a terminal value.
20
21 #include "GB.h"
22 #include "GB_binop.h"
23
GB_Monoid_new(GrB_Monoid * monoid,GrB_BinaryOp op,const void * identity,const void * terminal,GB_Type_code idcode,GB_Context Context)24 GrB_Info GB_Monoid_new // create a monoid
25 (
26 GrB_Monoid *monoid, // handle of monoid to create
27 GrB_BinaryOp op, // binary operator of the monoid
28 const void *identity, // identity value, if any
29 const void *terminal, // terminal value, if any (may be NULL)
30 GB_Type_code idcode, // identity and terminal type code
31 GB_Context Context
32 )
33 {
34
35 //--------------------------------------------------------------------------
36 // check inputs
37 //--------------------------------------------------------------------------
38
39 GB_RETURN_IF_NULL (monoid) ;
40 (*monoid) = NULL ;
41 GB_RETURN_IF_NULL (identity) ;
42 GB_RETURN_IF_NULL_OR_FAULTY (op) ;
43
44 ASSERT_BINARYOP_OK (op, "op for monoid", GB0) ;
45 ASSERT (idcode <= GB_UDT_code) ;
46
47 //--------------------------------------------------------------------------
48 // rename built-in binary operators
49 //--------------------------------------------------------------------------
50
51 // If the user requests the creation of a monoid based on a duplicate
52 // built-in binary operator, the unique boolean operator is used instead.
53 // See also GB_boolean_rename, which does this for opcodes, not operators.
54
55 op = GB_boolean_rename_op (op) ;
56 ASSERT_BINARYOP_OK (op, "revised op", GB0) ;
57
58 //--------------------------------------------------------------------------
59 // continue checking inputs
60 //--------------------------------------------------------------------------
61
62 // check operator types; all must be identical, and the operator cannot
63 // be positional
64 if (op->xtype != op->ztype || op->ytype != op->ztype ||
65 GB_OP_IS_POSITIONAL (op))
66 {
67 return (GrB_DOMAIN_MISMATCH) ;
68 }
69
70 // The idcode must match the monoid->op->ztype->code for built-in types,
71 // and this can be rigourously checked. For all user-defined types,
72 // identity is a mere void * pointer, and its actual type cannot be
73 // compared with the input op->ztype parameter. Only the type code,
74 // GB_UDT_code, can be checked to see if it matches. In
75 // that case, all that is known is that identity is a void * pointer that
76 // points to something; it must a scalar of the proper user-defined type.
77
78 GB_Type_code zcode = op->ztype->code ;
79 if (idcode != zcode)
80 {
81 return (GrB_DOMAIN_MISMATCH) ;
82 }
83
84 //--------------------------------------------------------------------------
85 // create the monoid
86 //--------------------------------------------------------------------------
87
88 // allocate the monoid
89 size_t header_size ;
90 (*monoid) = GB_MALLOC (1, struct GB_Monoid_opaque, &header_size) ;
91 if (*monoid == NULL)
92 {
93 // out of memory
94 return (GrB_OUT_OF_MEMORY) ;
95 }
96
97 // initialize the monoid
98 GrB_Monoid mon = *monoid ;
99 mon->magic = GB_MAGIC ;
100 mon->header_size = header_size ;
101 mon->op = op ;
102 size_t zsize = op->ztype->size ;
103 mon->identity = NULL ; // defined below (if present)
104 mon->terminal = NULL ; // defined below (if present)
105 mon->identity_size = 0 ;
106 mon->terminal_size = 0 ;
107
108 //--------------------------------------------------------------------------
109 // allocation of identity and terminal values
110 //--------------------------------------------------------------------------
111
112 // allocate the identity value
113 #define GB_ALLOC_IDENTITY \
114 { \
115 mon->identity = GB_MALLOC (zsize, GB_void, &(mon->identity_size)) ; \
116 if (mon->identity == NULL) \
117 { \
118 /* out of memory */ \
119 GB_FREE (&(mon->terminal), mon->terminal_size) ; \
120 GB_FREE (monoid, header_size) ; \
121 return (GrB_OUT_OF_MEMORY) ; \
122 } \
123 }
124
125 // allocate the terminal value
126 #define GB_ALLOC_TERMINAL \
127 { \
128 mon->terminal = GB_MALLOC (zsize, GB_void, &(mon->terminal_size)) ; \
129 if (mon->terminal == NULL) \
130 { \
131 /* out of memory */ \
132 GB_FREE (&(mon->identity), mon->identity_size) ; \
133 GB_FREE (monoid, header_size) ; \
134 return (GrB_OUT_OF_MEMORY) ; \
135 } \
136 }
137
138 //--------------------------------------------------------------------------
139 // create a user-defined monoid based on a known built-in monoid
140 //--------------------------------------------------------------------------
141
142 bool done = false ;
143
144 // If the user requests the creation of a monoid based on a built-in
145 // operator that corresponds to known built-in monoid, the identity and
146 // terminal values provided by the user to GrB_Monoid_new are ignored,
147 // since these are all handled by the same hard-coded functions as the
148 // built-in monoids based on the same operator.
149
150 // All of the monoids created in the switch statement below have non-NULL
151 // identity values; some have terminal values and some do not.
152
153 // create a monoid with both an identity and a terminal value,
154 // based on a built-in operator that is a known monoid
155 #define GB_IT(ztype,identity_value,terminal_value) \
156 { \
157 GB_ALLOC_TERMINAL ; \
158 GB_ALLOC_IDENTITY ; \
159 ztype *identity = (ztype *) mon->identity ; \
160 ztype *terminal = (ztype *) mon->terminal ; \
161 (*identity) = identity_value ; \
162 (*terminal) = terminal_value ; \
163 done = true ; \
164 } \
165 break ;
166
167 // create a monoid with just an identity but no terminal value,
168 // based on a built-in operator that is a known monoid
169 #define GB_IN(ztype,identity_value) \
170 { \
171 GB_ALLOC_IDENTITY ; \
172 ztype *identity = (ztype *) mon->identity ; \
173 (*identity) = identity_value ; \
174 done = true ; \
175 } \
176 break ;
177
178 switch (op->opcode)
179 {
180 case GB_MIN_opcode :
181
182 // MIN monoid: identity is +inf, terminal is -inf
183 // note there is no MIN monoid for complex types
184 switch (zcode)
185 {
186 case GB_INT8_code : GB_IT (int8_t , INT8_MAX , INT8_MIN )
187 case GB_INT16_code : GB_IT (int16_t , INT16_MAX , INT16_MIN )
188 case GB_INT32_code : GB_IT (int32_t , INT32_MAX , INT32_MIN )
189 case GB_INT64_code : GB_IT (int64_t , INT64_MAX , INT64_MIN )
190 case GB_UINT8_code : GB_IT (uint8_t , UINT8_MAX , 0 )
191 case GB_UINT16_code : GB_IT (uint16_t, UINT16_MAX, 0 )
192 case GB_UINT32_code : GB_IT (uint32_t, UINT32_MAX, 0 )
193 case GB_UINT64_code : GB_IT (uint64_t, UINT64_MAX, 0 )
194 case GB_FP32_code : GB_IT (float , INFINITY , -INFINITY )
195 case GB_FP64_code : GB_IT (double , ((double) INFINITY) ,
196 ((double) -INFINITY) )
197 default: ;
198 }
199 break ;
200
201 case GB_MAX_opcode :
202
203 // MAX monoid: identity is -inf, terminal is +inf
204 // note there is no MAX monoid for complex types
205 switch (zcode)
206 {
207 case GB_INT8_code : GB_IT (int8_t , INT8_MIN , INT8_MAX )
208 case GB_INT16_code : GB_IT (int16_t , INT16_MIN , INT16_MAX )
209 case GB_INT32_code : GB_IT (int32_t , INT32_MIN , INT32_MAX )
210 case GB_INT64_code : GB_IT (int64_t , INT64_MIN , INT64_MAX )
211 case GB_UINT8_code : GB_IT (uint8_t , 0 , UINT8_MAX )
212 case GB_UINT16_code : GB_IT (uint16_t, 0 , UINT16_MAX)
213 case GB_UINT32_code : GB_IT (uint32_t, 0 , UINT32_MAX)
214 case GB_UINT64_code : GB_IT (uint64_t, 0 , UINT64_MAX)
215 case GB_FP32_code : GB_IT (float , -INFINITY , INFINITY )
216 case GB_FP64_code : GB_IT (double , ((double) -INFINITY) ,
217 ((double) INFINITY) )
218 default: ;
219 }
220 break ;
221
222 case GB_PLUS_opcode :
223
224 // PLUS monoid: identity is zero, no terminal value
225 switch (zcode)
226 {
227 case GB_INT8_code : GB_IN (int8_t , 0 )
228 case GB_INT16_code : GB_IN (int16_t , 0 )
229 case GB_INT32_code : GB_IN (int32_t , 0 )
230 case GB_INT64_code : GB_IN (int64_t , 0 )
231 case GB_UINT8_code : GB_IN (uint8_t , 0 )
232 case GB_UINT16_code : GB_IN (uint16_t, 0 )
233 case GB_UINT32_code : GB_IN (uint32_t, 0 )
234 case GB_UINT64_code : GB_IN (uint64_t, 0 )
235 case GB_FP32_code : GB_IN (float , 0 )
236 case GB_FP64_code : GB_IN (double , 0 )
237 case GB_FC32_code : GB_IN (GxB_FC32_t, GxB_CMPLXF(0,0) )
238 case GB_FC64_code : GB_IN (GxB_FC64_t, GxB_CMPLX(0,0) )
239 default: ;
240 }
241 break ;
242
243 case GB_TIMES_opcode :
244
245 // TIMES monoid: identity is 1, no terminal value
246 switch (zcode)
247 {
248 case GB_INT8_code : GB_IN (int8_t , 1 )
249 case GB_INT16_code : GB_IN (int16_t , 1 )
250 case GB_INT32_code : GB_IN (int32_t , 1 )
251 case GB_INT64_code : GB_IN (int64_t , 1 )
252 case GB_UINT8_code : GB_IN (uint8_t , 1 )
253 case GB_UINT16_code : GB_IN (uint16_t, 1 )
254 case GB_UINT32_code : GB_IN (uint32_t, 1 )
255 case GB_UINT64_code : GB_IN (uint64_t, 1 )
256 case GB_FP32_code : GB_IN (float , 1 )
257 case GB_FP64_code : GB_IN (double , 1 )
258 case GB_FC32_code : GB_IN (GxB_FC32_t, GxB_CMPLXF(1,0) )
259 case GB_FC64_code : GB_IN (GxB_FC64_t, GxB_CMPLX(1,0) )
260 default: ;
261 }
262 break ;
263
264 case GB_ANY_opcode :
265
266 // ANY monoid: identity is anything, terminal value is anything
267 switch (zcode)
268 {
269 case GB_BOOL_code : GB_IT (bool , 0, 0 )
270 case GB_INT8_code : GB_IT (int8_t , 0, 0 )
271 case GB_INT16_code : GB_IT (int16_t , 0, 0 )
272 case GB_INT32_code : GB_IT (int32_t , 0, 0 )
273 case GB_INT64_code : GB_IT (int64_t , 0, 0 )
274 case GB_UINT8_code : GB_IT (uint8_t , 0, 0 )
275 case GB_UINT16_code : GB_IT (uint16_t, 0, 0 )
276 case GB_UINT32_code : GB_IT (uint32_t, 0, 0 )
277 case GB_UINT64_code : GB_IT (uint64_t, 0, 0 )
278 case GB_FP32_code : GB_IT (float , 0, 0 )
279 case GB_FP64_code : GB_IT (double , 0, 0 )
280 case GB_FC32_code :
281 GB_IT (GxB_FC32_t, GxB_CMPLXF(0,0), GxB_CMPLXF(0,0))
282 case GB_FC64_code :
283 GB_IT (GxB_FC64_t, GxB_CMPLX(0,0), GxB_CMPLX(0,0))
284 default: ;
285 }
286 break ;
287
288 case GB_LOR_opcode :
289
290 // boolean OR monoid: identity is false, terminal is true
291 if (zcode == GB_BOOL_code) GB_IT (bool, false, true)
292
293 case GB_LAND_opcode :
294
295 // boolean AND monoid: identity is true, terminal is false
296 if (zcode == GB_BOOL_code) GB_IT (bool, true, false)
297
298 case GB_LXOR_opcode :
299
300 // boolean XOR monoid: identity is false, no terminal value
301 if (zcode == GB_BOOL_code) GB_IN (bool, false)
302
303 case GB_EQ_opcode :
304
305 // boolean EQ monoid: identity is true, no terminal value
306 if (zcode == GB_BOOL_code) GB_IN (bool, true)
307
308 default : ;
309
310 // monoid identity and terminal value defined below
311 }
312
313 //--------------------------------------------------------------------------
314 // user-defined operators or unknown monoids
315 //--------------------------------------------------------------------------
316
317 // The monoid is based on a user-defined operator, or on a built-in
318 // operator that is not a known monoid. Use the identity and terminal
319 // values provided on input.
320
321 if (!done)
322 {
323 // create the monoid identity value
324 GB_ALLOC_IDENTITY ;
325 memcpy (mon->identity, identity, zsize) ;
326 if (terminal != NULL)
327 {
328 // create the monoid terminal value
329 GB_ALLOC_TERMINAL ;
330 memcpy (mon->terminal, terminal, zsize) ;
331 }
332 }
333
334 ASSERT_MONOID_OK (mon, "new monoid", GB0) ;
335 return (GrB_SUCCESS) ;
336 }
337
338