Struct IntervalTree

pub struct IntervalTree<T> { /* private fields */ }

An interval tree implementation specialized for VMM resource management.

Implementations

impl<T> IntervalTree<T>

pub fn new() -> Self

Construct a default empty IntervalTree object.

Examples

extern crate dbs_allocator;

let tree = dbs_allocator::IntervalTree::<u64>::new();

pub fn is_empty(&self) -> bool

Check whether the interval tree is empty.

pub fn get(&self, key: &Range) -> Option<NodeState<&T>>

Get the data item associated with the key, or return None if no match found.

Examples

extern crate dbs_allocator;
use dbs_allocator::{IntervalTree, NodeState, Range};

let mut tree = dbs_allocator::IntervalTree::<u64>::new();
assert!(tree.is_empty());
assert_eq!(tree.get(&Range::new(0x101u64, 0x101u64)), None);
tree.insert(Range::new(0x100u64, 0x100u64), Some(1));
tree.insert(Range::new(0x200u64, 0x2ffu64), None);
assert!(!tree.is_empty());
assert_eq!(
    tree.get(&Range::new(0x100u64, 0x100u64)),
    Some(NodeState::Valued(&1))
);
assert_eq!(
    tree.get(&Range::new(0x200u64, 0x2ffu64)),
    Some(NodeState::Free)
);
assert_eq!(tree.get(&Range::new(0x101u64, 0x101u64)), None);
assert_eq!(tree.get(&Range::new(0x100u64, 0x101u64)), None);

pub fn get_superset(&self, key: &Range) -> Option<(&Range, NodeState<&T>)>

Get a shared reference to the node fully covering the entire key range.

Examples

extern crate dbs_allocator;
use dbs_allocator::{IntervalTree, NodeState, Range};

let mut tree = IntervalTree::<u64>::new();
tree.insert(Range::new(0x100u32, 0x100u32), Some(1));
tree.insert(Range::new(0x200u32, 0x2ffu32), None);
assert_eq!(
    tree.get_superset(&Range::new(0x100u32, 0x100u32)),
    Some((&Range::new(0x100u32, 0x100u32), NodeState::Valued(&1)))
);
assert_eq!(
    tree.get_superset(&Range::new(0x210u32, 0x210u32)),
    Some((&Range::new(0x200u32, 0x2ffu32), NodeState::Free))
);
assert_eq!(
    tree.get_superset(&Range::new(0x2ffu32, 0x2ffu32)),
    Some((&Range::new(0x200u32, 0x2ffu32), NodeState::Free))
);

pub fn get_superset_mut( &mut self, key: &Range, ) -> Option<(&Range, NodeState<&mut T>)>

Get a mutable reference to the node fully covering the entire key range.

Examples

extern crate dbs_allocator;
use dbs_allocator::{IntervalTree, NodeState, Range};

let mut tree = IntervalTree::<u64>::new();
tree.insert(Range::new(0x100u32, 0x100u32), Some(1));
tree.insert(Range::new(0x200u32, 0x2ffu32), None);
assert_eq!(
    tree.get_superset_mut(&Range::new(0x100u32, 0x100u32)),
    Some((&Range::new(0x100u32, 0x100u32), NodeState::Valued(&mut 1)))
);
assert_eq!(
    tree.get_superset_mut(&Range::new(0x210u32, 0x210u32)),
    Some((&Range::new(0x200u32, 0x2ffu32), NodeState::Free))
);
assert_eq!(
    tree.get_superset_mut(&Range::new(0x2ffu32, 0x2ffu32)),
    Some((&Range::new(0x200u32, 0x2ffu32), NodeState::Free))
);

pub fn get_by_id<U>(&self, id: U) -> Option<&T>

where u64: From<U>,

Get a shared reference to the value associated with the id.

Examples

extern crate dbs_allocator;
use dbs_allocator::{IntervalTree, NodeState, Range};

let mut tree = IntervalTree::<u32>::new();
tree.insert(Range::new(0x100u16, 0x100u16), Some(1));
tree.insert(Range::new(0x200u16, 0x2ffu16), None);
assert_eq!(tree.get_by_id(0x100u16), Some(&1));
assert_eq!(tree.get_by_id(0x210u32), None);
assert_eq!(tree.get_by_id(0x2ffu64), None);

pub fn get_by_id_mut<U>(&mut self, id: U) -> Option<&mut T>

where u64: From<U>,

Get a mutable reference to the value associated with the id.

Examples

extern crate dbs_allocator;
use dbs_allocator::{IntervalTree, NodeState, Range};

let mut tree = IntervalTree::<u32>::new();
tree.insert(Range::new(0x100u16, 0x100u16), Some(1));
tree.insert(Range::new(0x200u16, 0x2ffu16), None);
assert_eq!(tree.get_by_id_mut(0x100u16), Some(&mut 1));
assert_eq!(tree.get_by_id_mut(0x210u32), None);
assert_eq!(tree.get_by_id_mut(0x2ffu64), None);

pub fn insert(&mut self, key: Range, data: Option<T>)

Insert the (key, data) pair into the interval tree, panic if intersects with existing nodes.

Examples

extern crate dbs_allocator;
use dbs_allocator::{IntervalTree, NodeState, Range};

let mut tree = IntervalTree::<u64>::new();
tree.insert(Range::new(0x100u32, 0x100u32), Some(1));
tree.insert(Range::new(0x200u32, 0x2ffu32), None);
assert_eq!(
    tree.get(&Range::new(0x100u64, 0x100u64)),
    Some(NodeState::Valued(&1))
);
assert_eq!(
    tree.get(&Range::new(0x200u64, 0x2ffu64)),
    Some(NodeState::Free)
);

pub fn update(&mut self, key: &Range, data: T) -> Option<T>

Update an existing entry and return the old value.

Examples

extern crate dbs_allocator;
use dbs_allocator::{Constraint, IntervalTree, Range};

let mut tree = IntervalTree::<u64>::new();
tree.insert(Range::new(0x100u64, 0x100u64), None);
tree.insert(Range::new(0x200u64, 0x2ffu64), None);

let constraint = Constraint::new(2u32);
let key = tree.allocate(&constraint);
assert_eq!(key, Some(Range::new(0x200u64, 0x201u64)));
let old = tree.update(&Range::new(0x200u64, 0x201u64), 2);
assert_eq!(old, None);
let old = tree.update(&Range::new(0x200u64, 0x201u64), 3);
assert_eq!(old, Some(2));

pub fn delete(&mut self, key: &Range) -> Option<T>

Remove the key from the tree and return the associated data.

Examples

extern crate dbs_allocator;
use dbs_allocator::{IntervalTree, Range};

let mut tree = IntervalTree::<u64>::new();
tree.insert(Range::new(0x100u64, 0x100u64), Some(1));
tree.insert(Range::new(0x200u64, 0x2ffu64), None);
let old = tree.delete(&Range::new(0x100u64, 0x100u64));
assert_eq!(old, Some(1));
let old = tree.delete(&Range::new(0x200u64, 0x2ffu64));
assert_eq!(old, None);

pub fn allocate(&mut self, constraint: &Constraint) -> Option<Range>

Allocate a resource range according the allocation constraints.

Examples

extern crate dbs_allocator;
use dbs_allocator::{Constraint, IntervalTree, Range};

let mut tree = IntervalTree::<u64>::new();
tree.insert(Range::new(0x100u64, 0x100u64), None);
tree.insert(Range::new(0x200u64, 0x2ffu64), None);

let constraint = Constraint::new(2u8);
let key = tree.allocate(&constraint);
assert_eq!(key, Some(Range::new(0x200u64, 0x201u64)));
tree.update(&Range::new(0x200u64, 0x201u64), 2);

pub fn free(&mut self, key: &Range) -> Option<T>

Free an allocated range and return the associated data.

Trait Implementations

impl<T: Debug> Debug for IntervalTree<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Default> Default for IntervalTree<T>

fn default() -> IntervalTree<T>

Returns the “default value” for a type.

impl<T: PartialEq> PartialEq for IntervalTree<T>

fn eq(&self, other: &IntervalTree<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Eq> Eq for IntervalTree<T>

impl<T> StructuralPartialEq for IntervalTree<T>