overvec 0.0.1

#![no_std]
#![warn(missing_docs)]

//! Provides an `OverVec<T, MIN>` type, which is an over-aligned vec.

use core::{
  mem::{align_of, size_of},
  ptr::NonNull,
  slice,
};

extern crate alloc;
use alloc::alloc::{alloc, dealloc, handle_alloc_error, Layout};

const fn max_usize(x: usize, y: usize) -> usize {
  x ^ ((x ^ y) & ((x < y) as usize).wrapping_neg())
}

/// An over-aligned vector type.
///
/// * `T`: The element type.
/// * `MIN`: The minimum alignment. If the alignment of `T` is greater than this
///   then that will be used.
#[derive(Debug)]
#[repr(C)]
pub struct OverVec<T, const MIN: usize> {
  nn: NonNull<T>,
  element_count: usize,
  byte_capacity: usize,
}

impl<T, const MIN: usize> Drop for OverVec<T, MIN> {
  fn drop(&mut self) {
    if core::mem::needs_drop::<T>() {
      let mut p = self.nn.as_ptr();
      for _ in 0..self.element_count {
        unsafe {
          core::ptr::drop_in_place(p);
          p = p.add(1);
        }
      }
    }
    let layout = Layout::from_size_align(self.byte_capacity, Self::ALIGN).expect("layout error!");
    unsafe { dealloc(self.nn.as_ptr().cast::<u8>(), layout) }
  }
}
impl<T, const MIN: usize> core::ops::Deref for OverVec<T, MIN> {
  type Target = [T];
  fn deref(&self) -> &[T] {
    unsafe { slice::from_raw_parts(self.nn.as_ptr(), self.element_count) }
  }
}
impl<T, const MIN: usize> core::ops::DerefMut for OverVec<T, MIN> {
  fn deref_mut(&mut self) -> &mut [T] {
    unsafe { slice::from_raw_parts_mut(self.nn.as_ptr(), self.element_count) }
  }
}

impl<T, const MIN: usize> OverVec<T, MIN> {
  /// This is the actual alignment that a particular `OverVec` instantiation
  /// will use.
  pub const ALIGN: usize = max_usize(align_of::<T>(), MIN);

  /// Constructs a new `OverVec` with no capacity.
  ///
  /// * Does not allocate.
  pub const fn new() -> Self {
    OverVec { nn: NonNull::dangling(), element_count: 0, byte_capacity: 0 }
  }

  /// Constructs a new, empty `OverVec` with at least the specified capacity.
  ///
  /// Because of minimum alignment, the obtained capacity might be greater than
  /// requested.
  /// ```rust
  /// # use overvec::*;
  /// let ov: OverVec<i32, 8> = OverVec::with_capacity(12);
  /// assert_eq!(ov.capacity(), 12);
  ///
  /// let ov2: OverVec<i32, 8> = OverVec::with_capacity(13);
  /// assert_eq!(ov2.capacity(), 14);
  /// ```
  pub fn with_capacity(cap: usize) -> Self {
    assert!(MIN.is_power_of_two(), "The `MIN` constant must be a power of two.");
    if cap == 0 {
      return Self::new();
    }
    if size_of::<T>() == 0 {
      OverVec::new()
    } else {
      let align = Self::ALIGN;
      debug_assert!(align > 0);
      let mut size = cap.checked_mul(size_of::<T>()).unwrap_or_else(|| {
        panic!(
          "Requested capacity {cap} times {size} per element exceeds the address space.",
          cap = cap,
          size = size_of::<T>()
        )
      });
      debug_assert!(size > 0);
      let size_slop = size % align;
      size = size.saturating_add(size_slop);
      debug_assert!(
        size % align == 0,
        "size not multiple of align! size:{size}, align:{align}",
        size = size,
        align = align
      );
      let layout = Layout::from_size_align(size, align).expect("layout error!");
      let nn = NonNull::new(unsafe { alloc(layout) }.cast::<T>())
        .unwrap_or_else(|| handle_alloc_error(layout));
      OverVec { nn, element_count: 0, byte_capacity: size }
    }
  }

  /// The number of elements in the vec.
  pub const fn len(&self) -> usize {
    self.element_count
  }

  /// Returns the number of elements the vector can hold without reallocating.
  pub const fn capacity(&self) -> usize {
    if size_of::<T>() == 0 {
      isize::MAX as usize
    } else {
      self.byte_capacity / size_of::<T>()
    }
  }

  /// Push an element onto the end of the `OverVec`.
  ///
  /// ```rust
  /// # use overvec::*;
  /// let mut ov: OverVec<i32, 8> = OverVec::with_capacity(12);
  /// ov.push(5);
  /// assert_eq!(&[5_i32][..], &ov[..]);
  /// ```
  pub fn push(&mut self, t: T) {
    let cap = self.capacity();
    let len = self.len();
    if len >= cap {
      todo!("handle how to reallocate the vector to make more space");
    } else {
      unsafe { self.nn.as_ptr().add(len).write(t) };
      self.element_count += 1;
    }
  }
}