node topological sorting

Change-Id: I6a6a6964255d818be1bf9a8f4ec9e317befa19c5

1 files changed, 0 insertions, 336 deletions

diff --git a/crates/core/src/hive/mod.rs b/crates/core/src/hive/mod.rs
deleted file mode 100644
index 3f83099..0000000
--- a/crates/core/src/hive/mod.rs
+++ /dev/null
@@ -1,336 +0,0 @@
-//! An implementation of a bucket array type following the approach used in
-//! the [C++26 `hive`](https://eel.is/c++draft/hive) structure.
-
-//TODO: traits to implement for `Hive`:
-//      - Ord - Eq - Clone - Debug - Deref<Target=[T]> (?) - AsRef - Borrow
-//      - AsMut - Extend - From [array, slice, vec, etc...] - FromIterator
-//      - Hash - IntoIterator - Index - IndexMut
-//      - PartialEq [array, slice, vec, etc...] - PartialOrd - Write
-//TODO: define zero-sized-type handling in `Hive`
-//TODO: define situations where we panic
-//TODO: consider factoring out code that does not care about the type
-//      parameters into a separate struct to reduce the amount of code
-//      generated, akin to what the standard library does with `RawVec` and
-//      `RawVecInner`
-//TODO: try_reserve_exact, reserve_exact
-
-use alloc::alloc::{Allocator, Global, Layout};
-use core::{cmp, mem, ptr::NonNull};
-
-#[cfg(feature = "core-fmt")]
-use core::fmt;
-
-#[cfg(feature = "core-error")]
-use core::error;
-
-pub mod group;
-pub mod skipfield;
-
-/// An implementation of a bucket array using a skipfield.
-#[cfg_attr(feature = "core-fmt", derive(Debug))]
-pub struct Hive<T, Sk = u16, A = Global>
-where
-    Sk: skipfield::SkipfieldType,
-    A: Allocator,
-{
-    /// Head of the doubly linked list of groups with erased elements
-    head_with_erasures: Option<NonNull<group::Group<T, Sk>>>,
-
-    /// Head of the singly linked list of unused groups
-    unused_head: Option<NonNull<group::Group<T, Sk>>>,
-
-    /// Number of occupied element spaces
-    size: usize,
-
-    /// Total number of element spaces available
-    capacity: usize,
-
-    /// Minimum capacity of new [`Group`]s
-    min_block_capacity: Sk,
-
-    /// Maximum capacity of new [`Group`]s
-    max_block_capacity: Sk,
-
-    /// The allocator used by this [`Hive`].
-    alloc: A,
-}
-
-impl<T, Sk> Hive<T, Sk, Global>
-where
-    Sk: skipfield::SkipfieldType,
-{
-    /// Constructs a new, empty `Hive<T, Sk>`.
-    ///
-    /// No allocations are performed until elements are inserted.
-    pub fn new() -> Self {
-        Self::new_in(Global)
-    }
-
-    /// Constructs a new, empty `Hive<T, Sk>` with at least the specified
-    /// capacity.
-    ///
-    /// The hive will be able to hold at least `capacity` elements without
-    /// reallocating. This method is allowed to allocate for more elements
-    /// than `capacity`. If `capacity` is zero, the hive will not
-    /// allocate.
-    ///
-    /// # Panics
-    ///
-    /// Panics if the allocator reports allocation failure or if the capacity
-    /// exceeds `isize::MAX` bytes.
-    #[cfg(feature = "core-fmt")]
-    pub fn with_capacity(capacity: usize) -> Self {
-        Self::with_capacity_in(capacity, Global)
-    }
-
-    /// Constructs a new, empty `Hive<T, Sk>` with at least the specified
-    /// capacity.
-    ///
-    /// The hive will be able to hold at least `capacity` elements without
-    /// reallocating. This method is allowed to allocate for more elements
-    /// than `capacity`. If `capacity` is zero, the hive will not
-    /// allocate.
-    ///
-    /// # Errors
-    ///
-    /// Returns an error if the allocator reports allocation failure or if the
-    /// capacity exceeds `isize::MAX` bytes.
-    pub fn try_with_capacity(capacity: usize) -> Result<Self, Error> {
-        Self::try_with_capacity_in(capacity, Global)
-    }
-}
-
-impl<T, Sk, A> Hive<T, Sk, A>
-where
-    Sk: skipfield::SkipfieldType,
-    A: Allocator,
-{
-    /// Function returning the default bounds for individual [`Group`]
-    /// capacity
-    ///
-    /// These are borrowed from [here], as those bounds were determined
-    /// according to benchmarking results. However, they have not been
-    /// replicated against this implementation of the concept.
-    ///
-    /// [here]: https://github.com/mattreecebentley/plf_hive/blob/main/plf_hive.h#L293-L307
-    fn default_group_capacity_bounds() -> (Sk, Sk)
-    where
-        Sk: skipfield::SkipfieldType,
-    {
-        let max_capacity = cmp::min(
-            cmp::min(Sk::MAXIMUM, Sk::from_usize(8192)),
-            Sk::from_isize(isize::MAX),
-        );
-        let adaptive_size = (mem::size_of::<Self>()
-            + mem::size_of::<group::Group<T, Sk>>() * 2)
-            / group::Group::<T, Sk>::ELEMENT_ALLOCATION_SIZE;
-        let min_capacity = cmp::max(
-            Sk::from_usize(8usize),
-            cmp::min(Sk::from_usize(adaptive_size), max_capacity),
-        );
-
-        //NOTE: anything that calls `panic` indirectly or does anything that
-        // touches standard output      requires core::fmt :skull:
-        #[cfg(feature = "core-fmt")]
-        debug_assert!(
-            max_capacity >= min_capacity,
-            "maximum capacity bound is greater than or equal to the minimum capacity bound"
-        );
-
-        (min_capacity, max_capacity)
-    }
-
-    /// Constructs a new, empty `Hive<T, Sk, A>`.
-    ///
-    /// No allocations are performed until elements are inserted.
-    pub fn new_in(alloc: A) -> Self {
-        let (min_block_capacity, max_block_capacity) =
-            Self::default_group_capacity_bounds();
-        Self {
-            head_with_erasures: None,
-            unused_head: None,
-            size: 0,
-            capacity: 0,
-            min_block_capacity,
-            max_block_capacity,
-            alloc,
-        }
-    }
-
-    /// Constructs a new, empty `Hive<T, Sk, A>` with at least the specified
-    /// capacity.
-    ///
-    /// The hive will be able to hold at least `capacity` elements without
-    /// reallocating. This method is allowed to allocate for more elements
-    /// than `capacity`. If `capacity` is zero, the hive will not
-    /// allocate.
-    ///
-    /// # Panics
-    ///
-    /// Panics if the allocator reports allocation failure or if the capacity
-    /// exceeds `isize::MAX` bytes.
-    #[cfg(feature = "core-fmt")]
-    pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
-        //PANIC: this is acceptable as the panic is mentioned above and it is
-        //       used to assert an invariant.
-        #[allow(clippy::expect_used)]
-        Self::try_with_capacity_in(capacity, alloc)
-            .expect("allocation should not fail")
-    }
-
-    /// Constructs a new, empty `Hive<T, Sk, A>` with at least the specified
-    /// capacity.
-    ///
-    /// The hive will be able to hold at least `capacity` elements without
-    /// reallocating. This method is allowed to allocate for more elements
-    /// than `capacity`. If `capacity` is zero, the hive will not
-    /// allocate.
-    ///
-    /// # Errors
-    ///
-    /// Returns an error if the allocator reports allocation failure or if the
-    /// capacity exceeds `isize::MAX` bytes.
-    pub fn try_with_capacity_in(
-        capacity: usize,
-        alloc: A,
-    ) -> Result<Self, Error> {
-        let mut hive = Self::new_in(alloc);
-        hive.try_reserve(capacity)?;
-        Ok(hive)
-    }
-
-    /// Reserves capacity for at least `additional` more elements to be
-    /// inserted in the given `Hive<T, Sk, A>`.
-    ///
-    /// The collection may reserve more space to avoid future allocations.
-    /// After calling `reserve`, the capacity will be greater than or equal to
-    /// `self.len() + additional`. Does nothing if the capacity is already
-    /// sufficient.
-    ///
-    /// # Panics
-    ///
-    /// Panics if the allocator reports allocation failure or if the new
-    /// capacity exceeds `isize::MAX` bytes.
-    #[cfg(feature = "core-fmt")]
-    pub fn reserve(&mut self, additional: usize) {
-        todo!()
-    }
-
-    /// Reserves capacity for at least `additional` more elements to be
-    /// inserted in the given `Hive<T, Sk, A>`.
-    ///
-    /// The collection may reserve more space to avoid future allocations.
-    /// After calling `reserve`, the capacity will be greater than or equal to
-    /// `self.len() + additional`. Does nothing if the capacity is already
-    /// sufficient.
-    ///
-    /// # Errors
-    ///
-    /// Returns an error if the allocator reports allocation failure or if the
-    /// new capacity exceeds `isize::MAX` bytes.
-    pub fn try_reserve(&mut self, additional: usize) -> Result<(), Error> {
-        todo!()
-    }
-
-    /// Checks if the container needs to grow to accommodate `additional` more
-    /// elements
-    #[inline]
-    fn needs_to_grow(&self, additional: usize) -> bool {
-        additional > self.capacity.wrapping_sub(self.size)
-    }
-
-    /// Grow the `Hive<T, Sk, A>` by the given amount, leaving room for more
-    /// elements than necessary.
-    ///
-    /// # Errors
-    ///
-    /// Returns an error if the allocator reports allocation failure or if the
-    /// new capacity exceeds `isize::MAX` bytes.
-    fn grow_amortized(&mut self, additional: usize) -> Result<(), Error> {
-        #[cfg(feature = "core-fmt")]
-        debug_assert!(
-            additional > 0,
-            "at least space enough for one element will be added"
-        );
-
-        if mem::size_of::<T>() == 0 {
-            //NOTE: akin to raw_vec in alloc, if we get here with a zero
-            //      sized type, since the capacity is definitionally full when
-            //      it is holding one, the hive would necessarily
-            //      be overfull
-            return Err(Error::CapacityOverflow);
-        }
-
-        todo!()
-    }
-}
-
-impl<T, Sk> Default for Hive<T, Sk, Global>
-where
-    Sk: skipfield::SkipfieldType,
-{
-    fn default() -> Self {
-        Self::new()
-    }
-}
-
-/// Representation of an error that occurred within [`Hive`].
-#[non_exhaustive]
-#[derive(Eq, PartialEq)]
-#[cfg_attr(feature = "core-fmt", derive(Debug))]
-pub enum Error {
-    /// Allocation size exceeded `isize::MAX`.
-    CapacityOverflow,
-
-    /// Unspecified allocation error.
-    ///
-    /// The layout used during allocation is provided for troubleshooting
-    /// where that is possible. Ideally, future revisions of the
-    /// `allocator_api` feature will provide more information in `AllocError`
-    /// but for now this is all we can do.
-    #[non_exhaustive]
-    AllocError {
-        /// Layout of the failed allocation.
-        layout: Layout,
-    },
-}
-
-#[cfg(feature = "core-fmt")]
-impl fmt::Display for Error {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.write_str("memory allocation failed")?;
-        let reason = match self {
-            Error::CapacityOverflow => {
-                " because the computed capacity exceeded the hive's maximum"
-            }
-            Error::AllocError { .. } => {
-                " because the memory allocator returned an error"
-            }
-        };
-        f.write_str(reason)
-    }
-}
-
-#[cfg(feature = "core-error")]
-impl error::Error for Error {}
-
-/// Guard function ensuring that we don't overflow `isize::MAX`.
-///
-/// The Rust standard library has a similar function, found [here]. However,
-/// that implementation of it ignores the check on platforms with a `usize`
-/// wider than 64 bits. This is probably fine, as no platform Rust supports
-/// has a virtual address space larger than 8 EiB, but out of caution, we
-/// always make the check here.
-///
-/// [here]: https://github.com/rust-lang/rust/blob/a27f3e3fd1e4d16160f8885b6b06665b5319f56c/library/alloc/src/raw_vec/mod.rs#L802-L817
-#[inline]
-fn alloc_guard(alloc_size: usize) -> Result<(), Error> {
-    //TODO: consider predicating this check over `usize::BITS < 64` as the
-    //      rust std does. only do this if it has a measurable performance
-    //      impact
-    if alloc_size > isize::MAX as usize {
-        Err(Error::CapacityOverflow)
-    } else {
-        Ok(())
-    }
-}