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
117
118
119
120
121
122
123
124
125
126
127
128
129
130

//! Configurations for [BitSet].
//!
//! Increasing block size will increase max index [BitSet] can hold.
//! Decreasing block size will lower memory footprint.
//!
//! For your task, you can make specialized config. For example, if you're
//! not limited by MAX index, and know that your indices will be dense,
//! you can try 64/64/256 bit levels.
//!
//! [BitSet]: crate::BitSet

use std::marker::PhantomData;
use crate::bit_block::BitBlock;
use crate::cache;
use crate::cache::ReduceCache;
use crate::primitive_array::PrimitiveArray;

type DefaultCache = cache::FixedCache<32>;

/// [BitSet] configuration
/// 
/// [BitSet]: crate::BitSet
pub trait Config: 'static {
// Level 0
    /// BitBlock used as bitmask for level 0.
    type Level0BitBlock: BitBlock;

    /// Contiguous container, used as indirection storage for level 0.
    ///
    /// * Must be big enough to accommodate at least [Level0BitBlock]::size().
    /// * Item should be able to store [Level0BitBlock]::size() integer.  
    ///
    /// [Level0BitBlock]: Self::Level0BitBlock
    type Level0BlockIndices: PrimitiveArray;

// Level 1
// There can be maximum [Level0BitBlock]::size() level1 blocks

    /// BitBlock used as bitmask for level 1 block.
    type Level1BitBlock: BitBlock;

    /// Contiguous container, used as indirection storage for level 1 block.
    ///
    /// * Must be big enough to accommodate at least [Level1BitBlock]::size().
    /// * Item should be able to store [Level0BitBlock]::size() * [Level1BitBlock]::size() integer.  
    ///
    /// [Level0BitBlock]: Self::Level0BitBlock
    /// [Level1BitBlock]: Self::Level1BitBlock
    type Level1BlockIndices: PrimitiveArray;

// Level data
// There can be maximum [Level0BitBlock]::SIZE * [Level1BitBlock]::SIZE data level blocks

    /// BitBlock used as bitmask for data level block.
    type DataBitBlock: BitBlock;

// Other
    const MAX_CAPACITY: usize;

    /// Cache used be [reduce()].
    /// 
    /// [reduce()]: crate::reduce()
    type DefaultCache: ReduceCache;
}

#[inline]
const fn max_capacity<Conf: Config>() -> usize {
    (1 << Conf::Level0BitBlock::SIZE_POT_EXPONENT)
        * (1 << Conf::Level1BitBlock::SIZE_POT_EXPONENT)
        * (1 << Conf::DataBitBlock::SIZE_POT_EXPONENT)
}

/// MAX = 262_144
#[derive(Default)]
pub struct _64bit<DefaultCache: ReduceCache = self::DefaultCache>(PhantomData<DefaultCache>);
impl<DefaultCache: ReduceCache> Config for _64bit<DefaultCache> {
    type Level0BitBlock = u64;
    type Level0BlockIndices = [u8; 64];

    type Level1BitBlock = u64;
    type Level1BlockIndices = [u16; 64];

    type DataBitBlock = u64;
    
    const MAX_CAPACITY: usize = max_capacity::<Self>();

    type DefaultCache = DefaultCache;
}

/// MAX = 2_097_152
#[cfg(feature = "simd")]
#[cfg_attr(docsrs, doc(cfg(feature = "simd")))]
#[derive(Default)]
pub struct _128bit<DefaultCache: ReduceCache = self::DefaultCache>(PhantomData<DefaultCache>);
#[cfg(feature = "simd")]
#[cfg_attr(docsrs, doc(cfg(feature = "simd")))]
impl<DefaultCache: ReduceCache> Config for _128bit<DefaultCache> {
    type Level0BitBlock = wide::u64x2;
    type Level0BlockIndices = [u8; 128];

    type Level1BitBlock = wide::u64x2;
    type Level1BlockIndices = [u16; 128];

    type DataBitBlock = wide::u64x2;
    
    const MAX_CAPACITY: usize = max_capacity::<Self>();    

    type DefaultCache = DefaultCache;
}

/// MAX = 16_777_216 
#[cfg(feature = "simd")]
#[cfg_attr(docsrs, doc(cfg(feature = "simd")))]
#[derive(Default)]
pub struct _256bit<DefaultCache: ReduceCache = self::DefaultCache>(PhantomData<DefaultCache>);
#[cfg(feature = "simd")]
#[cfg_attr(docsrs, doc(cfg(feature = "simd")))]
impl<DefaultCache: ReduceCache> Config for _256bit<DefaultCache> {
    type Level0BitBlock = wide::u64x4;
    type Level0BlockIndices = [u8; 256];

    type Level1BitBlock = wide::u64x4;
    type Level1BlockIndices = [u16; 256];

    type DataBitBlock = wide::u64x4;
    
    const MAX_CAPACITY: usize = max_capacity::<Self>() - (256*256);    

    type DefaultCache = DefaultCache;
}