node topological sorting

Change-Id: I6a6a6964255d818be1bf9a8f4ec9e317befa19c5

3 files changed, 0 insertions, 525 deletions

diff --git a/crates/core/src/hive/group.rs b/crates/core/src/hive/group.rs
deleted file mode 100644
index 9217897..0000000
--- a/crates/core/src/hive/group.rs
+++ /dev/null
@@ -1,122 +0,0 @@
-//! An implementation of the individual memory blocks that make up a hive.
-
-use core::{
-    mem::{self, ManuallyDrop},
-    ptr::NonNull,
-};
-
-use crate::hive::skipfield;
-
-/// A type that may be either part of the free list or an element.
-pub union Slot<T, Sk>
-where
-    Sk: skipfield::SkipfieldType,
-{
-    /// An element of the [`Group`].
-    element: ManuallyDrop<T>,
-
-    /// A free list index.
-    free_list: FreeList<Sk>,
-}
-
-/// The contents of a free list index.
-///
-/// This uses the `packed` C representation to avoid any excess space. This is
-/// not a problem in the general case as our type will only ever be `u16` or
-/// `u8` unless an end-user overrides the skipfield type with a custom
-/// implementation.
-#[repr(C, packed)]
-#[derive(Copy, Clone)]
-#[cfg_attr(feature = "core-fmt", derive(Debug))]
-pub struct FreeList<Sk>
-where
-    Sk: skipfield::SkipfieldType,
-{
-    /// Index of the previous element in the free list.
-    pub previous: Sk,
-
-    /// Index of the next element in the free list.
-    pub next: Sk,
-}
-
-/// A doubly-linked `Group` of `T` with a skipfield type of `Sk`.
-#[cfg_attr(feature = "core-fmt", derive(Debug))]
-pub struct Group<T, Sk>
-where
-    Sk: skipfield::SkipfieldType,
-{
-    /// Pointer to the start of the skipfield.
-    pub skipfield: Option<NonNull<Sk>>,
-
-    /// Pointer to the next [`Group`].
-    pub next: Option<NonNull<Group<T, Sk>>>,
-
-    /// Pointer to element storage.
-    pub elements: Option<NonNull<Slot<T, Sk>>>,
-
-    /// Pointer to the previous [`Group`].
-    pub previous: Option<NonNull<Group<T, Sk>>>,
-
-    /// Index of the last erased element in the group.
-    ///
-    /// The last erased element contains the index of the next, and so on. If
-    /// this is equal to the maximum value of the underlying integer type,
-    /// then the free list is considered to be empty.
-    pub free_list_head: Sk,
-
-    /// Total number of elements this [`Group`] can hold.
-    pub capacity: Sk,
-
-    /// Number of elements stored in this [`Group`].
-    pub size: Sk,
-
-    /// Pointer to the next [`Group`] with erased elements.
-    pub next_with_erasures: Option<NonNull<Group<T, Sk>>>,
-
-    /// Pointer to the previous [`Group`] with erased elements.
-    pub previous_with_erasures: Option<NonNull<Group<T, Sk>>>,
-
-    /// Number assigned to this group.
-    pub number: usize,
-}
-
-impl<T, Sk> Group<T, Sk>
-where
-    Sk: skipfield::SkipfieldType,
-{
-    /// Size of each individual element within a [`Group`]
-    pub const ELEMENT_ALLOCATION_SIZE: usize =
-        compute_element_allocation_size::<T, Sk>();
-}
-
-/// Helper function which computes the allocation size of elements
-const fn compute_element_allocation_size<T, Sk>() -> usize {
-    let t_align = mem::align_of::<T>();
-    let t_size = mem::size_of::<T>();
-    let sk2_size = mem::size_of::<Sk>() * 2;
-    if t_align > t_size {
-        if sk2_size > t_align {
-            sk2_size
-        } else {
-            t_align
-        }
-    } else if sk2_size > t_size {
-        sk2_size
-    } else {
-        t_size
-    }
-}
-
-#[cfg(all(test, feature = "core-error"))]
-mod test {
-    use super::*;
-
-    #[test]
-    fn validate_element_allocation_size() {
-        assert_eq!(
-            Group::<u32, u8>::ELEMENT_ALLOCATION_SIZE,
-            4,
-            "element allocation size with T = u32, Sk = u8 is 4"
-        );
-    }
-}
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(())
-    }
-}
diff --git a/crates/core/src/hive/skipfield.rs b/crates/core/src/hive/skipfield.rs
deleted file mode 100644
index 16a3dcb..0000000
--- a/crates/core/src/hive/skipfield.rs
+++ /dev/null
@@ -1,67 +0,0 @@
-//! An implementation of a trait describing valid skipfield integer types.
-//!
-//! Only `u16`s and `u8`s are supported by default. However, other integral
-//! types may be used by implementing this trait on them; the trait is not
-//! sealed.
-
-use core::{
-    cmp,
-    ops::{Add, AddAssign, Sub, SubAssign},
-};
-
-/// Trait describing integral types in a generic way suitable for use as the
-/// element type of a skipfield.
-pub trait SkipfieldType:
-    Add + AddAssign + Sub + SubAssign + Ord + PartialOrd + Copy + Sized
-{
-    /// The maximum attainable value of this type.
-    const MAXIMUM: Self;
-
-    /// The zero element of this type.
-    const ZERO: Self;
-
-    /// The one element of this type.
-    const ONE: Self;
-
-    /// Conversion method from `usize` using `as` or an equivalent
-    ///
-    /// Caps the value of the input by the maximum of `Self`.
-    fn from_usize(u: usize) -> Self;
-
-    /// Conversion method from `isize` using `as` or an equivalent
-    ///
-    /// Caps the value of the input by the maximum of `Self`.
-    fn from_isize(i: isize) -> Self;
-}
-
-impl SkipfieldType for u16 {
-    const MAXIMUM: Self = u16::MAX;
-    const ZERO: Self = 0;
-    const ONE: Self = 1;
-
-    #[inline(always)]
-    fn from_usize(u: usize) -> Self {
-        cmp::min(u, Self::MAXIMUM as usize) as u16
-    }
-
-    #[inline(always)]
-    fn from_isize(i: isize) -> Self {
-        cmp::min(i, Self::MAXIMUM as isize) as u16
-    }
-}
-
-impl SkipfieldType for u8 {
-    const MAXIMUM: Self = u8::MAX;
-    const ZERO: Self = 0;
-    const ONE: Self = 1;
-
-    #[inline(always)]
-    fn from_usize(u: usize) -> Self {
-        cmp::min(u, Self::MAXIMUM as usize) as u8
-    }
-
-    #[inline(always)]
-    fn from_isize(i: isize) -> Self {
-        cmp::min(i, Self::MAXIMUM as isize) as u8
-    }
-}