Repository navigation
Allow customization of key sizes #52
Description
An investigation is necessary to see if we can safely allow customization of key sizes. Something along the following lines should work:
pub trait Key {
type Index: KeyIndex;
type Version: KeyVersion;
}
pub trait KeyIndex: private::Sealed {
#[doc(hidden)]
type T: UInt;
}
pub trait KeyVersion: private::Sealed {
#[doc(hidden)]
type T: UInt;
#[doc(hidden)]
type NonZeroT: NonZeroUInt;
}
// All the ops needed for implementing.
#[doc(hidden)]
pub trait NonZeroUInt: Copy + PartialEq + Eq /* ... */ {}
#[doc(hidden)]
pub trait UInt: Copy + PartialEq + Eq /* ... */ {}
mod private {
pub trait Sealed {}
}
// Implement all for u8, u16, u32, u64, u128...
impl UInt for u32 {}
impl NonZeroUInt for NonZeroU32 {}
impl KeyIndex for u32 {
type T = u32;
}
impl KeyVersion for u32 {
type T = u32;
type NonZeroT = NonZeroU32;
}
impl private::Sealed for u32 {}
pub struct KeyData<I: KeyIndex, V: KeyVersion> {
idx: I::T,
version: V::NonZeroT,
}
// Allow following syntax:
new_key_type! {
struct DefaultKey; // u32 index/version
struct SmallKey(u16, u16); // u16 index/version
struct HardenedKey(u32, u128); // u32 index, u128 version
}Reacted by lazytype, José Luis Cruz, Peter Majchrak, Mateusz S. Szczygieł, bbb651 🇮🇱, Michael Partheil, Mick van Gelderen, Calandiel and Matthew Milner
Activity
orlp commentedon Jan 5, 2021
Eureka! If we implement this we can also add a marker indicating whether a version is allowed to wraparound or not.
For security sensitive application where under absolutely no circumstances a key might alias, ever, regardless of access pattern instead of allowing a slot version to wrap around we can simply retire a slot after its version field has reached the maximum value.
In fact, I will probably change the default to this behavior, and only allow wraparound as an opt-in for extremely memory leak sensitive applications.
Robbepop commentedon Jan 8, 2021
Would this allow use cases that never need to remove keys?
Currently
SlotMapadds overhead to use cases where keys never need to be removed after first added.Maybe this issue describes some way towards this feature where
SlotMapmethods for key removal would also be missing so that no protection through generational indices is required anymore.orlp commentedon Jan 8, 2021
@Robbepop I don't think that's in scope for
slotmap. The whole point ofslotmapis that it provides a data structure that allows for safe insertion and deletion, without deletion you could just use aVecand indices.Impl Wrapping as KeyVersion
Calandiel commentedon Aug 18, 2022
Hmmm, wouldn't there still be a benefit of having type safe Keys instead of indices into a vector?
nicoburns commentedon Jan 12, 2023
@orlp I don't suppose there's any chance that you will time to get around to this any time soon? (or if not, would you be open to accepting PRs making such a change?)
We are using slotmap the backing storage in taffy, and smaller slotmap keys would be useful to to us because we want to add a
Calcvariant (containing a large complex heap-allocated structure) to our Dimension enum. However, that enum is currently only 32 bits (excluding enum tag), and it is used (and persisently stored in memory) a lot in our code doubling it to 64 bits would constitute a large increase increase in library's memory usage, which would be unfortunate for a relatively rarely used feature.Ideally we would like something like a 24 bit index with 8 bit version, although 16 + 16 could probably also be made to work if necessary.
orlp commentedon Jan 13, 2023
@nicoburns Well, I certainly plan on getting around to this Soon:tm:, but my Soon:tm: might not match your soon, and usually it doesn't even match my own idea of soon :(
I would love to accept PRs if not for the fact that this is quite core to the crate and I want it done Right:tm:, as I will probably only get one, maybe two shots at releasing a version of
slotmapwith core breaking changes. I'm not saying that you wouldn't do it Right:tm:, but my Right:tm: might not be your "right", and if I don't take it slow and really think things through, it won't be my right either.There's a bit of a dichotomy in that a lot of people agree that Agile is the way to go, with many small releases, but at the same time everyone expects their libraries to not have breaking changes. But the only way I can do that is if I really get it right the first, maybe second time.
I have a big upcoming project release in the coming three weeks, so it's unlikely I'll get some work on this before then, but after that I'll be able to dedicate a weekend here and there to it.
I would love to be able to support that too, I should look around for a decent U24 type. Alignment tends to make such a thing a pain though.
mickvangelderen commentedon Apr 4, 2026
Just to express my interest, I came here looking for this functionality because I'd like to store keys in a
mio::Token(usize), and I'd just like it to work on smaller-than-64-bit platforms.After building what I needed based on
slabit all seemed awefully similar toslotmap.