o3 0.25.1

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

//! Fixed-capacity sets that retain their ordering through every insertion.

use std::{mem, ptr};

use crate::depot::array::prefix::Prefix;

/// An ordered inline set with no allocation or drop glue.
#[repr(transparent)]
pub struct Set<T: Copy, const N: usize> {
    prefix: Prefix<T, N>,
}

/// A rejected set member and the exact observed conflict or capacity.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum Error<T> {
    Duplicate { value: T, existing: T },
    Full { value: T, capacity: usize },
}

impl<T: Copy + Ord, const N: usize> Default for Set<T, N> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T: Copy + Ord, const N: usize> Set<T, N> {
    pub const fn new() -> Self {
        Self {
            prefix: Prefix::empty(),
        }
    }

    /// Searches once and consumes the resulting position in this same owner.
    pub fn try_insert(&mut self, value: T) -> Result<(), Error<T>> {
        let values = self.prefix.as_slice();
        let index = match values.binary_search(&value) {
            Ok(index) => {
                // SAFETY: binary_search selected an element of this exact slice.
                let existing = unsafe { *values.get_unchecked(index) };
                return Err(Error::Duplicate { value, existing });
            }
            Err(index) => index,
        };
        let next = self
            .prefix
            .len
            .vacancy()
            .ok_or(Error::Full { value, capacity: N })?;
        // SAFETY: the search bounds index by the current initialized length;
        // next proves room for the shifted suffix in this exclusively borrowed owner.
        unsafe {
            let start = self.prefix.entries.as_mut_ptr().add(index);
            ptr::copy(start, start.add(1), self.prefix.len.get() - index);
            start.write(mem::MaybeUninit::new(value));
        }
        self.prefix.len = next.commit();
        Ok(())
    }
}