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