Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LG_internal.h: include file for use within LAGraph itself
3 : //------------------------------------------------------------------------------
4 :
5 : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
6 : // SPDX-License-Identifier: BSD-2-Clause
7 : //
8 : // For additional details (including references to third party source code and
9 : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
10 : // Contributors.txt for a full list of contributors. Created, in part, with
11 : // funding and support from the U.S. Government (see Acknowledgments.txt file).
12 : // DM22-0790
13 :
14 : // Contributed by Timothy A. Davis, Texas A&M University
15 :
16 : //------------------------------------------------------------------------------
17 :
18 : // These definitions are not meant for the user application that relies on
19 : // LAGraph and/or GraphBLAS. LG_* methods are for internal use in LAGraph.
20 :
21 : #ifndef LG_INTERNAL_H
22 : #define LG_INTERNAL_H
23 :
24 : //------------------------------------------------------------------------------
25 : // include files
26 : //------------------------------------------------------------------------------
27 :
28 : #include <ctype.h>
29 : #include "LAGraph.h"
30 : #undef I
31 :
32 : #if defined ( __linux__ )
33 : #include <malloc.h>
34 : #endif
35 :
36 : #define LG_RESTRICT LAGRAPH_RESTRICT
37 :
38 : //------------------------------------------------------------------------------
39 : // string macros
40 : //------------------------------------------------------------------------------
41 :
42 : #define LG_XSTR(x) LG_STR(x)
43 : #define LG_STR(x) #x
44 :
45 : //------------------------------------------------------------------------------
46 : // string matching
47 : //------------------------------------------------------------------------------
48 :
49 : #define MATCH(s1,s2,n) (strncmp (s1, s2, n) == 0)
50 : #define MATCHNAME(s1,s2) MATCH (s1, s2, LAGRAPH_MAX_NAME_LEN)
51 :
52 : //------------------------------------------------------------------------------
53 : // typedefs
54 : //------------------------------------------------------------------------------
55 :
56 : // LG_void: used in place of (void *), but valid for pointer arithmetic
57 : typedef unsigned char LG_void ;
58 :
59 : //------------------------------------------------------------------------------
60 : // LG_CLEAR_MSG: clear the error msg string
61 : //------------------------------------------------------------------------------
62 :
63 : // When an LAGraph method starts, it first clears the caller's msg string.
64 : #define LG_CLEAR_MSG \
65 : { \
66 : if (msg != NULL) msg [0] = '\0' ; \
67 : }
68 :
69 : //------------------------------------------------------------------------------
70 : // LG_ERROR_MSG: set the error msg string
71 : //------------------------------------------------------------------------------
72 :
73 : // When an LAGraph method encounters an error, it can report details in the
74 : // msg. This is normally done via LG_ASSERT_MSG. For example:
75 :
76 : /*
77 : if (src < 0 || src >= n)
78 : {
79 : LG_ERROR_MSG ("Source node %ld must be in range 0 to n-1, "
80 : "where n = %ld is the number of nodes in the graph.", src, n) ;
81 : return (GrB_INVALID_INDEX) ;
82 : }
83 : // or, with a simpler message:
84 : LG_ASSERT_MSG (src >= 0 && src < n, GrB_INVALID_INDEX, "invalid src node") ;
85 : */
86 :
87 : #define LG_ERROR_MSG(...) \
88 : { \
89 : if (msg != NULL && msg [0] == '\0') \
90 : { \
91 : snprintf (msg, LAGRAPH_MSG_LEN, __VA_ARGS__) ; \
92 : } \
93 : }
94 :
95 : //------------------------------------------------------------------------------
96 : // LG_FREE_WORK: free all workspace
97 : //------------------------------------------------------------------------------
98 :
99 : #ifndef LG_FREE_WORK
100 : #define LG_FREE_WORK ;
101 : #endif
102 :
103 : //------------------------------------------------------------------------------
104 : // LG_FREE_ALL: free all workspace and all output arguments, on error
105 : //------------------------------------------------------------------------------
106 :
107 : #ifndef LG_FREE_ALL
108 : #define LG_FREE_ALL \
109 : { \
110 : LG_FREE_WORK ; \
111 : }
112 : #endif
113 :
114 : //------------------------------------------------------------------------------
115 : // GRB_CATCH: catch an error from GraphBLAS
116 : //------------------------------------------------------------------------------
117 :
118 : // A simple GRB_CATCH macro to be used by GRB_TRY. If an LAGraph function
119 : // wants something else, then #define a GRB_CATCH macro before the #include
120 : // "LG_internal.h" statement.
121 :
122 : #ifndef GRB_CATCH
123 : #define GRB_CATCH(info) \
124 : { \
125 : LG_ERROR_MSG ("GraphBLAS failure (file %s, line %d): info: %d", \
126 : __FILE__, __LINE__, info) ; \
127 : LG_FREE_ALL ; \
128 : return (info) ; \
129 : }
130 : #endif
131 :
132 : //------------------------------------------------------------------------------
133 : // LAGRAPH_CATCH: catch an error from LAGraph
134 : //------------------------------------------------------------------------------
135 :
136 : // A simple LAGRAPH_CATCH macro to be used by LAGRAPH_TRY. If an LAGraph
137 : // function wants something else, then #define a LAGRAPH_CATCH macro before the
138 : // #include "LG_internal.h" statement.
139 :
140 : #ifndef LAGRAPH_CATCH
141 : #define LAGRAPH_CATCH(status) \
142 : { \
143 : LG_ERROR_MSG ("LAGraph failure (file %s, line %d): status: %d", \
144 : __FILE__, __LINE__, status) ; \
145 : LG_FREE_ALL ; \
146 : return (status) ; \
147 : }
148 : #endif
149 :
150 : //------------------------------------------------------------------------------
151 : // LG_ASSERT_MSGF: assert an expression is true, and return if it is false
152 : //------------------------------------------------------------------------------
153 :
154 : // Identical to LG_ASSERT_MSG, except this allows a printf-style formatted
155 : // message.
156 :
157 : #define LG_ASSERT_MSGF(expression,error_status,expression_format,...) \
158 : { \
159 : if (!(expression)) \
160 : { \
161 : LG_ERROR_MSG ("LAGraph failure (file %s, line %d): " \
162 : expression_format, __FILE__, __LINE__, __VA_ARGS__) ; \
163 : LG_FREE_ALL ; \
164 : return (error_status) ; \
165 : } \
166 : }
167 :
168 : //------------------------------------------------------------------------------
169 : // LG_ASSERT_MSG: assert an expression is true, and return if it is false
170 : //------------------------------------------------------------------------------
171 :
172 : // Identical to LG_ASSERT, except this allows a different string to be
173 : // included in the message.
174 :
175 : #define LG_ASSERT_MSG(expression,error_status,expression_message) \
176 : LG_ASSERT_MSGF (expression,error_status,"%s",expression_message)
177 :
178 : //------------------------------------------------------------------------------
179 : // LG_ASSERT: assert an expression is true, and return if it is false
180 : //------------------------------------------------------------------------------
181 :
182 : // LAGraph methods can use this assertion macro for simple errors.
183 :
184 : #define LG_ASSERT(expression, error_status) \
185 : { \
186 : if (!(expression)) \
187 : { \
188 : LG_ERROR_MSG ("LAGraph assertion \"%s\" failed (file %s, line %d):" \
189 : " status: %d", LG_XSTR(expression), __FILE__, __LINE__, \
190 : error_status) ; \
191 : LG_FREE_ALL ; \
192 : return (error_status) ; \
193 : } \
194 : }
195 :
196 : //------------------------------------------------------------------------------
197 : // LG_TRY: check a condition and return on error
198 : //------------------------------------------------------------------------------
199 :
200 : // The msg is not modified. This should be used when an LAGraph method calls
201 : // another one.
202 :
203 : #define LG_TRY(LAGraph_method) \
204 : { \
205 : int LAGraph_status = LAGraph_method ; \
206 : if (LAGraph_status < 0) \
207 : { \
208 : LG_FREE_ALL ; \
209 : return (LAGraph_status) ; \
210 : } \
211 : }
212 :
213 : //------------------------------------------------------------------------------
214 : // LG_CLEAR_MSG_AND_BASIC_ASSERT: clear msg and do basic tests of a graph
215 : //------------------------------------------------------------------------------
216 :
217 : #define LG_CLEAR_MSG_AND_BASIC_ASSERT(G,msg) \
218 : { \
219 : LG_CLEAR_MSG ; \
220 : LG_ASSERT (G != NULL, GrB_NULL_POINTER) ; \
221 : LG_ASSERT_MSG (G->A != NULL, LAGRAPH_INVALID_GRAPH, \
222 : "graph adjacency matrix is NULL") ; \
223 : LG_ASSERT_MSG (G->kind >= LAGraph_ADJACENCY_UNDIRECTED && \
224 : G->kind <= LAGraph_ADJACENCY_DIRECTED, \
225 : LAGRAPH_INVALID_GRAPH, "graph kind invalid") ; \
226 : }
227 :
228 : //------------------------------------------------------------------------------
229 : // FPRINTF: fprintf and check result
230 : //------------------------------------------------------------------------------
231 :
232 : #define FPRINTF(f,...) \
233 : { \
234 : LG_ASSERT_MSG (fprintf (f, __VA_ARGS__) >= 0, \
235 : LAGRAPH_IO_ERROR, "Unable to write to file") ; \
236 : }
237 :
238 : //------------------------------------------------------------------------------
239 : // code development settings
240 : //------------------------------------------------------------------------------
241 :
242 : // turn off debugging; do not edit these three lines
243 : #ifndef NDEBUG
244 : #define NDEBUG
245 : #endif
246 :
247 : // These flags are used for code development. Uncomment them as needed.
248 :
249 : // to turn on debugging, uncomment this line:
250 : // #undef NDEBUG
251 :
252 : #undef ASSERT
253 :
254 : #ifndef NDEBUG
255 :
256 : // debugging enabled
257 : #ifdef MATLAB_MEX_FILE
258 : // debugging when LAGraph is part of a mexFunction
259 : #define ASSERT(x) \
260 : { \
261 : if (!(x)) mexErrMsgTxt ("failure: " __FILE__ " line: ") ; \
262 : }
263 : #else
264 : #include <assert.h>
265 : #define ASSERT(x) assert (x) ;
266 : #endif
267 :
268 : #else
269 :
270 : // debugging disabled
271 : #define ASSERT(x)
272 :
273 : #endif
274 :
275 : //------------------------------------------------------------------------------
276 : // LG_Multiply_size_t: c = a*b but check for overflow
277 : //------------------------------------------------------------------------------
278 :
279 29649 : static bool LG_Multiply_size_t // true if ok, false if overflow
280 : (
281 : size_t *c, // c = a*b, or zero if overflow occurs
282 : const size_t a,
283 : const size_t b
284 : )
285 : {
286 :
287 : ASSERT (c != NULL) ;
288 :
289 29649 : (*c) = 0 ;
290 29649 : if (a == 0 || b == 0)
291 : {
292 1 : return (true) ;
293 : }
294 :
295 29648 : if (a > SIZE_MAX / 2 || b > SIZE_MAX / 2)
296 : {
297 : // a or b are out of range
298 4 : return (false) ;
299 : }
300 :
301 : // a + b is now safe to compute
302 29644 : if ((a + b) > (SIZE_MAX / LAGRAPH_MIN (a,b)))
303 : {
304 : // a * b may overflow
305 1 : return (false) ;
306 : }
307 :
308 : // a * b will not overflow
309 29643 : (*c) = a * b ;
310 29643 : return (true) ;
311 : }
312 :
313 : //------------------------------------------------------------------------------
314 : // Matrix Market format
315 : //------------------------------------------------------------------------------
316 :
317 : // %%MatrixMarket matrix <fmt> <type> <storage> uses the following enums:
318 :
319 : typedef enum
320 : {
321 : MM_coordinate,
322 : MM_array,
323 : }
324 : MM_fmt_enum ;
325 :
326 : typedef enum
327 : {
328 : MM_real,
329 : MM_integer,
330 : MM_complex,
331 : MM_pattern
332 : }
333 : MM_type_enum ;
334 :
335 : typedef enum
336 : {
337 : MM_general,
338 : MM_symmetric,
339 : MM_skew_symmetric,
340 : MM_hermitian
341 : }
342 : MM_storage_enum ;
343 :
344 : // maximum length of each line in the Matrix Market file format
345 :
346 : // The MatrixMarket format specificies a maximum line length of 1024.
347 : // This is currently sufficient for GraphBLAS but will need to be relaxed
348 : // if this function is extended to handle arbitrary user-defined types.
349 : #define MMLEN 1024
350 : #define MAXLINE MMLEN+6
351 :
352 : //------------------------------------------------------------------------------
353 : // LG_PART and LG_PARTITION: definitions for partitioning an index range
354 : //------------------------------------------------------------------------------
355 :
356 : LAGRAPH_PUBLIC extern
357 : int LG_nthreads_outer ; // # of threads to use at the higher level of a nested
358 : // parallel region in LAGraph. Default: 1.
359 :
360 : LAGRAPH_PUBLIC extern
361 : int LG_nthreads_inner ; // # of threads to use at the lower level of a nested
362 : // parallel region, or to use inside GraphBLAS.
363 : // Default: the value obtained by omp_get_max_threads
364 : // if OpenMP is in use, or 1 otherwise.
365 :
366 : // LG_PART and LG_PARTITION: divide the index range 0:n-1 uniformly
367 : // for nthreads. LG_PART(tid,n,nthreads) is the first index for thread tid.
368 : #define LG_PART(tid,n,nthreads) \
369 : (((tid) * ((double) (n))) / ((double) (nthreads)))
370 :
371 : // thread tid will operate on the range k1:(k2-1)
372 : #define LG_PARTITION(k1,k2,n,tid,nthreads) \
373 : k1 = ((tid) == 0 ) ? 0 : LG_PART ((tid), n, nthreads) ; \
374 : k2 = ((tid) == (nthreads)-1) ? (n) : LG_PART ((tid)+1,n, nthreads)
375 :
376 : //------------------------------------------------------------------------------
377 : // LG_eslice: uniform partition of e items to each task
378 : //------------------------------------------------------------------------------
379 :
380 12 : static inline void LG_eslice
381 : (
382 : int64_t *Slice, // array of size ntasks+1
383 : int64_t e, // number items to partition amongst the tasks
384 : const int ntasks // # of tasks
385 : )
386 : {
387 12 : Slice [0] = 0 ;
388 204 : for (int tid = 0 ; tid < ntasks ; tid++)
389 : {
390 192 : Slice [tid] = LG_PART (tid, e, ntasks) ;
391 : }
392 12 : Slice [ntasks] = e ;
393 12 : }
394 :
395 : //------------------------------------------------------------------------------
396 : // definitions for sorting functions
397 : //------------------------------------------------------------------------------
398 :
399 : // All of the LG_qsort_* functions are single-threaded, by design. The
400 : // LG_msort* functions are parallel. None of these sorting methods are
401 : // guaranteed to be stable. These functions are contributed by Tim Davis, and
402 : // are derived from SuiteSparse:GraphBLAS. Functions named LG_* are not
403 : // meant to be accessible by end users of LAGraph.
404 :
405 : #define LG_BASECASE (64 * 1024)
406 :
407 : //------------------------------------------------------------------------------
408 : // LG_msort1: sort array of size n
409 : //------------------------------------------------------------------------------
410 :
411 : // LG_msort1 sorts an int64_t array of size n in ascending order.
412 :
413 : int LG_msort1
414 : (
415 : // input/output:
416 : int64_t *A_0, // size n array
417 : // input:
418 : const int64_t n,
419 : char *msg
420 : ) ;
421 :
422 : //------------------------------------------------------------------------------
423 : // LG_msort2: sort two arrays of size n
424 : //------------------------------------------------------------------------------
425 :
426 : // LG_msort2 sorts two int64_t arrays A of size n in ascending order.
427 : // The arrays are kept in the same order, where the pair (A_0 [k], A_1 [k]) is
428 : // treated as a single pair. The pairs are sorted by the first value A_0,
429 : // with ties broken by A_1.
430 :
431 : int LG_msort2
432 : (
433 : // input/output:
434 : int64_t *A_0, // size n array
435 : int64_t *A_1, // size n array
436 : // input:
437 : const int64_t n,
438 : char *msg
439 : ) ;
440 :
441 : //------------------------------------------------------------------------------
442 : // LG_msort3: sort three arrays of size n
443 : //------------------------------------------------------------------------------
444 :
445 : // LG_msort3 sorts three int64_t arrays A of size n in ascending order.
446 : // The arrays are kept in the same order, where the triplet (A_0 [k], A_1 [k],
447 : // A_2 [k]) is treated as a single triplet. The triplets are sorted by the
448 : // first value A_0, with ties broken by A_1, and then by A_2 if the values of
449 : // A_0 and A_1 are identical.
450 :
451 : int LG_msort3
452 : (
453 : // input/output:
454 : int64_t *A_0, // size n array
455 : int64_t *A_1, // size n array
456 : int64_t *A_2, // size n array
457 : // input:
458 : const int64_t n,
459 : char *msg
460 : ) ;
461 :
462 : void LG_qsort_1a // sort array A of size 1-by-n
463 : (
464 : int64_t *LG_RESTRICT A_0, // size n array
465 : const int64_t n
466 : ) ;
467 :
468 : void LG_qsort_2 // sort array A of size 2-by-n, using 2 keys (A [0:1][])
469 : (
470 : int64_t *LG_RESTRICT A_0, // size n array
471 : int64_t *LG_RESTRICT A_1, // size n array
472 : const int64_t n
473 : ) ;
474 :
475 : void LG_qsort_3 // sort array A of size 3-by-n, using 3 keys (A [0:2][])
476 : (
477 : int64_t *LG_RESTRICT A_0, // size n array
478 : int64_t *LG_RESTRICT A_1, // size n array
479 : int64_t *LG_RESTRICT A_2, // size n array
480 : const int64_t n
481 : ) ;
482 :
483 : //------------------------------------------------------------------------------
484 : // LG_lt_1: sorting comparator function, one key
485 : //------------------------------------------------------------------------------
486 :
487 : // A [a] and B [b] are keys of one integer.
488 :
489 : // LG_lt_1 returns true if A [a] < B [b], for LG_qsort_1b
490 :
491 : #define LG_lt_1(A_0, a, B_0, b) (A_0 [a] < B_0 [b])
492 :
493 : //------------------------------------------------------------------------------
494 : // LG_lt_2: sorting comparator function, two keys
495 : //------------------------------------------------------------------------------
496 :
497 : // A [a] and B [b] are keys of two integers.
498 :
499 : // LG_lt_2 returns true if A [a] < B [b], for LG_qsort_2 and LG_msort_2b
500 :
501 : #define LG_lt_2(A_0, A_1, a, B_0, B_1, b) \
502 : ( \
503 : (A_0 [a] < B_0 [b]) ? \
504 : ( \
505 : true \
506 : ) \
507 : : \
508 : ( \
509 : (A_0 [a] == B_0 [b]) ? \
510 : ( \
511 : /* primary key is the same; tie-break on the 2nd key */ \
512 : (A_1 [a] < B_1 [b]) \
513 : ) \
514 : : \
515 : ( \
516 : false \
517 : ) \
518 : ) \
519 : )
520 :
521 : //------------------------------------------------------------------------------
522 : // LG_lt_3: sorting comparator function, three keys
523 : //------------------------------------------------------------------------------
524 :
525 : // A [a] and B [b] are keys of three integers.
526 :
527 : // LG_lt_3 returns true if A [a] < B [b], for LG_qsort_3 and LG_msort_3b
528 :
529 : #define LG_lt_3(A_0, A_1, A_2, a, B_0, B_1, B_2, b) \
530 : ( \
531 : (A_0 [a] < B_0 [b]) ? \
532 : ( \
533 : true \
534 : ) \
535 : : \
536 : ( \
537 : (A_0 [a] == B_0 [b]) ? \
538 : ( \
539 : /* primary key is the same; tie-break on the 2nd and 3rd key */ \
540 : LG_lt_2 (A_1, A_2, a, B_1, B_2, b) \
541 : ) \
542 : : \
543 : ( \
544 : false \
545 : ) \
546 : ) \
547 : )
548 :
549 : //------------------------------------------------------------------------------
550 : // LG_eq_*: sorting comparator function, three keys
551 : //------------------------------------------------------------------------------
552 :
553 : // A [a] and B [b] are keys of two or three integers.
554 : // LG_eq_* returns true if A [a] == B [b]
555 :
556 : #define LG_eq_3(A_0, A_1, A_2, a, B_0, B_1, B_2, b) \
557 : ( \
558 : (A_0 [a] == B_0 [b]) && \
559 : (A_1 [a] == B_1 [b]) && \
560 : (A_2 [a] == B_2 [b]) \
561 : )
562 :
563 : #define LG_eq_2(A_0, A_1, a, B_0, B_1, b) \
564 : ( \
565 : (A_0 [a] == B_0 [b]) && \
566 : (A_1 [a] == B_1 [b]) \
567 : )
568 :
569 : #define LG_eq_1(A_0, a, B_0, b) \
570 : ( \
571 : (A_0 [a] == B_0 [b]) \
572 : )
573 :
574 : //------------------------------------------------------------------------------
575 : // count entries on the diagonal of a matrix
576 : //------------------------------------------------------------------------------
577 :
578 : int LG_nself_edges
579 : (
580 : // output
581 : int64_t *nself_edges, // # of entries
582 : // input
583 : GrB_Matrix A, // matrix to count
584 : char *msg // error message
585 : ) ;
586 :
587 : //------------------------------------------------------------------------------
588 : // simple and portable random number generator (internal use only)
589 : //------------------------------------------------------------------------------
590 :
591 : #define LG_RANDOM15_MAX 32767
592 : #define LG_RANDOM60_MAX ((1ULL << 60) -1)
593 :
594 : // return a random number between 0 and LG_RANDOM15_MAX
595 : GrB_Index LG_Random15 (uint64_t *seed) ;
596 :
597 : // return a random uint64_t, in range 0 to LG_RANDOM60_MAX
598 : GrB_Index LG_Random60 (uint64_t *seed) ;
599 :
600 : //------------------------------------------------------------------------------
601 : // LG_KindName: return the name of a kind
602 : //------------------------------------------------------------------------------
603 :
604 : // LG_KindName: return the name of a graph kind. For example, if given
605 : // LAGraph_ADJACENCY_UNDIRECTED, the string "undirected" is returned.
606 :
607 : int LG_KindName
608 : (
609 : // output:
610 : char *name, // name of the kind (user provided array of size at least
611 : // LAGRAPH_MAX_NAME_LEN)
612 : // input:
613 : LAGraph_Kind kind, // graph kind
614 : char *msg
615 : ) ;
616 :
617 : //------------------------------------------------------------------------------
618 :
619 : // # of entries to print for LAGraph_Matrix_Print and LAGraph_Vector_Print
620 : #define LG_SHORT_LEN 30
621 :
622 : #endif
|
