interned_string/
lib.rs

1#[cfg(target_family = "wasm")]
2compile_error!(
3    "The `interned-string` crate cannot run on WebAssembly due to needing multiple threads."
4);
5
6use std::{fmt::Debug, ops::Deref};
7use storage::{IStringKey, ThreadLocalReader, SHARED_STORAGE, THREAD_LOCAL_READER};
8
9mod storage;
10
11/// An immutable and interned string.
12/// 
13/// Reading an `IString`'s contents is very fast, lock-free and wait-free.
14/// It can be shared and read from any number of threads.
15/// It scales linearly with the number of reading threads.
16/// 
17/// `IString` provides `Hash` and `Eq` implementations that run in O(1),
18/// perfect for an high performance `HashMap<IString, _>`
19/// 
20/// The tradeoff is that creating a new `IString` is comparatively slower :
21/// - Creating a new `IString` with a string that is already interned is fast and lock-free.
22/// - Creating a new `IString` with a string that isn't already interned is slower.
23///   It acquires a global lock and waits for all readers to finish reading.
24#[derive(Eq, PartialEq, Ord, Hash)]
25pub struct IString {
26    pub(crate) key: IStringKey
27}
28
29// Indispensable traits impl : From, Drop, Deref
30
31impl From<String> for IString {
32    /// Intern the given `String` by consuming it. Its allocation is reused.
33    /// 
34    /// This operation runs in O(N) where N is the `string.len()`.
35    /// If the string was already interned, this operation is lock-free.
36    /// Otherwise, a global lock is acquired.
37    /// 
38    /// # Example
39    /// 
40    /// ```
41    /// use interned_string::IString;
42    /// 
43    /// let my_istring = IString::from("hello".to_string());
44    /// ```
45    #[inline]
46    fn from(string: String) -> Self {
47        Self {
48            // could block
49            key: SHARED_STORAGE.insert_or_retain(string)
50        }
51    }
52}
53
54impl From<&str> for IString {
55    /// Intern the given `&str` by cloning its contents.
56    /// 
57    /// This operation runs in O(N) where N is the `string.len()`.
58    /// If the string was already interned, this operation is lock-free.
59    /// Otherwise, a global lock is acquired.
60    /// 
61    /// # Example
62    /// 
63    /// ```
64    /// use interned_string::IString;
65    /// 
66    /// let my_istring = IString::from("hello");
67    /// ```
68    #[inline]
69    fn from(string: &str) -> Self {
70        Self {
71            // could block
72            key: SHARED_STORAGE.insert_or_retain(String::from(string))
73        }
74    }
75}
76
77impl Drop for IString {
78    #[inline]
79    fn drop(&mut self) {
80        THREAD_LOCAL_READER.with(|tl_reader| {
81            tl_reader.release(self);
82        });
83    }
84}
85
86impl Deref for IString {
87    type Target = str;
88    
89    /// Returns a reference to the string's contents.
90    /// 
91    /// This operation runs in O(1) and is lock-free.
92    /// 
93    /// # Example
94    /// ```
95    /// use interned_string::Intern;
96    /// 
97    /// fn foo(string: &str) {
98    ///     println!("{string}")
99    /// }
100    /// 
101    /// let my_istring = "hello".intern();
102    /// // implicit call to Deref::deref
103    /// foo(&my_istring);
104    /// ```
105    #[inline]
106    fn deref(&self) -> &Self::Target {
107        THREAD_LOCAL_READER.with(|reader: &ThreadLocalReader| {
108            reader.read(self)
109        })
110    }
111}
112
113impl AsRef<str> for IString {
114    /// Returns a reference to the string's contents.
115    /// 
116    /// This operation runs in O(1) and is lock-free.
117    /// 
118    /// # Example
119    /// ```
120    /// use interned_string::Intern;
121    /// 
122    /// let my_istring = "Hello, World!".intern();
123    /// let (hello, world) = my_istring.as_ref().split_at(5);
124    /// ```
125    #[inline]
126    fn as_ref(&self) -> &str {
127        THREAD_LOCAL_READER.with(|tl_reader: &ThreadLocalReader| {
128            tl_reader.read(self)
129        })
130    }
131}
132
133// Common traits impl that can't be derived : Clone, PartialOrd, Debug, Display, Default
134
135impl Clone for IString {
136    /// Returns a copy of the `IString`.
137    /// 
138    /// This operation runs in O(1) and is lock-free.
139    #[inline]
140    fn clone(&self) -> Self {
141        THREAD_LOCAL_READER.with(|reader: &ThreadLocalReader| {
142            reader.retain(self.key)
143        });
144
145        Self { key: self.key }
146    }
147}
148
149impl PartialOrd for IString {
150    #[inline]
151    fn lt(&self, other: &Self) -> bool {
152        self.deref().lt(other.deref())
153    }
154
155    #[inline]
156    fn le(&self, other: &Self) -> bool {
157        self.deref().le(other.deref())
158    }
159
160    #[inline]
161    fn gt(&self, other: &Self) -> bool {
162        self.deref().gt(other.deref())
163    }
164
165    #[inline]
166    fn ge(&self, other: &Self) -> bool {
167        self.deref().ge(other.deref())
168    }
169    
170    #[inline]
171    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
172        self.deref().partial_cmp(other.deref())
173    }
174}
175
176impl Debug for IString {
177    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
178        f.debug_tuple("IString")
179         .field(&self.deref())
180         .finish()
181    }
182}
183
184impl std::fmt::Display for IString {
185    #[inline]
186    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
187        f.write_str(self)
188    }
189}
190
191impl Default for IString {
192    /// Creates an empty `IString`.
193    #[inline]
194    fn default() -> Self {
195        Self::from(String::default())
196    }
197}
198
199// Convenience trait Intern
200
201pub trait Intern {
202    fn intern(self) -> IString where Self: Sized;
203}
204
205impl Intern for String {
206    /// Intern the given `String` by consuming it. Its allocation is reused.
207    /// 
208    /// This operation runs in O(N) where N is the `string.len()`.
209    /// If the string was already interned, this operation is lock-free.
210    /// Otherwise, a global lock is acquired.
211    /// 
212    /// # Example
213    /// 
214    /// ```
215    /// use interned_string::Intern;
216    /// 
217    /// let my_istring = "hello".to_string().intern();
218    /// ```
219    #[inline]
220    fn intern(self) -> IString {
221        IString::from(self)
222    }
223}
224
225impl Intern for &str {
226    /// Intern the given `&str` by cloning its contents.
227    /// 
228    /// This operation runs in O(N) where N is the `string.len()`.
229    /// If the string was already interned, this operation is lock-free.
230    /// Otherwise, a global lock is acquired.
231    /// 
232    /// # Example
233    /// 
234    /// ```
235    /// use interned_string::Intern;
236    /// 
237    /// let my_istring = "hello".intern();
238    /// ```
239    #[inline]
240    fn intern(self) -> IString {
241        IString::from(self)
242    }
243}
244
245// Garbage collection
246
247impl IString {
248    /// Immediately frees all the interned strings that are no longer used.
249    /// 
250    /// Call this function when you wish to immediately reduce memory usage,
251    /// at the cost of some CPU time. 
252    /// This will acquire a global lock and wait for all readers to finish reading.
253    /// It's recommended to only call this function when your program has nothing else to do.
254    /// 
255    /// Using this function is optional. Memory is always eventually freed.
256    pub fn collect_garbage_now() {
257        SHARED_STORAGE.writer.lock().unwrap().collect_garbage();
258    }
259}
260
261#[cfg(feature = "serde")]
262mod feature_serde {
263    use serde::{de::Visitor, Deserialize, Serialize};
264    use crate::IString;
265
266    impl Serialize for IString {
267        fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
268            serializer.serialize_str(std::ops::Deref::deref(&self))
269        }
270    }
271    
272    impl<'de> Deserialize<'de> for IString {
273        fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
274            deserializer.deserialize_string(IStringVisitor)
275        }
276    }
277    
278    struct IStringVisitor;
279    
280    impl<'de> Visitor<'de> for IStringVisitor {
281        type Value = IString;
282    
283        fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
284            formatter.write_str("a string")
285        }
286    
287        fn visit_string<E: serde::de::Error>(self, string: String) -> Result<Self::Value, E> {
288            // does not need to allocate a new string
289            Ok(IString::from(string))
290        }
291    
292        fn visit_str<E: serde::de::Error>(self, slice: &str) -> Result<Self::Value, E> {
293            // less performant, will allocate
294            Ok(IString::from(slice))
295        }
296    }
297}
298
299// tests
300
301#[cfg(test)]
302mod tests {
303    use std::{ops::Deref, sync::Mutex};
304    use radix_trie::TrieCommon;
305
306    use super::*;
307    use crate::storage::SHARED_STORAGE;
308
309    #[test]
310    fn it_creates_and_removes_1_string() {
311        with_exclusive_use_of_shared_storage(|| {
312            let my_istring1 = "hello".intern();
313            assert!(my_istring1.deref() == "hello");
314
315            assert_string_count_in_storage(1);
316            assert_string_is_stored_with_key("hello", my_istring1.key);
317
318            drop(my_istring1);
319
320            assert_string_count_in_storage(1);
321            assert_string_is_still_stored("hello");
322
323            let my_istring2 = "another".to_string().intern();
324            assert!(my_istring2.deref() == "another");
325
326            assert_string_count_in_storage(1);
327            assert_string_is_stored_with_key("another", my_istring2.key);
328            assert_string_is_not_stored("hello")
329        });
330    }
331
332    #[test]
333    fn it_creates_and_removes_1_shared_string() {
334        with_exclusive_use_of_shared_storage(|| {
335            let my_istring1 = IString::from("hello");
336            let my_istring2 = IString::from("hello");
337            assert!(my_istring1.deref() == "hello");
338            assert!(my_istring2.deref() == "hello");
339            assert!(my_istring1.key == my_istring2.key);
340
341            assert_string_count_in_storage(1);
342            assert_string_is_stored_with_key("hello", my_istring1.key);
343
344            drop(my_istring1);
345
346            assert_string_count_in_storage(1);
347            assert_string_is_stored_with_key("hello", my_istring2.key);
348
349            drop(my_istring2);
350
351            assert_string_count_in_storage(1);
352            assert_string_is_still_stored("hello");
353        });
354    }
355
356    #[test]
357    fn it_creates_and_removes_3_strings() {
358        with_exclusive_use_of_shared_storage(|| {
359            let my_istring1 = IString::from("hello");
360            let my_istring2 = IString::from("world");
361            let my_istring3 = IString::from("howdy");
362            assert!(my_istring1.deref() == "hello");
363            assert!(my_istring2.deref() == "world");
364            assert!(my_istring3.deref() == "howdy");
365            assert!(my_istring1.key != my_istring2.key);
366            assert!(my_istring2.key != my_istring3.key);
367
368            assert_string_count_in_storage(3);
369            assert_string_is_stored_with_key("hello", my_istring1.key);
370            assert_string_is_stored_with_key("world", my_istring2.key);
371            assert_string_is_stored_with_key("howdy", my_istring3.key);
372            assert_string_is_not_stored("hola");
373
374            drop(my_istring1);
375            drop(my_istring2);
376
377            assert_string_count_in_storage(3);
378            assert_string_is_still_stored("hello");
379            assert_string_is_still_stored("world");
380            assert_string_is_stored_with_key("howdy", my_istring3.key);
381            assert_string_is_not_stored("hola");
382
383            // it should reuse the storage
384            let my_istring1bis = IString::from("hello");
385            assert!(my_istring1bis.deref() == "hello");
386
387            // and not clean up the storage of "world" yet
388            assert_string_count_in_storage(3);
389            assert_string_is_stored_with_key("hello", my_istring1bis.key);
390            assert_string_is_stored_with_key("howdy", my_istring3.key);
391            assert_string_is_still_stored("world");
392
393            let my_istring4 = IString::from("another");
394            assert!(my_istring4.deref() == "another");
395
396            // creating a new string should cause the storage of unused strings to be cleaned up
397            assert_string_is_stored_with_key("hello", my_istring1bis.key);
398            assert_string_is_stored_with_key("howdy", my_istring3.key);
399            assert_string_is_stored_with_key("another", my_istring4.key);
400            assert_string_is_not_stored("world");
401            assert_string_count_in_storage(3);
402        });
403    }
404
405    /// Regression test for https://github.com/drash-course/interned-string/issues/3
406    #[test]
407    fn out_of_order_retain_release_does_not_panic() {
408        with_exclusive_use_of_shared_storage(|| {
409            let s1 = "hello".intern();
410            drop(s1); // Release queued
411
412            // Re-intern before GC runs: Retain queued while key is still in strings_to_possibly_free
413            let s2 = "hello".intern();
414            drop(s2); // Release queued again
415
416            // Trigger drain + GC
417            let _ = "trigger_gc".intern();
418        });
419    }
420
421    #[test]
422    fn it_is_send() {
423        fn assert_send<T: Send>() {}
424        assert_send::<IString>();
425    }
426
427    #[test]
428    fn it_is_sync() {
429        fn assert_sync<T: Sync>() {}
430        assert_sync::<IString>();
431    }
432
433    #[cfg(feature = "serde")]
434    #[test]
435    fn it_serializes() {
436        with_exclusive_use_of_shared_storage(|| {
437            use serde::Serialize;
438
439            #[derive(Serialize)]
440            struct ExampleDTO {
441                favorite_dish: IString
442            }
443
444            let dto = ExampleDTO { favorite_dish: "pasta".intern() };
445
446            assert_eq!(serde_json::to_string(&dto).unwrap(), "{\"favorite_dish\":\"pasta\"}");
447        });
448    }
449
450    #[cfg(feature = "serde")]
451    #[test]
452    fn it_deserializes() {
453        with_exclusive_use_of_shared_storage(|| {
454            use serde::Deserialize;
455
456            #[derive(Deserialize, PartialEq, Debug)]
457            struct ExampleDTO {
458                favorite_dish: IString
459            }
460
461            let input = "{\"favorite_dish\":\"pasta\"}";
462
463            let dto: Result<ExampleDTO, _> = serde_json::from_str(input);
464
465            assert_eq!(dto.unwrap(), ExampleDTO { favorite_dish: "pasta".into() });
466        });
467    }
468
469    fn assert_string_count_in_storage(count: usize) {
470        let guard = SHARED_STORAGE.read_handle.lock().unwrap();
471        let read_handle = guard.enter().unwrap();
472        assert_eq!(read_handle.map.len(), count);
473        assert_eq!(read_handle.trie.len(), count);
474    }
475
476    fn assert_string_is_still_stored(string: &str) {
477        let guard = SHARED_STORAGE.read_handle.lock().unwrap();
478        let read_handle = guard.enter().unwrap();
479        let key = read_handle.trie.get(&string.into());
480        if let Some(key) = key {
481            assert!(read_handle.map.get(&key).unwrap().inner.deref() == string);
482        } else {
483            assert!(false, "the string is not in the trie");
484        }
485    }
486
487    fn assert_string_is_stored_with_key(string: &str, key: u32) {
488        let guard = SHARED_STORAGE.read_handle.lock().unwrap();
489        let read_handle = guard.enter().unwrap();
490        assert!(read_handle.map.get(&key).unwrap().inner.deref() == string);
491        assert_eq!(read_handle.trie.get(&string.into()), Some(&key));
492    }
493
494    fn assert_string_is_not_stored(string: &str) {
495        let guard = SHARED_STORAGE.read_handle.lock().unwrap();
496        let read_handle = guard.enter().unwrap();
497        assert_eq!(read_handle.trie.get(&string.into()), None);
498    }
499
500    static SHARED_STORAGE_MUTEX: Mutex<()> = Mutex::new(());
501
502    fn with_exclusive_use_of_shared_storage(closure: fn()) {
503        let guard = SHARED_STORAGE_MUTEX.lock().expect("test lock is not poisoned");
504        closure();
505
506        // reset the writer for the next test
507        let mut writer = SHARED_STORAGE.writer.lock().unwrap();
508        writer.drain_channel_ops();
509        writer.write_handle.append(storage::StringStorageOp::DropUnusedStrings);
510        writer.write_handle.publish();
511        drop(writer);
512        drop(guard);
513    }
514}
interned_string/lib.rs

interned_string/
lib.rs
