o3 0.30.0

shared-nothing primitives
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
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

use std::{marker, num::NonZero};

use crate::depot::{
    capacity::Physical,
    index::bitmap::{self, entry},
};

/// One checked position retaining its original source owner.
pub struct Row<S, P = (), M = (), W = usize> {
    pub(in crate::depot::index::bitmap) phase: Phase<M, W>,
    pub(in crate::depot::index::bitmap) plane: P,
    pub(in crate::depot) source: S,
    pub(in crate::depot::index::bitmap) index: NonZero<u32>,
}

impl<S: Copy, W> Clone for Row<S, (), (), W> {
    fn clone(&self) -> Self {
        *self
    }
}

impl<S: Copy, W> Copy for Row<S, (), (), W> {}

impl<W: bitmap::Width, S: crate::depot::raw::Words<W>> Row<S, (), (), W> {
    /// Projects an admitted one-based row position in its exact source domain.
    /// This retains a physical bound, without claiming current membership.
    pub fn from_source(source: crate::depot::raw::Proof<(S, NonZero<u32>), Physical>) -> Self {
        let (source, index) = source.into_inner();
        Self {
            source,
            index,
            plane: (),
            phase: marker::PhantomData,
        }
    }

    pub fn try_new(source: S, index: usize) -> Result<Self, bitmap::Error> {
        let capacity = source.shape().bits();
        if index >= capacity {
            return Err(bitmap::Error { index, capacity });
        }
        // SAFETY: admission bounds this index in the exact retained source.
        Ok(unsafe { Self::new(source, index) })
    }

    /// # Safety
    /// The index belongs to this exact retained source's immutable domain.
    pub(in crate::depot) unsafe fn new(source: S, index: usize) -> Self {
        // SAFETY: the retained u32 domain bounds the nonzero encoded position.
        let index = unsafe { NonZero::new_unchecked(index as u32 + 1) };
        // SAFETY: the same retained domain admits this one-based row position.
        Self::from_source(unsafe { crate::depot::raw::Proof::new((source, index)) })
    }
}

impl<W: bitmap::Width, S: crate::depot::raw::Words<W>, P, M> Row<S, P, M, W> {
    pub(in crate::depot) const fn plane(&self) -> P
    where
        P: Copy,
    {
        self.plane
    }

    pub(in crate::depot::index::bitmap) fn borrow(&self) -> Row<&S, (), (), W> {
        Row {
            source: &self.source,
            index: self.index,
            plane: (),
            phase: marker::PhantomData,
        }
    }

    pub const fn index(&self) -> usize {
        self.index.get() as usize - 1
    }

    pub fn contains(&self, plane: S::Plane) -> bool {
        let index = self.index();
        let words = S::row(self.borrow(), plane);
        // SAFETY: this row retains the checked position in its exact plane.
        let word = unsafe { words.get_unchecked(index / W::BITS as usize) };
        word.get() & (1usize << (index % W::BITS as usize)) != 0
    }
}

impl<W: bitmap::Width, S: crate::depot::raw::Words<W>, P> Row<S, P, (), W> {
    pub const fn source(&self) -> &S {
        &self.source
    }

    /// # Safety
    /// The projection must retain the exact source, immutable domain, and owner lifetime.
    pub(in crate::depot) unsafe fn map<T: crate::depot::raw::Words<W>>(
        self,
        map: impl FnOnce(S) -> T,
    ) -> Row<T, (), (), W> {
        Row {
            source: map(self.source),
            index: self.index,
            plane: (),
            phase: marker::PhantomData,
        }
    }
}

impl<'a, W: bitmap::Width, S: crate::depot::raw::Bitmap<W>> Row<&'a mut S, (), (), W> {
    pub fn occupied(
        self,
        plane: S::Plane,
    ) -> Result<Mutable<'a, S, entry::Occupied, W>, Mutable<'a, S, entry::Absent, W>> {
        let entry: Row<_, _, (), W> = Row {
            source: self.source,
            index: self.index,
            plane,
            phase: marker::PhantomData,
        };
        if entry.contains(plane) {
            Ok(entry.with_phase())
        } else {
            Err(entry.with_phase())
        }
    }
}

impl<W: bitmap::Width, S: crate::depot::raw::Words<W, Size = NonZero<u32>>> Row<S, (), (), W> {
    /// Selects the requested row, saturating at this nonempty source's final row.
    pub fn clamp(source: S, index: usize) -> Self {
        let capacity = source.shape().bits;
        let index = index.min(capacity.get() as usize - 1);
        // SAFETY: the nonzero exact domain and clamp bound this encoded position.
        unsafe { Self::new(source, index) }
    }
}

impl<S, P, M, W> Row<S, P, M, W> {
    /// The compact one-based position retained by this row's source proof.
    pub const fn position(&self) -> NonZero<u32> {
        self.index
    }

    pub(in crate::depot) fn with_phase<N>(self) -> Row<S, P, N, W> {
        Row {
            source: self.source,
            index: self.index,
            plane: self.plane,
            phase: marker::PhantomData,
        }
    }
}

/// An exclusive row retains its bitmap owner and selected plane across phase changes.
type Mutable<'a, S, P, W> = Row<&'a mut S, <S as crate::depot::raw::Words<W>>::Plane, P, W>;

type Phase<M, W> = marker::PhantomData<fn(M, W) -> (M, W)>;

const _: () = {
    assert!(size_of::<Row<&()>>() == 2 * size_of::<usize>());
    assert!(size_of::<Option<Row<&()>>>() == size_of::<Row<&()>>());
};