1 //------------------------------------------------------------------------------
2 // GB_binary_search.h: binary search in a sorted list
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 #ifndef GB_BINARY_SEARCH_H
11 #define GB_BINARY_SEARCH_H
12 
13 //------------------------------------------------------------------------------
14 // GB_TRIM_BINARY_SEARCH: simple binary search
15 //------------------------------------------------------------------------------
16 
17 // search for integer i in the list X [pleft...pright]; no zombies.
18 // The list X [pleft ... pright] is in ascending order.  It may have
19 // duplicates.
20 
21 #if GB_KERNEL
22 
23 // version for the GPU, with fewer branches
24 #define GB_TRIM_BINARY_SEARCH(i,X,pleft,pright)                             \
25 {                                                                           \
26     /* binary search of X [pleft ... pright] for integer i */               \
27     while (pleft < pright)                                                  \
28     {                                                                       \
29         int64_t pmiddle = (pleft + pright) >> 1 ;                           \
30         bool less = (X [pmiddle] < i) ;                                     \
31         pleft  = less ? (pmiddle+1) : pleft ;                               \
32         pright = less ? pright : pmiddle ;                                  \
33     }                                                                       \
34     /* binary search is narrowed down to a single item */                   \
35     /* or it has found the list is empty */                                 \
36     ASSERT (pleft == pright || pleft == pright + 1) ;                       \
37 }
38 
39 #else
40 
41 // version for the CPU
42 #define GB_TRIM_BINARY_SEARCH(i,X,pleft,pright)                             \
43 {                                                                           \
44     /* binary search of X [pleft ... pright] for integer i */               \
45     while (pleft < pright)                                                  \
46     {                                                                       \
47         int64_t pmiddle = (pleft + pright) / 2 ;                            \
48         if (X [pmiddle] < i)                                                \
49         {                                                                   \
50             /* if in the list, it appears in [pmiddle+1..pright] */         \
51             pleft = pmiddle + 1 ;                                           \
52         }                                                                   \
53         else                                                                \
54         {                                                                   \
55             /* if in the list, it appears in [pleft..pmiddle] */            \
56             pright = pmiddle ;                                              \
57         }                                                                   \
58     }                                                                       \
59     /* binary search is narrowed down to a single item */                   \
60     /* or it has found the list is empty */                                 \
61     ASSERT (pleft == pright || pleft == pright + 1) ;                       \
62 }
63 #endif
64 
65 //------------------------------------------------------------------------------
66 // GB_BINARY_SEARCH: binary search and check if found
67 //------------------------------------------------------------------------------
68 
69 // If found is true then X [pleft == pright] == i.  If duplicates appear then
70 // X [pleft] is any one of the entries with value i in the list.
71 // If found is false then
72 //    X [original_pleft ... pleft-1] < i and
73 //    X [pleft+1 ... original_pright] > i holds.
74 // The value X [pleft] may be either < or > i.
75 #define GB_BINARY_SEARCH(i,X,pleft,pright,found)                            \
76 {                                                                           \
77     GB_TRIM_BINARY_SEARCH (i, X, pleft, pright) ;                           \
78     found = (pleft == pright && X [pleft] == i) ;                           \
79 }
80 
81 //------------------------------------------------------------------------------
82 // GB_SPLIT_BINARY_SEARCH: binary search, and then partition the list
83 //------------------------------------------------------------------------------
84 
85 // If found is true then X [pleft] == i.  If duplicates appear then X [pleft]
86 //    is any one of the entries with value i in the list.
87 // If found is false then
88 //    X [original_pleft ... pleft-1] < i and
89 //    X [pleft ... original_pright] > i holds, and pleft-1 == pright
90 // If X has no duplicates, then whether or not i is found,
91 //    X [original_pleft ... pleft-1] < i and
92 //    X [pleft ... original_pright] >= i holds.
93 #define GB_SPLIT_BINARY_SEARCH(i,X,pleft,pright,found)                      \
94 {                                                                           \
95     GB_BINARY_SEARCH (i, X, pleft, pright, found)                           \
96     if (!found && (pleft == pright))                                        \
97     {                                                                       \
98         if (i > X [pleft])                                                  \
99         {                                                                   \
100             pleft++ ;                                                       \
101         }                                                                   \
102         else                                                                \
103         {                                                                   \
104             pright++ ;                                                      \
105         }                                                                   \
106     }                                                                       \
107 }
108 
109 //------------------------------------------------------------------------------
110 // GB_TRIM_BINARY_SEARCH_ZOMBIE: binary search in the presence of zombies
111 //------------------------------------------------------------------------------
112 
113 #if GB_KERNEL
114 
115 // version for the GPU, with fewer branches
116 #define GB_TRIM_BINARY_SEARCH_ZOMBIE(i,X,pleft,pright)                      \
117 {                                                                           \
118     /* binary search of X [pleft ... pright] for integer i */               \
119     while (pleft < pright)                                                  \
120     {                                                                       \
121         int64_t pmiddle = (pleft + pright) >> 1 ;                           \
122         bool less = (GB_UNFLIP (X [pmiddle]) < i) ;                         \
123         pleft  = less ? (pmiddle+1) : pleft ;                               \
124         pright = less ? pright : pmiddle ;                                  \
125     }                                                                       \
126     /* binary search is narrowed down to a single item */                   \
127     /* or it has found the list is empty */                                 \
128     ASSERT (pleft == pright || pleft == pright + 1) ;                       \
129 }
130 
131 #else
132 
133 // version for the CPU
134 #define GB_TRIM_BINARY_SEARCH_ZOMBIE(i,X,pleft,pright)                      \
135 {                                                                           \
136     /* binary search of X [pleft ... pright] for integer i */               \
137     while (pleft < pright)                                                  \
138     {                                                                       \
139         int64_t pmiddle = (pleft + pright) / 2 ;                            \
140         if (i > GB_UNFLIP (X [pmiddle]))                                    \
141         {                                                                   \
142             /* if in the list, it appears in [pmiddle+1..pright] */         \
143             pleft = pmiddle + 1 ;                                           \
144         }                                                                   \
145         else                                                                \
146         {                                                                   \
147             /* if in the list, it appears in [pleft..pmiddle] */            \
148             pright = pmiddle ;                                              \
149         }                                                                   \
150     }                                                                       \
151     /* binary search is narrowed down to a single item */                   \
152     /* or it has found the list is empty */                                 \
153     ASSERT (pleft == pright || pleft == pright + 1) ;                       \
154 }
155 #endif
156 
157 //------------------------------------------------------------------------------
158 // GB_BINARY_SEARCH_ZOMBIE: binary search with zombies; check if found
159 //------------------------------------------------------------------------------
160 
161 #define GB_BINARY_SEARCH_ZOMBIE(i,X,pleft,pright,found,nzombies,is_zombie)  \
162 {                                                                           \
163     if (nzombies > 0)                                                       \
164     {                                                                       \
165         GB_TRIM_BINARY_SEARCH_ZOMBIE (i, X, pleft, pright) ;                \
166         found = false ;                                                     \
167         is_zombie = false ;                                                 \
168         if (pleft == pright)                                                \
169         {                                                                   \
170             int64_t i2 = X [pleft] ;                                        \
171             is_zombie = GB_IS_ZOMBIE (i2) ;                                 \
172             if (is_zombie)                                                  \
173             {                                                               \
174                 i2 = GB_FLIP (i2) ;                                         \
175             }                                                               \
176             found = (i == i2) ;                                             \
177         }                                                                   \
178     }                                                                       \
179     else                                                                    \
180     {                                                                       \
181         is_zombie = false ;                                                 \
182         GB_BINARY_SEARCH(i,X,pleft,pright,found)                            \
183     }                                                                       \
184 }
185 
186 //------------------------------------------------------------------------------
187 // GB_SPLIT_BINARY_SEARCH_ZOMBIE: binary search with zombies; then partition
188 //------------------------------------------------------------------------------
189 
190 #define GB_SPLIT_BINARY_SEARCH_ZOMBIE(i,X,pleft,pright,found,nzom,is_zombie) \
191 {                                                                           \
192     if (nzom > 0)                                                           \
193     {                                                                       \
194         GB_TRIM_BINARY_SEARCH_ZOMBIE (i, X, pleft, pright) ;                \
195         found = false ;                                                     \
196         is_zombie = false ;                                                 \
197         if (pleft == pright)                                                \
198         {                                                                   \
199             int64_t i2 = X [pleft] ;                                        \
200             is_zombie = GB_IS_ZOMBIE (i2) ;                                 \
201             if (is_zombie)                                                  \
202             {                                                               \
203                 i2 = GB_FLIP (i2) ;                                         \
204             }                                                               \
205             found = (i == i2) ;                                             \
206             if (!found)                                                     \
207             {                                                               \
208                 if (i > i2)                                                 \
209                 {                                                           \
210                     pleft++ ;                                               \
211                 }                                                           \
212                 else                                                        \
213                 {                                                           \
214                     pright++ ;                                              \
215                 }                                                           \
216             }                                                               \
217         }                                                                   \
218     }                                                                       \
219     else                                                                    \
220     {                                                                       \
221         is_zombie = false ;                                                 \
222         GB_SPLIT_BINARY_SEARCH(i,X,pleft,pright,found)                      \
223     }                                                                       \
224 }
225 
226 //------------------------------------------------------------------------------
227 // GB_lookup: find k so that j == Ah [k]
228 //------------------------------------------------------------------------------
229 
230 #include "GB_lookup_template.c"
231 
232 #endif
233 
234