use core::borrow::Borrow;
use core::marker::PhantomData;
use core::mem;
use unreachable::UncheckedOptionExt;
use node::{Leaf, Node};
use util::nybble_get_mismatch;
pub fn make_entry<'a, K: 'a + Borrow<[u8]>, V: 'a>(
key: K,
root: &'a mut Option<Node<K, V>>,
count: &'a mut usize,
) -> Entry<'a, K, V> {
match *root {
Some(..) => Entry::nonempty(key, root, count),
None => Entry::empty(key, root, count),
}
}
#[derive(Debug)]
pub enum Entry<'a, K: 'a, V: 'a> {
Vacant(VacantEntry<'a, K, V>),
Occupied(OccupiedEntry<'a, K, V>),
}
impl<'a, K: 'a + Borrow<[u8]>, V: 'a> Entry<'a, K, V> {
fn nonempty(key: K, root: &'a mut Option<Node<K, V>>, count: &'a mut usize) -> Entry<'a, K, V> {
let (exemplar_ptr, mismatch) = {
let node = unsafe { root.as_mut().unchecked_unwrap() };
let exemplar = node.get_exemplar_mut(key.borrow());
let mismatch = nybble_get_mismatch(exemplar.key_slice(), key.borrow());
(exemplar as *mut Leaf<K, V>, mismatch)
};
match mismatch {
None => Entry::occupied(exemplar_ptr, root as *mut Option<Node<K, V>>, count),
Some((b, i)) => {
let node = unsafe { root.as_mut().unchecked_unwrap() };
Entry::vacant_nonempty(key, i, b, node, count)
}
}
}
fn occupied(
leaf: *mut Leaf<K, V>,
root: *mut Option<Node<K, V>>,
count: &'a mut usize,
) -> Entry<'a, K, V> {
Entry::Occupied(OccupiedEntry {
_dummy: PhantomData,
leaf,
root,
count,
})
}
fn vacant_nonempty(
key: K,
graft: usize,
graft_nybble: u8,
node: &'a mut Node<K, V>,
count: &'a mut usize,
) -> Entry<'a, K, V> {
Entry::Vacant(VacantEntry {
key,
inner: VacantEntryInner::Internal(graft, graft_nybble, node),
count,
})
}
fn empty(key: K, root: &'a mut Option<Node<K, V>>, count: &'a mut usize) -> Entry<'a, K, V> {
Entry::Vacant(VacantEntry {
key,
inner: VacantEntryInner::Root(root),
count,
})
}
pub fn or_insert(self, default: V) -> &'a mut V {
match self {
Entry::Vacant(vacant) => vacant.insert(default),
Entry::Occupied(occupied) => occupied.into_mut(),
}
}
pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
match self {
Entry::Vacant(vacant) => vacant.insert(default()),
Entry::Occupied(occupied) => occupied.into_mut(),
}
}
pub fn key(&self) -> &K {
match self {
Entry::Vacant(vacant) => vacant.key(),
Entry::Occupied(occupied) => occupied.key(),
}
}
}
#[derive(Debug)]
pub struct VacantEntry<'a, K: 'a, V: 'a> {
key: K,
inner: VacantEntryInner<'a, K, V>,
count: &'a mut usize,
}
#[derive(Debug)]
enum VacantEntryInner<'a, K: 'a, V: 'a> {
Root(&'a mut Option<Node<K, V>>),
Internal(usize, u8, &'a mut Node<K, V>),
}
impl<'a, K: 'a + Borrow<[u8]>, V: 'a> VacantEntry<'a, K, V> {
pub fn key(&self) -> &K {
&self.key
}
pub fn into_key(self) -> K {
self.key
}
pub fn insert(self, val: V) -> &'a mut V {
*self.count += 1;
match self.inner {
VacantEntryInner::Root(root) => {
debug_assert!(root.is_none());
*root = Some(Node::Leaf(Leaf::new(self.key, val)));
let root_mut_opt = root.as_mut();
let leaf_mut = unsafe { root_mut_opt.unchecked_unwrap().unwrap_leaf_mut() };
&mut leaf_mut.val
}
VacantEntryInner::Internal(graft, graft_nybble, node) => {
node.insert_with_graft_point(graft, graft_nybble, self.key, val)
}
}
}
}
#[derive(Debug)]
pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
_dummy: PhantomData<&'a mut ()>,
leaf: *mut Leaf<K, V>,
root: *mut Option<Node<K, V>>,
count: &'a mut usize,
}
impl<'a, K: 'a + Borrow<[u8]>, V: 'a> OccupiedEntry<'a, K, V> {
pub fn key(&self) -> &K {
let leaf = unsafe { &*self.leaf };
&leaf.key
}
pub fn remove_entry(self) -> (K, V) {
let root = unsafe { &mut *self.root };
*self.count -= 1;
match *root {
Some(Node::Leaf(_)) => {
let leaf_opt = root.take();
let leaf = unsafe { leaf_opt.unchecked_unwrap().unwrap_leaf() };
debug_assert!(leaf.key_slice() == self.key().borrow());
(leaf.key, leaf.val)
}
Some(Node::Branch(_)) => {
let branch_opt = root.as_mut();
let branch = unsafe { branch_opt.unchecked_unwrap() };
let leaf_opt = branch.remove_validated(self.key().borrow());
debug_assert!(leaf_opt.is_some());
let leaf = unsafe { leaf_opt.unchecked_unwrap() };
(leaf.key, leaf.val)
}
None => unsafe { debug_unreachable!() },
}
}
pub fn get(&self) -> &V {
let leaf = unsafe { &*self.leaf };
&leaf.val
}
pub fn get_mut(&mut self) -> &mut V {
let leaf = unsafe { &mut *self.leaf };
&mut leaf.val
}
pub fn into_mut(self) -> &'a mut V {
let leaf = unsafe { &mut *self.leaf };
&mut leaf.val
}
pub fn insert(&mut self, val: V) -> V {
let leaf = unsafe { &mut *self.leaf };
mem::replace(&mut leaf.val, val)
}
pub fn remove(self) -> V {
self.remove_entry().1
}
}