papaya 0.2.4

A fast and ergonomic concurrent hash-table for read-heavy workloads.
Documentation 
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

use std::mem::align_of;
use std::sync::atomic::{AtomicPtr, Ordering};

// Polyfill for the strict-provenance API.
#[allow(clippy::missing_safety_doc)]
#[allow(dead_code)] // `strict_provenance` has stabilized on 1.84.0.
pub unsafe trait StrictProvenance<T>: Sized {
    fn addr(self) -> usize;
    fn map_addr(self, f: impl FnOnce(usize) -> usize) -> Self;
    fn unpack(self) -> Tagged<T>
    where
        T: Unpack;
}

// Unpack a tagged pointer.
pub trait Unpack: Sized {
    // A mask for the pointer tag bits.
    const MASK: usize;

    // This constant, if used, will fail to compile if T doesn't have an alignment
    // that guarantees all valid pointers have zero in the bits excluded by T::MASK.
    const ASSERT_ALIGNMENT: () = assert!(align_of::<Self>() > !Self::MASK);
}

unsafe impl<T> StrictProvenance<T> for *mut T {
    #[inline(always)]
    fn addr(self) -> usize {
        self as usize
    }

    #[inline(always)]
    fn map_addr(self, f: impl FnOnce(usize) -> usize) -> Self {
        f(self.addr()) as Self
    }

    #[inline(always)]
    fn unpack(self) -> Tagged<T>
    where
        T: Unpack,
    {
        let () = T::ASSERT_ALIGNMENT;
        Tagged {
            raw: self,
            ptr: self.map_addr(|addr| addr & T::MASK),
        }
    }
}

// An unpacked tagged pointer.
pub struct Tagged<T> {
    // The raw tagged pointer.
    pub raw: *mut T,

    // The untagged pointer.
    pub ptr: *mut T,
}

// Creates a `Tagged` from an untagged pointer.
#[inline]
pub fn untagged<T>(value: *mut T) -> Tagged<T> {
    Tagged {
        raw: value,
        ptr: value,
    }
}

impl<T> Tagged<T>
where
    T: Unpack,
{
    // Returns the tag portion of this pointer.
    #[inline]
    pub fn tag(self) -> usize {
        self.raw.addr() & !T::MASK
    }

    // Maps the tag of this pointer.
    #[inline]
    pub fn map_tag(self, f: impl FnOnce(usize) -> usize) -> Self {
        Tagged {
            raw: self.raw.map_addr(f),
            ptr: self.ptr,
        }
    }
}

impl<T> Copy for Tagged<T> {}

impl<T> Clone for Tagged<T> {
    fn clone(&self) -> Self {
        *self
    }
}

// Polyfill for the strict-provenance `AtomicPtr` API.
#[allow(dead_code)] // `strict_provenance_atomic_ptr` has stabilized on 1.91.0.
pub trait AtomicPtrFetchOps<T> {
    fn fetch_or(&self, value: usize, ordering: Ordering) -> *mut T;
}

impl<T> AtomicPtrFetchOps<T> for AtomicPtr<T> {
    #[inline]
    fn fetch_or(&self, value: usize, ordering: Ordering) -> *mut T {
        #[cfg(not(miri))]
        {
            use std::sync::atomic::AtomicUsize;

            // Safety: `AtomicPtr` and `AtomicUsize` are identical in terms
            // of memory layout. This operation is technically invalid in that
            // it loses provenance, but there is no stable alternative.
            unsafe { &*(self as *const AtomicPtr<T> as *const AtomicUsize) }
                .fetch_or(value, ordering) as *mut T
        }

        // Avoid ptr2int under Miri.
        #[cfg(miri)]
        {
            // Returns the ordering for the read in an RMW operation.
            const fn read_ordering(ordering: Ordering) -> Ordering {
                match ordering {
                    Ordering::SeqCst => Ordering::SeqCst,
                    Ordering::AcqRel => Ordering::Acquire,
                    _ => Ordering::Relaxed,
                }
            }

            self.fetch_update(ordering, read_ordering(ordering), |ptr| {
                Some(ptr.map_addr(|addr| addr | value))
            })
            .unwrap()
        }
    }
}