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