device_driver_common/
interner.rs

1//! Interner based on https://matklad.github.io/2020/03/22/fast-simple-rust-interner.html
2
3use std::{
4    borrow::Borrow,
5    collections::HashMap,
6    hash::Hash,
7    mem,
8    num::NonZero,
9    ops::Deref,
10    sync::{LazyLock, Mutex},
11};
12
13static GLOBAL_INTERNER: LazyLock<Mutex<Interner>> =
14    LazyLock::new(|| Mutex::new(Interner::with_capacity(1024 * 32)));
15
16pub struct Interner {
17    map: HashMap<&'static str, NonZero<u32>>,
18    vec: Vec<&'static str>,
19    buf: String,
20    full: Vec<String>,
21}
22
23impl Interner {
24    fn with_capacity(cap: usize) -> Interner {
25        let cap = cap.next_power_of_two();
26        let mut interner = Interner {
27            map: HashMap::default(),
28            vec: Vec::new(),
29            buf: String::with_capacity(cap),
30            full: Vec::new(),
31        };
32
33        // Allocate a default Istr at 0
34        let default_istr = interner.intern("");
35        debug_assert_eq!(default_istr.0.get(), 1);
36
37        interner
38    }
39
40    pub fn intern(&mut self, name: &str) -> Istr {
41        if let Some(&id) = self.map.get(name) {
42            return Istr(id);
43        }
44        let name = unsafe { self.alloc(name) };
45        let id = NonZero::new(self.map.len() as u32 + 1).unwrap();
46        self.map.insert(name, id);
47        self.vec.push(name);
48
49        debug_assert!(self.lookup(Istr(id)) == name);
50        debug_assert!(self.intern(name) == Istr(id));
51
52        Istr(id)
53    }
54
55    pub fn lookup(&self, id: Istr) -> &'static str {
56        self.vec[id.0.get() as usize - 1]
57    }
58
59    unsafe fn alloc(&mut self, name: &str) -> &'static str {
60        let cap = self.buf.capacity();
61        if cap < self.buf.len() + name.len() {
62            let new_cap = (cap.max(name.len()) + 1).next_power_of_two();
63            let new_buf = String::with_capacity(new_cap);
64            let old_buf = mem::replace(&mut self.buf, new_buf);
65            self.full.push(old_buf);
66        }
67
68        let interned = {
69            let start = self.buf.len();
70            self.buf.push_str(name);
71            &self.buf[start..]
72        };
73
74        unsafe { &*(interned as *const str) }
75    }
76}
77
78impl Drop for Interner {
79    fn drop(&mut self) {
80        panic!("Interner must not be dropped since it has given out static references")
81    }
82}
83
84#[derive(PartialEq, Eq, Clone, Copy)]
85pub struct Istr(NonZero<u32>);
86
87impl Istr {
88    pub fn as_str(self) -> &'static str {
89        let interner = GLOBAL_INTERNER.lock().unwrap();
90        interner.lookup(self)
91    }
92}
93
94impl std::fmt::Debug for Istr {
95    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
96        if f.alternate() {
97            write!(f, "({}){:?}", self.0, self.as_str())
98        } else {
99            write!(f, "{:?}", self.as_str())
100        }
101    }
102}
103
104impl std::fmt::Display for Istr {
105    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
106        write!(f, "{}", self.as_str())
107    }
108}
109
110impl Deref for Istr {
111    type Target = str;
112
113    fn deref(&self) -> &Self::Target {
114        self.as_str()
115    }
116}
117
118impl AsRef<str> for Istr {
119    fn as_ref(&self) -> &str {
120        self.as_str()
121    }
122}
123
124impl Borrow<str> for Istr {
125    fn borrow(&self) -> &str {
126        self.as_str()
127    }
128}
129
130impl Hash for Istr {
131    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
132        self.as_str().hash(state);
133    }
134}
135
136impl<'a> From<&'a str> for Istr {
137    fn from(value: &'a str) -> Self {
138        value.intern()
139    }
140}
141
142impl Default for Istr {
143    fn default() -> Self {
144        Self(NonZero::new(1).unwrap())
145    }
146}
147
148pub trait StrExt {
149    fn intern(&self) -> Istr;
150}
151impl<T: AsRef<str>> StrExt for T {
152    fn intern(&self) -> Istr {
153        GLOBAL_INTERNER.lock().unwrap().intern(self.as_ref())
154    }
155}
device_driver_common/interner.rs

device_driver_common/
interner.rs
