hash_on_write/
lib.rs

1#![doc = include_str!("../README.md")]
2
3#[cfg(test)]
4mod tests;
5mod borrowed;
6
7pub use borrowed::Borrowed;
8
9use core::{
10    borrow::{Borrow, BorrowMut},
11    cell::Cell,
12    cmp::Ordering,
13    fmt::{self, Debug},
14    hash::{Hash, Hasher},
15    marker::PhantomData,
16    ops::{Deref, DerefMut},
17    sync::atomic::{AtomicU64, Ordering as MOrd},
18};
19use std::{
20    rc::Rc,
21    sync::Arc,
22    collections::hash_map::DefaultHasher,
23};
24
25/// Adapters that do not store hash values
26///
27/// Hashing occurs every time, just like [`How`] doesn't exist
28///
29/// [`How`]: crate::How
30#[derive(Debug, Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
31pub struct NoneStorer;
32
33const ZERO_MAPPED: u64 = u64::MAX >> 2;
34
35/// storage trait for storing hash status
36pub trait HashStorer {
37    /// Clear stored hash code to none
38    fn clear(&mut self);
39
40    /// Get stored hash code
41    fn get(&self) -> Option<u64>;
42
43    /// if stored hash code is uninit, call init func
44    ///
45    /// return inited hash code
46    fn get_or_init<F>(&self, f: F) -> u64
47    where F: FnOnce() -> u64;
48
49    fn hash_one<T, H>(value: &T) -> u64
50    where T: ?Sized + Hash,
51          H: Hasher + Default,
52          Self: Default,
53    {
54        Self::default()
55            .get_or_init(|| {
56                let mut hasher = H::default();
57                value.hash(&mut hasher);
58                hasher.finish()
59            })
60    }
61}
62
63impl HashStorer for Cell<u64> {
64    fn clear(&mut self) {
65        self.set(0)
66    }
67
68    fn get(&self) -> Option<u64> {
69        let n = self.get();
70        if n == 0 { return None; }
71        Some(n)
72    }
73
74    fn get_or_init<F>(&self, f: F) -> u64
75    where F: FnOnce() -> u64,
76    {
77        HashStorer::get(self)
78            .unwrap_or_else(|| {
79                let mut n = f();
80                if n == 0 { n = ZERO_MAPPED }
81                self.set(n);
82                n
83            })
84    }
85}
86impl HashStorer for AtomicU64 {
87    fn clear(&mut self) {
88        self.store(0, MOrd::Relaxed)
89    }
90
91    fn get(&self) -> Option<u64> {
92        let n = self.load(MOrd::Relaxed);
93        if n == 0 { return None; }
94        Some(n)
95    }
96
97    fn get_or_init<F>(&self, f: F) -> u64
98    where F: FnOnce() -> u64,
99    {
100        HashStorer::get(self)
101            .unwrap_or_else(|| {
102                let mut n = f();
103                if n == 0 { n = ZERO_MAPPED }
104                self.store(n, MOrd::Relaxed);
105                n
106            })
107    }
108}
109impl HashStorer for NoneStorer {
110    #[inline]
111    fn get(&self) -> Option<u64> {
112        None
113    }
114
115    #[inline]
116    fn clear(&mut self) { }
117
118    #[inline]
119    fn get_or_init<F>(&self, f: F) -> u64
120    where F: FnOnce() -> u64,
121    {
122        f()
123    }
124}
125impl<T: HashStorer + Default> HashStorer for Rc<T> {
126    fn get(&self) -> Option<u64> {
127        <T as HashStorer>::get(&**self)
128    }
129
130    fn clear(&mut self) {
131        Rc::get_mut(self)
132            .map(T::clear)
133            .unwrap_or_else(|| {
134                *self = Default::default()
135            })
136    }
137
138    fn get_or_init<F>(&self, f: F) -> u64
139    where F: FnOnce() -> u64,
140    {
141        <T as HashStorer>::get_or_init(&**self, f)
142    }
143
144    fn hash_one<T1, H>(value: &T1) -> u64
145    where T1: ?Sized + Hash,
146          H: Hasher + Default,
147          Self: Default,
148    {
149        T::hash_one::<T1, H>(value)
150    }
151}
152impl<T: HashStorer + Default> HashStorer for Arc<T> {
153    fn get(&self) -> Option<u64> {
154        <T as HashStorer>::get(&**self)
155    }
156
157    fn clear(&mut self) {
158        Arc::get_mut(self)
159            .map(T::clear)
160            .unwrap_or_else(|| {
161                *self = Default::default()
162            })
163    }
164
165    fn get_or_init<F>(&self, f: F) -> u64
166    where F: FnOnce() -> u64,
167    {
168        <T as HashStorer>::get_or_init(&**self, f)
169    }
170
171    fn hash_one<T1, H>(value: &T1) -> u64
172    where T1: ?Sized + Hash,
173          H: Hasher + Default,
174          Self: Default,
175    {
176        T::hash_one::<T1, H>(value)
177    }
178}
179
180/// A wrapper for storing hash results to avoid running costly hash functions
181/// multiple times without modifying the value
182///
183/// # Examples
184/// ```
185/// # use hash_on_write::How;
186/// # use std::collections::HashSet;
187/// let mut x = How::new_default("foo".to_owned());
188///
189/// assert!(! How::is_hashed(&x));
190/// HashSet::new().insert(&x);
191/// assert!(How::is_hashed(&x));
192///
193/// How::make_mut(&mut x).push('!');
194/// assert!(! How::is_hashed(&x));
195/// assert_eq!(*x, "foo!");
196/// ```
197///
198/// ---
199/// Due to the inability of the stored hashcode to replicate the action of `T::hash,`
200/// it is not possible to implement [`Borrow<T>`]
201///
202/// [`Borrow<T>`]: core::borrow::Borrow
203pub struct How<T: ?Sized, H = DefaultHasher, S = Cell<u64>> {
204    _hasher: PhantomData<H>,
205    hashcode: S,
206    value: T,
207}
208impl<T, H, S> Default for How<T, H, S>
209where T: Default,
210      S: Default,
211{
212    fn default() -> Self {
213        Self::new(Default::default())
214    }
215}
216impl<T: ?Sized, H, S> AsRef<T> for How<T, H, S> {
217    fn as_ref(&self) -> &T {
218        &self.value
219    }
220}
221impl<T: ?Sized, H, S: HashStorer> AsMut<T> for How<T, H, S> {
222    fn as_mut(&mut self) -> &mut T {
223        How::make_mut(self)
224    }
225}
226impl<T: ?Sized, H, S> AsRef<Self> for How<T, H, S> {
227    fn as_ref(&self) -> &Self {
228        self
229    }
230}
231impl<T: ?Sized, H, S> AsMut<Self> for How<T, H, S> {
232    fn as_mut(&mut self) -> &mut Self {
233        self
234    }
235}
236impl<T, Q, H, S> Borrow<Borrowed<Q, H, S>> for How<T, H, S>
237where T: ?Sized + Borrow<Q>,
238      Q: ?Sized,
239{
240    fn borrow(&self) -> &Borrowed<Q, H, S> {
241        Borrowed::make_ref(self.value.borrow())
242    }
243}
244impl<T, Q, H, S> BorrowMut<Borrowed<Q, H, S>> for How<T, H, S>
245where T: ?Sized + BorrowMut<Q>,
246      Q: ?Sized,
247{
248    fn borrow_mut(&mut self) -> &mut Borrowed<Q, H, S> {
249        Borrowed::make_mut(self.value.borrow_mut())
250    }
251}
252impl<T: ?Sized + Debug, H, S: Debug> Debug for How<T, H, S> {
253    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
254        f.debug_struct("How")
255            .field("hashcode", &self.hashcode)
256            .field("value", &&self.value)
257            .finish()
258    }
259}
260impl<T: Clone, H, S: Clone> Clone for How<T, H, S> {
261    fn clone(&self) -> Self {
262        Self {
263            _hasher: PhantomData,
264            hashcode: self.hashcode.clone(),
265            value: self.value.clone(),
266        }
267    }
268}
269impl<T: ?Sized + Eq, H, S: HashStorer> Eq for How<T, H, S> { }
270impl<T: ?Sized + Ord, H, S: HashStorer> Ord for How<T, H, S> {
271    fn cmp(&self, other: &Self) -> Ordering {
272        self.value.cmp(&other.value)
273    }
274}
275impl<T: ?Sized + PartialEq, H, S: HashStorer> PartialEq for How<T, H, S> {
276    fn eq(&self, other: &Self) -> bool {
277        self.hashcode.get()
278            .zip(other.hashcode.get())
279            .is_none_or(|(a, b)| a == b)
280            && self.value == other.value
281    }
282}
283impl<T: ?Sized + PartialEq, H, S> PartialEq<T> for How<T, H, S> {
284    fn eq(&self, other: &T) -> bool {
285        **self == *other
286    }
287}
288impl<T: ?Sized + PartialOrd, H, S: HashStorer> PartialOrd for How<T, H, S> {
289    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
290        self.value.partial_cmp(&other.value)
291    }
292}
293impl<T: ?Sized + PartialOrd, H, S> PartialOrd<T> for How<T, H, S> {
294    fn partial_cmp(&self, other: &T) -> Option<Ordering> {
295        (**self).partial_cmp(other)
296    }
297}
298impl<T: ?Sized, H, S> Deref for How<T, H, S> {
299    type Target = T;
300
301    fn deref(&self) -> &Self::Target {
302        &self.value
303    }
304}
305impl<T, H, S> DerefMut for How<T, H, S>
306where T: ?Sized + Hash,
307      H: Hasher + Default,
308      S: HashStorer,
309{
310    fn deref_mut(&mut self) -> &mut Self::Target {
311        Self::make_mut(self)
312    }
313}
314impl<T, IH, S> Hash for How<T, IH, S>
315where T: ?Sized + Hash,
316      IH: Hasher + Default,
317      S: HashStorer,
318{
319    #[inline]
320    fn hash<H: Hasher>(&self, state: &mut H) {
321        Self::make_hash(self)
322            .hash(state)
323    }
324}
325impl<T, H, S> From<T> for How<T, H, S>
326where H: Hasher + Default,
327      S: HashStorer + Default,
328{
329    #[inline]
330    fn from(value: T) -> Self {
331        Self::new(value)
332    }
333}
334impl<T> How<T> {
335    /// new, but use [`DefaultHasher`]
336    ///
337    /// [`DefaultHasher`]: std::collections::hash_map::DefaultHasher
338    pub fn new_default(value: T) -> Self {
339        How {
340            _hasher: PhantomData,
341            hashcode: Default::default(),
342            value,
343        }
344    }
345}
346impl<T, H, S: Default> How<T, H, S> {
347    /// New a wrapped value
348    #[inline]
349    pub fn new(value: T) -> Self {
350        How {
351            _hasher: PhantomData,
352            hashcode: Default::default(),
353            value,
354        }
355    }
356}
357
358impl<T, H, S> How<T, H, S> {
359    /// Consume `self` into wrapped value
360    pub fn into_inner(this: Self) -> T {
361        this.value
362    }
363}
364impl<T: ?Sized, H, S: HashStorer> How<T, H, S> {
365    /// Get mutable and clear hash cache
366    pub fn make_mut(this: &mut Self) -> &mut T {
367        this.hashcode.clear();
368        &mut this.value
369    }
370
371    /// Get hash cache status
372    pub fn hash_code(this: &Self) -> Option<u64> {
373        this.hashcode.get()
374    }
375
376    /// Get hash cache status is cached,
377    /// like `How::hash_code(&value).is_some()`
378    pub fn is_hashed(this: &Self) -> bool {
379        Self::hash_code(this).is_some()
380    }
381}
382impl<T, H, S> How<T, H, S>
383where T: ?Sized + Hash,
384      H: Default + Hasher,
385      S: HashStorer,
386{
387    /// Get or init hash cache
388    pub fn make_hash(this: &Self) -> u64 {
389        this.hashcode.get_or_init(|| {
390            let mut inner_hasher = H::default();
391            this.value.hash(&mut inner_hasher);
392            inner_hasher.finish()
393        })
394    }
395}
hash_on_write/lib.rs

hash_on_write/
lib.rs
