1#![doc(html_root_url = "https://docs.rs/slotmap/1.0.7")]
2#![crate_name = "slotmap"]
3#![cfg_attr(all(nightly, feature = "unstable"), feature(try_reserve))]
4#![cfg_attr(all(not(test), not(feature = "std")), no_std)]
5#![cfg_attr(all(nightly, doc), feature(doc_cfg))]
6#![warn(
7 missing_debug_implementations,
8 trivial_casts,
9 trivial_numeric_casts,
10 unused_lifetimes,
11 unused_import_braces
12)]
13#![deny(missing_docs, unaligned_references)]
14#![cfg_attr(feature = "cargo-clippy", allow(renamed_and_removed_lints))]
15#![cfg_attr(feature = "cargo-clippy", deny(clippy, clippy_pedantic))]
16#![cfg_attr(
17 feature = "cargo-clippy",
18 allow(
19 // Style differences.
20 module_name_repetitions,
21 redundant_closure_for_method_calls,
22 unseparated_literal_suffix,
23
24 // I know what I'm doing and want these.
25 wildcard_imports,
26 inline_always,
27 cast_possible_truncation,
28 needless_pass_by_value,
29
30 // Very noisy.
31 missing_errors_doc,
32 must_use_candidate
33 ))]
34
35//! # slotmap
36//!
37//! This library provides a container with persistent unique keys to access
38//! stored values, [`SlotMap`]. Upon insertion a key is returned that can be
39//! used to later access or remove the values. Insertion, removal and access all
40//! take O(1) time with low overhead. Great for storing collections of objects
41//! that need stable, safe references but have no clear ownership otherwise,
42//! such as game entities or graph nodes.
43//!
44//! The difference between a [`BTreeMap`] or [`HashMap`] and a slot map is
45//! that the slot map generates and returns the key when inserting a value. A
46//! key is always unique and will only refer to the value that was inserted.
47//! A slot map's main purpose is to simply own things in a safe and efficient
48//! manner.
49//!
50//! You can also create (multiple) secondary maps that can map the keys returned
51//! by [`SlotMap`] to other values, to associate arbitrary data with objects
52//! stored in slot maps, without hashing required - it's direct indexing under
53//! the hood.
54//!
55//! The minimum required stable Rust version for this crate is 1.49.
56//!
57//! # Examples
58//!
59//! ```
60//! # use slotmap::*;
61//! let mut sm = SlotMap::new();
62//! let foo = sm.insert("foo"); // Key generated on insert.
63//! let bar = sm.insert("bar");
64//! assert_eq!(sm[foo], "foo");
65//! assert_eq!(sm[bar], "bar");
66//!
67//! sm.remove(bar);
68//! let reuse = sm.insert("reuse"); // Space from bar reused.
69//! assert_eq!(sm.contains_key(bar), false); // After deletion a key stays invalid.
70//!
71//! let mut sec = SecondaryMap::new();
72//! sec.insert(foo, "noun"); // We provide the key for secondary maps.
73//! sec.insert(reuse, "verb");
74//!
75//! for (key, val) in sm {
76//! println!("{} is a {}", val, sec[key]);
77//! }
78//! ```
79//!
80//! # Serialization through [`serde`], [`no_std`] support and unstable features
81//!
82//! Both keys and the slot maps have full (de)seralization support through
83//! the [`serde`] library. A key remains valid for a slot map even after one or
84//! both have been serialized and deserialized! This makes storing or
85//! transferring complicated referential structures and graphs a breeze. Care has
86//! been taken such that deserializing keys and slot maps from untrusted sources
87//! is safe. If you wish to use these features you must enable the `serde`
88//! feature flag for `slotmap` in your `Cargo.toml`.
89//!
90//! ```text
91//! slotmap = { version = "1.0", features = ["serde"] }
92//! ```
93//!
94//! This crate also supports [`no_std`] environments, but does require the
95//! [`alloc`] crate to be available. To enable this you have to disable the
96//! `std` feature that is enabled by default:
97//!
98//! ```text
99//! slotmap = { version = "1.0", default-features = false }
100//! ```
101//!
102//! Unfortunately [`SparseSecondaryMap`] is not available in [`no_std`], because
103//! it relies on [`HashMap`]. Finally the `unstable` feature can be defined to
104//! enable the parts of `slotmap` that only work on nightly Rust.
105//!
106//! # Why not index a [`Vec`], or use [`slab`], [`stable-vec`], etc?
107//!
108//! Those solutions either can not reclaim memory from deleted elements or
109//! suffer from the ABA problem. The keys returned by `slotmap` are versioned.
110//! This means that once a key is removed, it stays removed, even if the
111//! physical storage inside the slotmap is reused for new elements. The key is a
112//! permanently unique<sup>*</sup> reference to the inserted value. Despite
113//! supporting versioning, a [`SlotMap`] is often not (much) slower than the
114//! alternative, by internally using carefully checked unsafe code. Finally,
115//! `slotmap` simply has a lot of features that make your life easy.
116//!
117//! # Performance characteristics and implementation details
118//!
119//! Insertion, access and deletion is all O(1) with low overhead by storing the
120//! elements inside a [`Vec`]. Unlike references or indices into a vector,
121//! unless you remove a key it is never invalidated. Behind the scenes each
122//! slot in the vector is a `(value, version)` tuple. After insertion the
123//! returned key also contains a version. Only when the stored version and
124//! version in a key match is a key valid. This allows us to reuse space in the
125//! vector after deletion without letting removed keys point to spurious new
126//! elements. <sup>*</sup>After 2<sup>31</sup> deletions and insertions to the
127//! same underlying slot the version wraps around and such a spurious reference
128//! could potentially occur. It is incredibly unlikely however, and in all
129//! circumstances is the behavior safe. A slot map can hold up to
130//! 2<sup>32</sup> - 2 elements at a time.
131//!
132//! The memory usage for each slot in [`SlotMap`] is `4 + max(sizeof(T), 4)`
133//! rounded up to the alignment of `T`. Similarly it is `4 + max(sizeof(T), 12)`
134//! for [`HopSlotMap`]. [`DenseSlotMap`] has an overhead of 8 bytes per element
135//! and 8 bytes per slot.
136//!
137//! # Choosing [`SlotMap`], [`HopSlotMap`] or [`DenseSlotMap`]
138//!
139//! A [`SlotMap`] is the fastest for most operations, except iteration. It can
140//! never shrink the size of its underlying storage, because it must remember
141//! for each storage slot what the latest stored version was, even if the slot
142//! is empty now. This means that iteration can be slow as it must iterate over
143//! potentially a lot of empty slots.
144//!
145//! [`HopSlotMap`] solves this by maintaining more information on
146//! insertion/removal, allowing it to iterate only over filled slots by 'hopping
147//! over' contiguous blocks of vacant slots. This can give it significantly
148//! better iteration speed. If you expect to iterate over all elements in a
149//! [`SlotMap`] a lot, and potentially have a lot of deleted elements, choose
150//! [`HopSlotMap`]. The downside is that insertion and removal is roughly twice
151//! as slow. Random access is the same speed for both.
152//!
153//! [`DenseSlotMap`] goes even further and stores all elements on a contiguous
154//! block of memory. It uses two indirections per random access; the slots
155//! contain indices used to access the contiguous memory. This means random
156//! access is slower than both [`SlotMap`] and [`HopSlotMap`], but iteration is
157//! significantly faster, as fast as a normal [`Vec`].
158//!
159//! # Choosing [`SecondaryMap`] or [`SparseSecondaryMap`]
160//!
161//! You want to associate extra data with objects stored in a slot map, so you
162//! use (multiple) secondary maps to map keys to that data.
163//!
164//! A [`SecondaryMap`] is simply a [`Vec`] of slots like slot map is, and
165//! essentially provides all the same guarantees as [`SlotMap`] does for its
166//! operations (with the exception that you provide the keys as produced by the
167//! primary slot map). This does mean that even if you associate data to only
168//! a single element from the primary slot map, you could need and have to
169//! initialize as much memory as the original.
170//!
171//! A [`SparseSecondaryMap`] is like a [`HashMap`] from keys to objects, however
172//! it automatically removes outdated keys for slots that had their space
173//! reused. You should use this variant if you expect to store some associated
174//! data for only a small portion of the primary slot map.
175//!
176//! # Custom key types
177//!
178//! If you have multiple slot maps it's an error to use the key of one slot map
179//! on another slot map. The result is safe, but unspecified, and can not be
180//! detected at runtime, so it can lead to a hard to find bug.
181//!
182//! To prevent this, slot maps allow you to specify what the type is of the key
183//! they return. You can construct new key types using the [`new_key_type!`]
184//! macro. The resulting type behaves exactly like [`DefaultKey`], but is a
185//! distinct type. So instead of simply using `SlotMap<DefaultKey, Player>` you
186//! would use:
187//!
188//! ```
189//! # use slotmap::*;
190//! # #[derive(Copy, Clone)]
191//! # struct Player;
192//! new_key_type! { struct PlayerKey; }
193//! let sm: SlotMap<PlayerKey, Player> = SlotMap::with_key();
194//! ```
195//!
196//! You can write code generic over any key type using the [`Key`] trait.
197//!
198//! [`Vec`]: std::vec::Vec
199//! [`BTreeMap`]: std::collections::BTreeMap
200//! [`HashMap`]: std::collections::HashMap
201//! [`serde`]: https://github.com/serde-rs/serde
202//! [`slab`]: https://crates.io/crates/slab
203//! [`stable-vec`]: https://crates.io/crates/stable-vec
204//! [`no_std`]: https://doc.rust-lang.org/1.7.0/book/no-stdlib.html
205
206extern crate alloc;
207
208// So our macros can refer to these.
209#[doc(hidden)]
210pub mod __impl {
211 #[cfg(feature = "serde")]
212 pub use serde::{Deserialize, Deserializer, Serialize, Serializer};
213 pub use core::convert::From;
214 pub use core::result::Result;
215}
216
217pub mod basic;
218pub mod dense;
219pub mod hop;
220pub mod secondary;
221#[cfg(feature = "std")]
222pub mod sparse_secondary;
223pub(crate) mod util;
224
225use core::fmt::{self, Debug, Formatter};
226use core::hash::{Hash, Hasher};
227use core::num::NonZeroU32;
228
229#[doc(inline)]
230pub use crate::basic::SlotMap;
231#[doc(inline)]
232pub use crate::dense::DenseSlotMap;
233#[doc(inline)]
234pub use crate::hop::HopSlotMap;
235#[doc(inline)]
236pub use crate::secondary::SecondaryMap;
237#[cfg(feature = "std")]
238#[doc(inline)]
239pub use crate::sparse_secondary::SparseSecondaryMap;
240
241// Keep Slottable for backwards compatibility, but warn about deprecation
242// and hide from documentation.
243#[doc(hidden)]
244#[deprecated(
245 since = "1.0.0",
246 note = "Slottable is not necessary anymore, slotmap now supports all types on stable."
247)]
248pub trait Slottable {}
249
250#[doc(hidden)]
251#[allow(deprecated)]
252impl<T> Slottable for T {}
253
254/// The actual data stored in a [`Key`].
255///
256/// This implements [`Ord`](std::cmp::Ord) so keys can be stored in e.g.
257/// [`BTreeMap`](std::collections::BTreeMap), but the order of keys is
258/// unspecified.
259#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
260pub struct KeyData {
261 idx: u32,
262 version: NonZeroU32,
263}
264
265impl KeyData {
266 fn new(idx: u32, version: u32) -> Self {
267 debug_assert!(version > 0);
268
269 Self {
270 idx,
271 version: unsafe { NonZeroU32::new_unchecked(version | 1) },
272 }
273 }
274
275 fn null() -> Self {
276 Self::new(core::u32::MAX, 1)
277 }
278
279 fn is_null(self) -> bool {
280 self.idx == core::u32::MAX
281 }
282
283 /// Returns the key data as a 64-bit integer. No guarantees about its value
284 /// are made other than that passing it to [`from_ffi`](Self::from_ffi)
285 /// will return a key equal to the original.
286 ///
287 /// With this you can easily pass slot map keys as opaque handles to foreign
288 /// code. After you get them back you can confidently use them in your slot
289 /// map without worrying about unsafe behavior as you would with passing and
290 /// receiving back references or pointers.
291 ///
292 /// This is not a substitute for proper serialization, use [`serde`] for
293 /// that. If you are not doing FFI, you almost surely do not need this
294 /// function.
295 ///
296 /// [`serde`]: crate#serialization-through-serde-no_std-support-and-unstable-features
297 pub fn as_ffi(self) -> u64 {
298 (u64::from(self.version.get()) << 32) | u64::from(self.idx)
299 }
300
301 /// Iff `value` is a value received from `k.as_ffi()`, returns a key equal
302 /// to `k`. Otherwise the behavior is safe but unspecified.
303 pub fn from_ffi(value: u64) -> Self {
304 let idx = value & 0xffff_ffff;
305 let version = (value >> 32) | 1; // Ensure version is odd.
306 Self::new(idx as u32, version as u32)
307 }
308}
309
310impl Debug for KeyData {
311 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
312 write!(f, "{}v{}", self.idx, self.version.get())
313 }
314}
315
316impl Default for KeyData {
317 fn default() -> Self {
318 Self::null()
319 }
320}
321
322impl Hash for KeyData
323{
324 fn hash<H: Hasher>(&self, state: &mut H) {
325 // A derived Hash impl would call write_u32 twice. We call write_u64
326 // once, which is beneficial if the hasher implements write_u64
327 // explicitly.
328 state.write_u64(self.as_ffi())
329 }
330}
331
332/// Key used to access stored values in a slot map.
333///
334/// Do not use a key from one slot map in another. The behavior is safe but
335/// non-sensical (and might panic in case of out-of-bounds).
336///
337/// To prevent this, it is suggested to have a unique key type for each slot
338/// map. You can create new key types using [`new_key_type!`], which makes a
339/// new type identical to [`DefaultKey`], just with a different name.
340///
341/// This trait is intended to be a thin wrapper around [`KeyData`], and all
342/// methods must behave exactly as if we're operating on a [`KeyData`] directly.
343/// The internal unsafe code relies on this, therefore this trait is `unsafe` to
344/// implement. It is strongly suggested to simply use [`new_key_type!`] instead
345/// of implementing this trait yourself.
346pub unsafe trait Key:
347 From<KeyData>
348 + Copy
349 + Clone
350 + Default
351 + Eq
352 + PartialEq
353 + Ord
354 + PartialOrd
355 + core::hash::Hash
356 + core::fmt::Debug
357{
358 /// Creates a new key that is always invalid and distinct from any non-null
359 /// key. A null key can only be created through this method (or default
360 /// initialization of keys made with [`new_key_type!`], which calls this
361 /// method).
362 ///
363 /// A null key is always invalid, but an invalid key (that is, a key that
364 /// has been removed from the slot map) does not become a null key. A null
365 /// is safe to use with any safe method of any slot map instance.
366 ///
367 /// # Examples
368 ///
369 /// ```
370 /// # use slotmap::*;
371 /// let mut sm = SlotMap::new();
372 /// let k = sm.insert(42);
373 /// let nk = DefaultKey::null();
374 /// assert!(nk.is_null());
375 /// assert!(k != nk);
376 /// assert_eq!(sm.get(nk), None);
377 /// ```
378 fn null() -> Self {
379 KeyData::null().into()
380 }
381
382 /// Checks if a key is null. There is only a single null key, that is
383 /// `a.is_null() && b.is_null()` implies `a == b`.
384 ///
385 /// # Examples
386 ///
387 /// ```
388 /// # use slotmap::*;
389 /// new_key_type! { struct MyKey; }
390 /// let a = MyKey::null();
391 /// let b = MyKey::default();
392 /// assert_eq!(a, b);
393 /// assert!(a.is_null());
394 /// ```
395 fn is_null(&self) -> bool {
396 self.data().is_null()
397 }
398
399 /// Gets the [`KeyData`] stored in this key.
400 ///
401 /// # Examples
402 ///
403 /// ```
404 /// # use slotmap::*;
405 /// new_key_type! { struct MyKey; }
406 /// let dk = DefaultKey::null();
407 /// let mk = MyKey::null();
408 /// assert_eq!(dk.data(), mk.data());
409 /// ```
410 fn data(&self) -> KeyData;
411}
412
413/// A helper macro to create new key types. If you use a new key type for each
414/// slot map you create you can entirely prevent using the wrong key on the
415/// wrong slot map.
416///
417/// The type constructed by this macro is defined exactly as [`DefaultKey`],
418/// but is a distinct type for the type checker and does not implicitly convert.
419///
420/// # Examples
421///
422/// ```
423/// # extern crate slotmap;
424/// # use slotmap::*;
425/// new_key_type! {
426/// // A private key type.
427/// struct RocketKey;
428///
429/// // A public key type with a doc comment.
430/// /// Key for the user slot map.
431/// pub struct UserKey;
432/// }
433///
434/// fn main() {
435/// let mut users = SlotMap::with_key();
436/// let mut rockets = SlotMap::with_key();
437/// let bob: UserKey = users.insert("bobby");
438/// let apollo: RocketKey = rockets.insert("apollo");
439/// // Now this is a type error because rockets.get expects an RocketKey:
440/// // rockets.get(bob);
441///
442/// // If for some reason you do end up needing to convert (e.g. storing
443/// // keys of multiple slot maps in the same data structure without
444/// // boxing), you can use KeyData as an intermediate representation. This
445/// // does mean that once again you are responsible for not using the wrong
446/// // key on the wrong slot map.
447/// let keys = vec![bob.data(), apollo.data()];
448/// println!("{} likes rocket {}",
449/// users[keys[0].into()], rockets[keys[1].into()]);
450/// }
451/// ```
452#[macro_export(local_inner_macros)]
453macro_rules! new_key_type {
454 ( $(#[$outer:meta])* $vis:vis struct $name:ident; $($rest:tt)* ) => {
455 $(#[$outer])*
456 #[derive(Copy, Clone, Default,
457 Eq, PartialEq, Ord, PartialOrd,
458 Hash, Debug)]
459 #[repr(transparent)]
460 $vis struct $name($crate::KeyData);
461
462 impl $crate::__impl::From<$crate::KeyData> for $name {
463 fn from(k: $crate::KeyData) -> Self {
464 $name(k)
465 }
466 }
467
468 unsafe impl $crate::Key for $name {
469 fn data(&self) -> $crate::KeyData {
470 self.0
471 }
472 }
473
474 $crate::__serialize_key!($name);
475
476 $crate::new_key_type!($($rest)*);
477 };
478
479 () => {}
480}
481
482#[cfg(feature = "serde")]
483#[doc(hidden)]
484#[macro_export]
485macro_rules! __serialize_key {
486 ( $name:ty ) => {
487 impl $crate::__impl::Serialize for $name {
488 fn serialize<S>(&self, serializer: S) -> $crate::__impl::Result<S::Ok, S::Error>
489 where
490 S: $crate::__impl::Serializer,
491 {
492 $crate::Key::data(self).serialize(serializer)
493 }
494 }
495
496 impl<'de> $crate::__impl::Deserialize<'de> for $name {
497 fn deserialize<D>(deserializer: D) -> $crate::__impl::Result<Self, D::Error>
498 where
499 D: $crate::__impl::Deserializer<'de>,
500 {
501 let key_data: $crate::KeyData =
502 $crate::__impl::Deserialize::deserialize(deserializer)?;
503 Ok(key_data.into())
504 }
505 }
506 };
507}
508
509#[cfg(not(feature = "serde"))]
510#[doc(hidden)]
511#[macro_export]
512macro_rules! __serialize_key {
513 ( $name:ty ) => {};
514}
515
516new_key_type! {
517 /// The default slot map key type.
518 pub struct DefaultKey;
519}
520
521// Serialization with serde.
522#[cfg(feature = "serde")]
523mod serialize {
524 use serde::{Deserialize, Deserializer, Serialize, Serializer};
525
526 use super::*;
527
528 #[derive(Serialize, Deserialize)]
529 pub struct SerKey {
530 idx: u32,
531 version: u32,
532 }
533
534 impl Serialize for KeyData {
535 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
536 where
537 S: Serializer,
538 {
539 let ser_key = SerKey {
540 idx: self.idx,
541 version: self.version.get(),
542 };
543 ser_key.serialize(serializer)
544 }
545 }
546
547 impl<'de> Deserialize<'de> for KeyData {
548 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
549 where
550 D: Deserializer<'de>,
551 {
552 let mut ser_key: SerKey = Deserialize::deserialize(deserializer)?;
553
554 // Ensure a.is_null() && b.is_null() implies a == b.
555 if ser_key.idx == core::u32::MAX {
556 ser_key.version = 1;
557 }
558
559 ser_key.version |= 1; // Ensure version is odd.
560 Ok(Self::new(ser_key.idx, ser_key.version))
561 }
562 }
563}
564
565#[cfg(test)]
566mod tests {
567 // Intentionally no `use super::*;` because we want to test macro expansion
568 // in the *users* scope, which might not have that.
569 #[test]
570 fn macro_expansion() {
571 #![allow(dead_code)]
572 use super::new_key_type;
573
574 // Clobber namespace with clashing names - should still work.
575 trait Serialize { }
576 trait Deserialize { }
577 trait Serializer { }
578 trait Deserializer { }
579 trait Key { }
580 trait From { }
581 struct Result;
582 struct KeyData;
583
584 new_key_type! {
585 struct A;
586 pub(crate) struct B;
587 pub struct C;
588 }
589 }
590
591 #[test]
592 fn check_is_older_version() {
593 use super::util::is_older_version;
594
595 let is_older = |a, b| is_older_version(a, b);
596 assert!(!is_older(42, 42));
597 assert!(is_older(0, 1));
598 assert!(is_older(0, 1 << 31));
599 assert!(!is_older(0, (1 << 31) + 1));
600 assert!(is_older(u32::MAX, 0));
601 }
602
603 #[test]
604 fn iters_cloneable() {
605 use super::*;
606
607 struct NoClone;
608
609 let mut sm = SlotMap::new();
610 let mut hsm = HopSlotMap::new();
611 let mut dsm = DenseSlotMap::new();
612 let mut scm = SecondaryMap::new();
613 let mut sscm = SparseSecondaryMap::new();
614 scm.insert(sm.insert(NoClone), NoClone);
615 sscm.insert(hsm.insert(NoClone), NoClone);
616 dsm.insert(NoClone);
617
618 let _ = sm.keys().clone();
619 let _ = sm.values().clone();
620 let _ = sm.iter().clone();
621 let _ = hsm.keys().clone();
622 let _ = hsm.values().clone();
623 let _ = hsm.iter().clone();
624 let _ = dsm.keys().clone();
625 let _ = dsm.values().clone();
626 let _ = dsm.iter().clone();
627 let _ = scm.keys().clone();
628 let _ = scm.values().clone();
629 let _ = scm.iter().clone();
630 let _ = sscm.keys().clone();
631 let _ = sscm.values().clone();
632 let _ = sscm.iter().clone();
633 }
634
635 #[cfg(feature = "serde")]
636 #[test]
637 fn key_serde() {
638 use super::*;
639
640 // Check round-trip through serde.
641 let mut sm = SlotMap::new();
642 let k = sm.insert(42);
643 let ser = serde_json::to_string(&k).unwrap();
644 let de: DefaultKey = serde_json::from_str(&ser).unwrap();
645 assert_eq!(k, de);
646
647 // Even if a malicious entity sends up even (unoccupied) versions in the
648 // key, we make the version point to the occupied version.
649 let malicious: KeyData = serde_json::from_str(&r#"{"idx":0,"version":4}"#).unwrap();
650 assert_eq!(malicious.version.get(), 5);
651 }
652}
653