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
160
161
162
163

use alloc::boxed::Box;
use core::{
    iter::repeat_with,
    mem::{self, ManuallyDrop},
    ptr,
};

use crate::key::Key;

union Slot<T, K: Key> {
    val: ManuallyDrop<T>,
    next: K,
    uninit: (),
}

impl<T, K: Key> Slot<T, K> {
    #[inline]
    fn uninit() -> Self {
        Self { uninit: () }
    }
}

/// A [`Slab`] which can hold some number of elements, depending on the chosen `K`.
///
/// # Examples
///
/// ```
/// let mut slab = slabby::Slab32::new();
/// unsafe {
///     let key1 = slab.insert(1);
///     let key2 = slab.insert(2);
///     let key3 = slab.insert(3);
///
///     assert_eq!(slab.get(key1), &1);
///     assert_eq!(slab.get(key2), &2);
///     assert_eq!(slab.get(key3), &3);
///
///     assert_eq!(slab.remove(key2), 2);
///     assert_eq!(slab.remove(key1), 1);
///
///     assert_eq!(slab.get(key3), &3);
///
///     slab.insert(4);
///     let key5 = slab.insert(5);
///     slab.insert(6);
///
///     assert_eq!(slab.len(), 4);
///
///     *slab.get_mut(key5) += 1;
///     assert_eq!(slab.remove(key5), 6);
///
///     assert_eq!(slab.len(), 3);
/// }
/// ```
pub struct Slab<T, K: Key> {
    slots: Box<[Slot<T, K>]>,
    next: K,
    len: K,
}

impl<T, K: Key> Slab<T, K> {
    /// Create a new [`Slab`]. No allocations will occur until the first [`Slab::insert`].
    #[inline]
    #[must_use]
    pub fn new() -> Self {
        Self {
            slots: Box::new([]),
            next: K::ZERO,
            len: K::ZERO,
        }
    }

    #[inline(never)]
    fn extend(&mut self) {
        const INITIAL_SIZE: usize = 4;
        let ptr = &mut self.slots as *mut Box<[_]>;
        unsafe {
            let b = ptr::read(ptr);
            let extend_by = if b.len() == 0 { INITIAL_SIZE } else { b.len() };
            let mut vec = b.into_vec();
            vec.extend(repeat_with(Slot::uninit).take(extend_by));
            ptr::write(ptr, vec.into_boxed_slice());
        }
    }

    /// # Safety
    ///
    /// The number of occupied slots must be lower than the maximum value of `K`. This is trivially
    /// true if the maximum value of `K` is greater or equal to that of [`usize`].
    #[inline]
    pub unsafe fn insert(&mut self, val: T) -> K {
        let next = self.next;

        if next.as_usize() == self.slots.len() {
            self.extend();
        }

        let slot = unsafe { self.slots.get_unchecked_mut(next.as_usize()) };

        self.next = if self.next == self.len {
            self.next.inc()
        } else {
            unsafe { slot.next }
        };
        self.len = self.len.inc();

        slot.val = ManuallyDrop::new(val);

        next
    }

    /// Remove a previously inserted element from the [`Slab`]. Returns the contained `T`.
    ///
    /// # Safety
    ///
    /// The provided `key` must have been obtained from this instance of [`Slab`] and not removed
    /// between the insertion and this call.
    #[inline]
    pub unsafe fn remove(&mut self, key: K) -> T {
        let slot = unsafe { self.slots.get_unchecked_mut(key.as_usize()) };
        let slot = mem::replace(slot, Slot { next: self.next });

        self.next = key;
        self.len = self.len.dec();

        ManuallyDrop::into_inner(unsafe { slot.val })
    }

    /// # Safety
    ///
    /// The provided `key` must have been obtained from this instance of [`Slab`] and not removed
    /// between the insertion and this call.
    #[inline]
    #[must_use]
    pub unsafe fn get(&self, key: K) -> &T {
        unsafe { &self.slots.get_unchecked(key.as_usize()).val }
    }

    /// # Safety
    ///
    /// The provided `key` must have been obtained from this instance of [`Slab`] and not removed
    /// between the insertion and this call.
    #[inline]
    #[must_use]
    pub unsafe fn get_mut(&mut self, key: K) -> &mut T {
        unsafe { &mut self.slots.get_unchecked_mut(key.as_usize()).val }
    }

    /// Get the number of elements contained within this [`Slab`].
    #[inline]
    #[must_use]
    pub fn len(&self) -> K {
        self.len
    }
}

impl<T, K: Key> Default for Slab<T, K> {
    #[inline]
    #[must_use]
    fn default() -> Self {
        Self::new()
    }
}