usize_set/
lib.rs

1//! Set data structures optimized to store [`usize`] values.
2
3#![cfg_attr(not(test), no_std)]
4
5extern crate alloc;
6
7pub mod btree;
8mod macros;
9mod storage;
10pub mod vec;
11
12/// Public interface of any index set implementation.
13pub trait IndexSet {
14    /// Return the number of [`usize`] values present
15    /// in this [`IndexSet`].
16    fn len(&self) -> usize;
17
18    /// Checks if this [`IndexSet`] has no inner indexes
19    /// stored within.
20    fn is_empty(&self) -> bool;
21
22    /// Add a new index to this [`IndexSet`].
23    fn insert(&mut self, index: usize);
24
25    /// Remove an index from this [`IndexSet`].
26    fn remove(&mut self, index: usize);
27
28    /// Check the presence of an index in this [`IndexSet`].
29    fn contains(&self, index: usize) -> bool;
30
31    /// Return an iterator over the indices in
32    /// this [`IndexSet`], in ascending order.
33    fn iter(&self) -> impl Iterator<Item = usize> + '_;
34
35    /// Merge two [`IndexSet`] instances.
36    ///
37    /// Corresponds to a mutating set union operation,
38    /// between `self` and `other`.
39    fn union(&mut self, other: &Self);
40
41    /// Attempt to reserve space for the specified
42    /// number of additional [`usize`] elements.
43    fn reserve(&mut self, _size: usize) {
44        // NOOP
45    }
46}
47
48#[inline]
49fn safe_iter_reserve_cap<I>(iter: &I) -> usize
50where
51    I: Iterator,
52{
53    let (min_cap, _) = iter.size_hint();
54
55    // NB: guard against malicious impls
56    // with a reasonable higher bound
57    min_cap.min(256)
58}
59
60#[inline]
61const fn calculate_map_and_set_indices<S>(index: usize) -> (usize, usize)
62where
63    S: storage::Storage,
64{
65    // these let exprs will get optimized into a single op,
66    // since they're in sequence, which is nice
67    let map_index = index / S::WIDTH;
68    let bit_set_index = index % S::WIDTH;
69
70    (map_index, bit_set_index)
71}
usize_set/lib.rs

usize_set/
lib.rs
