1 //------------------------------------------------------------------------------
2 // GB_ijproperties: check I and determine its properties
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 // check a list of indices I and determine its properties
11
12 #include "GB_ij.h"
13
14 // FUTURE:: if limit=0, print a different message. see also setEl, extractEl.
15 #define GB_ICHECK(i,limit) \
16 { \
17 if ((i) < 0 || (i) >= (limit)) \
18 { \
19 GB_ERROR (GrB_INDEX_OUT_OF_BOUNDS, \
20 "index " GBd " out of bounds, must be < " GBd , (i), (limit)) ; \
21 } \
22 }
23
GB_ijproperties(const GrB_Index * I,const int64_t ni,const int64_t nI,const int64_t limit,int * Ikind,int64_t Icolon[3],bool * I_is_unsorted,bool * I_has_dupl,bool * I_is_contig,int64_t * imin_result,int64_t * imax_result,GB_Context Context)24 GrB_Info GB_ijproperties // check I and determine its properties
25 (
26 // input:
27 const GrB_Index *I, // list of indices, or special
28 const int64_t ni, // length I, or special
29 const int64_t nI, // actual length from GB_ijlength
30 const int64_t limit, // I must be in the range 0 to limit-1
31 // input/output:
32 int *Ikind, // kind of I, from GB_ijlength
33 int64_t Icolon [3], // begin:inc:end from GB_ijlength
34 // output:
35 bool *I_is_unsorted, // true if I is out of order
36 bool *I_has_dupl, // true if I has a duplicate entry (undefined
37 // if I is unsorted)
38 bool *I_is_contig, // true if I is a contiguous list, imin:imax
39 int64_t *imin_result, // min (I)
40 int64_t *imax_result, // max (I)
41 GB_Context Context
42 )
43 {
44
45 //--------------------------------------------------------------------------
46 // check inputs
47 //--------------------------------------------------------------------------
48
49 // inputs:
50 // I: a list of indices if Ikind is GB_LIST
51 // limit: the matrix dimension (# of rows or # of columns)
52 // ni: only used if Ikind is GB_LIST: the length of the array I
53 // nI: the length of the list I, either actual or implicit
54
55 // input/output: these can be modified
56 // Ikind: GB_ALL, GB_RANGE, GB_STRIDE (both +/- inc), or GB_LIST
57 // Icolon: begin:inc:end for all but GB_LIST
58
59 // outputs:
60 // I_is_unsorted: true if Ikind == GB_LIST and not in ascending order
61 // I_is_contig: true if I has the form I = begin:end
62 // imin, imax: min (I) and max (I), but only including actual indices
63 // in the sequence. The end value of I=begin:inc:end may not be
64 // reached. For example if I=1:2:10 then max(I)=9, not 10.
65
66 ASSERT (I != NULL) ;
67 ASSERT (limit >= 0) ;
68 ASSERT (limit <= GxB_INDEX_MAX) ;
69 int64_t imin, imax ;
70
71 //--------------------------------------------------------------------------
72 // scan I
73 //--------------------------------------------------------------------------
74
75 // scan the list of indices: check if OK, determine if they are
76 // unsorted, or contiguous, their min and max index, and actual length
77 bool I_unsorted = false ;
78 bool I_has_duplicates = false ;
79 bool I_contig = true ;
80
81 if ((*Ikind) == GB_ALL)
82 {
83
84 //----------------------------------------------------------------------
85 // I = 0:limit-1
86 //----------------------------------------------------------------------
87
88 imin = 0 ;
89 imax = limit-1 ;
90
91 ASSERT (Icolon [GxB_BEGIN] == imin) ;
92 ASSERT (Icolon [GxB_INC ] == 1) ;
93 ASSERT (Icolon [GxB_END ] == imax) ;
94
95 }
96 else if ((*Ikind) == GB_RANGE)
97 {
98
99 //----------------------------------------------------------------------
100 // I = imin:imax
101 //----------------------------------------------------------------------
102
103 imin = Icolon [GxB_BEGIN] ;
104 ASSERT (Icolon [GxB_INC] == 1) ;
105 imax = Icolon [GxB_END ] ;
106
107 if (imin > imax)
108 {
109 // imin > imax: list is empty
110 imin = limit ;
111 imax = -1 ;
112 }
113 else
114 {
115 // check the limits
116 GB_ICHECK (imin, limit) ;
117 GB_ICHECK (imax, limit) ;
118 }
119
120 }
121 else if ((*Ikind) == GB_STRIDE)
122 {
123
124 //----------------------------------------------------------------------
125 // I = imin:iinc:imax
126 //----------------------------------------------------------------------
127
128 // int64_t ibegin = Icolon [GxB_BEGIN] ;
129 int64_t iinc = Icolon [GxB_INC ] ;
130 // int64_t iend = Icolon [GxB_END ] ;
131
132 // if iinc == 1 on input, the kind has been changed to GB_RANGE
133 ASSERT (iinc != 1) ;
134
135 if (iinc == 0)
136 {
137 // stride is zero: list is empty, contiguous, and sorted
138 imin = limit ;
139 imax = -1 ;
140 }
141 else if (iinc > 0)
142 {
143 // stride is positive, get the first and last indices
144 imin = GB_ijlist (I, 0, GB_STRIDE, Icolon) ;
145 imax = GB_ijlist (I, nI-1, GB_STRIDE, Icolon) ;
146 }
147 else
148 {
149 // stride is negative, get the first and last indices
150 imin = GB_ijlist (I, nI-1, GB_STRIDE, Icolon) ;
151 imax = GB_ijlist (I, 0, GB_STRIDE, Icolon) ;
152 }
153
154 if (imin > imax)
155 {
156 // list is empty: so it is contiguous and sorted
157 imin = limit ;
158 imax = -1 ;
159
160 // change this to an empty GB_RANGE
161 (*Ikind) = GB_RANGE ;
162 Icolon [GxB_BEGIN] = imin ;
163 Icolon [GxB_INC ] = 1 ;
164 Icolon [GxB_END ] = imax ;
165
166 }
167 else
168 {
169 // list is contiguous if the stride is 1, not contiguous otherwise
170 I_contig = false ;
171
172 // check the limits
173 GB_ICHECK (imin, limit) ;
174 GB_ICHECK (imax, limit) ;
175 }
176
177 }
178 else // (*Ikind) == GB_LIST
179 {
180
181 //----------------------------------------------------------------------
182 // determine the number of threads to use
183 //----------------------------------------------------------------------
184
185 GB_GET_NTHREADS_MAX (nthreads_max, chunk, Context) ;
186 int nthreads = GB_nthreads (ni, chunk, nthreads_max) ;
187 int ntasks = (nthreads == 1) ? 1 : (8 * nthreads) ;
188 ntasks = GB_IMIN (ntasks, ni) ;
189 ntasks = GB_IMAX (ntasks, 0) ;
190
191 //----------------------------------------------------------------------
192 // I is an array of indices
193 //----------------------------------------------------------------------
194
195 // scan I to find imin and imax, and validate the list. Also determine
196 // if it is sorted or not, and contiguous or not.
197
198 imin = limit ;
199 imax = -1 ;
200
201 // allocate workspace for imin and imax
202 GB_WERK_DECLARE (Work_imin, int64_t) ;
203 GB_WERK_DECLARE (Work_imax, int64_t) ;
204 GB_WERK_PUSH (Work_imin, ntasks, int64_t) ;
205 GB_WERK_PUSH (Work_imax, ntasks, int64_t) ;
206 if (Work_imin == NULL || Work_imax == NULL)
207 {
208 // out of memory
209 GB_WERK_POP (Work_imax, int64_t) ;
210 GB_WERK_POP (Work_imin, int64_t) ;
211 return (GrB_OUT_OF_MEMORY) ;
212 }
213
214 int tid ;
215 #pragma omp parallel for num_threads(nthreads) schedule(dynamic,1) \
216 reduction(||:I_unsorted) reduction(&&:I_contig) \
217 reduction(||:I_has_duplicates)
218 for (tid = 0 ; tid < ntasks ; tid++)
219 {
220 int64_t my_imin = limit ;
221 int64_t my_imax = -1 ;
222 int64_t istart, iend ;
223 GB_PARTITION (istart, iend, ni, tid, ntasks) ;
224 int64_t ilast = (istart == 0) ? -1 : I [istart-1] ;
225 for (int64_t inew = istart ; inew < iend ; inew++)
226 {
227 int64_t i = I [inew] ;
228 if (inew > 0)
229 {
230 if (i < ilast)
231 {
232 // The list I of row indices is out of order, and
233 // C=A(I,J) will need to use qsort to sort each column.
234 // If C=A(I,J)' is computed, however, this flag will be
235 // set back to false, since qsort is not needed if the
236 // result is transposed.
237 I_unsorted = true ;
238 }
239 else if (i == ilast)
240 {
241 // I has at least one duplicate entry. If I is
242 // unsorted, then it is not known if I has duplicates
243 // or not. But if I is sorted, but with duplicates,
244 // then this flag will be true.
245 I_has_duplicates = true ;
246 }
247 if (i != ilast + 1)
248 {
249 I_contig = false ;
250 }
251 }
252 my_imin = GB_IMIN (my_imin, i) ;
253 my_imax = GB_IMAX (my_imax, i) ;
254 ilast = i ;
255 }
256 Work_imin [tid] = my_imin ;
257 Work_imax [tid] = my_imax ;
258 }
259
260 // wrapup
261 for (tid = 0 ; tid < ntasks ; tid++)
262 {
263 imin = GB_IMIN (imin, Work_imin [tid]) ;
264 imax = GB_IMAX (imax, Work_imax [tid]) ;
265 }
266
267 // free workspace
268 GB_WERK_POP (Work_imax, int64_t) ;
269 GB_WERK_POP (Work_imin, int64_t) ;
270
271 #ifdef GB_DEBUG
272 {
273 // check result with one thread
274 bool I_unsorted2 = false ;
275 bool I_has_dupl2 = false ;
276 bool I_contig2 = true ;
277 int64_t imin2 = limit ;
278 int64_t imax2 = -1 ;
279 int64_t ilast = -1 ;
280 for (int64_t inew = 0 ; inew < ni ; inew++)
281 {
282 int64_t i = I [inew] ;
283 if (inew > 0)
284 {
285 if (i < ilast) I_unsorted2 = true ;
286 else if (i == ilast) I_has_dupl2 = true ;
287 if (i != ilast + 1) I_contig2 = false ;
288 }
289 imin2 = GB_IMIN (imin2, i) ;
290 imax2 = GB_IMAX (imax2, i) ;
291 ilast = i ;
292 }
293 ASSERT (I_unsorted == I_unsorted2) ;
294 ASSERT (I_has_duplicates == I_has_dupl2) ;
295 ASSERT (I_contig == I_contig2) ;
296 ASSERT (imin == imin2) ;
297 ASSERT (imax == imax2) ;
298 }
299 #endif
300
301 if (ni > 0)
302 {
303 // check the limits
304 GB_ICHECK (imin, limit) ;
305 GB_ICHECK (imax, limit) ;
306 }
307
308 if (ni == 1)
309 {
310 // a single entry does not need to be sorted
311 ASSERT (I [0] == imin) ;
312 ASSERT (I [0] == imax) ;
313 ASSERT (I_unsorted == false) ;
314 ASSERT (I_contig == true) ;
315 }
316 if (ni == 0)
317 {
318 // the list is empty
319 ASSERT (imin == limit && imax == -1) ;
320 }
321
322 //----------------------------------------------------------------------
323 // change I if it is an explicit contiguous list of stride 1
324 //----------------------------------------------------------------------
325
326 if (I_contig)
327 {
328 // I is a contigous list of stride 1, imin:imax.
329 // change Ikind to GB_ALL if 0:limit-1, or GB_RANGE otherwise
330 if (imin == 0 && imax == limit-1)
331 {
332 (*Ikind) = GB_ALL ;
333 }
334 else
335 {
336 (*Ikind) = GB_RANGE ;
337 }
338 Icolon [GxB_BEGIN] = imin ;
339 Icolon [GxB_INC ] = 1 ;
340 Icolon [GxB_END ] = imax ;
341 }
342 }
343
344 //--------------------------------------------------------------------------
345 // return result
346 //--------------------------------------------------------------------------
347
348 ASSERT (GB_IMPLIES (I_contig, !I_unsorted)) ;
349 ASSERT (((*Ikind) == GB_ALL || (*Ikind) == GB_RANGE) == I_contig) ;
350
351 // I_is_contig is true if the list of row indices is a contiguous list,
352 // imin:imax in MATLAB notation. This is an important special case.
353
354 // I_is_unsorted is true if I is an explicit list, the list is non-empty,
355 // and the indices are not sorted in ascending order.
356
357 (*I_is_contig) = I_contig ;
358 (*I_is_unsorted) = I_unsorted ;
359 (*I_has_dupl) = I_has_duplicates ;
360 (*imin_result) = imin ;
361 (*imax_result) = imax ;
362 return (GrB_SUCCESS) ;
363 }
364
365