sled/
binary_search.rs

1use std::cmp::Ordering::{Equal, Greater, Less};
2
3use crate::{fastcmp, IVec};
4
5pub(crate) fn binary_search_lub(key: &[u8], s: &[IVec]) -> Option<usize> {
6    match binary_search(key, s) {
7        Ok(i) => Some(i),
8        Err(i) if i == 0 => None,
9        Err(i) => Some(i - 1),
10    }
11}
12
13pub fn binary_search(key: &[u8], s: &[IVec]) -> Result<usize, usize> {
14    let mut size = s.len();
15    if size == 0 || *key < *s[0] {
16        return Err(0);
17    }
18    let mut base = 0_usize;
19    while size > 1 {
20        let half = size / 2;
21        let mid = base + half;
22        // mid is always in [0, size), that means mid is >= 0 and < size.
23        // mid >= 0: by definition
24        // mid < size: mid = size / 2 + size / 4 + size / 8 ...
25        #[allow(unsafe_code)]
26        let l = unsafe { s.get_unchecked(mid).as_ref() };
27        let cmp = fastcmp(l, key);
28        base = if cmp == Greater { base } else { mid };
29        size -= half;
30    }
31    // base is always in [0, size) because base <= mid.
32    #[allow(unsafe_code)]
33    let l = unsafe { s.get_unchecked(base).as_ref() };
34    let cmp = fastcmp(l, key);
35    if cmp == Equal {
36        Ok(base)
37    } else {
38        Err(base + (cmp == Less) as usize)
39    }
40}
41
42#[test]
43fn test_binary_search_lub() {
44    let s = vec![
45        vec![4].into(),
46        vec![5].into(),
47        vec![5].into(),
48        vec![6].into(),
49        vec![9].into(),
50    ];
51    assert_eq!(binary_search_lub(&[3], &*s), None);
52    assert_eq!(binary_search_lub(&[4], &*s), Some(0));
53    assert_eq!(binary_search_lub(&[5], &*s), Some(2));
54    assert_eq!(binary_search_lub(&[6], &*s), Some(3));
55    assert_eq!(binary_search_lub(&[7], &*s), Some(3));
56    assert_eq!(binary_search_lub(&[8], &*s), Some(3));
57    assert_eq!(binary_search_lub(&[9], &*s), Some(4));
58    assert_eq!(binary_search_lub(&[10], &*s), Some(4));
59
60    let mut s = s;
61    s.clear();
62    assert_eq!(binary_search_lub(&[8], &*s), None);
63}
sled/binary_search.rs

sled/
binary_search.rs
