btree-slab 0.6.1

A memory compact Slab-based B-tree implementation
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

use crate::generic::node::Keyed;
use std::borrow::Borrow;

/// Search in `sorted_slice` for the item with the nearest key smaller or equal to the given one.
///
/// `sorted_slice` is assumed to be sorted.
#[inline]
pub fn binary_search_min<T: Keyed, Q: ?Sized>(sorted_slice: &[T], key: &Q) -> Option<usize>
where
	T::Key: Borrow<Q>,
	Q: Ord,
{
	if sorted_slice.is_empty() || sorted_slice[0].key().borrow() > key {
		None
	} else {
		let mut i = 0;
		let mut j = sorted_slice.len() - 1;

		if sorted_slice[j].key().borrow() <= key {
			return Some(j);
		}

		// invariants:
		// sorted_slice[i].key <= key
		// sorted_slice[j].key > key
		// j > i

		while j - i > 1 {
			let k = (i + j) / 2;

			if sorted_slice[k].key().borrow() > key {
				j = k;
			// sorted_slice[k].key > key --> sorted_slice[j] > key
			} else {
				i = k;
				// sorted_slice[k].key <= key --> sorted_slice[i] <= key
			}
		}

		Some(i)
	}
}