]>
git.proxmox.com Git - rustc.git/blob - vendor/rustc-ap-rustc_data_structures/src/binary_search_util/mod.rs
4 /// Uses a sorted slice `data: &[E]` as a kind of "multi-map". The
5 /// `key_fn` extracts a key of type `K` from the data, and this
6 /// function finds the range of elements that match the key. `data`
7 /// must have been sorted as if by a call to `sort_by_key` for this to
9 pub fn binary_search_slice
<E
, K
>(data
: &'d
[E
], key_fn
: impl Fn(&E
) -> K
, key
: &K
) -> &'d
[E
]
13 let mid
= match data
.binary_search_by_key(key
, &key_fn
) {
17 let size
= data
.len();
19 // We get back *some* element with the given key -- so do
20 // a galloping search backwards to find the *first* one.
22 let mut previous
= mid
;
25 start
= start
.saturating_sub(step
);
26 if start
== 0 || key_fn(&data
[start
]) != *key
{
32 step
= previous
- start
;
35 let mid
= start
+ half
;
36 if key_fn(&data
[mid
]) != *key
{
41 // adjust by one if we have overshot
42 if start
< size
&& key_fn(&data
[start
]) != *key
{
46 // Now search forward to find the *last* one.
48 let mut previous
= mid
;
51 end
= end
.saturating_add(step
).min(size
);
52 if end
== size
|| key_fn(&data
[end
]) != *key
{
58 step
= end
- previous
;
62 if key_fn(&data
[mid
]) != *key
{