#![no_std]
#![allow(clippy::let_and_return)]
#![deny(unsafe_code, missing_docs)]
//! # `handy`
//!
//! `handy` provides handles and handle maps. A handle map is a fairly useful
//! data structure for rust code, since it can help you work around borrow
//! checker issues.
//!
//! Essentially, [`Handle`] and [`HandleMap`] are a more robust version of the
//! pattern where instead of storing a reference to a &T directly, you instead
//! store a `usize` which indicates where it is in some `Vec`. I claim they're
//! more robust because:
//!
//! - They can detect if you try to use a handle in a map other than the one
//! that provided it.
//!
//! - If you remove an item from the HandleMap, the handle map won't let you use
//! the stale handle to get whatever value happens to be in that index at the
//! time.
//!
//! ## Usage Example
//!
//! ```
//! # use handy::HandleMap;
//! let mut m = HandleMap::new();
//! let h0 = m.insert(3u32);
//! assert_eq!(m[h0], 3);
//! m.remove(h0);
//! assert_eq!(m.get(h0), None);
//! ```
//!
//! # Similar crates
//!
//! A whole bunch.
//!
//! - `slotmap`: Same idea as this, but it requires `T: Copy` (there's a way
//! around this but it's a pain IMO). Has a system for defining handles for
//! use in specific maps, but can't detect if you use a key from one map in
//! another, if the maps are the same type. It also has a bunch of other maps
//! for different performance cases but honestly the limitation of `T: Copy`
//! has prevented me from digging too deeply.
//!
//! - `slab`: Also the same idea but you might not realize it from the docs. It
//! can't detect use with the wrong map or use after the item is removed and
//! another occupies the same spot.
//!
//! - `ffi_support`'s `HandleMap`: I wrote this one. It's very similar, but with
//! some different tradeoffs, and essentially different code. Also, this
//! library doesn't bring in as many heavyweight dependencies, has more
//! features, and isn't focused on use inside the FFI.
//!
//! - Unlike any of them, we're usable in no_std situations (we do link with
//! `extern crate alloc`, of course).
extern crate alloc;
use alloc::vec::Vec;
use core::sync::atomic::{AtomicU16, Ordering};
mod halloc;
pub mod typed;
pub use halloc::HandleAlloc;
/// `HandleMap`s are a collection data structure that allow you to reference
/// their members by using a opaque handle.
///
/// In rust code, you often use these handles as a sort of lifetime-less
/// reference. `Handle` is a paper-thin wrapper around a `u64`, so it is `Copy +
/// Send + Sync + Eq + Ord + ...` even if `T` (or even `&T`) wouldn't be,
/// however you need access to the map in order to read the value.
///
/// This is probably starting to sound like `HandleMap` is just a `Vec`, and
/// `Handle` is just `usize`, but unlike `usize`:
///
/// - a `HandleMap` can tell if you try to use a `Handle` from a different map
/// to access one of it's values.
///
/// - a `HandleMap` tracks insertion/removal of the value at each index, will
/// know if you try to use a handle to get a value that was removed, even if
/// another value occupies the same index.
///
/// # Example
/// ```
/// # use handy::HandleMap;
/// let mut m = HandleMap::new();
/// let h0 = m.insert(3usize);
/// assert_eq!(m[h0], 3);
/// m[h0] += 2;
/// assert_eq!(m[h0], 5);
/// let v = m.remove(h0);
/// assert_eq!(v, Some(5));
/// assert_eq!(m.get(h0), None);
/// ```
#[derive(Clone)]
pub struct HandleMap<T> {
entries: Vec<Entry<T>>,
len: usize,
next: Option<u32>,
end_of_list: Option<u32>,
id: u16,
}
impl<T> Default for HandleMap<T> {
#[inline]
fn default() -> Self {
Self::new()
}
}
static SOURCE_ID: AtomicU16 = AtomicU16::new(1);
impl<T> HandleMap<T> {
/// Create a new handle map.
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let m: HandleMap<u32> = HandleMap::new();
/// // No allocation is performed by default.
/// assert_eq!(m.capacity(), 0);
/// ```
#[inline]
pub fn new() -> Self {
Self::new_with_map_id(SOURCE_ID.fetch_add(1, Ordering::Relaxed))
}
#[inline]
pub(crate) fn new_with_map_id(id: u16) -> Self {
Self {
entries: Vec::new(),
len: 0,
next: None,
end_of_list: None,
id,
}
}
/// Create a new handle map with at least the specified capacity.
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let m: HandleMap<u32> = HandleMap::with_capacity(10);
/// // Note that we don't guarantee the capacity will be exact.
/// // (though in practice it will so long as the requested
/// // capacity is >= 8)
/// assert!(m.capacity() >= 10);
/// ```
pub fn with_capacity(c: usize) -> Self {
let mut a = Self::new();
if c == 0 {
return a;
}
assert!(c < i32::max_value() as usize);
a.reserve(c);
a
}
/// Get the number of entries we can hold before reallocation.
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// m.insert(10);
/// assert!(m.capacity() >= 1);
/// ```
#[inline]
pub fn capacity(&self) -> usize {
self.entries.len()
}
/// Get the number of occupied entries.
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// assert_eq!(m.len(), 0);
/// m.insert(10u32);
/// assert_eq!(m.len(), 1);
/// ```
#[inline]
pub fn len(&self) -> usize {
self.len
}
/// Returns true if our length is zero
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// assert!(m.is_empty());
/// ```
#[inline]
pub fn is_empty(&self) -> bool {
self.len == 0
}
/// Get the id of this map, which is used to validate handles.
///
/// This is typically not needed except for debugging and advanced usage.
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// let h = m.insert(10u32);
/// assert_eq!(m.map_id(), h.map_id());
/// ```
#[inline]
pub fn map_id(&self) -> u16 {
self.id
}
/// Set the id of this map, which is used to validate handles (See
/// [`Handle`] documentation for more details).
///
/// # Warning
/// Doing so will cause the map to fail to recognize handles that it
/// previously returned, and probably other problems! You're recommended
/// against using it unless you know what you're doing!
#[inline]
pub fn raw_set_map_id(&mut self, v: u16) {
self.id = v;
}
/// Add a new item, returning a handle to it.
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// let h = m.insert(10u32);
/// assert_eq!(m[h], 10);
/// ```
pub fn insert(&mut self, value: T) -> Handle {
let index = self.get_next();
let mut e = &mut self.entries[index];
debug_assert!(e.payload.is_none());
e.payload = Some(value);
e.gen = e.gen.wrapping_add(1);
if e.gen == 0 {
// Zero generation indicates an invalid handle.
e.gen = 2;
}
self.next = core::mem::replace(&mut e.next, None);
self.len += 1;
let res = Handle::from_raw_parts(index, e.gen, self.id);
#[cfg(test)]
{
self.assert_valid();
}
res
}
/// Remove the value referenced by this handle from the map, returning it.
///
/// If the handle doesn't point to an entry in the map we return None. This
/// will happen if:
///
/// - The handle comes from a different map.
/// - The item it referenced has been removed already.
/// - It appears corrupt in some other way (For example, it's
/// `Handle::default()`, or comes from a dubious `Handle::from_raw_*`)
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// let h = m.insert(10u32);
/// // Present:
/// assert_eq!(m.remove(h), Some(10));
/// // Not present:
/// assert_eq!(m.remove(h), None);
/// ```
pub fn remove(&mut self, handle: Handle) -> Option<T> {
self.handle_check_mut(handle)?;
self.raw_remove(handle.index())
}
/// Remove all entries in this handle map.
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// let h = m.insert(10u32);
/// m.clear();
/// assert_eq!(m.len(), 0);
/// assert_eq!(m.get(h), None);
/// ```
pub fn clear(&mut self) {
if self.entries.is_empty() {
return;
}
let update_gen = move |e: &mut Entry<T>| {
if (e.gen & 1) == 0 {
e.gen = e.gen.wrapping_add(1);
} else {
e.gen = e.gen.wrapping_add(2);
}
if e.gen == 0 {
e.gen = 1;
}
};
for i in 0..(self.entries.len() - 1) {
update_gen(&mut self.entries[i]);
self.entries[i].next = Some((i + 1) as u32);
self.entries[i].payload = None;
}
let mut end = self.entries.last_mut().unwrap();
update_gen(&mut end);
end.next = None;
end.payload = None;
self.next = Some(0);
self.end_of_list = Some((self.entries.len() - 1) as u32);
self.len = 0;
#[cfg(test)]
{
self.assert_valid();
}
}
/// Try and get a reference to the item backed by the handle.
///
/// If the handle doesn't point to an entry in the map we return None. This
/// will happen if:
///
/// - The handle comes from a different map.
/// - The item it referenced has been removed already.
/// - It appears corrupt in some other way (For example, it's
/// `Handle::default()`, or comes from a dubious `Handle::from_raw_*`)
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// let h = m.insert(10u32);
/// assert_eq!(m.get(h), Some(&10));
/// m.remove(h);
/// assert_eq!(m.get(h), None);
/// ```
#[inline]
pub fn get(&self, handle: Handle) -> Option<&T> {
self.handle_check(handle).and_then(|e| e.payload.as_ref())
}
/// Try and get mutable a reference to the item backed by the handle.
///
/// If the handle doesn't point to an entry in the map we return None. This
/// will happen if:
///
/// - The handle comes from a different map.
/// - The item it referenced has been removed already.
/// - It appears corrupt in some other way (For example, it's
/// `Handle::default()`, or comes from a dubious `Handle::from_raw_*`)
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// let h = m.insert(10u32);
/// *m.get_mut(h).unwrap() += 1;
/// assert_eq!(m[h], 11);
/// // Note: The following is equivalent if you're going to `unwrap` the result of get_mut:
/// m[h] += 1;
/// assert_eq!(m[h], 12);
/// ```
#[inline]
pub fn get_mut(&mut self, handle: Handle) -> Option<&mut T> {
self.handle_check_mut(handle)
.and_then(|e| e.payload.as_mut())
}
/// Returns true if the handle refers to an item present in this map.
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// let h = m.insert(10u32);
/// assert!(m.contains(h));
/// m.remove(h);
/// assert!(!m.contains(h));
/// ```
#[inline]
pub fn contains(&self, h: Handle) -> bool {
self.get(h).is_some()
}
/// Returns true if the handle refers to an item present in this map.
///
/// This is equivalent to [`HandleMap::contains`] but provided for some
/// compatibility with other Map apis.
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// let h = m.insert(10u32);
/// assert!(m.contains_key(h));
/// m.remove(h);
/// assert!(!m.contains_key(h));
/// ```
#[inline]
pub fn contains_key(&self, h: Handle) -> bool {
self.get(h).is_some()
}
/// Search the map for `item`, and if it's found, return a handle to it.
///
/// If more than one value compare as equal to `item`, it's not specified
/// which we will return.
///
/// Note that this is a naive O(n) search, so if you want this often, you
/// might want to store the handle as a field on the value.
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// let h = m.insert(10u32);
/// assert_eq!(m.find_handle(&10), Some(h));
/// assert_eq!(m.find_handle(&11), None);
/// ```
#[inline]
pub fn find_handle(&self, item: &T) -> Option<Handle>
where
T: PartialEq,
{
for (i, e) in self.entries.iter().enumerate() {
if e.payload.as_ref() == Some(item) {
return Some(Handle::from_raw_parts(i, e.gen, self.id));
}
}
None
}
/// Reserve space for `sz` additional items.
///
/// ## Example
///
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// assert_eq!(m.capacity(), 0);
/// m.reserve(10);
/// assert!(m.capacity() >= 10);
/// ```
pub fn reserve(&mut self, sz: usize) {
self.grow(self.len() + sz);
}
/// Get an iterator over every occupied slot of this map.
///
/// See also `iter_with_handles` if you want the handles during
/// iteration.
///
/// ## Example
///
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// m.insert(10u32);
/// assert_eq!(*m.iter().next().unwrap(), 10);
/// ```
#[inline]
pub fn iter<'a>(&'a self) -> impl Iterator<Item = &'a T> + 'a {
self.entries.iter().filter_map(|e| e.payload.as_ref())
}
/// Get a mut iterator over every occupied slot of this map.
///
/// See also `iter_mut_with_handles` if you want the handles during
/// iteration.
///
/// ## Example
///
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// let h = m.insert(10u32);
/// for v in m.iter_mut() {
/// *v += 1;
/// }
/// assert_eq!(m[h], 11);
/// ```
#[inline]
pub fn iter_mut<'a>(&'a mut self) -> impl Iterator<Item = &'a mut T> + 'a {
self.entries.iter_mut().filter_map(|e| e.payload.as_mut())
}
/// Get an iterator over every occupied slot of this map, as well as a
/// handle which can be used to fetch them later.
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// # let m: HandleMap<u32> = HandleMap::new();
/// for (h, v) in m.iter_with_handles() {
/// println!("{:?} => {}", h, v);
/// }
/// ```
#[inline]
pub fn iter_with_handles<'a>(&'a self) -> impl Iterator<Item = (Handle, &'a T)> + 'a {
self.entries.iter().enumerate().filter_map(move |(i, e)| {
e.payload
.as_ref()
.map(|p| (Handle::from_raw_parts(i, e.gen, self.id), p))
})
}
/// Get a mut iterator over every occupied slot of this map, as well as a
/// handle which can be used to fetch them later.
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// # let mut m = HandleMap::<u32>::new();
/// for (h, v) in m.iter_mut_with_handles() {
/// *v += 1;
/// println!("{:?}", h);
/// }
/// ```
#[inline]
pub fn iter_mut_with_handles<'a>(
&'a mut self,
) -> impl Iterator<Item = (Handle, &'a mut T)> + 'a {
let id = self.id;
self.entries
.iter_mut()
.enumerate()
.filter_map(move |(i, e)| {
let gen = e.gen;
e.payload
.as_mut()
.map(|p| (Handle::from_raw_parts(i, gen, id), p))
})
}
/// If `index` refers to an occupied entry, return a `Handle` to it.
/// Otherwise, return None. This is a low level API that shouldn't be needed
/// for typical use.
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// let h = m.insert(10u32);
/// assert_eq!(m.handle_for_index(h.index()), Some(h));
/// ```
#[inline]
pub fn handle_for_index(&self, index: usize) -> Option<Handle> {
let e = self.entries.get(index)?;
if e.payload.is_some() {
debug_assert!((e.gen & 1) == 0 && (e.gen != 0));
Some(Handle::from_raw_parts(index, e.gen, self.id))
} else {
None
}
}
/// Access the value at the provided index, whatever it happens to be.
///
/// Returns none if `index` >= `capacity()` or if the index is unoccupied.
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// let h = m.insert(10u32);
/// assert_eq!(m.raw_value_at_index(h.index()), Some(&10));
/// ```
///
/// # Caveat
/// This is a low level feature intended for advanced usage, typically you
/// do not need to call this function.
#[inline]
pub fn raw_value_at_index(&self, index: usize) -> Option<&T> {
self.entries.get(index).and_then(|v| v.payload.as_ref())
}
/// Access the value at the provided index, whatever it happens to be.
///
/// Returns none if `index` >= `capacity()` or if the index is unoccupied.
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m: HandleMap<u32> = HandleMap::new();
/// let h = m.insert(10u32);
/// *m.raw_mut_value_at_index(h.index()).unwrap() = 11;
/// assert_eq!(m[h], 11);
/// ```
/// # Caveat
/// This is a low level feature intended for advanced usage, typically you
/// do not need to call this function.
#[inline]
pub fn raw_mut_value_at_index(&mut self, index: usize) -> Option<&mut T> {
self.entries.get_mut(index).and_then(|v| v.payload.as_mut())
}
#[inline]
fn handle_check(&self, handle: Handle) -> Option<&Entry<T>> {
if handle.meta() != self.id {
unlikely_hint();
return None;
}
let i = handle.index();
if i >= self.entries.len() {
unlikely_hint();
return None;
}
let e = &self.entries[i];
let gen = handle.generation();
if e.gen != gen || (gen & 1) != 0 {
unlikely_hint();
None
} else {
Some(e)
}
}
#[inline]
fn handle_check_mut(&mut self, handle: Handle) -> Option<&mut Entry<T>> {
if handle.meta() != self.id {
unlikely_hint();
return None;
}
let i = handle.index();
if i >= self.entries.len() {
unlikely_hint();
return None;
}
let e = &mut self.entries[i];
let gen = handle.generation();
if e.gen != gen || (gen & 1) != 0 {
unlikely_hint();
None
} else {
Some(e)
}
}
#[inline]
fn get_next(&mut self) -> usize {
if let Some(n) = self.next {
n as usize
} else {
let n = self.grow_for_insert();
debug_assert!(self.next == Some(n as u32));
n
}
}
#[cold]
fn grow_for_insert(&mut self) -> usize {
self.grow(self.capacity() + 1).expect("bug")
}
// note: returns `self.next` unwrapped.
fn grow(&mut self, need: usize) -> Option<usize> {
if need <= self.capacity() {
return self.next.map(|u| u as usize);
}
let cap = (self.capacity() * 2).max(need).max(8);
assert!(cap <= i32::max_value() as usize, "Capacity overflow");
self.entries.reserve(cap - self.entries.len());
let current_cap = self.capacity();
self.entries.extend((current_cap..(cap - 1)).map(|i| Entry {
next: Some((i + 1) as u32),
payload: None,
gen: 1,
}));
self.entries.push(Entry {
next: None,
payload: None,
gen: 1,
});
if self.next.is_none() {
self.next = Some(current_cap as u32);
self.end_of_list = Some((self.entries.len() - 1) as u32);
} else {
let end = self.end_of_list.unwrap();
let ee = &mut self.entries[end as usize];
debug_assert!(ee.payload.is_none());
ee.next = Some(current_cap as u32);
self.end_of_list = Some((self.entries.len() - 1) as u32);
}
#[cfg(test)]
{
self.assert_valid();
}
Some(current_cap as usize)
}
#[cfg(test)]
#[allow(clippy::cognitive_complexity)]
fn assert_valid(&self) {
if self.entries.is_empty() {
return;
}
assert!(self.len() <= self.capacity());
assert!(
self.capacity() <= i32::max_value() as usize,
"Entries too large"
);
if self.len() == self.capacity() {
assert!(self.next.is_none());
} else {
assert!(self.next.is_some());
}
let number_of_ends = self
.entries
.iter()
.filter(|e| e.next.is_none() && e.payload.is_none())
.count();
if self.capacity() != 0 {
let end = self.end_of_list.expect("Should have end") as usize;
assert_eq!(self.entries[end].next, None);
if self.capacity() == self.len() {
assert!(self.entries[end].payload.is_some());
assert_eq!(number_of_ends, 0);
} else {
assert!(self.entries[end].payload.is_none());
assert_eq!(number_of_ends, 1);
}
} else {
assert_eq!(number_of_ends, 0);
}
if self.next.is_none() {
assert!(self.entries[self.end_of_list.unwrap() as usize]
.payload
.is_some());
}
// Check that the free list hits every unoccupied item.
// The tuple is: `(should_be_in_free_list, is_in_free_list)`.
let mut free_indices = alloc::vec![(false, false); self.capacity()];
for (i, e) in self.entries.iter().enumerate() {
if e.payload.is_none() {
free_indices[i].0 = true;
} else {
assert!(e.next.is_none(), "occupied slot in free list");
}
}
let mut next = self.next;
while let Some(ni) = next {
let ni = ni as usize;
assert!(
ni <= free_indices.len(),
"Free list contains out of bounds index!"
);
assert!(
free_indices[ni].0,
"Free list has an index that shouldn't be free! {}",
ni
);
assert!(
!free_indices[ni].1,
"Free list hit an index ({}) more than once! Cycle detected!",
ni
);
free_indices[ni].1 = true;
assert!(self.entries[ni].payload.is_none());
next = self.entries[ni].next;
if next.is_none() {
assert_eq!(Some(ni as u32), self.end_of_list);
}
}
let mut occupied_count = 0;
for (i, &(should_be_free, is_free)) in free_indices.iter().enumerate() {
assert_eq!(
should_be_free, is_free,
"Free list missed item, or contains an item it shouldn't: {}",
i
);
if !should_be_free {
occupied_count += 1;
}
}
assert_eq!(
self.len, occupied_count,
"len doesn't reflect the actual number of entries"
);
}
/// Directly query the value of the generation at that index.
///
/// If `index` is greater then `self.capacity()`, then this returns None.
///
/// Advanced usage note: Even generations always indicate an occupied index,
/// except for 0, which is never a valid generation.
///
/// ## Example
/// ```
/// # use handy::HandleMap;
/// let mut m = HandleMap::new();
/// let h = m.insert(10u32);
/// assert_eq!(m.raw_generation_for_index(h.index()), Some(h.generation()));
/// ```
///
/// # Caveat
/// This is a low level feature intended for advanced usage, typically you
/// do not need to call this function, however doing so is harmless.
#[inline]
pub fn raw_generation_for_index(&self, index: usize) -> Option<u16> {
self.entries.get(index).map(|e| e.gen)
}
pub(crate) fn raw_remove(&mut self, index: usize) -> Option<T> {
let mut e = &mut self.entries[index];
e.gen = e.gen.wrapping_add(1);
if e.gen == 0 {
e.gen = 1;
}
e.next = self.next;
self.next = Some(index as u32);
self.len -= 1;
let r = e.payload.take();
debug_assert!(r.is_some());
#[cfg(test)]
{
self.assert_valid();
}
r
}
}
impl<T> core::ops::Index<Handle> for HandleMap<T> {
type Output = T;
fn index(&self, h: Handle) -> &T {
self.get(h).expect("Invalid handle used in index")
}
}
impl<T> core::ops::IndexMut<Handle> for HandleMap<T> {
fn index_mut(&mut self, h: Handle) -> &mut T {
self.get_mut(h).expect("Invalid handle used in index_mut")
}
}
/// An iterator that moves out of a HandleMap.
#[derive(Debug)]
pub struct IntoIter<T> {
inner: alloc::vec::IntoIter<Entry<T>>,
}
impl<T> IntoIterator for HandleMap<T> {
type IntoIter = IntoIter<T>;
type Item = T;
fn into_iter(self) -> Self::IntoIter {
IntoIter {
inner: self.entries.into_iter(),
}
}
}
impl<T> Iterator for IntoIter<T> {
type Item = T;
#[inline]
fn next(&mut self) -> Option<T> {
self.inner
.try_for_each(|e| {
if let Some(p) = e.payload {
Err(p)
} else {
Ok(())
}
})
.err()
}
// TODO: Size hint.
}
#[cold]
fn unlikely_hint() {}
#[derive(Debug, Clone)]
struct Entry<T> {
next: Option<u32>,
gen: u16,
payload: Option<T>,
}
/// An untyped reference to some value. Handles are just a fancy u64.
///
/// Internally these store:
///
/// - A 32-bit index field.
/// - The 16-bit 'generation' of that index (this is incremented both when an
/// item is removed from the index, and when another is inserted).
/// - An extra value typically used to store the ID of their map.
///
/// They're a #[repr(transparent)] wrapper around a u64, so if they need to be
/// passed into C code over the FFI, that can be done directly.
///
/// # Advanced Details
///
/// Typical use of this library expects that you just treat these as opaque,
/// however you're free to inspect and construct them as you please (with
/// `from_raw` and `from_raw_parts`), with the caveat that using the API to do
/// so could cause the map to return non-sensical answers.
///
/// That said, should you want to do so, you absolutely can.
///
/// Some important notes if you're going to construct these:
///
/// - Valid indices should always be between 0 and i32::max_value.
///
/// - Generations for occupied indexs have a even value, and for empty indexs
/// have an odd value. The zero generation is always skipped, and is never
/// considered valid.
///
/// - If used with a HandleMap, the `meta` value must match the map they came
/// from.
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
pub struct Handle(u64);
impl Handle {
/// A constant for the default (null) handle. Never valid or returned by any
/// map.
pub const EMPTY: Handle = Handle::from_raw(0);
/// Returns the index value of this handle.
///
/// While a usize is returned, this value is guaranteed to be 32 bits.
///
/// # Caveat
///
/// This is a low level feature intended for advanced usage, typically you
/// do not need to access this value, however doing so is harmless.
#[inline]
pub const fn index(self) -> usize {
(self.0 as u32) as usize
}
/// Returns the generation value of this handle.
///
/// # Caveat
///
/// This is a low level feature intended for advanced usage, typically you
/// do not need to access this value, however doing so is harmless.
#[inline]
pub const fn generation(self) -> u16 {
(self.0 >> 48) as u16
}
/// Returns the metadata field of this handle. This is an alias for
/// `map_id`, as in the common case, this is what the metadata field is used
/// for.
///
/// See [`Handle::meta`] for more info.
#[inline]
pub const fn map_id(self) -> u16 {
(self.0 >> 32) as u16
}
/// Returns the metadata field of this handle.
///
/// If used with a [`HandleMap`] (instead of directly coming from a
/// [`HandleAlloc`]), this is the `id` of the `HandleMap` which constructed
/// this handle. If used with a HandleAlloc, then the value has no meaning
/// aside from whatever you assign to it -- it's 16 free bits you can use
/// for whatever tagging you want.
///
/// # Caveat
///
/// This is a low level feature intended for advanced usage, typically you
/// do not need to access this value, however doing so is harmless.
#[inline]
pub const fn meta(self) -> u16 {
(self.0 >> 32) as u16
}
/// Construct a handle from the separate parts.
///
/// # Warning
/// This is a feature intended for advanced usage. An attempt is made to
/// cope with dubious handles, but it's almost certainly possible to pierce
/// the abstraction veil of the HandleMap if you use this.
///
/// However, it should not be possible to cause memory unsafety -- this
/// crate has no unsafe code.
#[inline]
#[allow(clippy::cast_lossless)] // const fn
pub const fn from_raw_parts(index: usize, generation: u16, meta: u16) -> Self {
Handle((index as u32 as u64) | ((meta as u64) << 32) | ((generation as u64) << 48))
}
/// Construct a handle from it's internal `u64` value.
///
/// # Layout
///
/// The 64 bit value is interpreted as such. It's recommended that you
/// instead use `from_raw_parts` to construct these in cases where this is
/// relevant, though.
///
/// ```text
/// [16 bits of generation | 16 bits of map id | 32 bit index]
/// MSB LSB
/// ```
///
/// # Warning
///
/// This is a feature intended for advanced usage. An attempt is made to
/// cope with dubious handles, but it's almost certainly possible to pierce
/// the abstraction veil of the HandleMap if you use this.
///
/// However, it should not be possible to cause memory unsafety -- this
/// crate has no unsafe code.
#[inline]
pub const fn from_raw(value: u64) -> Self {
Self(value)
}
/// Get the internal u64 representation of this handle.
///
/// # Caveat
///
/// This is a low level feature intended for advanced usage, typically you
/// do not need to access this value, however doing so is harmless.
///
/// # Layout
///
/// The layout of the returned value is as such:
///
/// ```text
/// [16 bits of generation | 16 bits of map id | 32 bit index]
/// MSB LSB
/// ```
#[inline]
pub const fn into_raw(self) -> u64 {
self.0
}
/// Get the internal parts of this handle.
///
/// Equivalent to `(self.index(), self.generation(), self.meta())`
///
/// # Caveat
///
/// This is a low level feature intended for advanced usage, typically you
/// do not need to access this value, however doing so is harmless.
#[inline]
pub fn decompose(self) -> (u32, u16, u16) {
(self.index() as u32, self.generation(), self.meta())
}
}
struct EntriesDebug<'a, T>(&'a HandleMap<T>);
impl<'a, T> core::fmt::Debug for EntriesDebug<'a, T>
where
T: core::fmt::Debug,
{
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
f.debug_map().entries(self.0.iter_with_handles()).finish()
}
}
impl<T> core::fmt::Debug for HandleMap<T>
where
T: core::fmt::Debug,
{
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
f.debug_struct("HandleMap")
.field("id", &self.id)
.field("entries", &EntriesDebug(self))
.finish()
}
}
impl core::fmt::Debug for Handle {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
f.debug_struct("Handle")
.field("meta", &self.meta())
.field("generation", &self.generation())
.field("index", &self.index())
.finish()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_handle_parts() {
let h = Handle::from_raw_parts(0, 0, 0);
assert_eq!(h.index(), 0);
assert_eq!(h.generation(), 0);
assert_eq!(h.meta(), 0);
assert_eq!(h.meta(), h.map_id());
let h = Handle::from_raw_parts(!0, 0, 0);
assert_eq!(h.index(), (!0u32) as usize);
assert_eq!(h.generation(), 0);
assert_eq!(h.meta(), 0);
assert_eq!(h.meta(), h.map_id());
assert_eq!(h.decompose(), (h.index() as u32, h.generation(), h.meta()));
assert_eq!(Handle::from_raw(h.into_raw()), h);
let h = Handle::from_raw_parts(0, !0, 0);
assert_eq!(h.index(), 0);
assert_eq!(h.generation(), !0);
assert_eq!(h.meta(), 0);
assert_eq!(h.meta(), h.map_id());
let h = Handle::from_raw_parts(0, 0, !0);
assert_eq!(h.index(), 0);
assert_eq!(h.generation(), 0);
assert_eq!(h.meta(), !0);
assert_eq!(h.meta(), h.map_id());
let h = Handle::from_raw_parts(!0, !0, !0);
assert_eq!(h.index(), (!0u32) as usize);
assert_eq!(h.generation(), !0);
assert_eq!(h.meta(), !0);
assert_eq!(h.meta(), h.map_id());
}
#[derive(PartialEq, Debug, Clone, Copy)]
pub(crate) struct Foobar(pub(crate) usize);
#[test]
fn test_correct_value_single() {
let mut map = HandleMap::new();
let handle = map.insert(Foobar(1234));
assert_eq!(map.get(handle).unwrap(), &Foobar(1234));
map.remove(handle).unwrap();
assert_eq!(map.get(handle), None);
}
#[test]
fn test_indexing() {
let mut map = HandleMap::new();
let handle = map.insert(Foobar(5454));
assert_eq!(map[handle].0, 5454);
map[handle] = Foobar(6767);
assert_eq!(map[handle].0, 6767);
}
#[test]
fn test_correct_value_multiple() {
let mut map = HandleMap::new();
let handle1 = map.insert(Foobar(1234));
let handle2 = map.insert(Foobar(4321));
assert_eq!(map.get(handle1).unwrap(), &Foobar(1234));
assert_eq!(map.get(handle2).unwrap(), &Foobar(4321));
map.remove(handle1).unwrap();
assert_eq!(map.get(handle1), None);
assert_eq!(map.get(handle2).unwrap(), &Foobar(4321));
}
#[test]
fn test_wrong_map() {
let mut map1 = HandleMap::new();
let mut map2 = HandleMap::new();
let handle1 = map1.insert(Foobar(1234));
let handle2 = map2.insert(Foobar(1234));
assert_eq!(map1.get(handle1).unwrap(), &Foobar(1234));
assert_eq!(map2.get_mut(handle2).unwrap(), &mut Foobar(1234));
assert_eq!(map1.get(handle2), None);
assert_eq!(map2.get_mut(handle1), None);
assert_eq!(handle1.meta(), map1.map_id());
map1.raw_set_map_id(5);
let h = map1.insert(Foobar(3));
assert_eq!(h.meta(), map1.map_id());
assert_eq!(h.meta(), 5);
}
#[test]
fn test_bad_index() {
let map: HandleMap<Foobar> = HandleMap::new();
assert_eq!(map.get(Handle::from_raw_parts(100, 2, map.id)), None);
}
#[test]
fn test_wrong_gen() {
let mut map: HandleMap<usize> = HandleMap::new();
let h = map.insert(3);
map.remove(h).unwrap();
assert_eq!(map.get(h), None);
assert_eq!(map.remove(h), None);
}
#[test]
fn test_resizing() {
let mut map = HandleMap::new();
let mut handles = alloc::vec![];
// should trigger resize many times
for i in 0..2000 {
handles.push(map.insert(Foobar(i)))
}
for (i, &h) in handles.iter().enumerate() {
assert_eq!(map[h], Foobar(i));
assert_eq!(map.remove(h).unwrap(), Foobar(i));
}
let mut handles2 = alloc::vec![];
for i in 2050..4100 {
// Not really related to this test, but it's convenient to check this here.
let h = map.insert(Foobar(i));
handles2.push(h);
}
for (i, (&h0, h1)) in handles.iter().zip(handles2).enumerate() {
// It's still a stale version, even though the index is occupied again.
assert_eq!(map.get(h0), None);
assert_eq!(map.get(h1).unwrap(), &Foobar(i + 2050));
}
}
#[test]
fn test_reserve() {
let mut map = HandleMap::with_capacity(10);
map.reserve(30);
let mut handles = alloc::vec![];
for i in 0..10 {
handles.push(map.insert(Foobar(i)));
map.reserve(3);
}
map.reserve(0);
for i in 0..10 {
handles.push(map.insert(Foobar(i + 10)))
}
map.reserve(map.capacity());
for (i, &h) in handles.iter().enumerate() {
assert_eq!(map[h], Foobar(i));
assert_eq!(map.remove(h).unwrap(), Foobar(i));
}
let mut handles2 = alloc::vec![];
for i in 20..30 {
let h = map.insert(Foobar(i));
handles2.push(h);
}
map.reserve(50);
for (i, (&h0, h1)) in handles.iter().zip(handles2).enumerate() {
assert_eq!(map.get(h0), None);
assert_eq!(map.get(h1).unwrap(), &Foobar(i + 20));
}
}
#[test]
fn test_clear() {
let mut map = HandleMap::new();
map.clear(); // no-op.
for _ in 0..2 {
let mut handles = alloc::vec![];
for i in 0..120 {
handles.push(map.insert(Foobar(i)))
}
map.clear();
for h in handles.iter() {
assert_eq!(map.get(*h), None);
}
}
}
#[test]
fn test_iters() {
use alloc::collections::BTreeMap;
let (mut map, handles) = mixed_handlemap();
assert_eq!(map.len(), handles.len());
let handle_to_foo: BTreeMap<Handle, usize> = handles.iter().copied().collect();
let foo_to_handle: BTreeMap<usize, Handle> =
handles.iter().copied().map(|t| (t.1, t.0)).collect();
assert_eq!(handle_to_foo.len(), handles.len());
assert_eq!(foo_to_handle.len(), handles.len());
// iter
let mut count = 0;
for i in map.iter() {
count += 1;
assert!(foo_to_handle.contains_key(&i.0));
}
assert_eq!(count, handles.len());
// iter_mut
let mut count = 0;
for i in map.iter_mut() {
count += 1;
assert!(foo_to_handle.contains_key(&i.0));
}
assert_eq!(count, handles.len());
// into_iter
let mut count = 0;
for i in map.clone() {
count += 1;
assert!(foo_to_handle.contains_key(&i.0));
}
assert_eq!(count, handles.len());
// iter_with_handles
let mut count = 0;
for (h, i) in map.iter_with_handles() {
count += 1;
assert!(foo_to_handle.contains_key(&i.0));
assert_eq!(handle_to_foo[&h], i.0);
}
assert_eq!(count, handles.len());
// iter_mut_with_handles
let mut count = 0;
for (h, i) in map.iter_mut_with_handles() {
count += 1;
assert!(foo_to_handle.contains_key(&i.0));
assert_eq!(handle_to_foo[&h], i.0);
}
assert_eq!(count, handles.len());
}
pub(crate) fn mixed_handlemap() -> (HandleMap<Foobar>, Vec<(Handle, usize)>) {
let mut handles = alloc::vec![];
let mut map = HandleMap::with_capacity(10);
let mut c = 0;
for &sp in &[2, 3, 5] {
for _ in 0..100 {
c += 1;
handles.push((map.insert(Foobar(c)), c));
assert_eq!(map.len(), handles.len());
}
let mut i = 0;
while i < handles.len() {
map.remove(handles.swap_remove(i).0).unwrap();
assert_eq!(map.len(), handles.len());
i += sp;
}
}
(map, handles)
}
#[test]
fn test_find() {
let mut m = HandleMap::new();
let mut v = alloc::vec![];
for i in 0..10usize {
v.push(m.insert(i));
}
for (i, h) in v.iter().enumerate() {
assert_eq!(m.find_handle(&i), Some(*h));
assert!(m.contains_key(*h));
}
m.clear();
assert!(m.is_empty());
for (i, h) in v.iter().enumerate() {
assert_eq!(m.find_handle(&i), None);
assert!(!m.contains_key(*h));
}
}
#[test]
fn test_dbg() {
let mut m = HandleMap::new_with_map_id(0);
m.insert(0u32);
assert_eq!(
alloc::format!("{:?}", m),
"HandleMap { id: 0, entries: {Handle { meta: 0, generation: 2, index: 0 }: 0} }"
);
}
}