smallmap/
space.rs

1//! Space-efficient small maps and sets
2//!
3//! To make an entirely space efficient `Map` (i.e. size of each page is 256 bytes, there is never more than 1 page), the following must be true:
4//!
5//! * The key must be 8 bits wide and subject to the *null pointer optimisation*
6//! * The value must be a ZST.
7//!
8//! This leaves pretty much only `std::num::NonZeroU8` and `std::num::NonZeroI8` as entirely space-efficient key candidates.
9//! The restriction on values also means the only entirely space-efficient smallmaps are sets, enable to encode only if a key is present, with no extra information. (See `std::collections::HashSet`).
10use super::*;
11
12/// A set of only non-zero bytes.
13///
14/// This type is entirely space efficient and will only ever allocate `256` bytes of memory.
15pub type NonZeroByteSet = Set<core::num::NonZeroU8>;
16
17/// A set of non-zero signed 8-bit integers.
18///
19/// This type is entirely space efficient and will only ever allocate `256` bytes of memory.
20pub type NonZeroI8Set = Set<core::num::NonZeroI8>;
21
22/// A set of non-zero unsigned 8-bit integers.
23///
24/// This type is entirely space efficient and will only ever allocate `256` bytes of memory.
25pub type NonZeroU8Set = NonZeroByteSet;
26
27#[cfg(test)]
28mod tests
29{
30    use super::*;
31
32    /// Returns the currently allocated space of `map`.
33    pub fn space_of<K, V>(map: &Map<K,V>) -> usize
34    {
35	map.internal_size_bytes()
36    }
37
38    /// Check the allocation size of types in this module
39    mod allocsz {
40	use super::*;
41
42	/// Assert the allocated space (in bytes) of `map` is equal to `expected`.
43	pub fn assert_space_of<T, K, V>(map: T, expected: usize)
44	    where T: std::borrow::Borrow<Map<K,V>>
45	{
46	    let sz = space_of(map.borrow());
47	    assert_eq!(sz, expected, "unexpected full allocated size of type {}: expected {expected}, got {sz}.", std::any::type_name::<Map<K,V>>());
48	}
49
50	/// Create a test that asserts the allocation size of a type is equal to a specific number of bytes
51	///
52	/// # Usage
53	/// ```
54	/// # use super::*;
55	/// size_test!(non_zero_byte_set, NonZeroByteSet, 256); // Creates a test function, named `non_zero_byte_set`, that asserts the type `NonZeroByteSet` allocates exactly 256 bytes.
56	/// ```
57	macro_rules! size_test {
58	    ($name:ident, $type:ty, $num:expr) => {
59		#[test]
60		fn $name() {
61		    assert_space_of(<$type>::new(), $num);
62		}
63	    }
64	}
65
66	size_test!(non_zero_byte_set, NonZeroByteSet, 256);
67	size_test!(non_zero_u8_set, NonZeroU8Set, 256);
68	size_test!(non_zero_i8_set, NonZeroI8Set, 256);
69    }
70}
smallmap/space.rs

smallmap/
space.rs
