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
131
132
133
134
135
136
137
138
139

//! helpers and type for the HAMT bitmap
//!
//! The bitmap map a index into the sparse array index
//!
//! The number of bits set represent the number of elements
//! currently present in the array
//!
//! e.g for the following elements and their indices:
//!
//! ```text
//!     [ (0b0010_0000, x) ]
//! ```
//!
//! will map into this bitmap:
//!
//! ```text
//!     0b0010_0000 (1 bit set)
//! ```
//!
//! and a vector of 1 element containing x
//!
//! ```text
//!     | x |
//! ```
//!
//! or the following elements and their indices:
//!
//! ```text
//!     [ (0b0010_0000, x), (0b1000_0000, y), (0b0000_0010, z) ]
//! ```
//!
//! will map into this bitmap:
//!
//! ```text
//!     0b1010_0010 (3 bit set)
//! ```
//!
//! and a vector of 3 elements containing x, y, z in the following order:
//!
//! ```text
//!     | z | x | y |
//! ```
//!
//!

use super::hash::LevelIndex;
use std::fmt;

/// This is a node size bitmap to allow to find element
/// in the node's array
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct SmallBitmap(u32);

impl fmt::Debug for SmallBitmap {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "SmallBitmap {:032b}", self.0)
    }
}

impl SmallBitmap {
    /// Create a new bitmap with no element
    pub const fn new() -> Self {
        SmallBitmap(0u32)
    }

    #[inline]
    pub fn is_empty(self) -> bool {
        self.0 == 0
    }

    #[inline]
    pub fn present(self) -> usize {
        self.0.count_ones() as usize
    }

    #[inline]
    /// Create a new bitmap with 1 element set
    pub const fn once(b: LevelIndex) -> Self {
        SmallBitmap(b.mask())
    }

    /// Get the sparse array index from a level index
    #[inline]
    pub fn get_index_sparse(self, b: LevelIndex) -> ArrayIndex {
        let mask = b.mask();
        if self.0 & mask == 0 {
            ArrayIndex::not_found()
        } else {
            ArrayIndex::create((self.0 & (mask - 1)).count_ones() as usize)
        }
    }

    /// Get the position of a level index in the sparse array for insertion
    #[inline]
    pub fn get_sparse_pos(self, b: LevelIndex) -> ArrayIndex {
        let mask = b.mask();
        ArrayIndex::create((self.0 & (mask - 1)).count_ones() as usize)
    }

    /// Check if the element exist
    pub fn is_set(self, b: LevelIndex) -> bool {
        (self.0 & b.mask()) != 0
    }

    #[inline]
    pub fn set_index(self, b: LevelIndex) -> Self {
        SmallBitmap(self.0 | b.mask())
    }
    #[inline]
    pub fn clear_index(self, b: LevelIndex) -> Self {
        SmallBitmap(self.0 & !b.mask())
    }
}

/// Sparse index in the array.
///
/// The array elements are allocated on demand,
/// and their presence is indicated by the bitmap
#[derive(Debug, Clone, Copy)]
pub struct ArrayIndex(usize);

impl ArrayIndex {
    pub fn is_not_found(self) -> bool {
        self.0 == 0xff
    }

    pub fn get_found(self) -> usize {
        assert!(!self.is_not_found());
        self.0
    }

    pub fn not_found() -> Self {
        ArrayIndex(0xff)
    }

    pub fn create(s: usize) -> Self {
        ArrayIndex(s)
    }
}