fn drop(&mut self) {

        if let Some(block_ptr) = self.head_block.take() {

            // Safety: we own all blocks in the list.

            unsafe { drop(Box::from_raw(block_ptr.as_ptr())) };

        }

    }

    pub fn new() -> Self {

        Self {

            blocks: Mutex::new(BlockList {

                head_block: None,

                free_chunks: Vec::new(),

            }),

            alloc_state: ThreadLocal::new(),

        }

    }

    pub fn allocate_object(&self) -> Result<NonNull<T>, AllocError> {

        let state = self.alloc_state.get_or(ThreadLocalAllocState::new);

        if let Some(entry) = state.free.try_pop() {

            return Ok(entry.cast());

        }

        if self.refill_local_free_from_chunks(state)

            && let Some(entry) = state.free.try_pop()

            return Ok(entry.cast());

        }

        let block_ptr = state.current_block.get();

        let offset = state.bump_offset.get();

        if !block_ptr.is_null() && offset < N {

            state.bump_offset.set(offset + 1);

                let data_ptr = (*block_ptr).data.get() as *mut Entry<T>;

                let entry_ptr = data_ptr.add(offset);

                Ok(NonNull::new_unchecked(

                    std::ptr::addr_of_mut!((*entry_ptr).data) as *mut T

                ))

        }

        self.allocate_new_block(state)

    }

    fn refill_local_free_from_chunks(&self, state: &ThreadLocalAllocState<T, N>) -> bool {

        let mut guard = self.blocks.lock().expect("Lock poisoned");

        let Some(current) = guard.free_chunks.pop() else {

            return false;

        drop(guard);

        debug_assert!(

            state.free.is_empty(),

        unsafe {

            state.free.set_head(current.as_ptr());

        }

        true

    }

    fn allocate_new_block(&self, state: &ThreadLocalAllocState<T, N>) -> Result<NonNull<T>, AllocError> {

        let mut guard = self.blocks.lock().expect("Lock poisoned");

        let mut new_block = Block::new();

        new_block.next = guard.head_block;

        let new_block_ptr = unsafe { NonNull::new_unchecked(Box::into_raw(Box::new(new_block))) };

        guard.head_block = Some(new_block_ptr);

        drop(guard);

        state.current_block.set(new_block_ptr.as_ptr());

        state.bump_offset.set(1);

            let data_ptr = (*new_block_ptr.as_ptr()).data.get() as *mut Entry<T>;

            Ok(NonNull::new_unchecked(

                std::ptr::addr_of_mut!((*data_ptr).data) as *mut T

            ))

    }

    pub fn deallocate_object(&self, ptr: NonNull<T>) {

        let state = self.alloc_state.get_or(ThreadLocalAllocState::new);

        state.free.push(ptr.cast());

    }

    pub fn remove_free_blocks(&mut self) -> (usize, usize)

    where

        T: BlockAllocatorSafe,

        let nonexisting_value = NONEXISTING_VALUE as *mut Entry<T>;

        let mut freelist_ptrs: std::collections::HashSet<*mut Entry<T>> = std::collections::HashSet::new();

        let mark_freelist =

                let mut previous: Option<NonNull<Entry<T>>> = None;

                let mut count: usize = 0;

                for current in list.iter() {

                    ptrs.insert(current.as_ptr());

                    if let Some(previous) = previous {

                        *(*previous.as_ptr()).next = nonexisting_value;

                    }

                    previous = Some(current);

                    count += 1;

                if let Some(previous) = previous {

                    *(*previous.as_ptr()).next = nonexisting_value;

                }

                count

            };

        let mut free_size = 0;

        for state in self.alloc_state.iter_mut() {

            free_size += mark_freelist(

                &state.free,

                #[cfg(debug_assertions)]

                &mut freelist_ptrs,

            );

            state.free.clear();

            state.current_block.set(std::ptr::null_mut());

            state.bump_offset.set(N);

        }

        let mut guard = self.blocks.lock().expect("Lock poisoned");

        for &chunk_head in &guard.free_chunks {

            let mut current = Some(chunk_head);

            while let Some(entry) = current {

                #[cfg(debug_assertions)]

                freelist_ptrs.insert(entry.as_ptr());

                let next = unsafe { Entry::get_next(entry.as_ptr()) };

                unsafe {

                    *(*entry.as_ptr()).next = nonexisting_value;

                }

                free_size += 1;

                current = NonNull::new(next);

            }

        guard.free_chunks.clear();

            for block_ptr in Self::iter_blocks(&guard) {

                let data = unsafe { &*(*block_ptr.as_ptr()).data.get() };

                for entry in data {

                    let entry_ptr = entry as *const Entry<T> as *mut Entry<T>;

                    if !freelist_ptrs.contains(&entry_ptr) {

                            debug_assert!(

                                !std::ptr::eq(*entry.next, nonexisting_value),

                    }

        let removed = if guard.head_block.is_some() {

            let mut prev_next_field: *mut Option<NonNull<Block<T, N>>> = &mut guard.head_block;

            let mut removed_blocks = 0;

            while let Some(current_ptr) = unsafe { *prev_next_field } {

                let all_free = unsafe {

                    let data = &*(*current_ptr.as_ptr()).data.get();

                    data.iter().all(|entry| std::ptr::eq(*entry.next, nonexisting_value))

                if all_free {

                } else {

                    // Keep this block; advance to next.

                    prev_next_field = unsafe { &mut (*current_ptr.as_ptr()).next };

                }

            removed_blocks

            0

        let mut rebuilt_chunk_heads: Vec<NonNull<Entry<T>>> = Vec::new();

        let mut chunk_head: Option<NonNull<Entry<T>>> = None;

        let mut chunk_tail: Option<NonNull<Entry<T>>> = None;

        let mut chunk_len = 0usize;

        for block_ptr in Self::iter_blocks(&guard) {

            let data_ptr = unsafe { (*block_ptr.as_ptr()).data.get() as *mut Entry<T> };

            for i in 0..N {

                    let entry_ptr = data_ptr.add(i);

                    if std::ptr::eq(*(*entry_ptr).next, nonexisting_value) {

                        *(*entry_ptr).next = std::ptr::null_mut();

                        let entry_ptr = NonNull::new_unchecked(entry_ptr);

                        if let Some(tail) = chunk_tail {

                            *(*tail.as_ptr()).next = entry_ptr.as_ptr();

                            chunk_tail = Some(entry_ptr);

                            chunk_len += 1;

                        } else {

                            chunk_head = Some(entry_ptr);

                            chunk_tail = Some(entry_ptr);

                            chunk_len = 1;

                        }

                        if chunk_len == FREE_LIST_CHUNK_SIZE {

                            rebuilt_chunk_heads.push(chunk_head.expect("chunk head set"));

                            chunk_head = None;

                            chunk_tail = None;

                            chunk_len = 0;

                        }

                    }

        if let Some(head) = chunk_head {

            rebuilt_chunk_heads.push(head);

        }

        guard.free_chunks.extend(rebuilt_chunk_heads);

        drop(guard);

        (removed, free_size)

    }

    fn iter_blocks<'a>(guard: &'a MutexGuard<'_, BlockList<T, N>>) -> BlockIter<'a, T, N> {

        BlockIter {

            current: guard.head_block,

            _marker: PhantomData,

        }

    }

    fn new() -> Self {

        Self {

            current_block: Cell::new(std::ptr::null_mut()),

            bump_offset: Cell::new(N),

            free: FreeList::new(),

        }

    }

    pub fn new() -> Self {

        Self {

            block_allocator: BlockAllocator::new(),

        }

    }

    pub fn remove_free_blocks(&mut self) -> usize

    where

        T: BlockAllocatorSafe,

        self.block_allocator.remove_free_blocks().0

    }

    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {

        debug_assert_eq!(

            Layout::new::<T>(),

        let ptr = self.block_allocator.allocate_object()?;

        let byte_ptr = ptr.cast::<u8>();

        let slice_ptr = NonNull::slice_from_raw_parts(byte_ptr, std::mem::size_of::<T>());

        Ok(slice_ptr)

    }

    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {

        debug_assert_eq!(

            Layout::new::<T>(),

        self.block_allocator.deallocate_object(ptr.cast::<T>());

    }

    unsafe fn get_next(ptr: *mut Self) -> *mut Self {

        unsafe { *(*ptr).next }

    }

    unsafe fn set_next(ptr: *mut Self, next: *mut Self) {

        unsafe {

            *(*ptr).next = next;

        }

    }

    fn next(&mut self) -> Option<Self::Item> {

        let current_ptr = self.current?;

        self.current = unsafe { (*current_ptr.as_ptr()).next };

        Some(current_ptr)

    }

    fn new() -> Self {

            data: UnsafeCell::new(array::from_fn(|_i| Entry {

                next: ManuallyDrop::new(std::ptr::null_mut()),

            })),

            next: None,

    }

    fn drop(&mut self) {

        let mut current = self.next.take();

        while let Some(block_ptr) = current {

            let mut block = unsafe { Box::from_raw(block_ptr.as_ptr()) };

            current = block.next.take();

        }

    }

    fn test_block_allocator() {

        random_test(100, |rng| {

            let mut allocator: BlockAllocator<usize, 32> = BlockAllocator::new();

            let mut allocated: Vec<(NonNull<usize>, usize)> = Vec::new();

            for _ in 0..1000 {

                let ptr = allocator.allocate_object().unwrap();

                let value: usize = rng.random_range(0..=usize::MAX - 1);

                unsafe {

                    ptr.as_ptr().write(value);

                }

                allocated.push((ptr, value));

            }

            let mut remaining = Vec::new();

            for (ptr, value) in allocated {

                if rng.random_bool(0.5) {

                    allocator.deallocate_object(ptr);

                } else {

                    remaining.push((ptr, value));

                }

            for (ptr, expected) in &remaining {

                    assert_eq!(*ptr.as_ref(), *expected);

            let (removed, free_size) = allocator.remove_free_blocks();

            println!("{removed} removed, {free_size} free");

            for _ in 0..500 {

                let ptr = allocator.allocate_object().unwrap();

                let value: usize = rng.random_range(0..=usize::MAX - 1);

                unsafe {

                    ptr.as_ptr().write(value);

                }

                remaining.push((ptr, value));

            }

            for (ptr, expected) in &remaining {

                    assert_eq!(*ptr.as_ref(), *expected);

        })

    }

    fn test_block_allocator_parallel_freelist() {

        let block_allocator = Arc::new(BlockAllocator::<u32, 32>::new());

        let threads: Vec<_> = (0..=2)

            .map(|_| {

                let block_allocator = block_allocator.clone();

                std::thread::spawn(move || {

                    let mut ptrs = Vec::new();

                    for _ in 0..100 {

                        let ptr = block_allocator.allocate_object().unwrap();

                        unsafe {

                            ptr.as_ptr().write(42);

                        }

                        ptrs.push(ptr);

                    }

                    for ptr in ptrs {

                            assert_eq!(*ptr.as_ref(), 42);

                        block_allocator.deallocate_object(ptr);

                })

            })

            .collect();

        for thread in threads {

            thread.join().unwrap();

        }

    }