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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
//------------------------------------------------------------------------------
// GB_cumsum1: cumlative sum of an array (single threaded)
//------------------------------------------------------------------------------
// SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2025, All Rights Reserved.
// SPDX-License-Identifier: Apache-2.0
//------------------------------------------------------------------------------
// Compute the cumulative sum of an array count[0:n], of size n+1:
// count = cumsum ([0 count[0:n-1]]) ;
// That is, count [j] on input is overwritten with sum (count [0..j-1]).
// On input, count [n] is not accessed and is implicitly zero on input.
// On output, count [n] is the total sum.
#ifndef GB_CUMSUM1_H
#define GB_CUMSUM1_H
//------------------------------------------------------------------------------
// GB_cumsum1_64: uint64_t variant
//------------------------------------------------------------------------------
static inline bool GB_cumsum1_64 // cumulative sum of an array
(
uint64_t *restrict count, // size n+1, input/output
const int64_t n
)
{
//--------------------------------------------------------------------------
// check inputs
//--------------------------------------------------------------------------
ASSERT (count != NULL) ;
ASSERT (n >= 0) ;
//--------------------------------------------------------------------------
// count = cumsum ([0 count[0:n-1]]) ;
//--------------------------------------------------------------------------
uint64_t s = 0 ;
for (int64_t i = 0 ; i < n ; i++)
{
uint64_t c = count [i] ;
count [i] = s ;
s += c ;
}
count [n] = s ;
return (true) ; // do not check for integer overflow
}
//------------------------------------------------------------------------------
// GB_cumsum1_32: uint32_t variant
//------------------------------------------------------------------------------
// Returns true if successful, false if integer overflow occurs.
static inline bool GB_cumsum1_32 // cumulative sum of an array
(
uint32_t *restrict count, // size n+1, input/output
const int64_t n
)
{
//--------------------------------------------------------------------------
// check inputs
//--------------------------------------------------------------------------
ASSERT (count != NULL) ;
ASSERT (n >= 0) ;
//--------------------------------------------------------------------------
// check for overflow
//--------------------------------------------------------------------------
uint64_t s = 0 ;
for (int64_t i = 0 ; i < n ; i++)
{
s += count [i] ;
if (s > UINT32_MAX)
{
return (false) ;
}
}
//--------------------------------------------------------------------------
// count = cumsum ([0 count[0:n-1]]) ;
//--------------------------------------------------------------------------
s = 0 ;
for (int64_t i = 0 ; i < n ; i++)
{
uint64_t c = count [i] ;
count [i] = s ;
s += c ;
}
count [n] = s ;
return (true) ;
}
//------------------------------------------------------------------------------
// GB_cumsum1_float: float variant
//------------------------------------------------------------------------------
static inline bool GB_cumsum1_float // cumulative sum of an array
(
float *restrict count, // size n+1, input/output
const int64_t n
)
{
//--------------------------------------------------------------------------
// check inputs
//--------------------------------------------------------------------------
ASSERT (count != NULL) ;
ASSERT (n >= 0) ;
//--------------------------------------------------------------------------
// count = cumsum ([0 count[0:n-1]]) ;
//--------------------------------------------------------------------------
double s = 0 ;
for (int64_t i = 0 ; i < n ; i++)
{
double c = count [i] ;
count [i] = s ;
s += c ;
}
count [n] = s ;
return (true) ;
}
#endif
|
