ztmux 0.1.0

use core::ptr::null_mut;
use std::ptr::NonNull;

pub trait ListEntry<T, Discriminant = ()> {
    unsafe fn field(this: *mut Self) -> *mut list_entry<T>;
}

#[repr(C)]
#[derive(Debug, Copy, Clone)]
pub struct list_head<T> {
    pub lh_first: *mut T,
}
pub const fn list_head_initializer<T>() -> list_head<T> {
    list_head {
        lh_first: null_mut(),
    }
}

#[repr(C)]
#[derive(Debug, Copy, Clone)]
pub struct list_entry<T> {
    pub le_next: *mut T,
    pub le_prev: *mut *mut T,
}

impl<T> Default for list_entry<T> {
    fn default() -> Self {
        Self { le_next: Default::default(), le_prev: Default::default() }
    }
}

pub unsafe fn list_first<T>(head: *mut list_head<T>) -> *mut T {
    unsafe { (*head).lh_first }
}


pub unsafe fn list_next<T, Discriminant>(elm: *mut T) -> *mut T
where
    T: ListEntry<T, Discriminant>,
{
    unsafe { (*ListEntry::field(elm)).le_next }
}

pub unsafe fn list_foreach<T, D>(head: *mut list_head<T>) -> ListIterator<T, D>
where
    T: ListEntry<T, D>,
{
    ListIterator {
        curr: unsafe { NonNull::new(list_first(head)) },
        _phantom: std::marker::PhantomData,
    }
}

// this implementation can be used in place of safe and non-safe
pub struct ListIterator<T, D> {
    curr: Option<NonNull<T>>,
    _phantom: std::marker::PhantomData<D>,
}
impl<T, D> Iterator for ListIterator<T, D>
where
    T: ListEntry<T, D>,
{
    type Item = NonNull<T>;

    fn next(&mut self) -> Option<Self::Item> {
        let curr = self.curr?.as_ptr();
        std::mem::replace(&mut self.curr, NonNull::new(unsafe { list_next(curr) }))
    }
}

pub unsafe fn list_insert_head<T, D>(head: *mut list_head<T>, elm: *mut T)
where
    T: ListEntry<T, D>,
{
    unsafe {
        (*ListEntry::field(elm)).le_next = (*head).lh_first;
        if !(*ListEntry::field(elm)).le_next.is_null() {
            (*ListEntry::field((*head).lh_first)).le_prev =
                &raw mut (*ListEntry::field(elm)).le_next;
        }
        (*head).lh_first = elm;
        (*ListEntry::field(elm)).le_prev = &raw mut (*head).lh_first;
    }
}

pub unsafe fn list_remove<T, D>(elm: *mut T)
where
    T: ListEntry<T, D>,
{
    unsafe {
        if !(*ListEntry::field(elm)).le_next.is_null() {
            (*ListEntry::field((*ListEntry::field(elm)).le_next)).le_prev =
                (*ListEntry::field(elm)).le_prev;
        }
        *(*ListEntry::field(elm)).le_prev = (*ListEntry::field(elm)).le_next;
    }
}

// tailq

#[repr(C)]
#[derive(Debug, Copy, Clone)]
pub struct tailq_head<T> {
    pub tqh_first: *mut T,
    pub tqh_last: *mut *mut T,
}

macro_rules! TAILQ_HEAD_INITIALIZER {
    ($ident:ident) => {
        $crate::compat::queue::tailq_head {
            tqh_first: null_mut(),
            tqh_last: unsafe { &raw mut $ident.tqh_first },
        }
    };
}
pub(crate) use TAILQ_HEAD_INITIALIZER;

#[repr(C)]
#[derive(Copy, Clone)]
pub struct tailq_entry<T> {
    pub tqe_next: *mut T,
    pub tqe_prev: *mut *mut T,
}

impl<T> Default for tailq_entry<T> {
    fn default() -> Self {
        Self {
            tqe_next: null_mut(),
            tqe_prev: null_mut(),
        }
    }
}

impl<T> std::fmt::Debug for tailq_entry<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("tailq_entry")
            .field("tqe_next", &self.tqe_next)
            .field("tqe_prev", &self.tqe_prev)
            .finish()
    }
}

pub trait Entry<T, Discriminant = ()> {
    unsafe fn entry(this: *mut Self) -> *mut tailq_entry<T>;
}

pub unsafe fn tailq_init<T>(head: *mut tailq_head<T>) {
    unsafe {
        (*head).tqh_first = core::ptr::null_mut();
        (*head).tqh_last = &raw mut (*head).tqh_first;
    }
}

pub fn tailq_init_<T>(head: &mut tailq_head<T>) {
    head.tqh_first = core::ptr::null_mut();
    head.tqh_last = &raw mut head.tqh_first;
}

pub unsafe fn tailq_first<T>(head: *mut tailq_head<T>) -> *mut T {
    unsafe { (*head).tqh_first }
}

pub unsafe fn tailq_next<T, Q, D>(elm: *mut T) -> *mut Q
where
    T: Entry<Q, D>,
{
    unsafe { (*Entry::entry(elm)).tqe_next }
}

pub unsafe fn tailq_last<T>(head: *mut tailq_head<T>) -> *mut T {
    unsafe { *(*(*head).tqh_last.cast::<tailq_head<T>>()).tqh_last }
}

pub unsafe fn tailq_prev<T, Q, D>(elm: *mut T) -> *mut Q
where
    T: Entry<Q, D>,
{
    unsafe {
        let head: *mut tailq_head<Q> = (*Entry::entry(elm)).tqe_prev.cast();
        *(*head).tqh_last
    }
}

pub unsafe fn tailq_empty<T>(head: *const tailq_head<T>) -> bool {
    unsafe { (*head).tqh_first.is_null() }
}

pub unsafe fn tailq_insert_head<T, D>(head: *mut tailq_head<T>, elm: *mut T)
where
    T: Entry<T, D>,
{
    unsafe {
        (*T::entry(elm)).tqe_next = (*head).tqh_first;

        if !(*T::entry(elm)).tqe_next.is_null() {
            (*T::entry((*head).tqh_first)).tqe_prev = &raw mut (*T::entry(elm)).tqe_next;
        } else {
            (*head).tqh_last = &raw mut (*T::entry(elm)).tqe_next;
        }

        (*head).tqh_first = elm;
        (*T::entry(elm)).tqe_prev = &raw mut (*head).tqh_first;
    }
}

pub unsafe fn tailq_insert_tail<T, D>(head: *mut tailq_head<T>, elm: *mut T)
where
    T: Entry<T, D>,
{
    unsafe {
        (*Entry::<_, D>::entry(elm)).tqe_next = null_mut();
        (*Entry::<_, D>::entry(elm)).tqe_prev = (*head).tqh_last;
        *(*head).tqh_last = elm;
        (*head).tqh_last = &raw mut (*Entry::<_, D>::entry(elm)).tqe_next;
    }
}

pub unsafe fn tailq_insert_after<T, D>(head: *mut tailq_head<T>, listelm: *mut T, elm: *mut T)
where
    T: Entry<T, D>,
{
    unsafe {
        (*T::entry(elm)).tqe_next = (*T::entry(listelm)).tqe_next;

        if !(*T::entry(elm)).tqe_next.is_null() {
            (*T::entry((*T::entry(elm)).tqe_next)).tqe_prev = &raw mut (*T::entry(elm)).tqe_next;
        } else {
            (*head).tqh_last = &raw mut (*T::entry(elm)).tqe_next;
        }

        (*T::entry(listelm)).tqe_next = elm;
        (*T::entry(elm)).tqe_prev = &raw mut (*T::entry(listelm)).tqe_next;
    }
}

pub unsafe fn tailq_insert_before<T, D>(listelm: *mut T, elm: *mut T)
where
    T: Entry<T, D>,
{
    unsafe {
        (*T::entry(elm)).tqe_prev = (*T::entry(listelm)).tqe_prev;
        (*T::entry(elm)).tqe_next = listelm;
        *(*T::entry(listelm)).tqe_prev = elm;
        (*T::entry(listelm)).tqe_prev = &raw mut (*T::entry(elm)).tqe_next;
    }
}

pub unsafe fn tailq_remove<T, D>(head: *mut tailq_head<T>, elm: *mut T)
where
    T: Entry<T, D>,
{
    unsafe {
        if !(*Entry::<_, D>::entry(elm)).tqe_next.is_null() {
            (*Entry::<_, D>::entry((*Entry::<_, D>::entry(elm)).tqe_next)).tqe_prev =
                (*Entry::<_, D>::entry(elm)).tqe_prev;
        } else {
            (*head).tqh_last = (*Entry::<_, D>::entry(elm)).tqe_prev;
        }
        *(*Entry::<_, D>::entry(elm)).tqe_prev = (*Entry::<_, D>::entry(elm)).tqe_next;
    }
}

pub unsafe fn tailq_replace<T, D>(head: *mut tailq_head<T>, elm: *mut T, elm2: *mut T)
where
    T: Entry<T, D>,
{
    unsafe {
        (*Entry::<_, D>::entry(elm2)).tqe_next = (*Entry::<_, D>::entry(elm)).tqe_next;
        if !(*Entry::<_, D>::entry(elm2)).tqe_next.is_null() {
            (*Entry::<_, D>::entry((*Entry::<_, D>::entry(elm2)).tqe_next)).tqe_prev =
                &raw mut (*Entry::<_, D>::entry(elm2)).tqe_next;
        } else {
            (*head).tqh_last = &raw mut (*Entry::<_, D>::entry(elm2)).tqe_next;
        }
        (*Entry::<_, D>::entry(elm2)).tqe_prev = (*Entry::<_, D>::entry(elm)).tqe_prev;
        *(*Entry::<_, D>::entry(elm2)).tqe_prev = elm2;
    }
}

pub unsafe fn tailq_foreach_const<T, D>(
    head: *const tailq_head<T>,
) -> ConstTailqForwardIterator<T, D>
where
    T: Entry<T, D>,
{
    unsafe {
        ConstTailqForwardIterator {
            curr: NonNull::new((*head).tqh_first),
            _phantom: std::marker::PhantomData,
        }
    }
}
// this implementation can be used in place of safe and non-safe
pub struct ConstTailqForwardIterator<T, D> {
    curr: Option<NonNull<T>>,
    _phantom: std::marker::PhantomData<D>,
}
impl<T, D> Iterator for ConstTailqForwardIterator<T, D>
where
    T: Entry<T, D>,
{
    type Item = NonNull<T>;

    fn next(&mut self) -> Option<Self::Item> {
        let curr = self.curr?.as_ptr();
        std::mem::replace(&mut self.curr, NonNull::new(unsafe { tailq_next(curr) }))
    }
}

pub unsafe fn tailq_foreach<T, D>(head: *mut tailq_head<T>) -> TailqForwardIterator<T, D>
where
    T: Entry<T, D>,
{
    unsafe {
        TailqForwardIterator {
            curr: NonNull::new(tailq_first(head)),
            _phantom: std::marker::PhantomData,
        }
    }
}

// this implementation can be used in place of safe and non-safe
pub struct TailqForwardIterator<T, D> {
    curr: Option<NonNull<T>>,
    _phantom: std::marker::PhantomData<D>,
}
impl<T, D> Iterator for TailqForwardIterator<T, D>
where
    T: Entry<T, D>,
{
    type Item = NonNull<T>;

    fn next(&mut self) -> Option<Self::Item> {
        let curr = self.curr?.as_ptr();
        std::mem::replace(&mut self.curr, NonNull::new(unsafe { tailq_next(curr) }))
    }
}

pub unsafe fn tailq_foreach_reverse<T, D>(head: *mut tailq_head<T>) -> TailqReverseIterator<T, D>
where
    T: Entry<T, D>,
{
    unsafe {
        TailqReverseIterator {
            curr: NonNull::new(tailq_last(head)),
            _phantom: std::marker::PhantomData,
        }
    }
}

// this implementation can be used in place of safe and non-safe
pub struct TailqReverseIterator<T, D> {
    curr: Option<NonNull<T>>,
    _phantom: std::marker::PhantomData<D>,
}
impl<T, D> Iterator for TailqReverseIterator<T, D>
where
    T: Entry<T, D>,
{
    type Item = NonNull<T>;

    fn next(&mut self) -> Option<Self::Item> {
        let curr = self.curr?.as_ptr();
        std::mem::replace(&mut self.curr, NonNull::new(unsafe { tailq_prev(curr) }))
    }
}

#[inline]
pub unsafe fn tailq_concat<T, D>(head1: *mut tailq_head<T>, head2: *mut tailq_head<T>)
where
    T: Entry<T, D>,
{
    unsafe {
        if !tailq_empty::<T>(head2) {
            *(*head1).tqh_last = (*head2).tqh_first;
            (*Entry::entry((*head2).tqh_first)).tqe_prev = (*head1).tqh_last;
            (*head1).tqh_last = (*head2).tqh_last;
            tailq_init(head2);
        }
    }
}

macro_rules! impl_tailq_entry {
    ($struct_name:ident, $attribute_field_name:ident, $attribute_field_ty:ty) => {
        impl $crate::compat::queue::Entry<$struct_name> for $struct_name {
            unsafe fn entry(this: *mut Self) -> *mut $attribute_field_ty {
                unsafe { &raw mut (*this).$attribute_field_name }
            }
        }
    };
}
pub(crate) use impl_tailq_entry;

#[cfg(test)]
mod tests {
    use super::*;

    // ---- TAILQ test fixtures --------------------------------------------
    //
    // A minimal doubly-linked tail-queue node keyed by an i32. This mirrors the
    // C `TAILQ_ENTRY(type)` pattern from vendor/tmux/compat/queue.h (lines
    // 416-420) where each node embeds a `{ tqe_next; tqe_prev; }`. We drive the
    // ported TAILQ_* ops in isolation with no dependency on server globals.
    #[repr(C)]
    struct TNode {
        key: i32,
        entry: tailq_entry<TNode>,
    }

    impl Entry<TNode> for TNode {
        unsafe fn entry(this: *mut Self) -> *mut tailq_entry<TNode> {
            unsafe { &raw mut (*this).entry }
        }
    }

    unsafe fn tmake(key: i32) -> *mut TNode {
        Box::into_raw(Box::new(TNode {
            key,
            entry: tailq_entry::default(),
        }))
    }

    // Collect the keys by walking TAILQ_FIRST / TAILQ_NEXT (queue.h 425, 427).
    unsafe fn tkeys(head: *mut tailq_head<TNode>) -> Vec<i32> {
        unsafe {
            let mut out = Vec::new();
            let mut n = tailq_first(head);
            while !n.is_null() {
                out.push((*n).key);
                n = tailq_next::<_, TNode, ()>(n);
            }
            out
        }
    }

    // Collect keys walking the forward iterator (TAILQ_FOREACH, queue.h 436).
    unsafe fn tkeys_foreach(head: *mut tailq_head<TNode>) -> Vec<i32> {
        unsafe { tailq_foreach::<TNode, ()>(head).map(|p| (*p.as_ptr()).key).collect() }
    }

    // Collect keys walking backwards (TAILQ_FOREACH_REVERSE, queue.h 448).
    unsafe fn tkeys_reverse(head: *mut tailq_head<TNode>) -> Vec<i32> {
        unsafe {
            tailq_foreach_reverse::<TNode, ()>(head)
                .map(|p| (*p.as_ptr()).key)
                .collect()
        }
    }

    unsafe fn tfree_all(head: *mut tailq_head<TNode>) {
        unsafe {
            let mut n = tailq_first(head);
            while !n.is_null() {
                let next = tailq_next::<_, TNode, ()>(n);
                drop(Box::from_raw(n));
                n = next;
            }
            tailq_init(head);
        }
    }

    // TAILQ_INIT (queue.h 462) leaves an empty queue: first is NULL and last
    // points back at first. TAILQ_EMPTY (queue.h 433) must be true.
    #[test]
    fn tailq_init_makes_empty() {
        unsafe {
            let mut head: tailq_head<TNode> = tailq_head {
                tqh_first: null_mut(),
                tqh_last: null_mut(),
            };
            tailq_init(&raw mut head);
            assert!(tailq_empty(&raw const head));
            assert!(head.tqh_first.is_null());
            assert_eq!(head.tqh_last, &raw mut head.tqh_first);
            assert!(tailq_first(&raw mut head).is_null());
            // last on empty is NULL, so both iterators yield nothing.
            assert!(tailq_last(&raw mut head).is_null());
            assert!(tkeys_foreach(&raw mut head).is_empty());
            assert!(tkeys_reverse(&raw mut head).is_empty());
        }
    }

    // tailq_init_ is the &mut-taking twin of tailq_init; same postconditions.
    #[test]
    fn tailq_init_ref_makes_empty() {
        let mut head: tailq_head<TNode> = tailq_head {
            tqh_first: null_mut(),
            tqh_last: null_mut(),
        };
        tailq_init_(&mut head);
        assert!(head.tqh_first.is_null());
        assert_eq!(head.tqh_last, &raw mut head.tqh_first);
    }

    // TAILQ_INSERT_HEAD (queue.h 467) prepends: inserting 1 then 2 then 3 yields
    // front-to-back order 3,2,1. first/last and both traversal directions agree.
    #[test]
    fn tailq_insert_head_prepends() {
        unsafe {
            let mut head: tailq_head<TNode> = tailq_head {
                tqh_first: null_mut(),
                tqh_last: null_mut(),
            };
            tailq_init(&raw mut head);
            for k in [1, 2, 3] {
                tailq_insert_head(&raw mut head, tmake(k));
            }
            assert!(!tailq_empty(&raw const head));
            assert_eq!(tkeys(&raw mut head), vec![3, 2, 1]);
            assert_eq!(tkeys_foreach(&raw mut head), vec![3, 2, 1]);
            assert_eq!(tkeys_reverse(&raw mut head), vec![1, 2, 3]);
            assert_eq!((*tailq_first(&raw mut head)).key, 3);
            assert_eq!((*tailq_last(&raw mut head)).key, 1);
            tfree_all(&raw mut head);
        }
    }

    // TAILQ_INSERT_TAIL (queue.h 477) appends: 1,2,3 stays 1,2,3. Exercises the
    // tqh_last bookkeeping that keeps the reverse walk consistent.
    #[test]
    fn tailq_insert_tail_appends() {
        unsafe {
            let mut head: tailq_head<TNode> = tailq_head {
                tqh_first: null_mut(),
                tqh_last: null_mut(),
            };
            tailq_init(&raw mut head);
            for k in [1, 2, 3] {
                tailq_insert_tail(&raw mut head, tmake(k));
            }
            assert_eq!(tkeys(&raw mut head), vec![1, 2, 3]);
            assert_eq!(tkeys_foreach(&raw mut head), vec![1, 2, 3]);
            assert_eq!(tkeys_reverse(&raw mut head), vec![3, 2, 1]);
            assert_eq!((*tailq_first(&raw mut head)).key, 1);
            assert_eq!((*tailq_last(&raw mut head)).key, 3);
            tfree_all(&raw mut head);
        }
    }

    // TAILQ_INSERT_AFTER (queue.h 484): insert after a middle element and after
    // the current tail. The after-tail case must update tqh_last so the reverse
    // walk still starts at the new tail.
    #[test]
    fn tailq_insert_after_middle_and_tail() {
        unsafe {
            let mut head: tailq_head<TNode> = tailq_head {
                tqh_first: null_mut(),
                tqh_last: null_mut(),
            };
            tailq_init(&raw mut head);
            let a = tmake(1);
            let c = tmake(3);
            tailq_insert_tail(&raw mut head, a);
            tailq_insert_tail(&raw mut head, c);
            // after 'a' (middle insert): 1,2,3
            tailq_insert_after(&raw mut head, a, tmake(2));
            assert_eq!(tkeys(&raw mut head), vec![1, 2, 3]);
            // after 'c' (tail insert): 1,2,3,4
            tailq_insert_after(&raw mut head, c, tmake(4));
            assert_eq!(tkeys(&raw mut head), vec![1, 2, 3, 4]);
            assert_eq!((*tailq_last(&raw mut head)).key, 4);
            assert_eq!(tkeys_reverse(&raw mut head), vec![4, 3, 2, 1]);
            tfree_all(&raw mut head);
        }
    }

    // TAILQ_INSERT_BEFORE (queue.h 494): insert before a middle element and
    // before the head. Before-head effectively becomes the new first.
    #[test]
    fn tailq_insert_before_middle_and_head() {
        unsafe {
            let mut head: tailq_head<TNode> = tailq_head {
                tqh_first: null_mut(),
                tqh_last: null_mut(),
            };
            tailq_init(&raw mut head);
            let a = tmake(2);
            let b = tmake(4);
            tailq_insert_tail(&raw mut head, a);
            tailq_insert_tail(&raw mut head, b);
            // before 'b': 2,3,4
            tailq_insert_before(b, tmake(3));
            assert_eq!(tkeys(&raw mut head), vec![2, 3, 4]);
            // before 'a' (the head): 1,2,3,4
            tailq_insert_before(a, tmake(1));
            assert_eq!(tkeys(&raw mut head), vec![1, 2, 3, 4]);
            assert_eq!((*tailq_first(&raw mut head)).key, 1);
            assert_eq!(tkeys_reverse(&raw mut head), vec![4, 3, 2, 1]);
            tfree_all(&raw mut head);
        }
    }

    // TAILQ_NEXT / TAILQ_PREV (queue.h 427, 431) navigation over a built queue.
    #[test]
    fn tailq_next_prev_navigation() {
        unsafe {
            let mut head: tailq_head<TNode> = tailq_head {
                tqh_first: null_mut(),
                tqh_last: null_mut(),
            };
            tailq_init(&raw mut head);
            let n1 = tmake(10);
            let n2 = tmake(20);
            let n3 = tmake(30);
            tailq_insert_tail(&raw mut head, n1);
            tailq_insert_tail(&raw mut head, n2);
            tailq_insert_tail(&raw mut head, n3);

            assert_eq!((*tailq_next::<_, TNode, ()>(n1)).key, 20);
            assert_eq!((*tailq_next::<_, TNode, ()>(n2)).key, 30);
            assert!(tailq_next::<_, TNode, ()>(n3).is_null());

            assert_eq!((*tailq_prev::<_, TNode, ()>(n3)).key, 20);
            assert_eq!((*tailq_prev::<_, TNode, ()>(n2)).key, 10);
            tfree_all(&raw mut head);
        }
    }

    // TAILQ_REMOVE (queue.h 501) for the three distinct branches: removing the
    // head, a middle node, and the tail (the else branch that fixes tqh_last).
    #[test]
    fn tailq_remove_head_middle_tail() {
        unsafe {
            let mut head: tailq_head<TNode> = tailq_head {
                tqh_first: null_mut(),
                tqh_last: null_mut(),
            };
            tailq_init(&raw mut head);
            let n1 = tmake(1);
            let n2 = tmake(2);
            let n3 = tmake(3);
            let n4 = tmake(4);
            for n in [n1, n2, n3, n4] {
                tailq_insert_tail(&raw mut head, n);
            }
            // remove middle
            tailq_remove(&raw mut head, n2);
            drop(Box::from_raw(n2));
            assert_eq!(tkeys(&raw mut head), vec![1, 3, 4]);
            assert_eq!(tkeys_reverse(&raw mut head), vec![4, 3, 1]);
            // remove tail (else branch updates tqh_last)
            tailq_remove(&raw mut head, n4);
            drop(Box::from_raw(n4));
            assert_eq!(tkeys(&raw mut head), vec![1, 3]);
            assert_eq!((*tailq_last(&raw mut head)).key, 3);
            assert_eq!(tkeys_reverse(&raw mut head), vec![3, 1]);
            // remove head
            tailq_remove(&raw mut head, n1);
            drop(Box::from_raw(n1));
            assert_eq!(tkeys(&raw mut head), vec![3]);
            assert_eq!((*tailq_first(&raw mut head)).key, 3);
            // remove last remaining -> empty
            tailq_remove(&raw mut head, n3);
            drop(Box::from_raw(n3));
            assert!(tailq_empty(&raw const head));
            assert_eq!(head.tqh_last, &raw mut head.tqh_first);
        }
    }

    // TAILQ_REPLACE (queue.h 512): swap a node in place, both middle and tail.
    #[test]
    fn tailq_replace_middle_and_tail() {
        unsafe {
            let mut head: tailq_head<TNode> = tailq_head {
                tqh_first: null_mut(),
                tqh_last: null_mut(),
            };
            tailq_init(&raw mut head);
            let n1 = tmake(1);
            let n2 = tmake(2);
            let n3 = tmake(3);
            for n in [n1, n2, n3] {
                tailq_insert_tail(&raw mut head, n);
            }
            // replace middle n2 with key 20
            let r = tmake(20);
            tailq_replace(&raw mut head, n2, r);
            drop(Box::from_raw(n2));
            assert_eq!(tkeys(&raw mut head), vec![1, 20, 3]);
            assert_eq!(tkeys_reverse(&raw mut head), vec![3, 20, 1]);
            // replace tail n3 with key 30 (else branch updates tqh_last)
            let r2 = tmake(30);
            tailq_replace(&raw mut head, n3, r2);
            drop(Box::from_raw(n3));
            assert_eq!(tkeys(&raw mut head), vec![1, 20, 30]);
            assert_eq!((*tailq_last(&raw mut head)).key, 30);
            assert_eq!(tkeys_reverse(&raw mut head), vec![30, 20, 1]);
            tfree_all(&raw mut head);
        }
    }

    // TAILQ_CONCAT (queue.h 524): splice head2 onto the end of head1 and leave
    // head2 empty. Also verify the no-op path when head2 is empty.
    #[test]
    fn tailq_concat_splices_and_empties() {
        unsafe {
            let mut h1: tailq_head<TNode> = tailq_head {
                tqh_first: null_mut(),
                tqh_last: null_mut(),
            };
            let mut h2: tailq_head<TNode> = tailq_head {
                tqh_first: null_mut(),
                tqh_last: null_mut(),
            };
            tailq_init(&raw mut h1);
            tailq_init(&raw mut h2);
            for k in [1, 2] {
                tailq_insert_tail(&raw mut h1, tmake(k));
            }
            for k in [3, 4] {
                tailq_insert_tail(&raw mut h2, tmake(k));
            }
            tailq_concat(&raw mut h1, &raw mut h2);
            assert_eq!(tkeys(&raw mut h1), vec![1, 2, 3, 4]);
            assert_eq!(tkeys_reverse(&raw mut h1), vec![4, 3, 2, 1]);
            assert!(tailq_empty(&raw const h2));
            assert_eq!(h2.tqh_last, &raw mut h2.tqh_first);

            // concat with an empty head2 is a no-op.
            let mut h3: tailq_head<TNode> = tailq_head {
                tqh_first: null_mut(),
                tqh_last: null_mut(),
            };
            tailq_init(&raw mut h3);
            tailq_concat(&raw mut h1, &raw mut h3);
            assert_eq!(tkeys(&raw mut h1), vec![1, 2, 3, 4]);
            tfree_all(&raw mut h1);
        }
    }

    // The const forward iterator (TAILQ_FOREACH over a *const head) must visit
    // the same nodes in the same order as the mutable one.
    #[test]
    fn tailq_foreach_const_matches() {
        unsafe {
            let mut head: tailq_head<TNode> = tailq_head {
                tqh_first: null_mut(),
                tqh_last: null_mut(),
            };
            tailq_init(&raw mut head);
            for k in [5, 6, 7] {
                tailq_insert_tail(&raw mut head, tmake(k));
            }
            let got: Vec<i32> = tailq_foreach_const::<TNode, ()>(&raw const head)
                .map(|p| (*p.as_ptr()).key)
                .collect();
            assert_eq!(got, vec![5, 6, 7]);
            tfree_all(&raw mut head);
        }
    }

    // ---- LIST test fixtures ---------------------------------------------
    //
    // Doubly-linked LIST node (LIST_ENTRY, queue.h 172-176) with le_next and
    // le_prev. Only head-insert plus arbitrary remove and forward traversal are
    // ported, matching what the crate uses.
    #[repr(C)]
    struct LNode {
        key: i32,
        entry: list_entry<LNode>,
    }

    impl ListEntry<LNode> for LNode {
        unsafe fn field(this: *mut Self) -> *mut list_entry<LNode> {
            unsafe { &raw mut (*this).entry }
        }
    }

    unsafe fn lmake(key: i32) -> *mut LNode {
        Box::into_raw(Box::new(LNode {
            key,
            entry: list_entry::default(),
        }))
    }

    unsafe fn lkeys(head: *mut list_head<LNode>) -> Vec<i32> {
        unsafe {
            let mut out = Vec::new();
            let mut n = list_first(head);
            while !n.is_null() {
                out.push((*n).key);
                n = list_next::<_, ()>(n);
            }
            out
        }
    }

    unsafe fn lfree_all(head: *mut list_head<LNode>) {
        unsafe {
            let mut n = list_first(head);
            while !n.is_null() {
                let next = list_next::<_, ()>(n);
                drop(Box::from_raw(n));
                n = next;
            }
            (*head).lh_first = null_mut();
        }
    }

    // LIST_HEAD_INITIALIZER / LIST_INSERT_HEAD (queue.h 169, 218): the head list
    // starts empty (lh_first NULL) and prepends, so 1,2,3 becomes 3,2,1.
    #[test]
    fn list_insert_head_prepends() {
        unsafe {
            let mut head: list_head<LNode> = list_head_initializer();
            assert!(list_first(&raw mut head).is_null());
            for k in [1, 2, 3] {
                list_insert_head(&raw mut head, lmake(k));
            }
            assert_eq!(lkeys(&raw mut head), vec![3, 2, 1]);
            let got: Vec<i32> = list_foreach::<LNode, ()>(&raw mut head)
                .map(|p| (*p.as_ptr()).key)
                .collect();
            assert_eq!(got, vec![3, 2, 1]);
            assert_eq!((*list_first(&raw mut head)).key, 3);
            lfree_all(&raw mut head);
        }
    }

    // LIST_REMOVE (queue.h 225) for head, middle and tail. le_prev indirection
    // must keep the chain intact after each removal.
    #[test]
    fn list_remove_head_middle_tail() {
        unsafe {
            let mut head: list_head<LNode> = list_head_initializer();
            // insert_head of 1,2,3,4 -> order is 4,3,2,1
            let n1 = lmake(1);
            let n2 = lmake(2);
            let n3 = lmake(3);
            let n4 = lmake(4);
            for n in [n1, n2, n3, n4] {
                list_insert_head(&raw mut head, n);
            }
            assert_eq!(lkeys(&raw mut head), vec![4, 3, 2, 1]);
            // remove middle (n3): 4,2,1
            list_remove::<_, ()>(n3);
            drop(Box::from_raw(n3));
            assert_eq!(lkeys(&raw mut head), vec![4, 2, 1]);
            // remove head (n4): 2,1
            list_remove::<_, ()>(n4);
            drop(Box::from_raw(n4));
            assert_eq!(lkeys(&raw mut head), vec![2, 1]);
            assert_eq!((*list_first(&raw mut head)).key, 2);
            // remove tail (n1): 2
            list_remove::<_, ()>(n1);
            drop(Box::from_raw(n1));
            assert_eq!(lkeys(&raw mut head), vec![2]);
            // remove last: empty
            list_remove::<_, ()>(n2);
            drop(Box::from_raw(n2));
            assert!(list_first(&raw mut head).is_null());
        }
    }

    // LIST_NEXT (queue.h 184): forward navigation, next of the tail is NULL.
    #[test]
    fn list_next_navigation() {
        unsafe {
            let mut head: list_head<LNode> = list_head_initializer();
            let a = lmake(1);
            let b = lmake(2);
            list_insert_head(&raw mut head, b);
            list_insert_head(&raw mut head, a); // order: 1,2
            assert_eq!((*list_next::<_, ()>(a)).key, 2);
            assert!(list_next::<_, ()>(b).is_null());
            lfree_all(&raw mut head);
        }
    }
}