1 //------------------------------------------------------------------------------
2 // GrB_Vector_removeElement: remove a single entry from a vector
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 // Removes a single entry, V (i), from the vector V.
11
12 #include "GB.h"
13
14 #define GB_FREE_ALL ;
15 #define GB_WHERE_STRING "GrB_Vector_removeElement (v, i)"
16
17 //------------------------------------------------------------------------------
18 // GB_removeElement: remove V(i) if it exists
19 //------------------------------------------------------------------------------
20
GB_removeElement(GrB_Vector V,GrB_Index i)21 static inline bool GB_removeElement
22 (
23 GrB_Vector V,
24 GrB_Index i
25 )
26 {
27
28 //--------------------------------------------------------------------------
29 // check inputs
30 //--------------------------------------------------------------------------
31
32 ASSERT (!GB_IS_FULL (V)) ;
33
34 //--------------------------------------------------------------------------
35 // remove V(i)
36 //--------------------------------------------------------------------------
37
38 if (GB_IS_BITMAP (V))
39 {
40
41 //----------------------------------------------------------------------
42 // V is bitmap
43 //----------------------------------------------------------------------
44
45 int8_t *restrict Vb = V->b ;
46 int8_t vb = Vb [i] ;
47 if (vb != 0)
48 {
49 // V(i) is present; remove it
50 Vb [i] = 0 ;
51 V->nvals-- ;
52 }
53 // V(i) is always found, whether present or not
54 return (true) ;
55
56 }
57 else
58 {
59
60 //----------------------------------------------------------------------
61 // V is sparse
62 //----------------------------------------------------------------------
63
64 const int64_t *restrict Vp = V->p ;
65 const int64_t *restrict Vi = V->i ;
66 bool found ;
67
68 // look in V(:)
69 int64_t pleft = 0 ;
70 int64_t pright = Vp [1] ;
71 int64_t vnz = pright ;
72
73 bool is_zombie ;
74 if (vnz == V->vlen)
75 {
76 // V(:) is packed so no binary search is needed to find V(i)
77 pleft = i ;
78 ASSERT (GB_UNFLIP (Vi [pleft]) == i) ;
79 found = true ;
80 is_zombie = GB_IS_ZOMBIE (Vi [pleft]) ;
81 }
82 else
83 {
84 // binary search for V(i): time is O(log(vnz))
85 int64_t nzombies = V->nzombies ;
86 pright-- ;
87 GB_BINARY_SEARCH_ZOMBIE (i, Vi, pleft, pright, found,
88 nzombies, is_zombie) ;
89 }
90
91 // remove the entry
92 if (found && !is_zombie)
93 {
94 // V(i) becomes a zombie
95 V->i [pleft] = GB_FLIP (i) ;
96 V->nzombies++ ;
97 }
98 return (found) ;
99 }
100 }
101
102 //------------------------------------------------------------------------------
103 // GrB_Vector_removeElement: remove a single entry from a vector
104 //------------------------------------------------------------------------------
105
GrB_Vector_removeElement(GrB_Vector V,GrB_Index i)106 GrB_Info GrB_Vector_removeElement
107 (
108 GrB_Vector V, // vector to remove entry from
109 GrB_Index i // index
110 )
111 {
112
113 //--------------------------------------------------------------------------
114 // check inputs
115 //--------------------------------------------------------------------------
116
117 GB_RETURN_IF_NULL_OR_FAULTY (V) ;
118
119 //--------------------------------------------------------------------------
120 // if V is jumbled, wait on the vector first. If full, convert to nonfull
121 //--------------------------------------------------------------------------
122
123 if (V->jumbled || GB_IS_FULL (V))
124 {
125 GrB_Info info ;
126 GB_WHERE (V, GB_WHERE_STRING) ;
127 GB_BURBLE_START ("GrB_Vector_removeElement") ;
128 if (GB_IS_FULL (V))
129 {
130 // convert V from full to sparse
131 GB_OK (GB_convert_to_nonfull ((GrB_Matrix) V, Context)) ;
132 }
133 else
134 {
135 // V is sparse and jumbled
136 GB_OK (GB_Matrix_wait ((GrB_Matrix) V, "v", Context)) ;
137 }
138 ASSERT (!GB_IS_FULL (V)) ;
139 ASSERT (!GB_ZOMBIES (V)) ;
140 ASSERT (!GB_JUMBLED (V)) ;
141 ASSERT (!GB_PENDING (V)) ;
142 // remove the entry
143 info = GrB_Vector_removeElement (V, i) ;
144 GB_BURBLE_END ;
145 return (info) ;
146 }
147
148 //--------------------------------------------------------------------------
149 // V is not jumbled and not full; it may have zombies and pending tuples
150 //--------------------------------------------------------------------------
151
152 ASSERT (!GB_IS_FULL (V)) ;
153 ASSERT (GB_ZOMBIES_OK (V)) ;
154 ASSERT (!GB_JUMBLED (V)) ;
155 ASSERT (GB_PENDING_OK (V)) ;
156
157 // check index
158 if (i >= V->vlen)
159 {
160 GB_WHERE (V, GB_WHERE_STRING) ;
161 GB_ERROR (GrB_INVALID_INDEX, "Row index "
162 GBu " out of range; must be < " GBd, i, V->vlen) ;
163 }
164
165 // if V is sparse, it may have pending tuples
166 bool V_is_pending = GB_PENDING (V) ;
167 if (V->nzmax == 0 && !V_is_pending)
168 {
169 // quick return
170 return (GrB_SUCCESS) ;
171 }
172
173 // remove the entry
174 if (GB_removeElement (V, i))
175 {
176 // found it; no need to assemble pending tuples
177 return (GrB_SUCCESS) ;
178 }
179
180 // assemble any pending tuples; zombies are OK
181 if (V_is_pending)
182 {
183 GrB_Info info ;
184 GB_WHERE (V, GB_WHERE_STRING) ;
185 GB_BURBLE_START ("GrB_Vector_removeElement") ;
186 GB_OK (GB_Matrix_wait ((GrB_Matrix) V, "v", Context)) ;
187 ASSERT (!GB_ZOMBIES (V)) ;
188 ASSERT (!GB_JUMBLED (V)) ;
189 ASSERT (!GB_PENDING (V)) ;
190 // look again; remove the entry if it was a pending tuple
191 GB_removeElement (V, i) ;
192 GB_BURBLE_END ;
193 }
194
195 return (GrB_SUCCESS) ;
196 }
197
198