1 //------------------------------------------------------------------------------
2 // GB_Matrix_extractElement: x = A(row,col)
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 // Extract the value of single scalar, x = A(row,col), typecasting from the
11 // type of A to the type of x, as needed.
12
13 // Returns GrB_SUCCESS if A(row,col) is present, and sets x to its value.
14 // Returns GrB_NO_VALUE if A(row,col) is not present, and x is unmodified.
15
16 // This template constructs GrB_Matrix_extractElement_[TYPE] for each of the
17 // 13 built-in types, and the _UDT method for all user-defined types.
18
19 // FUTURE: tolerate zombies
20
GB_EXTRACT_ELEMENT(GB_XTYPE * x,const GrB_Matrix A,GrB_Index row,GrB_Index col)21 GrB_Info GB_EXTRACT_ELEMENT // extract a single entry, x = A(row,col)
22 (
23 GB_XTYPE *x, // scalar to extract, not modified if not found
24 const GrB_Matrix A, // matrix to extract a scalar from
25 GrB_Index row, // row index
26 GrB_Index col // column index
27 )
28 {
29
30 //--------------------------------------------------------------------------
31 // check inputs
32 //--------------------------------------------------------------------------
33
34 GB_RETURN_IF_NULL_OR_FAULTY (A) ;
35 GB_RETURN_IF_NULL (x) ;
36
37 // delete any lingering zombies, assemble any pending tuples, and unjumble
38 if (GB_ANY_PENDING_WORK (A))
39 {
40 GrB_Info info ;
41 GB_WHERE1 (GB_WHERE_STRING) ;
42 GB_BURBLE_START ("GrB_Matrix_extractElement") ;
43 GB_OK (GB_Matrix_wait (A, "A", Context)) ;
44 GB_BURBLE_END ;
45 }
46
47 ASSERT (!GB_ANY_PENDING_WORK (A)) ;
48
49 // look for index i in vector j
50 int64_t i, j, nrows, ncols ;
51 if (A->is_csc)
52 {
53 i = row ;
54 j = col ;
55 nrows = A->vlen ;
56 ncols = A->vdim ;
57 }
58 else
59 {
60 i = col ;
61 j = row ;
62 nrows = A->vdim ;
63 ncols = A->vlen ;
64 }
65
66 // check row and column indices
67 if (row >= nrows || col >= ncols)
68 {
69 return (GrB_INVALID_INDEX) ;
70 }
71
72 // GB_XCODE and A must be compatible
73 GB_Type_code acode = A->type->code ;
74 if (!GB_code_compatible (GB_XCODE, acode))
75 {
76 return (GrB_DOMAIN_MISMATCH) ;
77 }
78
79 if (A->nzmax == 0)
80 {
81 // quick return
82 return (GrB_NO_VALUE) ;
83 }
84
85 //--------------------------------------------------------------------------
86 // find the entry A(i,j)
87 //--------------------------------------------------------------------------
88
89 int64_t pleft ;
90 bool found ;
91 const int64_t *restrict Ap = A->p ;
92
93 if (Ap != NULL)
94 {
95 // A is sparse or hypersparse
96 const int64_t *restrict Ai = A->i ;
97
98 // extract from vector j of a GrB_Matrix
99 int64_t k ;
100 if (A->h != NULL)
101 {
102 // A is hypersparse: look for j in hyperlist A->h [0 ... A->nvec-1]
103 const int64_t *restrict Ah = A->h ;
104 int64_t pleft = 0 ;
105 int64_t pright = A->nvec-1 ;
106 GB_BINARY_SEARCH (j, Ah, pleft, pright, found) ;
107 if (!found)
108 {
109 // vector j is empty
110 return (GrB_NO_VALUE) ;
111 }
112 ASSERT (j == Ah [pleft]) ;
113 k = pleft ;
114 }
115 else
116 {
117 // A is sparse: j = k is the kth vector
118 k = j ;
119 }
120
121 pleft = Ap [k] ;
122 int64_t pright = Ap [k+1] - 1 ;
123
124 // binary search in kth vector for index i
125 // Time taken for this step is at most O(log(nnz(A(:,j))).
126 GB_BINARY_SEARCH (i, Ai, pleft, pright, found) ;
127 }
128 else
129 {
130 // A is bitmap or full
131 pleft = i + j * A->vlen ;
132 const int8_t *restrict Ab = A->b ;
133 if (Ab != NULL)
134 {
135 // A is bitmap
136 found = (Ab [pleft] == 1) ;
137 }
138 else
139 {
140 // A is full
141 found = true ;
142 }
143 }
144
145 //--------------------------------------------------------------------------
146 // extract the element
147 //--------------------------------------------------------------------------
148
149 if (found)
150 {
151 #if !defined ( GB_UDT_EXTRACT )
152 if (GB_XCODE == acode)
153 {
154 // copy the value from A into x, no typecasting, for built-in
155 // types only.
156 GB_XTYPE *restrict Ax = ((GB_XTYPE *) (A->x)) ;
157 (*x) = Ax [pleft] ;
158 }
159 else
160 #endif
161 {
162 // typecast the value from A into x
163 size_t asize = A->type->size ;
164 GB_cast_array ((GB_void *) x, GB_XCODE,
165 ((GB_void *) A->x) +(pleft*asize), acode, NULL, asize, 1, 1) ;
166 }
167 return (GrB_SUCCESS) ;
168 }
169 else
170 {
171 // Entry not found.
172 return (GrB_NO_VALUE) ;
173 }
174 }
175
176 #undef GB_UDT_EXTRACT
177 #undef GB_EXTRACT_ELEMENT
178 #undef GB_XTYPE
179 #undef GB_XCODE
180
181