string_hash_interner/
symbol.rs

1//! Interfaces and types to be used as symbols for the
2//! [`Interner`](crate::Interner).
3//!
4//! The [`Interner::intern`](crate::Interner::intern)
5//! method returns [`Symbol`] types that allow to look-up the original string
6//! using [`Interner::resolve`](crate::Interner::resolve).
7
8use core::num::{NonZeroU16, NonZeroU32, NonZeroUsize};
9
10/// Types implementing this trait can be used as symbols for string interners.
11///
12/// The [`Interner::intern`](crate::Interner::intern)
13/// method returns `Symbol` types that allow to look-up the original string
14/// using [`Interner::resolve`](crate::Interner::resolve).
15///
16/// # Note
17///
18/// Optimal symbols allow for efficient comparisons and have a small memory footprint.
19pub trait Symbol: Copy + Eq {
20    /// Creates a symbol from a `usize`.
21    ///
22    /// Returns `None` if `index` is out of bounds for the symbol.
23    fn try_from_usize(index: usize) -> Option<Self>;
24
25    /// Returns the `usize` representation of `self`.
26    fn to_usize(self) -> usize;
27}
28
29/// Creates the symbol `S` from the given `usize`.
30///
31/// # Panics
32///
33/// Panics if the conversion is invalid.
34#[inline]
35pub(crate) fn expect_valid_symbol<S>(index: usize) -> S
36where
37    S: Symbol,
38{
39    S::try_from_usize(index).expect("encountered invalid symbol")
40}
41
42/// The symbol type that is used by default.
43pub type DefaultSymbol = SymbolU32;
44
45impl Symbol for usize {
46    #[inline]
47    fn try_from_usize(index: usize) -> Option<Self> {
48        Some(index)
49    }
50
51    #[inline]
52    fn to_usize(self) -> usize {
53        self
54    }
55}
56
57macro_rules! gen_symbol_for {
58    (
59        $( #[$doc:meta] )*
60        struct $name:ident($non_zero:ty; $base_ty:ty);
61    ) => {
62        $( #[$doc] )*
63        #[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
64        pub struct $name {
65            pub(crate) value: $non_zero,
66        }
67
68        impl $name {
69            pub(crate) fn new(index: $base_ty) -> Option<Self> {
70                <$non_zero>::new((index).wrapping_add(1))
71                    .map(|value| Self { value })
72            }
73        }
74
75        impl Symbol for $name {
76            #[inline]
77            fn try_from_usize(index: usize) -> Option<Self> {
78                <$base_ty>::try_from(index).ok().and_then(Self::new)
79            }
80
81            #[inline]
82            fn to_usize(self) -> usize {
83                self.value.get() as usize - 1
84            }
85        }
86    };
87}
88gen_symbol_for!(
89    /// Symbol that is 16-bit in size.
90    ///
91    /// Is space-optimized for used in `Option`.
92    struct SymbolU16(NonZeroU16; u16);
93);
94gen_symbol_for!(
95    /// Symbol that is 32-bit in size.
96    ///
97    /// Is space-optimized for used in `Option`.
98    struct SymbolU32(NonZeroU32; u32);
99);
100gen_symbol_for!(
101    /// Symbol that is the same size as a pointer (`usize`).
102    ///
103    /// Is space-optimized for used in `Option`.
104    struct SymbolUsize(NonZeroUsize; usize);
105);
106
107#[cfg(test)]
108mod tests {
109    use super::*;
110
111    #[test]
112    fn same_size_as_u32() {
113        assert_eq!(size_of::<DefaultSymbol>(), size_of::<u32>());
114    }
115
116    #[test]
117    fn same_size_as_optional() {
118        assert_eq!(
119            size_of::<DefaultSymbol>(),
120            size_of::<Option<DefaultSymbol>>()
121        );
122    }
123
124    #[test]
125    fn try_from_usize_works() {
126        assert_eq!(
127            SymbolU16::try_from_usize(0),
128            Some(SymbolU16 {
129                value: NonZeroU16::new(1).unwrap()
130            })
131        );
132        assert_eq!(
133            SymbolU16::try_from_usize(u16::MAX as usize - 1),
134            Some(SymbolU16 {
135                value: NonZeroU16::new(u16::MAX).unwrap()
136            })
137        );
138        assert_eq!(SymbolU16::try_from_usize(u16::MAX as usize), None);
139        assert_eq!(SymbolU16::try_from_usize(u16::MAX as usize + 1), None);
140        assert_eq!(SymbolU16::try_from_usize(u16::MAX as usize + 123456), None);
141        assert_eq!(SymbolU16::try_from_usize(usize::MAX), None);
142        assert_eq!(SymbolU16::try_from_usize(usize::MAX - 1), None);
143        assert_eq!(SymbolU16::try_from_usize(usize::MAX - 123456), None);
144    }
145
146    macro_rules! gen_test_for {
147        ( $test_name:ident: struct $name:ident($non_zero:ty; $base_ty:ty); ) => {
148            #[test]
149            fn $test_name() {
150                for val in 0..10 {
151                    assert_eq!(
152                        <$name>::try_from_usize(val),
153                        Some($name {
154                            value: <$non_zero>::new(val as $base_ty + 1).unwrap()
155                        })
156                    );
157                }
158                assert_eq!(
159                    <$name>::try_from_usize(<$base_ty>::MAX as usize - 1),
160                    Some($name {
161                        value: <$non_zero>::new(<$base_ty>::MAX).unwrap()
162                    })
163                );
164                assert_eq!(<$name>::try_from_usize(<$base_ty>::MAX as usize), None);
165                assert_eq!(<$name>::try_from_usize(<usize>::MAX), None);
166            }
167        };
168    }
169    gen_test_for!(
170        try_from_usize_works_for_u16:
171        struct SymbolU16(NonZeroU16; u16);
172    );
173    gen_test_for!(
174        try_from_usize_works_for_u32:
175        struct SymbolU32(NonZeroU32; u32);
176    );
177    gen_test_for!(
178        try_from_usize_works_for_usize:
179        struct SymbolUsize(NonZeroUsize; usize);
180    );
181}
string_hash_interner/symbol.rs

string_hash_interner/
symbol.rs
