1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

//! Immutable string + immutable string storage. See docs of [`ImmutableString`] and
//! [`ImmutableStringStorage`] for more info.

#![warn(missing_docs)]

use crate::{
    parking_lot::Mutex,
    visitor::{Visit, VisitResult, Visitor},
};
use fxhash::{FxHashMap, FxHasher};
use std::{
    fmt::{Display, Formatter},
    hash::{Hash, Hasher},
    ops::Deref,
    sync::Arc,
};

/// Immutable string is a string with constant content. Immutability gives some nice properties:
///
/// - Address of the string could be used as a hash, which improves hashing performance dramatically
/// and basically making it constant in terms of complexity (O(1))
/// - Equality comparison becomes constant in terms of complexity.
/// - Uniqueness guarantees - means that calling multiple times will allocate memory only once
/// `ImmutableString::new("foo")` and in consecutive calls existing string will be used.
///
/// # Use cases
///
/// Most common use case for immutable strings is hash map keys in performance-critical places.
#[derive(Clone, Debug)]
pub struct ImmutableString(Arc<String>);

impl Display for ImmutableString {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        f.write_str(self.0.as_ref())
    }
}

impl Visit for ImmutableString {
    fn visit(&mut self, name: &str, visitor: &mut Visitor) -> VisitResult {
        // Serialize/deserialize as ordinary string.
        let mut string = self.0.deref().clone();
        string.visit(name, visitor)?;

        // Deduplicate on deserialization.
        if visitor.is_reading() {
            *self = SSTORAGE.lock().insert(string);
        }

        Ok(())
    }
}

impl Default for ImmutableString {
    fn default() -> Self {
        Self::new("")
    }
}

impl ImmutableString {
    /// Creates new immutable string from given string slice.
    ///
    /// # Performance
    ///
    /// This method has amortized O(1) complexity, in worst case (when there is no such string
    /// in backing storage) it allocates memory which could lead to complexity defined by current
    /// memory allocator.
    #[inline]
    pub fn new<S: AsRef<str>>(string: S) -> ImmutableString {
        SSTORAGE.lock().insert(string)
    }

    /// Returns unique identifier of the string. Keep in mind that uniqueness is guaranteed only
    /// for a single session, uniqueness is not preserved between application runs.
    #[inline]
    pub fn id(&self) -> u64 {
        &*self.0 as *const _ as u64
    }

    /// Clones content of inner immutable string to a mutable string.
    #[inline]
    pub fn to_mutable(&self) -> String {
        (*self.0).clone()
    }
}

impl Deref for ImmutableString {
    type Target = str;

    #[inline]
    fn deref(&self) -> &Self::Target {
        self.0.as_ref()
    }
}

impl Hash for ImmutableString {
    #[inline]
    fn hash<H: Hasher>(&self, state: &mut H) {
        state.write_u64(self.id())
    }
}

impl PartialEq for ImmutableString {
    #[inline]
    fn eq(&self, other: &Self) -> bool {
        self.id() == other.id()
    }
}

impl Eq for ImmutableString {}

/// Immutable string storage is a backing storage for every immutable string in the application,
/// storage is a singleton. In normal circumstances you should never use it directly.
#[derive(Default)]
pub struct ImmutableStringStorage {
    vec: FxHashMap<u64, Arc<String>>,
}

impl ImmutableStringStorage {
    #[inline]
    fn insert<S: AsRef<str>>(&mut self, string: S) -> ImmutableString {
        let mut hasher = FxHasher::default();
        string.as_ref().hash(&mut hasher);
        let hash = hasher.finish();

        if let Some(existing) = self.vec.get(&hash) {
            ImmutableString(existing.clone())
        } else {
            let immutable = Arc::new(string.as_ref().to_owned());
            self.vec.insert(hash, immutable.clone());
            ImmutableString(immutable)
        }
    }
}

impl ImmutableStringStorage {
    /// Returns total amount of immutable strings in the storage.
    pub fn entry_count() -> usize {
        SSTORAGE.lock().vec.len()
    }
}

lazy_static! {
    static ref SSTORAGE: Arc<Mutex<ImmutableStringStorage>> =
        Arc::new(Mutex::new(ImmutableStringStorage::default()));
}

#[cfg(test)]
mod test {
    use crate::sstorage::{ImmutableString, ImmutableStringStorage};

    #[test]
    fn test_immutable_string_uniqueness() {
        let a = ImmutableString::new("Foobar");
        let b = ImmutableString::new("Foobar");

        assert_eq!(ImmutableStringStorage::entry_count(), 1);
        assert_eq!(a.id(), b.id())
    }
}