/// A single region of the allocator. See the comment on the `crate::allocators::buddy` module for
/// more information.
///
/// This type is valid when zero-initialized.
#[derive(Debug)]
pub struct Tree<'buddy, const PAGE_SIZE: usize, const PAGE_SIZE_BITS: usize> {
    /// The base address of the tree.
    pub base_ptr: *const [u8; PAGE_SIZE],

    /// The log2 of the number of pages in the region represented by the tree.
    pub size_class: usize,

    /// The offset in the bitset to the bits responsible for this tree's pages.
    pub bitset_offset: usize,

    // /// The bitset used to track whether subregion are allocated or not in this tree.
    // pub bitset: &'buddy mut BitVec,
    phantom: core::marker::PhantomData<&'buddy mut [u8; PAGE_SIZE]>,
}

/*
use crate::{
    bitvec::BitVec,
    stripe::{FreeListNode, Stripe},
    MAX_ORDER, PAGE_SIZE_BITS,
};
use contracts::requires;

/// A single region of the allocator. See the comment on the `crate::allocators::buddy` module for
/// more information.
pub struct Tree<'buddy> {
    /// The base address of the tree.
    pub base: *const (),

    /// The log2 of the number of pages in the region represented by the tree.
    pub log2_page_count: usize,

    /// The array of sentinel nodes of the free-list for this node. As an invariant of the type,
    /// there are no live references to any node in any list in this array, and there are
    /// MAX_ORDER + 1 nodes.
    pub free_lists: NonNull<FreeListNode>,

    /// The bitset used to track whether subregion are allocated or not in this tree.
    pub bitset: &'buddy mut BitVec,
}

impl<'buddy> Tree<'buddy> {
    /// Tries to allocate a subregion with the given order, possibly splitting a larger subregion
    /// in order to so so.
    #[requires(order <= MAX_ORDER)]
    pub fn alloc(&mut self, order: usize) -> Option<NonNull<FreeListNode>> {
        if let Some(ptr) = self.stripe(order).pop() {
            Some(ptr)
        } else if order == MAX_ORDER {
            None
        } else {
            // Get a larger region.
            let ptr = self.alloc(order + 1)?;

            // Get a pointer to the higher half.
            //
            // SAFETY: This has to be in-bounds, it's part of the same allocation!
            let higher_half = unsafe { ptr.byte_add(1 << (PAGE_SIZE_BITS + order)) };

            // Put the higher half in the current buddy's stripe.
            //
            // SAFETY: The higher half is from this region, not in the higher stripe, and of the
            // right size.
            unsafe {
                self.stripe(order).push(higher_half);
            }

            // Return the pointer.
            Some(ptr)
        }
    }

    /// Returns the stripe with the given order.
    #[requires(order <= MAX_ORDER)]
    fn stripe<'stripe>(&'stripe mut self, order: usize) -> Stripe<'stripe> {
        // TODO: There should be some smart bitwise-math version of this...
        let mut bitset_offset = 0;
        for i in 0..order {
            bitset_offset += (1 << self.log2_page_count) >> i;
        }

        Stripe {
            base: self.base,
            order,
            // SAFETY: order is constrained to be in-bounds.
            free_list: unsafe { self.free_lists.add(order) },
            bitset: self.bitset,
            bitset_offset,
        }
    }
}

/// Evil bitwise version of the reasonable loop to compute the `bitset_offset` of a stripe.
#[requires(log2_page_count < usize::BITS as usize)]
#[requires(order < usize::BITS as usize)]
fn compute_bitset_offset(log2_page_count: usize, order: usize) -> usize {
    let ones = |i: usize| !(usize::MAX << i);

    if order > log2_page_count + 1 {
        ones(log2_page_count + 1)
    } else {
        ones(order).wrapping_shl((log2_page_count + 1 - order) as u32)
    }
}

#[test]
fn compute_bitset_offset_test() {
    fn compute_bitset_offset_loop(log2_page_count: usize, order: usize) -> usize {
        let mut bitset_offset = 0;
        for i in 0..order {
            bitset_offset += (1 << log2_page_count) >> i;
        }
        bitset_offset
    }

    for log2_page_count in 0..64 {
        for order in 0..64 {
            assert_eq!(
                compute_bitset_offset(log2_page_count, order),
                compute_bitset_offset_loop(log2_page_count, order),
            );
        }
    }
}
*/