#![doc(html_root_url = "https://docs.rs/slotmap/1.0.2")]
#![cfg_attr(all(nightly, feature = "unstable"), feature(try_reserve))]
#![cfg_attr(all(not(test), not(feature = "std")), no_std)]
#![cfg_attr(all(nightly, doc), feature(doc_cfg))]
#![warn(
invalid_html_tags,
missing_debug_implementations,
trivial_casts,
trivial_numeric_casts,
unused_lifetimes,
unused_import_braces
)]
#![deny(missing_docs, unaligned_references)]
#![cfg_attr(feature = "cargo-clippy", allow(renamed_and_removed_lints))]
#![cfg_attr(feature = "cargo-clippy", deny(clippy, clippy_pedantic))]
#![cfg_attr(
feature = "cargo-clippy",
allow(
// Style differences.
module_name_repetitions,
redundant_closure_for_method_calls,
unseparated_literal_suffix,
// I know what I'm doing and want these.
wildcard_imports,
inline_always,
cast_possible_truncation,
needless_pass_by_value,
// Very noisy.
missing_errors_doc,
must_use_candidate
))]
extern crate alloc;
#[cfg(feature = "serde")]
#[doc(hidden)]
pub mod __impl {
pub use serde::{Deserialize, Deserializer, Serialize, Serializer};
}
pub mod basic;
pub mod dense;
pub mod hop;
pub mod secondary;
#[cfg(feature = "std")]
pub mod sparse_secondary;
#[doc(inline)]
pub use crate::basic::SlotMap;
#[doc(inline)]
pub use crate::dense::DenseSlotMap;
#[doc(inline)]
pub use crate::hop::HopSlotMap;
#[doc(inline)]
pub use crate::secondary::SecondaryMap;
#[cfg(feature = "std")]
#[doc(inline)]
pub use crate::sparse_secondary::SparseSecondaryMap;
use core::fmt::{self, Debug, Formatter};
use core::num::NonZeroU32;
#[doc(hidden)]
#[deprecated(
since = "1.0.0",
note = "Slottable is not necessary anymore, slotmap now supports all types on stable."
)]
pub trait Slottable {}
#[doc(hidden)]
#[allow(deprecated)]
impl<T> Slottable for T {}
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct KeyData {
idx: u32,
version: NonZeroU32,
}
impl KeyData {
fn new(idx: u32, version: u32) -> Self {
debug_assert!(version > 0);
Self {
idx,
version: unsafe { NonZeroU32::new_unchecked(version | 1) },
}
}
fn null() -> Self {
Self::new(core::u32::MAX, 1)
}
fn is_null(self) -> bool {
self.idx == core::u32::MAX
}
pub fn as_ffi(self) -> u64 {
(u64::from(self.version.get()) << 32) | u64::from(self.idx)
}
pub fn from_ffi(value: u64) -> Self {
let idx = value & 0xffff_ffff;
let version = (value >> 32) | 1; Self::new(idx as u32, version as u32)
}
}
impl Debug for KeyData {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
write!(f, "{}v{}", self.idx, self.version.get())
}
}
impl Default for KeyData {
fn default() -> Self {
Self::null()
}
}
pub trait Key:
From<KeyData>
+ Copy
+ Clone
+ Default
+ Eq
+ PartialEq
+ Ord
+ PartialOrd
+ core::hash::Hash
+ core::fmt::Debug
{
fn null() -> Self {
KeyData::null().into()
}
fn is_null(&self) -> bool {
self.data().is_null()
}
fn data(&self) -> KeyData;
}
#[macro_export(local_inner_macros)]
macro_rules! new_key_type {
( $(#[$outer:meta])* $vis:vis struct $name:ident; $($rest:tt)* ) => {
$(#[$outer])*
#[derive(Copy, Clone, Default,
Eq, PartialEq, Ord, PartialOrd,
Hash, Debug)]
#[repr(transparent)]
$vis struct $name($crate::KeyData);
impl From<$crate::KeyData> for $name {
fn from(k: $crate::KeyData) -> Self {
$name(k)
}
}
impl $crate::Key for $name {
fn data(&self) -> $crate::KeyData {
self.0
}
}
$crate::__serialize_key!($name);
$crate::new_key_type!($($rest)*);
};
() => {}
}
#[cfg(feature = "serde")]
#[doc(hidden)]
#[macro_export]
macro_rules! __serialize_key {
( $name:ty ) => {
impl $crate::__impl::Serialize for $name {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: $crate::__impl::Serializer,
{
$crate::Key::data(self).serialize(serializer)
}
}
impl<'de> $crate::__impl::Deserialize<'de> for $name {
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: $crate::__impl::Deserializer<'de>,
{
let key_data: $crate::KeyData =
$crate::__impl::Deserialize::deserialize(deserializer)?;
Ok(key_data.into())
}
}
};
}
#[cfg(not(feature = "serde"))]
#[doc(hidden)]
#[macro_export]
macro_rules! __serialize_key {
( $name:ty ) => {};
}
new_key_type! {
pub struct DefaultKey;
}
fn is_older_version(a: u32, b: u32) -> bool {
let diff = a.wrapping_sub(b);
diff >= (1 << 31)
}
#[cfg(feature = "serde")]
mod serialize {
use super::*;
use serde::{Deserialize, Deserializer, Serialize, Serializer};
#[derive(Serialize, Deserialize)]
pub struct SerKey {
idx: u32,
version: u32,
}
impl Serialize for KeyData {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
let ser_key = SerKey {
idx: self.idx,
version: self.version.get(),
};
ser_key.serialize(serializer)
}
}
impl<'de> Deserialize<'de> for KeyData {
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: Deserializer<'de>,
{
let mut ser_key: SerKey = Deserialize::deserialize(deserializer)?;
if ser_key.idx == core::u32::MAX {
ser_key.version = 1;
}
ser_key.version |= 1; Ok(Self::new(ser_key.idx, ser_key.version))
}
}
}
#[cfg(test)]
mod tests {
#[test]
fn macro_expansion() {
use super::new_key_type;
new_key_type! {
struct A;
pub(crate) struct B;
pub struct C;
}
}
#[test]
fn check_is_older_version() {
use super::*;
let is_older = |a, b| is_older_version(a, b);
assert!(!is_older(42, 42));
assert!(is_older(0, 1));
assert!(is_older(0, 1 << 31));
assert!(!is_older(0, (1 << 31) + 1));
assert!(is_older(u32::MAX, 0));
}
#[cfg(feature = "serde")]
#[test]
fn key_serde() {
use super::*;
let mut sm = SlotMap::new();
let k = sm.insert(42);
let ser = serde_json::to_string(&k).unwrap();
let de: DefaultKey = serde_json::from_str(&ser).unwrap();
assert_eq!(k, de);
let malicious: KeyData = serde_json::from_str(&r#"{"idx":0,"version":4}"#).unwrap();
assert_eq!(malicious.version.get(), 5);
}
}