1 files changed, 215 insertions, 0 deletions
diff --git a/vendor/sharded-slab/src/cfg.rs b/vendor/sharded-slab/src/cfg.rs
new file mode 100644
index 000000000..b690ab2bf
--- /dev/null
+++ b/vendor/sharded-slab/src/cfg.rs
@@ -0,0 +1,215 @@
+use crate::page::{
+    slot::{Generation, RefCount},
+    Addr,
+};
+use crate::Pack;
+use std::{fmt, marker::PhantomData};
+/// Configuration parameters which can be overridden to tune the behavior of a slab.
+pub trait Config: Sized {
+    /// The maximum number of threads which can access the slab.
+    ///
+    /// This value (rounded to a power of two) determines the number of shards
+    /// in the slab. If a thread is created, accesses the slab, and then terminates,
+    /// its shard may be reused and thus does not count against the maximum
+    /// number of threads once the thread has terminated.
+    const MAX_THREADS: usize = DefaultConfig::MAX_THREADS;
+    /// The maximum number of pages in each shard in the slab.
+    ///
+    /// This value, in combination with `INITIAL_PAGE_SIZE`, determines how many
+    /// bits of each index are used to represent page addresses.
+    const MAX_PAGES: usize = DefaultConfig::MAX_PAGES;
+    /// The size of the first page in each shard.
+    ///
+    /// When a page in a shard has been filled with values, a new page
+    /// will be allocated that is twice as large as the previous page. Thus, the
+    /// second page will be twice this size, and the third will be four times
+    /// this size, and so on.
+    ///
+    /// Note that page sizes must be powers of two. If this value is not a power
+    /// of two, it will be rounded to the next power of two.
+    const INITIAL_PAGE_SIZE: usize = DefaultConfig::INITIAL_PAGE_SIZE;
+    /// Sets a number of high-order bits in each index which are reserved from
+    /// user code.
+    ///
+    /// Note that these bits are taken from the generation counter; if the page
+    /// address and thread IDs are configured to use a large number of bits,
+    /// reserving additional bits will decrease the period of the generation
+    /// counter. These should thus be used relatively sparingly, to ensure that
+    /// generation counters are able to effectively prevent the ABA problem.
+    const RESERVED_BITS: usize = 0;
+}
+
+pub(crate) trait CfgPrivate: Config {
+    const USED_BITS: usize = Generation::<Self>::LEN + Generation::<Self>::SHIFT;
+    const INITIAL_SZ: usize = next_pow2(Self::INITIAL_PAGE_SIZE);
+    const MAX_SHARDS: usize = next_pow2(Self::MAX_THREADS - 1);
+    const ADDR_INDEX_SHIFT: usize = Self::INITIAL_SZ.trailing_zeros() as usize + 1;
+
+    fn page_size(n: usize) -> usize {
+        Self::INITIAL_SZ * 2usize.pow(n as _)
+    }
+
+    fn debug() -> DebugConfig<Self> {
+        DebugConfig { _cfg: PhantomData }
+    }
+
+    fn validate() {
+        assert!(
+            Self::INITIAL_SZ.is_power_of_two(),
+            "invalid Config: {:#?}",
+            Self::debug(),
+        );
+        assert!(
+            Self::INITIAL_SZ <= Addr::<Self>::BITS,
+            "invalid Config: {:#?}",
+            Self::debug()
+        );
+
+        assert!(
+            Generation::<Self>::BITS >= 3,
+            "invalid Config: {:#?}\ngeneration counter should be at least 3 bits!",
+            Self::debug()
+        );
+
+        assert!(
+            Self::USED_BITS <= WIDTH,
+            "invalid Config: {:#?}\ntotal number of bits per index is too large to fit in a word!",
+            Self::debug()
+        );
+
+        assert!(
+            WIDTH - Self::USED_BITS >= Self::RESERVED_BITS,
+            "invalid Config: {:#?}\nindices are too large to fit reserved bits!",
+            Self::debug()
+        );
+
+        assert!(
+            RefCount::<Self>::MAX > 1,
+            "invalid config: {:#?}\n maximum concurrent references would be {}",
+            Self::debug(),
+            RefCount::<Self>::MAX,
+        );
+    }
+
+    #[inline(always)]
+    fn unpack<A: Pack<Self>>(packed: usize) -> A {
+        A::from_packed(packed)
+    }
+
+    #[inline(always)]
+    fn unpack_addr(packed: usize) -> Addr<Self> {
+        Self::unpack(packed)
+    }
+
+    #[inline(always)]
+    fn unpack_tid(packed: usize) -> crate::Tid<Self> {
+        Self::unpack(packed)
+    }
+
+    #[inline(always)]
+    fn unpack_gen(packed: usize) -> Generation<Self> {
+        Self::unpack(packed)
+    }
+}
+impl<C: Config> CfgPrivate for C {}
+
+/// Default slab configuration values.
+#[derive(Copy, Clone)]
+pub struct DefaultConfig {
+    _p: (),
+}
+
+pub(crate) struct DebugConfig<C: Config> {
+    _cfg: PhantomData<fn(C)>,
+}
+
+pub(crate) const WIDTH: usize = std::mem::size_of::<usize>() * 8;
+
+pub(crate) const fn next_pow2(n: usize) -> usize {
+    let pow2 = n.count_ones() == 1;
+    let zeros = n.leading_zeros();
+    1 << (WIDTH - zeros as usize - pow2 as usize)
+}
+
+// === impl DefaultConfig ===
+
+impl Config for DefaultConfig {
+    const INITIAL_PAGE_SIZE: usize = 32;
+
+    #[cfg(target_pointer_width = "64")]
+    const MAX_THREADS: usize = 4096;
+    #[cfg(target_pointer_width = "32")]
+    // TODO(eliza): can we find enough bits to give 32-bit platforms more threads?
+    const MAX_THREADS: usize = 128;
+
+    const MAX_PAGES: usize = WIDTH / 2;
+}
+
+impl fmt::Debug for DefaultConfig {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        Self::debug().fmt(f)
+    }
+}
+
+impl<C: Config> fmt::Debug for DebugConfig<C> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_struct(std::any::type_name::<C>())
+            .field("initial_page_size", &C::INITIAL_SZ)
+            .field("max_shards", &C::MAX_SHARDS)
+            .field("max_pages", &C::MAX_PAGES)
+            .field("used_bits", &C::USED_BITS)
+            .field("reserved_bits", &C::RESERVED_BITS)
+            .field("pointer_width", &WIDTH)
+            .field("max_concurrent_references", &RefCount::<C>::MAX)
+            .finish()
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use crate::test_util;
+    use crate::Slab;
+
+    #[test]
+    #[cfg_attr(loom, ignore)]
+    #[should_panic]
+    fn validates_max_refs() {
+        struct GiantGenConfig;
+
+        // Configure the slab with a very large number of bits for the generation
+        // counter. This will only leave 1 bit to use for the slot reference
+        // counter, which will fail to validate.
+        impl Config for GiantGenConfig {
+            const INITIAL_PAGE_SIZE: usize = 1;
+            const MAX_THREADS: usize = 1;
+            const MAX_PAGES: usize = 1;
+        }
+
+        let _slab = Slab::<usize>::new_with_config::<GiantGenConfig>();
+    }
+
+    #[test]
+    #[cfg_attr(loom, ignore)]
+    fn big() {
+        let slab = Slab::new();
+
+        for i in 0..10000 {
+            println!("{:?}", i);
+            let k = slab.insert(i).expect("insert");
+            assert_eq!(slab.get(k).expect("get"), i);
+        }
+    }
+
+    #[test]
+    #[cfg_attr(loom, ignore)]
+    fn custom_page_sz() {
+        let slab = Slab::new_with_config::<test_util::TinyConfig>();
+
+        for i in 0..4096 {
+            println!("{}", i);
+            let k = slab.insert(i).expect("insert");
+            assert_eq!(slab.get(k).expect("get"), i);
+        }
+    }
+}