blob: 98296413fb099787f68102fdfb5dac68dfd40753 [file]
//! A map that is optimized for having few elements: when the length is low, it is stored as a `ThinVec`.
#![deny(unsafe_code)]
mod set;
#[cfg(test)]
mod tests;
use std::{
borrow::Borrow,
hash::{BuildHasher, Hash},
mem,
};
use thin_vec::ThinVec;
pub use self::set::{ThinHashSet, ThinSet};
pub use self::unsafe_encapsulation::ThinMap;
#[derive(Clone, PartialEq)]
#[cfg_attr(feature = "salsa", derive(salsa::SalsaValue))]
#[repr(align(2))]
struct Align<T>(T);
type ThinReprItem<K, V> = Align<(K, V)>;
type ThinReprVec<K, V> = ThinVec<ThinReprItem<K, V>>;
enum ReprRef<'a, K, V, M> {
Thin(&'a [ThinReprItem<K, V>]),
Map(&'a M),
}
enum ReprMut<'a, K, V, M> {
Thin(&'a mut ThinReprVec<K, V>),
Map(&'a mut M),
}
#[cfg_attr(feature = "salsa", derive(salsa::SalsaValue))]
enum Repr<K, V, M> {
Thin(ThinReprVec<K, V>),
Map(Box<Align<M>>),
}
pub enum MapEntry<'a, K, V, M: Map<K, V> + 'a> {
Occupied(M::OccupiedEntry<'a>),
Vacant(M::VacantEntry<'a>),
}
// We use generic parameters and not associated types because this allows us to keep `ThinMap` covariant over `M`
// (associated types are invariant).
pub trait Map<K, V>: Default {
fn with_capacity(capacity: usize) -> Self;
fn reserve(&mut self, additional: usize);
fn len(&self) -> usize;
fn shrink_to_fit(&mut self);
type Iter<'a>: ExactSizeIterator<Item = (&'a K, &'a V)>
where
K: 'a,
V: 'a,
Self: 'a;
type IterMut<'a>: ExactSizeIterator<Item = (&'a K, &'a mut V)>
where
K: 'a,
V: 'a,
Self: 'a;
type IntoIter: ExactSizeIterator<Item = (K, V)>;
fn iter(&self) -> Self::Iter<'_>;
fn iter_mut(&mut self) -> Self::IterMut<'_>;
fn into_iter(self) -> Self::IntoIter;
fn get<Q>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
Q: ?Sized + Hash + Eq;
fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
where
K: Borrow<Q>,
Q: ?Sized + Hash + Eq;
fn get_disjoint_mut<Q, const N: usize>(&mut self, ks: [&Q; N]) -> [Option<&mut V>; N]
where
K: Borrow<Q>,
Q: ?Sized + Hash + Eq;
fn insert(&mut self, key: K, value: V) -> Option<V>;
fn remove<Q>(&mut self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: ?Sized + Hash + Eq;
type OccupiedEntry<'a>
where
Self: 'a;
type VacantEntry<'a>
where
Self: 'a;
fn entry(&mut self, key: K) -> MapEntry<'_, K, V, Self>;
fn vacant_entry_insert<'a>(entry: Self::VacantEntry<'a>, value: V) -> &'a mut V
where
Self: 'a;
fn occupied_entry_get<'a, 'b>(entry: &'a Self::OccupiedEntry<'b>) -> &'a V
where
Self: 'b;
fn occupied_entry_get_mut<'a, 'b>(entry: &'a mut Self::OccupiedEntry<'b>) -> &'a mut V
where
Self: 'b;
fn occupied_entry_into_mut<'a>(entry: Self::OccupiedEntry<'a>) -> &'a mut V
where
Self: 'a;
fn occupied_entry_insert<'a>(entry: &mut Self::OccupiedEntry<'a>, value: V) -> V
where
Self: 'a;
}
#[expect(clippy::disallowed_types)]
impl<K: Hash + Eq, V, S: BuildHasher + Default> Map<K, V> for std::collections::HashMap<K, V, S> {
#[inline]
fn with_capacity(capacity: usize) -> Self {
Self::with_capacity_and_hasher(capacity, S::default())
}
#[inline]
fn reserve(&mut self, additional: usize) {
self.reserve(additional);
}
#[inline]
fn len(&self) -> usize {
self.len()
}
#[inline]
fn shrink_to_fit(&mut self) {
self.shrink_to_fit();
}
type Iter<'a>
= std::collections::hash_map::Iter<'a, K, V>
where
Self: 'a;
type IterMut<'a>
= std::collections::hash_map::IterMut<'a, K, V>
where
Self: 'a;
type IntoIter = std::collections::hash_map::IntoIter<K, V>;
#[inline]
fn iter(&self) -> Self::Iter<'_> {
self.iter()
}
#[inline]
fn iter_mut(&mut self) -> Self::IterMut<'_> {
self.iter_mut()
}
#[inline]
fn into_iter(self) -> Self::IntoIter {
IntoIterator::into_iter(self)
}
#[inline]
fn get<Q>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
Q: ?Sized + Hash + Eq,
{
self.get(key)
}
#[inline]
fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
where
K: Borrow<Q>,
Q: ?Sized + Hash + Eq,
{
self.get_mut(key)
}
#[inline]
fn get_disjoint_mut<Q, const N: usize>(&mut self, ks: [&Q; N]) -> [Option<&mut V>; N]
where
K: Borrow<Q>,
Q: ?Sized + Hash + Eq,
{
self.get_disjoint_mut(ks)
}
#[inline]
fn insert(&mut self, key: K, value: V) -> Option<V> {
self.insert(key, value)
}
#[inline]
fn remove<Q>(&mut self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: ?Sized + Hash + Eq,
{
self.remove(key)
}
type OccupiedEntry<'a>
= std::collections::hash_map::OccupiedEntry<'a, K, V>
where
Self: 'a;
type VacantEntry<'a>
= std::collections::hash_map::VacantEntry<'a, K, V>
where
Self: 'a;
#[inline]
fn entry(&mut self, key: K) -> MapEntry<'_, K, V, Self> {
match self.entry(key) {
std::collections::hash_map::Entry::Occupied(it) => MapEntry::Occupied(it),
std::collections::hash_map::Entry::Vacant(it) => MapEntry::Vacant(it),
}
}
#[inline]
fn vacant_entry_insert<'a>(entry: Self::VacantEntry<'a>, value: V) -> &'a mut V
where
Self: 'a,
{
entry.insert(value)
}
#[inline]
fn occupied_entry_get<'a, 'b>(entry: &'a Self::OccupiedEntry<'b>) -> &'a V
where
Self: 'b,
{
entry.get()
}
#[inline]
fn occupied_entry_get_mut<'a, 'b>(entry: &'a mut Self::OccupiedEntry<'b>) -> &'a mut V
where
Self: 'b,
{
entry.get_mut()
}
#[inline]
fn occupied_entry_into_mut<'a>(entry: Self::OccupiedEntry<'a>) -> &'a mut V
where
Self: 'a,
{
entry.into_mut()
}
#[inline]
fn occupied_entry_insert<'a>(entry: &mut Self::OccupiedEntry<'a>, value: V) -> V
where
Self: 'a,
{
entry.insert(value)
}
}
#[expect(clippy::disallowed_types)]
pub type ThinHashMap<K, V, S> = ThinMap<K, V, std::collections::HashMap<K, V, S>>;
/// The maximum len to still use `ThinVec`.
const LEN_CUTOFF: usize = 10;
impl<K: Hash + Eq, V, M: Map<K, V>> ThinMap<K, V, M> {
#[inline]
pub fn with_capacity(capacity: usize) -> Self {
let repr = if capacity > LEN_CUTOFF {
Repr::Map(Box::new(Align(M::with_capacity(capacity))))
} else {
Repr::Thin(ThinVec::with_capacity(capacity))
};
Self::from_repr(repr)
}
#[inline]
pub fn reserve(&mut self, additional: usize) {
match self.repr_mut() {
ReprMut::Thin(repr) => {
let expected_len = repr.len() + additional;
if expected_len > repr.capacity() || expected_len > LEN_CUTOFF {
self.reserve_cold(expected_len);
}
}
ReprMut::Map(repr) => repr.reserve(additional),
}
}
#[cold]
fn reserve_cold(&mut self, expected_len: usize) {
let ReprMut::Thin(repr) = self.repr_mut() else { unreachable!() };
if expected_len <= LEN_CUTOFF {
repr.reserve(expected_len - repr.len());
} else {
let mut map = M::with_capacity(expected_len);
for Align((key, value)) in mem::take(repr) {
map.insert(key, value);
}
*self = Self::from_repr(Repr::Map(Box::new(Align(map))));
}
}
pub fn shrink_to_fit(&mut self) {
let mut repr = mem::take(self).into_repr();
match repr {
Repr::Thin(ref mut repr) => repr.shrink_to_fit(),
Repr::Map(mut map) => {
repr = if map.0.len() > LEN_CUTOFF {
map.0.shrink_to_fit();
Repr::Map(map)
} else {
Repr::Thin(map.0.into_iter().map(Align).collect())
};
}
}
*self = Self::from_repr(repr);
}
#[inline]
pub fn len(&self) -> usize {
match self.repr_ref() {
ReprRef::Thin(repr) => repr.len(),
ReprRef::Map(repr) => repr.len(),
}
}
#[inline]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
#[inline]
pub fn iter(&self) -> Iter<'_, K, V, M> {
let repr = match self.repr_ref() {
ReprRef::Thin(repr) => IterRepr::Thin(repr.iter()),
ReprRef::Map(repr) => IterRepr::Map(repr.iter()),
};
Iter { repr }
}
#[inline]
pub fn iter_mut(&mut self) -> IterMut<'_, K, V, M> {
let repr = match self.repr_mut() {
ReprMut::Thin(repr) => IterMutRepr::Thin(repr.iter_mut()),
ReprMut::Map(repr) => IterMutRepr::Map(repr.iter_mut()),
};
IterMut { repr }
}
#[inline]
pub fn keys(&self) -> impl ExactSizeIterator<Item = &K> {
self.iter().map(|(key, _value)| key)
}
#[inline]
pub fn values(&self) -> impl ExactSizeIterator<Item = &V> {
self.iter().map(|(_key, value)| value)
}
#[inline]
pub fn values_mut(&mut self) -> impl ExactSizeIterator<Item = &mut V> {
self.iter_mut().map(|(_key, value)| value)
}
#[inline]
pub fn into_keys(self) -> impl ExactSizeIterator<Item = K> {
self.into_iter().map(|(key, _value)| key)
}
#[inline]
pub fn into_values(self) -> impl ExactSizeIterator<Item = V> {
self.into_iter().map(|(_key, value)| value)
}
#[inline]
pub fn contains_key<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
Q: ?Sized + Hash + Eq,
{
self.get(key).is_some()
}
#[inline]
pub fn get<Q>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
Q: ?Sized + Hash + Eq,
{
match self.repr_ref() {
ReprRef::Thin(repr) => {
repr.iter().find_map(|Align((k, v))| (k.borrow() == key).then_some(v))
}
ReprRef::Map(repr) => repr.get(key),
}
}
#[inline]
pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
where
K: Borrow<Q>,
Q: ?Sized + Hash + Eq,
{
match self.repr_mut() {
ReprMut::Thin(repr) => {
repr.iter_mut().find_map(|Align((k, v))| ((*k).borrow() == key).then_some(v))
}
ReprMut::Map(repr) => repr.get_mut(key),
}
}
pub fn get_disjoint_mut<Q, const N: usize>(&mut self, ks: [&Q; N]) -> [Option<&mut V>; N]
where
K: Borrow<Q>,
Q: ?Sized + Hash + Eq,
{
match self.repr_mut() {
ReprMut::Thin(repr) => {
let mut result = [const { None }; N];
for Align((key, value)) in repr {
for (&k, v) in std::iter::zip(&ks, &mut result) {
if (*key).borrow() == k {
*v = Some(value);
break;
}
}
}
result
}
ReprMut::Map(repr) => repr.get_disjoint_mut(ks),
}
}
#[inline]
pub fn insert(&mut self, key: K, value: V) -> Option<V> {
match self.repr_mut() {
ReprMut::Thin(repr) => {
let existing = repr.iter_mut().find(|Align((k, _v))| *k == key);
match existing {
Some(Align((_k, v))) => Some(mem::replace(v, value)),
None => {
if repr.len() < LEN_CUTOFF {
repr.push(Align((key, value)));
} else {
self.insert_cold(key, value);
}
None
}
}
}
ReprMut::Map(repr) => repr.insert(key, value),
}
}
#[inline]
#[expect(unsafe_code)]
pub fn entry(&mut self, key: K) -> Entry<'_, K, V, M> {
let this_ptr = self as *mut Self;
match self.repr_mut() {
ReprMut::Thin(repr) => {
let existing = repr.iter().position(|Align((k, _v))| *k == key);
match existing {
Some(existing) => Entry::Occupied(OccupiedEntry {
repr: OccupiedEntryRepr::Thin { slice: repr, index: existing },
}),
None => {
if repr.len() < LEN_CUTOFF {
Entry::Vacant(VacantEntry {
repr: VacantEntryRepr::ThinHasSpace(key, repr),
})
} else {
// SAFETY: Polonius workaround.
Entry::Vacant(VacantEntry {
repr: VacantEntryRepr::ThinNoSpace(key, unsafe { &mut *this_ptr }),
})
}
}
}
}
ReprMut::Map(repr) => match repr.entry(key) {
MapEntry::Occupied(it) => {
Entry::Occupied(OccupiedEntry { repr: OccupiedEntryRepr::Map(it) })
}
MapEntry::Vacant(it) => {
Entry::Vacant(VacantEntry { repr: VacantEntryRepr::Map(it) })
}
},
}
}
#[cold]
fn insert_cold(&mut self, new_key: K, new_value: V) -> &mut V {
let old_repr = match self.repr_mut() {
ReprMut::Thin(repr) => mem::take(repr),
ReprMut::Map(_) => unreachable!(),
};
let map = M::with_capacity(old_repr.len() + 1);
*self = Self::from_repr(Repr::Map(Box::new(Align(map))));
let map = match self.repr_mut() {
ReprMut::Map(map) => map,
ReprMut::Thin(_) => unreachable!(),
};
for Align((old_key, old_value)) in old_repr {
map.insert(old_key, old_value);
}
match M::entry(map, new_key) {
MapEntry::Vacant(entry) => M::vacant_entry_insert(entry, new_value),
MapEntry::Occupied(_) => panic!("non-existing key somehow compares equal?!"),
}
}
#[inline]
pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
where
K: Borrow<Q>,
Q: ?Sized + Hash + Eq,
{
match self.repr_mut() {
ReprMut::Thin(repr) => {
let index = repr.iter().position(|Align((k, _v))| k.borrow() == key);
index.map(|index| repr.swap_remove(index).0.1)
}
ReprMut::Map(repr) => repr.remove(key),
}
}
}
enum OccupiedEntryRepr<'a, K, V, M: Map<K, V> + 'a> {
Thin { slice: &'a mut [Align<(K, V)>], index: usize },
Map(M::OccupiedEntry<'a>),
}
enum VacantEntryRepr<'a, K, V, M: Map<K, V>> {
ThinHasSpace(K, &'a mut ThinReprVec<K, V>),
ThinNoSpace(K, &'a mut ThinMap<K, V, M>),
Map(M::VacantEntry<'a>),
}
pub struct OccupiedEntry<'a, K, V, M: Map<K, V>> {
repr: OccupiedEntryRepr<'a, K, V, M>,
}
pub struct VacantEntry<'a, K, V, M: Map<K, V>> {
repr: VacantEntryRepr<'a, K, V, M>,
}
pub enum Entry<'a, K, V, M: Map<K, V>> {
Occupied(OccupiedEntry<'a, K, V, M>),
Vacant(VacantEntry<'a, K, V, M>),
}
impl<'a, K: Hash + Eq, V, M: Map<K, V>> VacantEntry<'a, K, V, M> {
#[inline]
pub fn insert(self, value: V) -> &'a mut V {
match self.repr {
VacantEntryRepr::ThinHasSpace(key, repr) => {
repr.push(Align((key, value)));
&mut repr.last_mut().unwrap().0.1
}
VacantEntryRepr::ThinNoSpace(key, repr) => repr.insert_cold(key, value),
VacantEntryRepr::Map(repr) => M::vacant_entry_insert(repr, value),
}
}
}
impl<'a, K: Hash + Eq, V, M: Map<K, V>> OccupiedEntry<'a, K, V, M> {
#[inline]
pub fn get(&self) -> &V {
match &self.repr {
OccupiedEntryRepr::Thin { slice, index } => &slice[*index].0.1,
OccupiedEntryRepr::Map(repr) => M::occupied_entry_get(repr),
}
}
#[inline]
pub fn get_mut(&mut self) -> &mut V {
match &mut self.repr {
OccupiedEntryRepr::Thin { slice, index } => &mut slice[*index].0.1,
OccupiedEntryRepr::Map(repr) => M::occupied_entry_get_mut(repr),
}
}
#[inline]
pub fn into_mut(self) -> &'a mut V {
match self.repr {
OccupiedEntryRepr::Thin { slice, index } => &mut slice[index].0.1,
OccupiedEntryRepr::Map(repr) => M::occupied_entry_into_mut(repr),
}
}
#[inline]
pub fn insert(&mut self, value: V) -> V {
match &mut self.repr {
OccupiedEntryRepr::Thin { slice, index } => mem::replace(&mut slice[*index].0.1, value),
OccupiedEntryRepr::Map(repr) => M::occupied_entry_insert(repr, value),
}
}
}
impl<Q, K, V, M> std::ops::Index<&Q> for ThinMap<K, V, M>
where
Q: ?Sized + Hash + Eq,
K: Borrow<Q> + Hash + Eq,
M: Map<K, V>,
{
type Output = V;
#[inline]
#[track_caller]
fn index(&self, index: &Q) -> &Self::Output {
self.get(index).expect("missing key")
}
}
impl<'a, K: Hash + Eq, V, M: Map<K, V>> Entry<'a, K, V, M> {
#[inline]
pub fn or_insert_with(self, default: impl FnOnce() -> V) -> &'a mut V {
match self {
Entry::Occupied(entry) => {
drop(default);
entry.into_mut()
}
Entry::Vacant(entry) => entry.insert(default()),
}
}
#[inline]
pub fn or_insert(self, default: V) -> &'a mut V {
self.or_insert_with(move || default)
}
#[inline]
pub fn or_default(self) -> &'a mut V
where
V: Default,
{
self.or_insert_with(V::default)
}
}
impl<K, V, M: Map<K, V>> Default for ThinMap<K, V, M> {
#[inline]
fn default() -> Self {
Self::new()
}
}
impl<K, V, M> std::fmt::Debug for ThinMap<K, V, M>
where
M: Map<K, V>,
K: Hash + Eq + std::fmt::Debug,
V: std::fmt::Debug,
{
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_map().entries(self).finish()
}
}
impl<K, V, M> Clone for ThinMap<K, V, M>
where
M: Map<K, V> + Clone,
K: Clone,
V: Clone,
{
#[inline]
fn clone(&self) -> Self {
let repr = match self.repr_ref() {
ReprRef::Thin(repr) => Repr::Thin(ThinVec::from(repr)),
ReprRef::Map(repr) => Repr::Map(Box::new(Align(repr.clone()))),
};
Self::from_repr(repr)
}
}
impl<K, V, M> PartialEq for ThinMap<K, V, M>
where
M: Map<K, V> + PartialEq,
K: Hash + Eq,
V: PartialEq,
{
#[inline]
fn eq(&self, other: &Self) -> bool {
match (self.repr_ref(), other.repr_ref()) {
(ReprRef::Map(this), ReprRef::Map(other)) => {
this.len() == other.len()
&& other.iter().all(|(key, value)| this.get(key) == Some(value))
}
(ReprRef::Map(map), ReprRef::Thin(thin)) | (ReprRef::Thin(thin), ReprRef::Map(map)) => {
thin.len() == map.len()
&& thin.iter().all(|Align((key, value))| map.get(key) == Some(value))
}
(ReprRef::Thin(this), ReprRef::Thin(other)) => {
this.len() == other.len() && this.iter().all(|this_item| other.contains(this_item))
}
}
}
}
impl<K, V, M> Eq for ThinMap<K, V, M>
where
M: Map<K, V> + Eq,
K: Hash + Eq,
V: Eq,
{
}
impl<'a, K: Hash + Eq, V, M: Map<K, V>> IntoIterator for &'a ThinMap<K, V, M> {
type Item = (&'a K, &'a V);
type IntoIter = Iter<'a, K, V, M>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl<'a, K: Hash + Eq, V, M: Map<K, V>> IntoIterator for &'a mut ThinMap<K, V, M> {
type Item = (&'a K, &'a mut V);
type IntoIter = IterMut<'a, K, V, M>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.iter_mut()
}
}
impl<K, V, M: Map<K, V>> IntoIterator for ThinMap<K, V, M> {
type Item = (K, V);
type IntoIter = IntoIter<K, V, M>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
let repr = match self.into_repr() {
Repr::Thin(repr) => IntoIterRepr::Thin(repr.into_iter()),
Repr::Map(repr) => IntoIterRepr::Map(repr.0.into_iter()),
};
IntoIter { repr }
}
}
enum IterRepr<'a, K, V, M: Map<K, V> + 'a> {
Thin(std::slice::Iter<'a, Align<(K, V)>>),
Map(M::Iter<'a>),
}
enum IterMutRepr<'a, K, V, M: Map<K, V> + 'a> {
Thin(std::slice::IterMut<'a, Align<(K, V)>>),
Map(M::IterMut<'a>),
}
enum IntoIterRepr<K, V, M: Map<K, V>> {
Thin(thin_vec::IntoIter<Align<(K, V)>>),
Map(M::IntoIter),
}
macro_rules! impl_iter_methods {
( $repr:ident, $map:expr ) => {
#[inline]
fn next(&mut self) -> Option<Self::Item> {
match &mut self.repr {
$repr::Thin(repr) => repr.next().map($map),
$repr::Map(repr) => repr.next(),
}
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let len = match &self.repr {
$repr::Thin(repr) => repr.len(),
$repr::Map(repr) => repr.len(),
};
(len, Some(len))
}
#[inline]
fn fold<B, F>(self, init: B, mut f: F) -> B
where
Self: Sized,
F: FnMut(B, Self::Item) -> B,
{
match self.repr {
$repr::Thin(repr) => repr.fold(init, move |init, item| f(init, $map(item))),
$repr::Map(repr) => repr.fold(init, f),
}
}
#[inline]
fn for_each<F>(self, mut f: F)
where
Self: Sized,
F: FnMut(Self::Item),
{
match self.repr {
$repr::Thin(repr) => repr.for_each(move |item| f($map(item))),
$repr::Map(repr) => repr.for_each(f),
}
}
#[inline]
fn all<F>(&mut self, mut f: F) -> bool
where
Self: Sized,
F: FnMut(Self::Item) -> bool,
{
match &mut self.repr {
$repr::Thin(repr) => repr.all(move |item| f($map(item))),
$repr::Map(repr) => repr.all(f),
}
}
#[inline]
fn any<F>(&mut self, mut f: F) -> bool
where
Self: Sized,
F: FnMut(Self::Item) -> bool,
{
match &mut self.repr {
$repr::Thin(repr) => repr.any(move |item| f($map(item))),
$repr::Map(repr) => repr.any(f),
}
}
};
}
pub struct Iter<'a, K, V, M: Map<K, V>> {
repr: IterRepr<'a, K, V, M>,
}
impl<'a, K, V, M: Map<K, V>> Iterator for Iter<'a, K, V, M> {
type Item = (&'a K, &'a V);
impl_iter_methods!(IterRepr, |item: &'a Align<(K, V)>| (&item.0.0, &item.0.1));
}
impl<K, V, M: Map<K, V>> ExactSizeIterator for Iter<'_, K, V, M> {}
pub struct IterMut<'a, K, V, M: Map<K, V>> {
repr: IterMutRepr<'a, K, V, M>,
}
impl<'a, K, V, M: Map<K, V>> Iterator for IterMut<'a, K, V, M> {
type Item = (&'a K, &'a mut V);
impl_iter_methods!(IterMutRepr, |item: &'a mut Align<(K, V)>| (&item.0.0, &mut item.0.1));
}
impl<K, V, M: Map<K, V>> ExactSizeIterator for IterMut<'_, K, V, M> {}
pub struct IntoIter<K, V, M: Map<K, V>> {
repr: IntoIterRepr<K, V, M>,
}
impl<K, V, M: Map<K, V>> Iterator for IntoIter<K, V, M> {
type Item = (K, V);
impl_iter_methods!(IntoIterRepr, |item: Align<(K, V)>| item.0);
}
impl<K, V, M: Map<K, V>> ExactSizeIterator for IntoIter<K, V, M> {}
impl<K: Hash + Eq, V, M: Map<K, V>> FromIterator<(K, V)> for ThinMap<K, V, M> {
#[inline]
fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
let mut result = Self::new();
result.extend(iter);
result
}
}
impl<K: Hash + Eq, V, M: Map<K, V>> Extend<(K, V)> for ThinMap<K, V, M> {
#[inline]
fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
let iter = iter.into_iter();
self.reserve(iter.size_hint().0);
iter.for_each(|(key, value)| {
self.insert(key, value);
});
}
}
#[expect(unsafe_code)]
mod unsafe_encapsulation {
use std::{
marker::PhantomData,
mem::{self, ManuallyDrop},
ptr::NonNull,
};
use thin_vec::ThinVec;
use super::{Align, Repr, ReprMut, ReprRef, ThinReprVec};
struct PhantomRepr<K, V, M>(PhantomData<Repr<K, V, M>>);
impl<K, V, M> PhantomRepr<K, V, M> {
const NEW: Self = {
// Disallow ZSTs. A `ThinVec` of a ZST stores `len + 1` in its `ptr` field, which causes
// the LSB of `ptr` to be set if `len` is even. This would break the `ThinMap::TAG`
// mechanism that `ThinMap` uses to distinguish whether its `ptr` contains a `ThinVec`
// or a `Box<Align<M>>`.
assert!(
mem::size_of::<Align<(K, V)>>() > 0,
"ThinMap does not support zero-sized types",
);
Self(PhantomData)
};
}
pub struct ThinMap<K, V, M> {
// INVARIANT: Holds a transmuted `ThinReprVec` or a `Box<Align<M>>` with its LSB set.
// `Align<(K, V)>` is not zero-sized (enforced by `PhantomRepr::NEW`, so `ThinReprVec`'s
// pointer always points to an aligned header with LSB == 0).
ptr: NonNull<()>,
_repr: PhantomRepr<K, V, M>,
}
// SAFETY: We essentially own `Repr<K, V, M>`.
unsafe impl<K, V, M> Send for ThinMap<K, V, M> where Repr<K, V, M>: Send {}
unsafe impl<K, V, M> Sync for ThinMap<K, V, M> where Repr<K, V, M>: Sync {}
#[cfg(feature = "salsa")]
unsafe impl<K, V, M> salsa::SalsaValue for ThinMap<K, V, M> where Repr<K, V, M>: salsa::SalsaValue {}
impl<K, V, M> ThinMap<K, V, M> {
const TAG: usize = 0b1;
#[inline]
pub(super) fn repr_ref<'a>(&'a self) -> ReprRef<'a, K, V, M> {
let tag = self.ptr.addr().get() & Self::TAG;
// SAFETY: Per our invariant. `ThinVec` is layout-equivalent to a pointer.
// FIXME: Technically `ThinVec`'s layout isn't guaranteed unless we enable the `gecko-ffi` feature. Should we enable it?
unsafe {
match tag {
0 => {
let thin_vec =
mem::transmute::<&'a NonNull<()>, &'a ThinReprVec<K, V>>(&self.ptr);
ReprRef::Thin(thin_vec)
}
1 => ReprRef::Map(
&(*self.ptr.as_ptr().map_addr(|addr| addr & !Self::TAG).cast::<Align<M>>())
.0,
),
_ => unreachable!(),
}
}
}
#[inline]
pub(super) fn repr_mut<'a>(&'a mut self) -> ReprMut<'a, K, V, M> {
let tag = self.ptr.addr().get() & Self::TAG;
// SAFETY: Per our invariant. `ThinVec` is layout-equivalent to a pointer.
unsafe {
match tag {
0 => {
let thin_vec = mem::transmute::<
&'a mut NonNull<()>,
&'a mut ThinReprVec<K, V>,
>(&mut self.ptr);
ReprMut::Thin(thin_vec)
}
1 => ReprMut::Map(
&mut (*self
.ptr
.as_ptr()
.map_addr(|addr| addr & !Self::TAG)
.cast::<Align<M>>())
.0,
),
_ => unreachable!(),
}
}
}
#[inline]
pub(super) fn into_repr(self) -> Repr<K, V, M> {
let this = ManuallyDrop::new(self);
let tag = this.ptr.addr().get() & Self::TAG;
// SAFETY: Per our invariant. `ThinVec` is layout-equivalent to a pointer.
unsafe {
match tag {
0 => Repr::Thin(mem::transmute::<NonNull<()>, ThinReprVec<K, V>>(this.ptr)),
1 => Repr::Map(Box::from_raw(
this.ptr.as_ptr().map_addr(|addr| addr & !Self::TAG).cast::<Align<M>>(),
)),
_ => unreachable!(),
}
}
}
#[inline]
pub(super) fn from_repr(repr: Repr<K, V, M>) -> Self {
let ptr = match repr {
// SAFETY: `ThinVec` is layout-equivalent to a pointer.
Repr::Thin(repr) => unsafe {
mem::transmute::<ThinReprVec<K, V>, NonNull<()>>(repr)
},
// SAFETY: `Box::into_raw()` never returns NULL.
// FIXME: Switch to `Box::into_non_null()` once stable.
Repr::Map(repr) => unsafe {
NonNull::new_unchecked(
Box::into_raw(repr).cast::<()>().map_addr(|addr| addr | 1),
)
},
};
// INVARIANT: We keep it properly.
Self { ptr, _repr: PhantomRepr::NEW }
}
#[inline]
pub const fn new() -> Self {
// INVARIANT: We keep it properly.
let ptr = unsafe { mem::transmute::<ThinReprVec<K, V>, NonNull<()>>(ThinVec::new()) };
Self { ptr, _repr: PhantomRepr::NEW }
}
}
impl<K, V, M> Drop for ThinMap<K, V, M> {
#[inline]
fn drop(&mut self) {
// INVARIANT: This is a copy of `self` only to drop it.
drop(ThinMap::<K, V, M> { ptr: self.ptr, _repr: PhantomRepr::NEW }.into_repr());
}
}
}