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
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        unsafe { Self::insert_ref(&self.set, hash, arena.alloc(value)) }
78    }
79
80    pub(crate) unsafe fn insert_ref<'a>(
81        set: &'a UnsafeCell<HashTable<NonNull<u8>>>,
82        hash: u64,
83        value: &T,
84    ) -> &'a T {
85        let cached = NonNull::from(value).cast();
86        unsafe {
87            (set.get().as_mut().unwrap())
88                .insert_unique(hash, cached, |t| FxBuildHasher.hash_one(t.cast::<T>().as_ref()));
89            cached.cast().as_ref()
90        }
91    }
92
93    /// Will return a reference to an equivalent value if it already exists
94    #[must_use]
95    pub fn try_resolve<Q>(&self, value: &Q) -> Option<&T>
96    where
97        T: Borrow<Q>,
98        Q: ?Sized + Hash + Eq,
99    {
100        let hash = FxBuildHasher.hash_one(value);
101        self.try_resolve_with(value, hash)
102    }
103
104    /// Returns a reference to either the value provided, or an equivalent value that was already inserted
105    pub fn intern(&self, value: T) -> &T {
106        let hash = FxBuildHasher.hash_one(&value);
107
108        if let Some(cached) = self.try_resolve_with(&value, hash) {
109            return cached;
110        }
111
112        self.insert(hash, value)
113    }
114
115    /// Inserts the value into the interner without checking if the value already exists
116    pub fn intern_new(&self, value: T) -> &T {
117        let hash = FxBuildHasher.hash_one(&value);
118        self.insert(hash, value)
119    }
120
121    /// Inserts a reference to the value into the interner.
122    /// All future calls the `Interner::intern` will return the provided reference.
123    ///
124    /// This function will *not* check if an equivalent value already exists within the table,
125    /// and may behave weirdly if one does.
126    pub fn intern_ref_unique(&self, value: &'static T) {
127        let hash = FxBuildHasher.hash_one(value);
128        unsafe { Self::insert_ref(&self.set, hash, value) };
129    }
130}
131
132impl<T: fmt::Debug> fmt::Debug for Interner<T> {
133    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
134        self.set().fmt(f)
135    }
136}
137
138unsafe impl<T> Send for Interner<T> where T: Send {}
petty_intern/unsync.rs

petty_intern/
unsync.rs
