devela 0.28.0

A development substrate of coherence.
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219

// devela::data::store::key::set::sparse
//
//! Dense/sparse integer sets.
//

use crate::is;

// Result alias for sparse-set operations.
pub(crate) type SparseSetResult<T> = Result<T, SparseSetError>;

// RETHINK
#[doc = crate::_tags!(data_structure error set)]
/// Sparse-set operation error.
#[doc = crate::_doc_meta!{location("data/store/key")}]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum SparseSetError {
    /// The value is outside the sparse universe.
    ValueOutOfBounds,

    /// The dense storage is full.
    Full,

    /// The requested backing storage is too large.
    AllocationTooLarge,

    /// The backing memory mapping failed.
    MapFailed,
}

#[doc = crate::_tags!(data_structure set)]
/// A sparse integer set with constant-time insertion, removal, lookup and clearing.
#[doc = crate::_doc_meta!{location("data/store/key")}]
///
/// Values are `usize`s in the range `0..SPARSE`.
///
/// `DENSE` is the maximum number of stored values.
/// `SPARSE` is the size of the membership universe.
#[derive(Clone, Debug)]
pub struct SparseSetArray<const DENSE: usize, const SPARSE: usize> {
    /// Stores the live values in `dense[..count]`.
    dense: [usize; DENSE],
    /// Maps each value to its candidate dense index.
    sparse: [usize; SPARSE],
    /// Number of live values in `dense`.
    count: usize,
}
#[rustfmt::skip]
impl<const DENSE: usize, const SPARSE: usize> SparseSetArray<DENSE, SPARSE> {
    /// Creates a new empty sparse set.
    #[must_use]
    pub const fn new() -> Self { Self { dense: [0; DENSE], sparse: [0; SPARSE], count: 0 } }

    /// Returns the maximum number of values this set can store.
    #[must_use]
    pub const fn capacity(&self) -> usize { DENSE }

    /// Returns the size of the value universe.
    #[must_use]
    pub const fn universe(&self) -> usize { SPARSE }

    /// Returns the number of stored values.
    #[must_use]
    pub const fn len(&self) -> usize { self.count }

    /// Returns `true` if the set contains no values.
    #[must_use]
    pub const fn is_empty(&self) -> bool { self.count == 0 }

    /// Returns `true` if the dense storage is full.
    #[must_use]
    pub const fn is_full(&self) -> bool { self.count == DENSE }

    /// Clears the set in constant time.
    ///
    /// This does not clear the dense or sparse arrays.
    pub const fn clear(&mut self) { self.count = 0; }

    /// Returns the live dense values.
    #[must_use]
    pub fn as_slice(&self) -> &[usize] { &self.dense[..self.count] }

    /// Returns an iterator over the stored values.
    pub fn iter(&self) -> core::slice::Iter<'_, usize> { self.as_slice().iter() }

    /// Returns `true` if `value` is present.
    #[must_use]
    pub fn contains(&self, value: usize) -> bool {
        contains_raw(&self.dense, &self.sparse, self.count, value)
    }
    /// Inserts `value`.
    ///
    /// Returns `Ok(true)` if the value was newly inserted.
    /// Returns `Ok(false)` if the value was already present.
    pub fn insert(&mut self, value: usize) -> SparseSetResult<bool> {
        insert_raw(&mut self.dense, &mut self.sparse, &mut self.count, value)
    }
    /// Removes `value`.
    ///
    /// Returns `Ok(true)` if the value was present.
    /// Returns `Ok(false)` if the value was absent.
    pub fn remove(&mut self, value: usize) -> SparseSetResult<bool> {
        remove_raw(&mut self.dense, &mut self.sparse, &mut self.count, value)
    }
    /// Checks the internal dense/sparse consistency.
    ///
    /// # Panics
    /// Panics if the internal invariant is broken.
    pub fn check_consistency(&self) {
        check_consistency_raw(&self.dense, &self.sparse, self.count);
    }
}

impl<const DENSE: usize, const SPARSE: usize> Default for SparseSetArray<DENSE, SPARSE> {
    fn default() -> Self {
        Self::new()
    }
}

#[inline(always)]
pub(super) fn contains_raw(dense: &[usize], sparse: &[usize], count: usize, value: usize) -> bool {
    if value >= sparse.len() {
        return false;
    }

    let index = sparse[value];
    index < count && dense[index] == value
}

#[inline(always)]
pub(super) fn insert_raw(
    dense: &mut [usize],
    sparse: &mut [usize],
    count: &mut usize,
    value: usize,
) -> SparseSetResult<bool> {
    is! { value >= sparse.len(), return Err(SparseSetError::ValueOutOfBounds) }
    is! { contains_raw(dense, sparse, *count, value), return Ok(false) }
    is! { *count == dense.len(), return Err(SparseSetError::Full) }
    dense[*count] = value;
    sparse[value] = *count;
    *count += 1;
    Ok(true)
}

#[inline(always)]
pub(super) fn remove_raw(
    dense: &mut [usize],
    sparse: &mut [usize],
    count: &mut usize,
    value: usize,
) -> SparseSetResult<bool> {
    is! { value >= sparse.len(), return Err(SparseSetError::ValueOutOfBounds) }
    is! { !contains_raw(dense, sparse, *count, value), return Ok(false) }
    let index = sparse[value];
    let last_index = *count - 1;
    let last_value = dense[last_index];
    dense[index] = last_value;
    sparse[last_value] = index;
    *count = last_index;
    Ok(true)
}

#[allow(clippy::needless_range_loop)]
pub(super) fn check_consistency_raw(dense: &[usize], sparse: &[usize], count: usize) {
    assert!(count <= dense.len());
    for index in 0..count {
        let value = dense[index];
        assert!(value < sparse.len());
        assert_eq!(sparse[value], index);
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn basic_sparse_set() {
        let mut set = SparseSetArray::<5, 10_000>::new();
        assert_eq!(set.insert(3), Ok(true));
        assert_eq!(set.insert(5), Ok(true));
        assert_eq!(set.insert(5), Ok(false));
        assert!(set.contains(3));
        assert!(set.contains(5));
        assert!(!set.contains(2));
        assert!(!set.contains(11_000));
        assert_eq!(set.as_slice().len(), 2);
        set.check_consistency();
        assert_eq!(set.remove(3), Ok(true));
        assert!(!set.contains(3));
        assert!(set.contains(5));
        assert_eq!(set.remove(500), Ok(false));
        assert_eq!(set.insert(20_000), Err(SparseSetError::ValueOutOfBounds));
        assert_eq!(set.remove(20_000), Err(SparseSetError::ValueOutOfBounds));
        set.check_consistency();
    }
    #[test]
    fn clear_is_constant_time_and_stale_sparse_is_harmless() {
        let mut set = SparseSetArray::<4, 16>::new();
        assert_eq!(set.insert(3), Ok(true));
        assert_eq!(set.insert(7), Ok(true));
        assert!(set.contains(3));
        assert!(set.contains(7));
        set.clear();
        assert_eq!(set.len(), 0);
        assert!(!set.contains(3));
        assert!(!set.contains(7));
        assert_eq!(set.insert(7), Ok(true));
        assert!(set.contains(7));
        assert!(!set.contains(3));
        set.check_consistency();
    }
    #[test]
    fn dense_capacity_is_checked() {
        let mut set = SparseSetArray::<2, 16>::new();
        assert_eq!(set.insert(1), Ok(true));
        assert_eq!(set.insert(2), Ok(true));
        assert_eq!(set.insert(3), Err(SparseSetError::Full));
    }
}