rg3d_core/
sstorage.rs

1//! Immutable string + immutable string storage. See docs of [`ImmutableString`] and
2//! [`ImmutableStringStorage`] for more info.
3
4#![warn(missing_docs)]
5
6use crate::{
7    parking_lot::Mutex,
8    visitor::{Visit, VisitResult, Visitor},
9};
10use fxhash::{FxHashMap, FxHasher};
11use std::{
12    fmt::{Display, Formatter},
13    hash::{Hash, Hasher},
14    ops::Deref,
15    sync::Arc,
16};
17
18/// Immutable string is a string with constant content. Immutability gives some nice properties:
19///
20/// - Address of the string could be used as a hash, which improves hashing performance dramatically
21/// and basically making it constant in terms of complexity (O(1))
22/// - Equality comparison becomes constant in terms of complexity.
23/// - Uniqueness guarantees - means that calling multiple times will allocate memory only once
24/// `ImmutableString::new("foo")` and in consecutive calls existing string will be used.
25///
26/// # Use cases
27///
28/// Most common use case for immutable strings is hash map keys in performance-critical places.
29#[derive(Clone, Debug)]
30pub struct ImmutableString(Arc<String>);
31
32impl Display for ImmutableString {
33    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
34        f.write_str(self.0.as_ref())
35    }
36}
37
38impl Visit for ImmutableString {
39    fn visit(&mut self, name: &str, visitor: &mut Visitor) -> VisitResult {
40        // Serialize/deserialize as ordinary string.
41        let mut string = self.0.deref().clone();
42        string.visit(name, visitor)?;
43
44        // Deduplicate on deserialization.
45        if visitor.is_reading() {
46            *self = SSTORAGE.lock().insert(string);
47        }
48
49        Ok(())
50    }
51}
52
53impl Default for ImmutableString {
54    fn default() -> Self {
55        Self::new("")
56    }
57}
58
59impl ImmutableString {
60    /// Creates new immutable string from given string slice.
61    ///
62    /// # Performance
63    ///
64    /// This method has amortized O(1) complexity, in worst case (when there is no such string
65    /// in backing storage) it allocates memory which could lead to complexity defined by current
66    /// memory allocator.
67    #[inline]
68    pub fn new<S: AsRef<str>>(string: S) -> ImmutableString {
69        SSTORAGE.lock().insert(string)
70    }
71
72    /// Returns unique identifier of the string. Keep in mind that uniqueness is guaranteed only
73    /// for a single session, uniqueness is not preserved between application runs.
74    #[inline]
75    pub fn id(&self) -> u64 {
76        &*self.0 as *const _ as u64
77    }
78
79    /// Clones content of inner immutable string to a mutable string.
80    #[inline]
81    pub fn to_mutable(&self) -> String {
82        (*self.0).clone()
83    }
84}
85
86impl Deref for ImmutableString {
87    type Target = str;
88
89    #[inline]
90    fn deref(&self) -> &Self::Target {
91        self.0.as_ref()
92    }
93}
94
95impl Hash for ImmutableString {
96    #[inline]
97    fn hash<H: Hasher>(&self, state: &mut H) {
98        state.write_u64(self.id())
99    }
100}
101
102impl PartialEq for ImmutableString {
103    #[inline]
104    fn eq(&self, other: &Self) -> bool {
105        self.id() == other.id()
106    }
107}
108
109impl Eq for ImmutableString {}
110
111/// Immutable string storage is a backing storage for every immutable string in the application,
112/// storage is a singleton. In normal circumstances you should never use it directly.
113#[derive(Default)]
114pub struct ImmutableStringStorage {
115    vec: FxHashMap<u64, Arc<String>>,
116}
117
118impl ImmutableStringStorage {
119    #[inline]
120    fn insert<S: AsRef<str>>(&mut self, string: S) -> ImmutableString {
121        let mut hasher = FxHasher::default();
122        string.as_ref().hash(&mut hasher);
123        let hash = hasher.finish();
124
125        if let Some(existing) = self.vec.get(&hash) {
126            ImmutableString(existing.clone())
127        } else {
128            let immutable = Arc::new(string.as_ref().to_owned());
129            self.vec.insert(hash, immutable.clone());
130            ImmutableString(immutable)
131        }
132    }
133}
134
135impl ImmutableStringStorage {
136    /// Returns total amount of immutable strings in the storage.
137    pub fn entry_count() -> usize {
138        SSTORAGE.lock().vec.len()
139    }
140}
141
142lazy_static! {
143    static ref SSTORAGE: Arc<Mutex<ImmutableStringStorage>> =
144        Arc::new(Mutex::new(ImmutableStringStorage::default()));
145}
146
147#[cfg(test)]
148mod test {
149    use crate::sstorage::{ImmutableString, ImmutableStringStorage};
150
151    #[test]
152    fn test_immutable_string_uniqueness() {
153        let a = ImmutableString::new("Foobar");
154        let b = ImmutableString::new("Foobar");
155
156        assert_eq!(ImmutableStringStorage::entry_count(), 1);
157        assert_eq!(a.id(), b.id())
158    }
159}
rg3d_core/sstorage.rs

rg3d_core/
sstorage.rs
