1 //------------------------------------------------------------------------------
2 // GB_search_for_vector_template: find the vector k that contains p
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 // Given an index p, find k so that Ap [k] <= p && p < Ap [k+1]. The search is
11 // limited to k in the range Ap [kleft ... anvec].
12
13 // A->p can come from any matrix: hypersparse, sparse, bitmap, or full.
14 // For the latter two cases, A->p is NULL.
15
16 #ifndef GB_SEARCH_FOR_VECTOR_H
17 #define GB_SEARCH_FOR_VECTOR_H
18
19 #ifdef GB_KERNEL
20 __device__
GB_search_for_vector_device(const int64_t p,const int64_t * restrict Ap,int64_t kleft,int64_t anvec,int64_t avlen)21 static inline int64_t GB_search_for_vector_device
22 #else
23 static inline int64_t GB_search_for_vector // return vector k that contains p
24 #endif
25 (
26 const int64_t p, // search for vector k that contains p
27 const int64_t *restrict Ap, // vector pointers to search
28 int64_t kleft, // left-most k to search
29 int64_t anvec, // Ap is of size anvec+1
30 int64_t avlen // A->vlen
31 )
32 {
33
34 //--------------------------------------------------------------------------
35 // check inputs
36 //--------------------------------------------------------------------------
37
38 if (Ap == NULL)
39 {
40 // A is full or bitmap
41 ASSERT (p >= 0 && p < avlen * anvec) ;
42 return ((avlen == 0) ? 0 : (p / avlen)) ;
43 }
44
45 // A is sparse
46 ASSERT (p >= 0 && p < Ap [anvec]) ;
47
48 //--------------------------------------------------------------------------
49 // search for k
50 //--------------------------------------------------------------------------
51
52 int64_t k = kleft ;
53 int64_t kright = anvec ;
54 bool found ;
55 GB_SPLIT_BINARY_SEARCH (p, Ap, k, kright, found) ;
56 if (found)
57 {
58 // Ap [k] == p has been found, but if k is an empty vector, then the
59 // next vector will also contain the entry p. In that case, k needs to
60 // be incremented until finding the first non-empty vector for which
61 // Ap [k] == p.
62 ASSERT (Ap [k] == p) ;
63 while (k < anvec-1 && Ap [k+1] == p)
64 {
65 k++ ;
66 }
67 }
68 else
69 {
70 // p has not been found in Ap, so it appears in the middle of Ap [k-1]
71 // ... Ap [k], as computed by the binary search. This is the range of
72 // entries for the vector k-1, so k must be decremented.
73 k-- ;
74 }
75
76 //--------------------------------------------------------------------------
77 // return result
78 //--------------------------------------------------------------------------
79
80 // The entry p must reside in a non-empty vector.
81 ASSERT (k >= 0 && k < anvec) ;
82 ASSERT (Ap [k] <= p && p < Ap [k+1]) ;
83
84 return (k) ;
85 }
86
87 #endif
88
89