Struct SparseTree

Source
pub struct SparseTree<Levels, Data, R = ReqDefault<false>>
where Levels: SparseTreeLevels, R: DefaultRequirement,
{ /* private fields */ }
Expand description

Uncompressed Hierarchical Bitmap Tree.

Nodes store children pointers in sparse array. This means that array size equals to maximum children count (bitmask width).

To save memory, instead of traditional pointers, integer indices are used. Root level use u8 for indices, first level - u16, everything below - u32.

It is slightly faster than DenseTree, and can have wider nodes with SIMD-accelerated bitmasks.

§get_or_default

Pass ReqDefault as R argument, to unlock get_or_default operation1. This will require Data to be Default to construct container.

get_or_default is as fast as get_unchecked and has no performance hit from branching2.


  1. We can’t just treat container with Data: Default as ReqDefault, due to stable Rust limitations - we need specialization for that. 

  2. All non-existent items just point to the very first default item. 

Implementations§

Source§

impl<Levels, Data, R> SparseTree<Levels, Data, R>
where Levels: SparseTreeLevels, R: DefaultRequirement,

Source

pub fn remove( &mut self, index: impl Into<Index<Levels::Mask, Levels::LevelCount>>, ) -> Option<Data>

Returns Some(item) if there is an element at index in container. None otherwise.

Source

pub fn get_or_insert( &mut self, index: impl Into<Index<Levels::Mask, Levels::LevelCount>>, ) -> &mut Data
where Data: Default,

Returns mutable reference to item at index, if exists. Inserts and return Default, otherwise.

Source

pub fn insert( &mut self, index: impl Into<Index<Levels::Mask, Levels::LevelCount>>, value: Data, )

Inserts value at index. If there was a value - it will be replaced.

Somewhat faster than *get_or_insert() = value, since it will not insert intermediate default value 1, if index unoccupied.


  1. Thou, if empty constructor is not complex - compiler may be able to optimize away intermediate value anyway. But better safe then sorry. 

Source

pub fn get_mut( &mut self, index: impl Into<Index<Levels::Mask, Levels::LevelCount>>, ) -> Option<&mut Data>

Returns Some, if element with index exists in container. None - otherwise.

Source

pub unsafe fn get_mut_unchecked(&mut self, index: usize) -> &mut Data

§Safety

Element at index must exist in container.

Source

pub fn key_values(&self) -> (&[usize], &[Data])

Key-values in arbitrary order.

Source

pub fn key_values_mut(&mut self) -> (&[usize], &mut [Data])

Mutable key-values in arbitrary order.

Source§

impl<Levels, Data> SparseTree<Levels, Data, ReqDefault>
where Levels: SparseTreeLevels, Data: Default,

Source

pub fn get_or_default( &self, index: impl Into<Index<Levels::Mask, Levels::LevelCount>>, ) -> &Data

This is SIGNIFICANTLY faster than get(index).unwrap_or(Default::default()).

Completely branchless implementation. Performance-wise equivalent of dereferencing LevelCount pointers.

Trait Implementations§

Source§

impl<Levels, Data, R> Borrowable for SparseTree<Levels, Data, R>
where Levels: SparseTreeLevels, R: DefaultRequirement,

Source§

type Borrowed = SparseTree<Levels, Data, R>

Source§

impl<Levels, Data, R> Default for SparseTree<Levels, Data, R>
where Levels: SparseTreeLevels, R: DefaultRequirement, DefaultInitFor<Data, R>: DefaultInit,

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

impl<Levels, Data, R> Drop for SparseTree<Levels, Data, R>
where Levels: SparseTreeLevels, R: DefaultRequirement,

Source§

fn drop(&mut self)

Executes the destructor for this type. Read more
Source§

impl<Levels, Data, R> HibitTree for SparseTree<Levels, Data, R>
where Levels: SparseTreeLevels, R: DefaultRequirement,

Source§

const EXACT_HIERARCHY: bool = true

Marker that this tree as a bitmap hierarchy does not have false-positive bits in bitmasks.
Source§

type LevelCount = <Levels as SparseTreeLevels>::LevelCount

Hierarchy levels count (without a data level).
Source§

type LevelMask = <Levels as SparseTreeLevels>::Mask

Bitmask used in each Node.
Source§

unsafe fn data(&self, index: usize, level_indices: &[usize]) -> Option<&Data>

Safety Read more
Source§

unsafe fn data_unchecked(&self, index: usize, level_indices: &[usize]) -> &Data

Safety Read more
Source§

fn iter(&self) -> Iter<'_, Self>

Source§

fn get( &self, index: impl Into<Index<<Self as HibitTree>::LevelMask, Self::LevelCount>>, ) -> Option<<Self as HibitTreeTypes<'_>>::Data>

You can use usize or Index for index.
Source§

unsafe fn get_unchecked( &self, index: usize, ) -> <Self as HibitTreeTypes<'_>>::DataUnchecked

Safety Read more
Source§

fn index_range() -> RangeTo<usize>

Index range this SparseHierarchy can handle - 0..width^depth. Read more
Source§

impl<'this, Levels, Data, R> HibitTreeTypes<'this> for SparseTree<Levels, Data, R>
where Levels: SparseTreeLevels, R: DefaultRequirement,

Source§

type Data = &'this Data

Source§

type DataUnchecked = &'this Data

Source§

type Cursor = Cursor<'this, Levels, Data, R>

Auto Trait Implementations§

§

impl<Levels, Data, R> Freeze for SparseTree<Levels, Data, R>
where Levels: Freeze,

§

impl<Levels, Data, R> RefUnwindSafe for SparseTree<Levels, Data, R>
where Levels: RefUnwindSafe, R: RefUnwindSafe, Data: RefUnwindSafe,

§

impl<Levels, Data, R> Send for SparseTree<Levels, Data, R>
where Levels: Send, R: Send, Data: Send,

§

impl<Levels, Data, R> Sync for SparseTree<Levels, Data, R>
where Levels: Sync, R: Sync, Data: Sync,

§

impl<Levels, Data, R> Unpin for SparseTree<Levels, Data, R>
where Levels: Unpin, R: Unpin, Data: Unpin,

§

impl<Levels, Data, R> UnwindSafe for SparseTree<Levels, Data, R>
where Levels: UnwindSafe, R: UnwindSafe, Data: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> RegularHibitTree for T
where T: HibitTree + for<'this> RegularHibitTreeTypes<'this>,

Source§

fn map<F>(self, f: F) -> Map<Self, F>
where F: for<'a> MapFunction<'a, <Self as HibitTreeTypes<'a>>::Data>,

Source§

fn map_ref<F>(&self, f: F) -> Map<&Self, F>
where F: for<'a> MapFunction<'a, <Self as HibitTreeTypes<'a>>::Data>,

Source§

impl<T> Take<T> for T

Source§

fn take(self) -> T

Takes self as T. Read more
Source§

fn try_take(self) -> Option<T>

Returned Option variant can be used for compile-time switch.
Source§

fn take_or_clone(self) -> T

Return self as is for T, clone for &T.
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.