fixed_map/
key.rs

1//! Module for the trait to define a `Key`.
2
3#[cfg(feature = "hashbrown")]
4use crate::map::storage::HashbrownMapStorage;
5use crate::map::storage::{BooleanMapStorage, MapStorage, OptionMapStorage, SingletonMapStorage};
6#[cfg(feature = "hashbrown")]
7use crate::set::storage::HashbrownSetStorage;
8use crate::set::storage::{BooleanSetStorage, OptionSetStorage, SetStorage, SingletonSetStorage};
9
10/// The trait for a key that can be used to store values in a
11/// [`Map`][crate::Set] or [`Set`][crate::Set].
12///
13/// This is implemented automatically from enums through the
14/// [`Key`][key-derive]. The following is a *simple* key which has no nested
15/// keys:
16///
17/// ```
18/// use fixed_map::Key;
19///
20/// #[derive(Clone, Copy, Key)]
21/// enum MyKey {
22///     First,
23///     Second,
24/// }
25/// ```
26///
27/// *Composite keys* are when keys structurally includes other keys. They have
28/// slightly worse performance than simple keys because they can't be simply
29/// arranged as arrays internally. `bool` below here implements [`Key`] and
30/// using it in one key constructs a composite key. It's a simple form of key
31/// since it can only inhabit two values - `true` or `false`. `Option<K>` can
32/// also be used as a composite key:
33///
34/// ```
35/// use fixed_map::Key;
36///
37/// #[derive(Clone, Copy, Key)]
38/// enum MyKey {
39///     First(bool),
40///     Second(Option<bool>),
41/// }
42/// ```
43///
44/// Some composite keys require dynamic storage since they can inhabit a large
45/// number of values, and preferrably should be avoided in favor of using a
46/// `HashMap` directly. But if you absolutely have to you can enable the `map`
47/// feature:
48///
49/// ```
50/// use fixed_map::Key;
51///
52/// #[derive(Clone, Copy, Key)]
53/// enum MyKey {
54///     # #[cfg(feature = "hashbrown")]
55///     First(u32),
56///     Second,
57/// }
58/// ```
59///
60/// ## Ordering
61///
62/// Keys provide their own ordering semantics instead of relying on the
63/// [`PartialOrd`] and [`Ord`] traits.
64///
65/// Therefore keys when stored in a collection such as [`Map`] and [`Set`] are
66/// always ordered in *declaration order*. This allows those containers
67/// themselves to be ordered if the underlying key supports, it similarly to how
68/// [`BTreeMap`] and [`BTreeSet`] works.
69///
70/// ```
71/// use fixed_map::{Key, Set};
72///
73/// #[derive(Clone, Copy, Key)]
74/// enum MyKey {
75///     First,
76///     Second,
77///     Third,
78/// }
79///
80/// let mut a = Set::new();
81/// a.insert(MyKey::First);
82///
83/// let mut b = Set::new();
84/// b.insert(MyKey::Third);
85///
86/// let mut c = Set::new();
87/// c.insert(MyKey::First);
88/// c.insert(MyKey::Third);
89///
90/// assert!(a < b);
91/// assert!(c < b);
92/// assert!(a < c);
93/// ```
94///
95/// The same example with [`BTreeSet`]:
96///
97/// ```
98/// use std::collections::BTreeSet;
99///
100/// #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
101/// enum MyKey {
102///     First,
103///     Second,
104///     Third,
105/// }
106///
107/// let mut a = BTreeSet::new();
108/// a.insert(MyKey::First);
109///
110/// let mut b = BTreeSet::new();
111/// b.insert(MyKey::Third);
112///
113/// let mut c = BTreeSet::new();
114/// c.insert(MyKey::First);
115/// c.insert(MyKey::Third);
116///
117/// assert!(a < b);
118/// assert!(c < b);
119/// assert!(a < c);
120/// ```
121///
122/// [`BTreeMap`]: https://doc.rust-lang.org/std/collections/struct.BTreeMap.html
123/// [`BTreeSet`]: https://doc.rust-lang.org/std/collections/struct.BTreeSet.html
124/// [`Map`]: crate::Map
125/// [`Set`]: crate::Set
126/// [key-derive]: derive@crate::Key
127pub trait Key: Copy {
128    /// The [`Map`][crate::Map] storage implementation to use for the key
129    /// implementing this trait.
130    type MapStorage<V>: MapStorage<Self, V>;
131
132    /// The [`Set`][crate::Set] storage implementation to use for the key
133    /// implementing this trait.
134    type SetStorage: SetStorage<Self>;
135}
136
137impl Key for bool {
138    type MapStorage<V> = BooleanMapStorage<V>;
139    type SetStorage = BooleanSetStorage;
140}
141
142impl<K> Key for Option<K>
143where
144    K: Key,
145{
146    type MapStorage<V> = OptionMapStorage<K, V>;
147    type SetStorage = OptionSetStorage<K>;
148}
149
150macro_rules! map_key {
151    ($ty:ty) => {
152        #[cfg(feature = "hashbrown")]
153        impl Key for $ty {
154            type MapStorage<V> = HashbrownMapStorage<$ty, V>;
155            type SetStorage = HashbrownSetStorage<$ty>;
156        }
157    };
158}
159
160macro_rules! singleton_key {
161    ($ty:ty) => {
162        impl Key for $ty {
163            type MapStorage<V> = SingletonMapStorage<V>;
164            type SetStorage = SingletonSetStorage;
165        }
166    };
167}
168
169map_key!(char);
170map_key!(u8);
171map_key!(u32);
172map_key!(u64);
173map_key!(u128);
174map_key!(usize);
175map_key!(i8);
176map_key!(i32);
177map_key!(i64);
178map_key!(i128);
179map_key!(isize);
180map_key!(&'static str);
181map_key!(&'static [u8]);
182singleton_key!(());
fixed_map/key.rs

fixed_map/
key.rs
