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
|
//------------------------------------------------------------------------------
// GB_search_for_vector_template: find the vector k that contains p
//------------------------------------------------------------------------------
// SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2022, All Rights Reserved.
// SPDX-License-Identifier: Apache-2.0
//------------------------------------------------------------------------------
// Given an index p, find k so that Ap [k] <= p && p < Ap [k+1]. The search is
// limited to k in the range Ap [kleft ... anvec].
// A->p can come from any matrix: hypersparse, sparse, bitmap, or full.
// For the latter two cases, A->p is NULL.
#ifndef GB_SEARCH_FOR_VECTOR_H
#define GB_SEARCH_FOR_VECTOR_H
#ifdef GB_CUDA_KERNEL
__device__
static inline int64_t GB_search_for_vector_device
#else
static inline int64_t GB_search_for_vector // return vector k that contains p
#endif
(
const int64_t p, // search for vector k that contains p
const int64_t *restrict Ap, // vector pointers to search
int64_t kleft, // left-most k to search
int64_t anvec, // Ap is of size anvec+1
int64_t avlen // A->vlen
)
{
//--------------------------------------------------------------------------
// check inputs
//--------------------------------------------------------------------------
if (Ap == NULL)
{
// A is full or bitmap
ASSERT (p >= 0 && p < avlen * anvec) ;
return ((avlen == 0) ? 0 : (p / avlen)) ;
}
// A is sparse
ASSERT (p >= 0 && p < Ap [anvec]) ;
//--------------------------------------------------------------------------
// search for k
//--------------------------------------------------------------------------
int64_t k = kleft ;
int64_t kright = anvec ;
bool found ;
GB_SPLIT_BINARY_SEARCH (p, Ap, k, kright, found) ;
if (found)
{
// Ap [k] == p has been found, but if k is an empty vector, then the
// next vector will also contain the entry p. In that case, k needs to
// be incremented until finding the first non-empty vector for which
// Ap [k] == p.
ASSERT (Ap [k] == p) ;
while (k < anvec-1 && Ap [k+1] == p)
{
k++ ;
}
}
else
{
// p has not been found in Ap, so it appears in the middle of Ap [k-1]
// ... Ap [k], as computed by the binary search. This is the range of
// entries for the vector k-1, so k must be decremented.
k-- ;
}
//--------------------------------------------------------------------------
// return result
//--------------------------------------------------------------------------
// The entry p must reside in a non-empty vector.
ASSERT (k >= 0 && k < anvec) ;
ASSERT (Ap [k] <= p && p < Ap [k+1]) ;
return (k) ;
}
#endif
|