1 //------------------------------------------------------------------------------
2 // GB_add_phase1: # entries in C=A+B, C<M or !M>=A+B (C is sparse/hyper)
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 // GB_add_phase1 counts the number of entries in each vector of C, for C=A+B,
11 // C<M>=A+B, or C<!M>=A+B and then does a cumulative sum to find Cp.
12 // GB_add_phase1 is preceded by GB_add_phase0, which finds the non-empty
13 // vectors of C. If the mask M is sparse, it is not complemented; only a
14 // bitmap or full M is complemented.
15
16 // C is sparse or hypersparse, as determined by GB_add_sparsity. M, A, and B
17 // can have any sparsity structure, but only a specific set of cases will be
18 // used (see the list in Template/GB_sparse_add_template.c).
19
20 // Cp is constructed here, and either freed by phase2, or transplanted into C.
21
22 #include "GB_add.h"
23 #include "GB_unused.h"
24
GB_add_phase1(int64_t ** Cp_handle,size_t * Cp_size_handle,int64_t * Cnvec_nonempty,const bool A_and_B_are_disjoint,GB_task_struct * restrict TaskList,const int C_ntasks,const int C_nthreads,const int64_t Cnvec,const int64_t * restrict Ch,const int64_t * restrict C_to_M,const int64_t * restrict C_to_A,const int64_t * restrict C_to_B,const bool Ch_is_Mh,const GrB_Matrix M,const bool Mask_struct,const bool Mask_comp,const GrB_Matrix A,const GrB_Matrix B,GB_Context Context)25 GrB_Info GB_add_phase1 // count nnz in each C(:,j)
26 (
27 int64_t **Cp_handle, // output of size Cnvec+1
28 size_t *Cp_size_handle,
29 int64_t *Cnvec_nonempty, // # of non-empty vectors in C
30 const bool A_and_B_are_disjoint, // if true, then A and B are disjoint
31 // tasks from phase0b:
32 GB_task_struct *restrict TaskList, // array of structs
33 const int C_ntasks, // # of tasks
34 const int C_nthreads, // # of threads to use
35 // analysis from phase0:
36 const int64_t Cnvec,
37 const int64_t *restrict Ch,
38 const int64_t *restrict C_to_M,
39 const int64_t *restrict C_to_A,
40 const int64_t *restrict C_to_B,
41 const bool Ch_is_Mh, // if true, then Ch == M->h
42 // original input:
43 const GrB_Matrix M, // optional mask, may be NULL
44 const bool Mask_struct, // if true, use the only structure of M
45 const bool Mask_comp, // if true, use !M
46 const GrB_Matrix A,
47 const GrB_Matrix B,
48 GB_Context Context
49 )
50 {
51
52 //--------------------------------------------------------------------------
53 // check inputs
54 //--------------------------------------------------------------------------
55
56 ASSERT (Cp_handle != NULL) ;
57 ASSERT (Cnvec_nonempty != NULL) ;
58
59 ASSERT_MATRIX_OK_OR_NULL (M, "M for add phase1", GB0) ;
60 ASSERT (!GB_ZOMBIES (M)) ;
61 ASSERT (!GB_JUMBLED (M)) ;
62 ASSERT (!GB_PENDING (M)) ;
63
64 ASSERT_MATRIX_OK (A, "A for add phase1", GB0) ;
65 ASSERT (!GB_ZOMBIES (A)) ;
66 ASSERT (!GB_JUMBLED (A)) ;
67 ASSERT (!GB_PENDING (A)) ;
68
69 ASSERT_MATRIX_OK (B, "B for add phase1", GB0) ;
70 ASSERT (!GB_ZOMBIES (B)) ;
71 ASSERT (!GB_JUMBLED (B)) ;
72 ASSERT (!GB_PENDING (B)) ;
73
74 ASSERT (A->vdim == B->vdim) ;
75
76 //--------------------------------------------------------------------------
77 // allocate the result
78 //--------------------------------------------------------------------------
79
80 (*Cp_handle) = NULL ;
81 int64_t *restrict Cp = NULL ; size_t Cp_size = 0 ;
82 Cp = GB_CALLOC (GB_IMAX (2, Cnvec+1), int64_t, &Cp_size) ;
83 if (Cp == NULL)
84 {
85 // out of memory
86 return (GrB_OUT_OF_MEMORY) ;
87 }
88
89 //--------------------------------------------------------------------------
90 // count the entries in each vector of C
91 //--------------------------------------------------------------------------
92
93 #define GB_PHASE_1_OF_2
94 #include "GB_add_template.c"
95
96 //--------------------------------------------------------------------------
97 // cumulative sum of Cp and fine tasks in TaskList
98 //--------------------------------------------------------------------------
99
100 GB_task_cumsum (Cp, Cnvec, Cnvec_nonempty, TaskList, C_ntasks, C_nthreads,
101 Context) ;
102
103 //--------------------------------------------------------------------------
104 // return the result
105 //--------------------------------------------------------------------------
106
107 (*Cp_handle) = Cp ;
108 (*Cp_size_handle) = Cp_size ;
109 return (GrB_SUCCESS) ;
110 }
111
112