hi_sparse_bitset 0.7.3

Hierarchical sparse bitset. Incredibly high performance. Compact memory usage.
Documentation 
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

use std::mem::{MaybeUninit, size_of};
use crate::bit_block::BitBlock;
use crate::{Primitive, PrimitiveArray};
use crate::bitset::level::IBlock;

#[derive(Clone)]
#[repr(C)]          // repr(C) for BitSet::deserialization Data level 
pub struct Block<Mask, BlockIndices> {
    mask: Mask,
    /// Next level block indices
    block_indices: BlockIndices,
}

impl<Mask, BlockIndices> Default for Block<Mask, BlockIndices>
where
    Mask: BitBlock,
    BlockIndices: PrimitiveArray
{
    #[inline]
    fn default() -> Self {
        Self {
            mask: Mask::zero(),
            // All indices 0.
            block_indices: unsafe{MaybeUninit::zeroed().assume_init()}
        }
    }
}

impl<Mask, BlockIndices> Block<Mask, BlockIndices>
where
    Mask: BitBlock,
    BlockIndices: PrimitiveArray
{
    #[inline]
    pub unsafe fn from_parts(mask: Mask, block_indices: BlockIndices) -> Self {
        Self { mask,block_indices }
    }
}

impl<Mask, BlockIndices> IBlock for Block<Mask, BlockIndices>
where
    Mask: BitBlock,
    BlockIndices: PrimitiveArray
{
    type Mask = Mask;

    #[inline]
    fn mask(&self) -> &Self::Mask {
        &self.mask
    }

    #[inline]
    unsafe fn mask_mut(&mut self) -> &mut Self::Mask {
        &mut self.mask
    }

    type Item = BlockIndices::Item;

    /// Same as `get_unchecked`
    /// 
    /// # Safety
    ///
    /// `index` is not checked.
    #[inline]
    unsafe fn get_or_zero(&self, index: usize) -> Self::Item {
        let block_indices = self.block_indices.as_ref();
        *block_indices.get_unchecked(index)
    }

    /// # Safety
    ///
    /// `index` is not checked.
    #[inline]
    unsafe fn get_or_insert(&mut self, index: usize, mut f: impl FnMut() -> Self::Item) -> Self::Item {
        // mask
        let exists = self.mask.set_bit_unchecked::<true>(index);

        // indices
        let block_indices = self.block_indices.as_mut();
        if exists {
            *block_indices.get_unchecked(index)
        } else {
            let block_index = f();
            *block_indices.get_unchecked_mut(index) = block_index;
            block_index
        }
    }

    /// # Safety
    ///
    /// `index` is not checked.
    #[inline]
    unsafe fn insert_unchecked(&mut self, index: usize, item: Self::Item) {
        // mask
        let exists = self.mask.set_bit_unchecked::<true>(index);
        debug_assert!(!exists);

        // indices
        let block_indices = self.block_indices.as_mut();
        *block_indices.get_unchecked_mut(index) = item;
    }

    /// # Safety
    ///
    /// `index` is not checked.
    #[inline]
    unsafe fn remove_unchecked(&mut self, index: usize) {
        // mask
        self.mask.set_bit_unchecked::<false>(index);
        // If we have block_indices section (compile-time check)
        if !size_of::<BlockIndices>().is_zero(){
            let block_indices = self.block_indices.as_mut();
            *block_indices.get_unchecked_mut(index) = Primitive::ZERO;
        }
    }
}