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
|
//------------------------------------------------------------------------------
// GB_hyper.h: definitions for hypersparse matrices and related methods
//------------------------------------------------------------------------------
// SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2022, All Rights Reserved.
// SPDX-License-Identifier: Apache-2.0
//------------------------------------------------------------------------------
#ifndef GB_HYPER_H
#define GB_HYPER_H
GB_PUBLIC
int64_t GB_nvec_nonempty // return # of non-empty vectors
(
const GrB_Matrix A, // input matrix to examine
GB_Context Context
) ;
GrB_Info GB_hyper_realloc
(
GrB_Matrix A, // matrix with hyperlist to reallocate
int64_t plen_new, // new size of A->p and A->h
GB_Context Context
) ;
GrB_Info GB_conform_hyper // conform a matrix to sparse/hypersparse
(
GrB_Matrix A, // matrix to conform
GB_Context Context
) ;
GrB_Info GB_hyper_prune
(
// output, not allocated on input:
int64_t *restrict *p_Ap, size_t *p_Ap_size, // size plen+1
int64_t *restrict *p_Ah, size_t *p_Ah_size, // size plen
int64_t *p_nvec, // # of vectors, all nonempty
int64_t *p_plen, // size of Ap and Ah
// input, not modified
const int64_t *Ap_old, // size nvec_old+1
const int64_t *Ah_old, // size nvec_old
const int64_t nvec_old, // original number of vectors
GB_Context Context
) ;
GrB_Info GB_hypermatrix_prune
(
GrB_Matrix A, // matrix to prune
GB_Context Context
) ;
GrB_Info GB_hyper_hash_build // construct A->Y if not already constructed
(
GrB_Matrix A,
GB_Context Context
) ;
#include "GB_hyper_hash_lookup.h"
//------------------------------------------------------------------------------
// GB_lookup: find k so that j == Ah [k], without using the A->Y hyper_hash
//------------------------------------------------------------------------------
// For a sparse, bitmap, or full matrix j == k.
// For a hypersparse matrix, find k so that j == Ah [k], if it
// appears in the list.
// k is not needed by the caller, just pstart, pend, pleft, and found.
// Once k is found, find pstart and pend, the start and end of the vector.
// pstart and pend are defined for all sparsity structures: hypersparse,
// sparse, bitmap, or full.
// With the introduction of the hyper_hash, this is used only when the
// hyper_hash is too costly to build.
static inline bool GB_lookup // find j = Ah [k]
(
// input:
const bool A_is_hyper, // true if A is hypersparse
const int64_t *restrict Ah, // A->h [0..A->nvec-1]: list of vectors
const int64_t *restrict Ap, // A->p [0..A->nvec ]: pointers to vectors
const int64_t avlen, // A->vlen
// input/output:
int64_t *restrict pleft, // on input: look in A->h [pleft..pright].
// on output: pleft == k if found.
// input:
int64_t pright, // normally A->nvec-1, but can be trimmed
const int64_t j, // vector to find, as j = Ah [k]
// output:
int64_t *restrict pstart, // start of vector: Ap [k]
int64_t *restrict pend // end of vector: Ap [k+1]
)
{
if (A_is_hyper)
{
// binary search of Ah [pleft...pright] for the value j
bool found ;
GB_BINARY_SEARCH (j, Ah, (*pleft), pright, found) ; // ok (historical)
if (found)
{
// j appears in the hyperlist at Ah [pleft]
// k = (*pleft)
(*pstart) = Ap [(*pleft)] ;
(*pend) = Ap [(*pleft)+1] ;
}
else
{
// j does not appear in the hyperlist Ah
// k = -1
(*pstart) = -1 ;
(*pend) = -1 ;
}
return (found) ;
}
else
{
// A is sparse, bitmap, or full; j always appears
// k = j
(*pstart) = GBP (Ap, j, avlen) ;
(*pend) = GBP (Ap, j+1, avlen) ;
return (true) ;
}
}
#endif
|