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.
Implementations§
Source§impl<Levels, Data, R> SparseTree<Levels, Data, R>where
Levels: SparseTreeLevels,
R: DefaultRequirement,
impl<Levels, Data, R> SparseTree<Levels, Data, R>where
Levels: SparseTreeLevels,
R: DefaultRequirement,
Sourcepub fn remove(
&mut self,
index: impl Into<Index<Levels::Mask, Levels::LevelCount>>,
) -> Option<Data>
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.
Sourcepub fn get_or_insert(
&mut self,
index: impl Into<Index<Levels::Mask, Levels::LevelCount>>,
) -> &mut Datawhere
Data: Default,
pub fn get_or_insert(
&mut self,
index: impl Into<Index<Levels::Mask, Levels::LevelCount>>,
) -> &mut Datawhere
Data: Default,
Returns mutable reference to item at index
, if exists.
Inserts and return Default, otherwise.
Sourcepub fn insert(
&mut self,
index: impl Into<Index<Levels::Mask, Levels::LevelCount>>,
value: Data,
)
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.
Thou, if empty constructor is not complex - compiler may be able to optimize away intermediate value anyway. But better safe then sorry. ↩
Sourcepub fn get_mut(
&mut self,
index: impl Into<Index<Levels::Mask, Levels::LevelCount>>,
) -> Option<&mut Data>
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.
Sourcepub unsafe fn get_mut_unchecked(&mut self, index: usize) -> &mut Data
pub unsafe fn get_mut_unchecked(&mut self, index: usize) -> &mut Data
§Safety
Element at index
must exist in container.
Sourcepub fn key_values(&self) -> (&[usize], &[Data])
pub fn key_values(&self) -> (&[usize], &[Data])
Key-values in arbitrary order.
Sourcepub fn key_values_mut(&mut self) -> (&[usize], &mut [Data])
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,
impl<Levels, Data> SparseTree<Levels, Data, ReqDefault>where
Levels: SparseTreeLevels,
Data: Default,
Sourcepub fn get_or_default(
&self,
index: impl Into<Index<Levels::Mask, Levels::LevelCount>>,
) -> &Data
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.