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
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

use crate::ChildIndex;

use slab::Slab;

/// Allocate branch or leaf nodes.
///
/// One [`AllocPtr`] corresponds to a single node at the given [`Level`](crate::Level). Branches always have children pointers,
/// although they may be [`EMPTY_ALLOC_PTR`]. Leaves do not allocate child pointers. For a given [`Level`](crate::Level), only one
/// type of node should be allocated. Level 0 is only leaves and all other levels are only branches.
#[derive(Clone, Debug)]
pub struct NodeAllocator<T, const CHILDREN: usize> {
    /// A slab of pointer blocks. Empty at level 0.
    pointers: Slab<[AllocPtr; CHILDREN]>,
    /// A slab of values.
    values: Slab<T>,
}

/// Points to a node owned by an internal allocator.
pub type AllocPtr = u32;

/// An [`AllocPtr`] that doesn't point to anything.
pub const EMPTY_ALLOC_PTR: AllocPtr = AllocPtr::MAX;

impl<T, const CHILDREN: usize> Default for NodeAllocator<T, CHILDREN> {
    fn default() -> Self {
        Self {
            pointers: Default::default(),
            values: Default::default(),
        }
    }
}

impl<T, const CHILDREN: usize> NodeAllocator<T, CHILDREN> {
    #[inline]
    pub fn insert_leaf(&mut self, value: T) -> AllocPtr {
        self.values.insert(value) as AllocPtr
    }

    #[inline]
    pub fn insert_branch(&mut self, value: T) -> AllocPtr {
        let ptr = self.values.insert(value);
        let pointer_entry = self.pointers.vacant_entry();
        debug_assert_eq!(ptr, pointer_entry.key());
        pointer_entry.insert([EMPTY_ALLOC_PTR; CHILDREN]);
        ptr as AllocPtr
    }

    #[inline]
    pub fn remove(&mut self, ptr: AllocPtr) -> (Option<T>, Option<[AllocPtr; CHILDREN]>) {
        (
            self.values.try_remove(ptr as usize),
            self.pointers.try_remove(ptr as usize),
        )
    }

    #[inline]
    pub fn contains_node(&self, ptr: AllocPtr) -> bool {
        // This assumes that every node has a value.
        self.values.contains(ptr as usize)
    }

    #[inline]
    pub unsafe fn get_value_unchecked(&self, ptr: AllocPtr) -> &T {
        self.values.get_unchecked(ptr as usize)
    }

    #[inline]
    pub unsafe fn get_value_unchecked_mut(&mut self, ptr: AllocPtr) -> &mut T {
        self.values.get_unchecked_mut(ptr as usize)
    }

    #[inline]
    pub fn get_children_mut_or_panic(&mut self, ptr: AllocPtr) -> &mut [AllocPtr; CHILDREN] {
        self.get_children_mut(ptr).unwrap_or_else(|| {
            panic!(
                "Tried inserting children of {:?} which has no child pointers",
                ptr,
            )
        })
    }

    #[inline]
    pub fn get_value(&self, ptr: AllocPtr) -> Option<&T> {
        self.values.get(ptr as usize)
    }

    #[inline]
    pub fn get_value_mut(&mut self, ptr: AllocPtr) -> Option<&mut T> {
        self.values.get_mut(ptr as usize)
    }

    #[inline]
    pub fn get_children(&self, ptr: AllocPtr) -> Option<&[AllocPtr; CHILDREN]> {
        self.pointers.get(ptr as usize)
    }

    #[inline]
    pub fn get_children_mut(&mut self, ptr: AllocPtr) -> Option<&mut [AllocPtr; CHILDREN]> {
        self.pointers.get_mut(ptr as usize)
    }

    #[inline]
    pub fn set_child_pointer(
        &mut self,
        parent_ptr: AllocPtr,
        child_index: ChildIndex,
        child_ptr: AllocPtr,
    ) {
        if let Some(children) = self.get_children_mut(parent_ptr) {
            children[child_index as usize] = child_ptr;
        }
    }

    #[inline]
    pub fn unlink_child(&mut self, parent_ptr: AllocPtr, child_index: ChildIndex) {
        self.set_child_pointer(parent_ptr, child_index, EMPTY_ALLOC_PTR)
    }
}