Struct extended_collections::bp_tree::BpMap

pub struct BpMap<T, U> { /* fields omitted */ }

An ordered map implemented using an on-disk B+ tree.

A B+ is an N-ary tree with a variable number of children per node. A B+ tree is a B-tree in which each internal node contains keys and pointers to other nodes, and each leaf node contains keys and values.

Examples

use extended_collections::bp_tree::BpMap;

let mut map: BpMap<u32, u64> = BpMap::new("bp_map", 4, 8)?;
map.insert(0, 1)?;
map.insert(3, 4)?;

assert_eq!(map.get(&0)?, Some(1));
assert_eq!(map.get(&1)?, None);
assert_eq!(map.len(), 2);

assert_eq!(map.min()?, Some(0));

assert_eq!(map.remove(&0)?, Some((0, 1)));
assert_eq!(map.remove(&1)?, None);

Methods

impl<T, U> BpMap<T, U>

pub fn new<P>(     file_path: P,     key_size: u64,     value_size: u64 ) -> Result<BpMap<T, U>> where     T: Serialize,     U: Serialize,     P: AsRef<Path>,

Constructs a new, empty BpMap<T, U> with maximum sizes for keys and values, and creates a file for data persistence.

Examples

use extended_collections::bp_tree::BpMap;

// keys have a maximum of 4 bytes and values have a maximum of 8 bytes
let map: BpMap<u32, u64> = BpMap::new("example_bp_map_new", 4, 8)?;

pub fn with_degrees<P>(     file_path: P,     key_size: u64,     value_size: u64,     leaf_degree: usize,     internal_degree: usize ) -> Result<BpMap<T, U>> where     T: Serialize,     U: Serialize,     P: AsRef<Path>,

Constructs a new, empty BpMap<T, U> with maximum sizes for keys and values and specific sizes for leaf and internal nodes, and creates a file for data persistence.

Examples

use extended_collections::bp_tree::BpMap;

let map: BpMap<u32, u64> = BpMap::with_degrees("example_bp_map_with_degrees", 4, 8, 3, 3)?;

pub fn open<P>(file_path: P) -> Result<BpMap<T, U>> where     P: AsRef<Path>,

Opens an existing BpMap<T, U> from a file.

Examples

use extended_collections::bp_tree::BpMap;

let map: BpMap<u32, u64> = BpMap::open("example_bp_map_open")?;

pub fn insert(&mut self, key: T, value: U) -> Result<Option<(T, U)>> where     T: Clone + DeserializeOwned + Ord + Serialize,     U: DeserializeOwned + Serialize,

Inserts a key-value pair into the map. If the key already exists in the map, it will return and replace the old key-value pair.

Panics

Panics if attempting to insert a key or value that exceeds the maximum key or value size specified on creation.

Examples

use extended_collections::bp_tree::BpMap;

let mut map: BpMap<u32, u64> = BpMap::new("example_bp_map_insert", 4, 8)?;
assert_eq!(map.insert(1, 1)?, None);
assert_eq!(map.get(&1)?, Some(1));
assert_eq!(map.insert(1, 2)?, Some((1, 1)));
assert_eq!(map.get(&1)?, Some(2));

pub fn remove<V: ?Sized>(&mut self, key: &V) -> Result<Option<(T, U)>> where     T: Borrow<V> + Clone + DeserializeOwned + Ord + Serialize,     U: DeserializeOwned + Serialize,     V: Ord,

Removes a key-value pair from the map. If the key exists in the map, it will return the associated key-value pair. Otherwise it will return None.

Examples

use extended_collections::bp_tree::BpMap;

let mut map: BpMap<u32, u64> = BpMap::new("example_bp_map_remove", 4, 8)?;
map.insert(1, 1)?;
assert_eq!(map.remove(&1)?, Some((1, 1)));
assert_eq!(map.remove(&1)?, None);

pub fn contains_key<V: ?Sized>(&mut self, key: &V) -> Result<bool> where     T: Borrow<V> + DeserializeOwned,     U: DeserializeOwned,     V: Ord,

Checks if a key exists in the map.

Examples

use extended_collections::bp_tree::BpMap;

let mut map: BpMap<u32, u64> = BpMap::new("example_bp_map_contains_key", 4, 8)?;
map.insert(1, 1)?;
assert!(!map.contains_key(&0)?);
assert!(map.contains_key(&1)?);

pub fn get<V: ?Sized>(&mut self, key: &V) -> Result<Option<U>> where     T: Borrow<V> + DeserializeOwned,     U: DeserializeOwned,     V: Ord,

Returns the value associated with a particular key. It will return None if the key does not exist in the map.

Examples

use extended_collections::bp_tree::BpMap;

let mut map: BpMap<u32, u64> = BpMap::new("example_bp_map_get", 4, 8)?;
map.insert(1, 1)?;
assert_eq!(map.get(&0)?, None);
assert_eq!(map.get(&1)?, Some(1));

pub fn len(&self) -> usize

Returns the number of elements in the map.

Examples

use extended_collections::bp_tree::BpMap;

let mut map: BpMap<u32, u64> = BpMap::new("example_bp_map_len", 4, 8)?;
map.insert(1, 1)?;
assert_eq!(map.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the map is empty.

Examples

use extended_collections::bp_tree::BpMap;

let map: BpMap<u32, u64> = BpMap::new("example_bp_map_is_empty", 4, 8)?;
assert!(map.is_empty());

pub fn clear(&mut self) -> Result<()> where     T: Serialize,     U: Serialize,

Clears the map, removing all values.

Examples

use extended_collections::bp_tree::BpMap;

let mut map: BpMap<u32, u64> = BpMap::new("example_bp_map_clear", 4, 8)?;
map.insert(1, 1)?;
map.insert(2, 2)?;
map.clear()?;
assert_eq!(map.is_empty(), true);

pub fn min(&mut self) -> Result<Option<T>> where     T: DeserializeOwned,     U: DeserializeOwned,

Returns the minimum key of the map. Returns None if the map is empty.

Examples

use extended_collections::bp_tree::BpMap;

let mut map: BpMap<u32, u64> = BpMap::new("example_bp_map_min", 4, 8)?;
map.insert(1, 1)?;
map.insert(3, 3)?;
assert_eq!(map.min()?, Some(1));

pub fn max(&mut self) -> Result<Option<T>> where     T: DeserializeOwned,     U: DeserializeOwned,

Returns the maximum key of the map. Returns None if the map is empty.

Examples

use extended_collections::bp_tree::BpMap;

let mut map: BpMap<u32, u64> = BpMap::new("example_bp_map_max", 4, 8)?;
map.insert(1, 1)?;
map.insert(3, 3)?;
assert_eq!(map.max()?, Some(3));

pub fn iter_mut(&mut self) -> Result<BpMapIterMut<T, U>> where     T: DeserializeOwned,     U: DeserializeOwned,

Returns a mutable iterator over the map. The iterator will yield key-value pairs using in-order traversal.

Examples

use extended_collections::bp_tree::BpMap;

let mut map: BpMap<u32, u64> = BpMap::new("example_bp_map_iter_mut", 4, 8)?;
map.insert(1, 1)?;
map.insert(2, 2)?;

let mut iterator = map.iter_mut()?.map(|value| value.unwrap());
assert_eq!(iterator.next(), Some((1, 1)));
assert_eq!(iterator.next(), Some((2, 2)));
assert_eq!(iterator.next(), None);

Trait Implementations

impl<'a, T, U> IntoIterator for &'a mut BpMap<T, U> where     T: 'a + DeserializeOwned,     U: 'a + DeserializeOwned,

type Item = Result<(T, U)>

The type of the elements being iterated over.

type IntoIter = BpMapIterMut<'a, T, U>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.