| 232 | } |
| 233 | |
| 234 | void *intmap_before_(const struct intmap *map, intmap_index_t *indexp) |
| 235 | { |
| 236 | const struct intmap *n, *prev = NULL; |
| 237 | intmap_index_t index = (*indexp) - 1; |
| 238 | |
| 239 | /* Special case of overflow */ |
| 240 | if (index == (intmap_index_t)-1ULL) |
| 241 | goto none_left; |
| 242 | |
| 243 | /* Special case of empty map */ |
| 244 | if (intmap_empty_(map)) |
| 245 | goto none_left; |
| 246 | |
| 247 | /* Follow down, until prefix differs. */ |
| 248 | n = map; |
| 249 | while (!n->v) { |
| 250 | int crit = critbit(n); |
| 251 | u8 direction; |
| 252 | intmap_index_t prefix, idx; |
| 253 | |
| 254 | idx = (index >> crit); |
| 255 | direction = idx & 1; |
| 256 | |
| 257 | /* Leave critbit in place: we can't shift by 64 anyway */ |
| 258 | idx |= 1; |
| 259 | prefix = n->u.n->prefix_and_critbit >> crit; |
| 260 | |
| 261 | /* If this entire tree is less than index, take last */ |
| 262 | if (idx > prefix) |
| 263 | return intmap_last_(n, indexp); |
| 264 | /* If this entire tree is greater than index, we're past it. */ |
| 265 | else if (idx < prefix) |
| 266 | goto try_lesser_tree; |
| 267 | |
| 268 | /* Remember lesser tree for backtracking */ |
| 269 | if (direction) |
| 270 | prev = n; |
| 271 | n = &n->u.n->child[direction]; |
| 272 | } |
| 273 | |
| 274 | /* Found a predecessor? */ |
| 275 | if (n->u.i <= index) { |
| 276 | errno = 0; |
| 277 | *indexp = n->u.i; |
| 278 | return n->v; |
| 279 | } |
| 280 | |
| 281 | try_lesser_tree: |
| 282 | /* If we ever took a lesser branch, go back to lesser branch */ |
| 283 | if (prev) |
| 284 | return intmap_last_(&prev->u.n->child[0], indexp); |
| 285 | |
| 286 | none_left: |
| 287 | errno = ENOENT; |
| 288 | return NULL; |
| 289 | } |
| 290 | |
| 291 | void *intmap_last_(const struct intmap *map, intmap_index_t *indexp) |
no test coverage detected