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

use std::mem;

use node::Node;

use crate::depot::{array::Index, queue::links};
pub(in crate::depot) mod node;

use lanes::entry;

use crate::depot::{capacity, index::Initialized, map::direct, queue::indexed::lanes};

pub(in crate::depot) struct Hooks<
    'a,
    K: crate::depot::raw::Key,
    V,
    const N: usize,
    S: lanes::raw::State<V> = (),
>(pub(in crate::depot) &'a direct::Table<K, Node<V, N, S>>);

/// Key-indexed values and their exclusive FIFO membership.
pub struct Table<K: crate::depot::raw::Key, V, const N: usize, S: lanes::raw::State<V> = ()> {
    pub(in crate::depot) values: direct::Table<K, Node<V, N, S>>,
    pub(in crate::depot) queues: [links::Chain; N],
}

// SAFETY: the retained table admits stable hooks at every initialized index.
unsafe impl<K: crate::depot::raw::Key, V, const N: usize, S: lanes::raw::State<V>>
    crate::depot::raw::Hooks for Hooks<'_, K, V, N, S>
{
    unsafe fn hook_raw(&self, index: links::Index) -> &links::Hook {
        // SAFETY: this exact table retains the admitted initialized hook slot.
        &unsafe { self.0.value(index) }.hook
    }
}

impl<K: crate::depot::raw::Key, V, const N: usize, S: lanes::raw::State<V>> Table<K, V, N, S> {
    /// Bytes reserved for each exact key, value, and its lane links.
    pub const NODE_BYTES: usize = mem::size_of::<direct::raw::Entry<K, Node<V, N, S>>>();

    pub fn try_new(cap: capacity::Count) -> Result<Self, crate::alloc::Error> {
        const { assert!(N <= u8::MAX as usize) };
        Ok(Self {
            values: direct::Table::try_new(cap)?,
            queues: [const { links::Chain::new() }; N],
        })
    }

    pub const fn capacity(&self) -> usize {
        self.values.capacity()
    }

    pub const fn is_empty(&self) -> bool {
        self.len() == 0
    }

    pub const fn len(&self) -> usize {
        self.values.len()
    }

    pub fn get(&self, key: K) -> Option<&V> {
        self.values.get(key).map(|node| &*node.value)
    }

    /// Returns the stored identity and value from one occupied index.
    pub fn entry_at(&self, index: usize) -> Option<(K, &V)> {
        let (key, node) = self.values.entry_at(index)?;
        Some((key, &*node.value))
    }

    pub fn key_at(&self, index: usize) -> Option<K> {
        self.values.key_at(index)
    }

    pub fn lane(&self, key: K) -> Option<Option<Index<N>>> {
        Some(self.values.get(key)?.lane.get())
    }

    pub fn try_vacant(
        &mut self,
        key: K,
    ) -> Result<entry::Vacancy<'_, K, V, N, S>, direct::Error<K>> {
        let slot = self.values.try_vacant(key)?;
        Ok(entry::Slot::new(slot, &self.queues))
    }

    pub fn vacant(&mut self, key: K) -> Option<entry::Vacancy<'_, K, V, N, S>> {
        let slot = self.values.vacant(key)?;
        Some(entry::Slot::new(slot, &self.queues))
    }

    pub fn entry(&mut self, key: K) -> Option<entry::Occupied<'_, K, V, N, S>> {
        let Self { values, queues } = self;
        let slot = values.entry(key)?;
        Some(entry::Slot::new(slot, queues))
    }

    pub fn front(&mut self, lane: Index<N>) -> Option<entry::Occupied<'_, K, V, N, S>> {
        let Self { values, queues } = self;
        let index = lane.get(queues).front()?;
        // SAFETY: membership in this exact queue proves its front is occupied
        // in the paired value store.
        let slot = unsafe { direct::raw::Entry::occupied(values, index) };
        Some(entry::Slot::new(slot, queues))
    }

    pub fn back(&self, lane: Index<N>) -> Option<K> {
        let index = lane.get(&self.queues).last()?;
        // SAFETY: this exact queue's retained tail belongs to the paired table.
        let live = unsafe {
            crate::depot::raw::Proof::<(_, _), Initialized<()>>::new((&self.values, index))
        };
        Some(direct::Table::project(live).into_inner().1)
    }

    pub fn is_vacant(&self, lane: Index<N>) -> bool {
        lane.get(&self.queues).is_empty()
    }

    pub fn move_all(&mut self, source: Index<N>, target: Index<N>) -> usize {
        if source == target {
            return 0;
        }
        let mut moved = 0;
        let mut next = source.get(&self.queues).first();
        while let Some(index) = next {
            // SAFETY: the original queue proves this exact initialized member.
            let node = unsafe { self.values.value(index) };
            next = node.hook.next_index();
            node.lane.set(Some(target));
            moved += 1;
        }
        if moved != 0 {
            unsafe {
                target
                    .get(&self.queues)
                    .append(source.get(&self.queues), &Hooks(&self.values));
            }
        }
        moved
    }

    pub fn clear(&mut self) {
        if self.is_empty() {
            return;
        }
        self.queues = [const { links::Chain::new() }; N];
        self.values.clear();
    }
}