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    // Inserts the value into the interner's arena without checking if the value already exists.
53    // Future calls to intern will not find the same value, use `intern_new` if you want that behaviour.
54    pub fn insert_arena(&self, value: T) -> &mut T {
55        self.arena.get_or_init(Bump::new).alloc(value)
56    }
57
58    fn set(&self) -> &HashTable<NonNull<u8>> {
59        // Safety: mutable access is entirely contained without the Interners methods.
60        unsafe { self.set.get().as_ref().unwrap() }
61    }
62
63    #[expect(clippy::mut_from_ref)]
64    fn set_mut(&self) -> &mut HashTable<NonNull<u8>> {
65        // Safety: mutable access is entirely contained without the Interners methods.
66        unsafe { self.set.get().as_mut().unwrap() }
67    }
68}
69
70impl<T: Hash + Eq> Interner<T> {
71    pub(crate) fn try_resolve_with<Q>(&self, value: &Q, hash: u64) -> Option<&T>
72    where
73        T: Borrow<Q>,
74        Q: ?Sized + Eq,
75    {
76        self.set()
77            .find(hash, |cached| T::borrow(unsafe { cached.cast().as_ref() }) == value)
78            .map(|ptr| unsafe { ptr.cast().as_ref() })
79    }
80
81    pub(crate) fn insert(&self, hash: u64, value: T) -> &T {
82        let arena = self.arena.get_or_init(Bump::new);
83
84        let cached = NonNull::from(arena.alloc(value)).cast();
85        self.set_mut().insert_unique(hash, cached, |t| FxBuildHasher.hash_one(t));
86        unsafe { cached.cast().as_ref() }
87    }
88
89    /// Will return a reference to an equivalent value if it already exists
90    #[must_use]
91    pub fn try_resolve<Q>(&self, value: &Q) -> Option<&T>
92    where
93        T: Borrow<Q>,
94        Q: ?Sized + Hash + Eq,
95    {
96        let hash = FxBuildHasher.hash_one(value);
97        self.try_resolve_with(value, hash)
98    }
99
100    /// Returns a reference to either the value provided, or an equivalent value that was already inserted
101    pub fn intern(&self, value: T) -> &T {
102        let hash = FxBuildHasher.hash_one(&value);
103
104        if let Some(cached) = self.try_resolve_with(&value, hash) {
105            return cached;
106        }
107
108        self.insert(hash, value)
109    }
110
111    /// Inserts the value into the interner without checking if the value already exists
112    pub fn intern_new(&self, value: T) -> &T {
113        let hash = FxBuildHasher.hash_one(&value);
114        self.insert(hash, value)
115    }
116}
117
118impl<T: fmt::Debug> fmt::Debug for Interner<T> {
119    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
120        self.set().fmt(f)
121    }
122}
123
124unsafe impl<T> Send for Interner<T> where T: Send {}
petty_intern/unsync.rs

petty_intern/
unsync.rs
