intmap/
int_key.rs

1use std::num::{
2    NonZeroI16, NonZeroI32, NonZeroI64, NonZeroI8, NonZeroIsize, NonZeroU16, NonZeroU32,
3    NonZeroU64, NonZeroU8, NonZeroUsize, Wrapping,
4};
5
6use crate::Int;
7
8/// A type that can be used as key for [`IntMap`].
9///
10/// The type needs to be integer based, i.e. it can be represented by a unique integer.
11/// This can be useful for types that wraps integers for type safety (e.g. [`Ipv4Addr`])
12/// or for enforcing invariants (e.g. [`NonZeroU64`]).
13///
14/// # Example
15///
16/// ```
17/// use intmap::{IntKey, IntMap};
18///
19/// #[derive(Clone, Copy)]
20/// struct MyKey(u64);
21///
22/// impl IntKey for MyKey {
23///     type Int = u64;
24///
25///     // You could also choose another prime number
26///     const PRIME: Self::Int = u64::PRIME;
27///
28///     fn into_int(self) -> Self::Int {
29///         self.0
30///     }
31/// }
32///
33/// let map: IntMap<MyKey, f32> = IntMap::new();
34/// ```
35///
36/// [`IntMap`]: crate::IntMap
37/// [`Ipv4Addr`]: std::net::Ipv4Addr
38/// [`NonZeroU64`]: std::num::NonZeroU64
39pub trait IntKey: Copy {
40    /// The underlying integer that will be used as actual key.
41    type Int: Int;
42
43    /// The prime number used for hashing.
44    ///
45    /// The choice might influence the number of key collisions which affects the performance.
46    const PRIME: Self::Int;
47
48    /// Converts the key into the underlying integer.
49    ///
50    /// [`IntMap`] assumes that this is a cheap operation and that two different values
51    /// don't return the same integer.
52    ///
53    /// [`IntMap`]: crate::IntMap
54    fn into_int(self) -> Self::Int;
55}
56
57macro_rules! impl_int_key_for_int {
58    ($self:ident, $prime:expr) => {
59        impl IntKey for $self {
60            type Int = $self;
61
62            const PRIME: Self::Int = $prime;
63
64            fn into_int(self) -> Self::Int {
65                self
66            }
67        }
68    };
69}
70
71// Source: https://t5k.org/lists/2small/
72// Checked with: https://www.numberempire.com/primenumbers.php
73const U8_PRIME_MAX: u8 = u8::MAX - 4; // 251
74const U16_PRIME_MAX: u16 = u16::MAX - 14; // 65521
75const U32_PRIME_MAX: u32 = u32::MAX - 4; // 4294967291
76const U64_PRIME_MAX: u64 = u64::MAX - 58; // 18446744073709551557
77const U128_PRIME_MAX: u128 = u128::MAX - 158; // 340282366920938463463374607431768211297
78
79impl_int_key_for_int!(u8, U8_PRIME_MAX);
80impl_int_key_for_int!(u16, U16_PRIME_MAX);
81impl_int_key_for_int!(u32, U32_PRIME_MAX);
82impl_int_key_for_int!(u64, U64_PRIME_MAX);
83impl_int_key_for_int!(u128, U128_PRIME_MAX);
84#[cfg(target_pointer_width = "16")]
85impl_int_key_for_int!(usize, U16_PRIME_MAX as usize);
86#[cfg(target_pointer_width = "32")]
87impl_int_key_for_int!(usize, U32_PRIME_MAX as usize);
88#[cfg(target_pointer_width = "64")]
89impl_int_key_for_int!(usize, U64_PRIME_MAX as usize);
90
91macro_rules! impl_int_key_for_signed_int {
92    ($self:ident, $unsigned:ident) => {
93        impl IntKey for $self {
94            type Int = $unsigned;
95
96            const PRIME: Self::Int = $unsigned::PRIME;
97
98            fn into_int(self) -> Self::Int {
99                self as $unsigned
100            }
101        }
102    };
103}
104
105impl_int_key_for_signed_int!(i8, u8);
106impl_int_key_for_signed_int!(i16, u16);
107impl_int_key_for_signed_int!(i32, u32);
108impl_int_key_for_signed_int!(i64, u64);
109impl_int_key_for_signed_int!(i128, u128);
110impl_int_key_for_signed_int!(isize, usize);
111
112macro_rules! impl_int_key_for_non_zero_int {
113    ($non_zero_int:ident, $int:ident) => {
114        impl IntKey for $non_zero_int {
115            type Int = <$int as IntKey>::Int;
116
117            const PRIME: Self::Int = $int::PRIME;
118
119            fn into_int(self) -> Self::Int {
120                self.get().into_int()
121            }
122        }
123    };
124}
125
126impl_int_key_for_non_zero_int!(NonZeroU8, u8);
127impl_int_key_for_non_zero_int!(NonZeroU16, u16);
128impl_int_key_for_non_zero_int!(NonZeroU32, u32);
129impl_int_key_for_non_zero_int!(NonZeroU64, u64);
130impl_int_key_for_non_zero_int!(NonZeroUsize, usize);
131impl_int_key_for_non_zero_int!(NonZeroI8, i8);
132impl_int_key_for_non_zero_int!(NonZeroI16, i16);
133impl_int_key_for_non_zero_int!(NonZeroI32, i32);
134impl_int_key_for_non_zero_int!(NonZeroI64, i64);
135impl_int_key_for_non_zero_int!(NonZeroIsize, isize);
136
137impl<K: IntKey> IntKey for Wrapping<K> {
138    type Int = K::Int;
139
140    const PRIME: Self::Int = K::PRIME;
141
142    fn into_int(self) -> Self::Int {
143        self.0.into_int()
144    }
145}
146
147impl IntKey for std::net::Ipv4Addr {
148    type Int = u32;
149
150    const PRIME: Self::Int = u32::PRIME;
151
152    fn into_int(self) -> Self::Int {
153        // Copied from Ipv4Addr::to_bits, which does not exist for our MSRV
154        u32::from_be_bytes(self.octets())
155    }
156}
157
158impl IntKey for std::net::Ipv6Addr {
159    type Int = u128;
160
161    const PRIME: Self::Int = u128::PRIME;
162
163    fn into_int(self) -> Self::Int {
164        // Copied from Ipv6Addr::to_bits, which does not exist for our MSRV
165        u128::from_be_bytes(self.octets())
166    }
167}
intmap/int_key.rs

intmap/
int_key.rs
