petty_intern/
unsync.rs

1use {
2    bumpalo::Bump,
3    hashbrown::HashTable,
4    rustc_hash::FxBuildHasher,
5    std::{
6        borrow::Borrow,
7        cell::{OnceCell, UnsafeCell},
8        fmt,
9        hash::{BuildHasher, Hash},
10        marker::PhantomData,
11        ptr::NonNull,
12    },
13};
14
15pub struct Interner<T> {
16    // an interner must be covariant in `T`
17    __marker: PhantomData<T>,
18    // UnsafeCell for interior mutability, the NonNull<u8> is a reference into the arena.
19    // It uses u8 instead of T to avoid making T invariant
20    set: UnsafeCell<HashTable<NonNull<u8>>>,
21    arena: OnceCell<Bump>,
22}
23
24impl<T> Default for Interner<T> {
25    fn default() -> Self {
26        Self::new()
27    }
28}
29
30impl<T> Interner<T> {
31    /// Creates an empty Interner.
32    /// The current implementation does not allocate
33    #[must_use]
34    pub const fn new() -> Self {
35        Self {
36            __marker: PhantomData,
37            set: UnsafeCell::new(HashTable::new()),
38            arena: OnceCell::new(),
39        }
40    }
41
42    /// Returns the number of entries in the interner
43    pub fn len(&self) -> usize {
44        self.set().len()
45    }
46
47    /// Returns `true` if the interner contains no elements
48    pub fn is_empty(&self) -> bool {
49        self.len() == 0
50    }
51
52    fn set(&self) -> &HashTable<NonNull<u8>> {
53        // Safety: mutable access is entirely contained without the Interners methods.
54        unsafe { self.set.get().as_ref().unwrap() }
55    }
56
57    #[expect(clippy::mut_from_ref)]
58    fn set_mut(&self) -> &mut HashTable<NonNull<u8>> {
59        // Safety: mutable access is entirely contained without the Interners methods.
60        unsafe { self.set.get().as_mut().unwrap() }
61    }
62}
63
64impl<T: Hash + Eq> Interner<T> {
65    pub(crate) fn try_resolve_with<Q>(&self, value: &Q, hash: u64) -> Option<&T>
66    where
67        T: Borrow<Q>,
68        Q: ?Sized + Eq,
69    {
70        self.set()
71            .find(hash, |cached| T::borrow(unsafe { cached.cast().as_ref() }) == value)
72            .map(|ptr| unsafe { ptr.cast().as_ref() })
73    }
74
75    pub(crate) fn insert(&self, hash: u64, value: T) -> &T {
76        let arena = self.arena.get_or_init(Bump::new);
77
78        let cached = NonNull::from(arena.alloc(value)).cast();
79        self.set_mut().insert_unique(hash, cached, |t| FxBuildHasher.hash_one(t));
80        unsafe { cached.cast().as_ref() }
81    }
82
83    /// Will return a reference to an equivalent value if it already exists
84    #[must_use]
85    pub fn try_resolve<Q>(&self, value: &Q) -> Option<&T>
86    where
87        T: Borrow<Q>,
88        Q: ?Sized + Hash + Eq,
89    {
90        let hash = FxBuildHasher.hash_one(value);
91        self.try_resolve_with(value, hash)
92    }
93
94    /// Returns a reference to either the value provided, or an equivalent value that was already inserted
95    pub fn intern(&self, value: T) -> &T {
96        let hash = FxBuildHasher.hash_one(&value);
97
98        if let Some(cached) = self.try_resolve_with(&value, hash) {
99            return cached;
100        }
101
102        self.insert(hash, value)
103    }
104
105    /// Inserts the value into the interner without checking if the value already exists
106    pub fn intern_new(&self, value: T) -> &T {
107        let hash = FxBuildHasher.hash_one(&value);
108        self.insert(hash, value)
109    }
110}
111
112impl<T: fmt::Debug> fmt::Debug for Interner<T> {
113    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
114        self.set().fmt(f)
115    }
116}
117
118unsafe impl<T> Send for Interner<T> where T: Send {}
petty_intern/unsync.rs

petty_intern/
unsync.rs
