A basic doubly linked list implementation in Rust

d_list.rs

mod doubly_linked_list 
{ 
  extern crate core;
  extern crate alloc;
  use 
  { core::
    { ptr
    , marker::PhantomData
    , option::Option::{self, *}
    , iter::{Iterator, IntoIterator, DoubleEndedIterator}
    , result::Result::*}
  , alloc::alloc::Layout
  };
  struct DListNode<T> 
  { data : T
  , prev : *mut DListNode<T>
  , next : *mut DListNode<T>
  }

  pub struct DList<T> { ptr : *mut DListNode<T> , phantom : PhantomData<T>}

  impl<T> DList<T> 
  { pub fn new()->Self { DList { ptr: ptr::null_mut(), phantom: PhantomData } }

    pub fn push_front(&mut self, data : T) -> &mut Self
    { unsafe 
      { let new_head = alloc::alloc::alloc(Layout::new::<DListNode<T>>()) as  *mut DListNode<T>
      ; core::ptr::write(&mut (*new_head).data, data)

      ; if self.is_empty()
        { (*new_head).next = new_head
        ; (*new_head).prev = new_head
        }
        else 
        { let old_prev = (*self.ptr).prev

        ; (*new_head).prev = (*self.ptr).prev
        ; (*new_head).next = self.ptr

        ; (*self.ptr).prev = new_head
        ; (*old_prev).next = new_head
        }
      ; self.ptr = new_head
      }
    ; self
    }
    pub fn push_back(&mut self, data : T)->&mut Self 
    { unsafe 
      { let new_end = alloc::alloc::alloc(Layout::new::<DListNode<T>>()) as  *mut DListNode<T>
      ; core::ptr::write(&mut (*new_end).data, data)
      ; if self.is_empty()
        { self.ptr = new_end
        ; (*new_end).next = new_end
        ; (*new_end).prev = new_end
        }
        else
        { let old_prev = (*self.ptr).prev

        ; (*new_end).next = self.ptr
        ; (*new_end).prev = old_prev

        ; (*old_prev).next = new_end
        ; (*self.ptr).prev = new_end
        }
      }
    ; self
    }

    pub fn pop_front(&mut self)->Option<T>
    { match self.quantity() { 
        DListQuantity::Empty => None
      , DListQuantity::One   => 
        { let out = unsafe {core::ptr::read( &mut(*self.ptr).data )} 
        ; unsafe {alloc::alloc::dealloc(self.ptr as *mut u8, Layout::new::<DListNode<T>>())}
        ; self.ptr = core::ptr::null_mut()
        ; Some(out)
        }
      , DListQuantity::Many  =>
        unsafe 
        { let next = (*self.ptr).next 
        ; let prev = (*self.ptr).prev
        ; (*next).prev = prev
        ; (*prev).next = next
        
        ; let out = core::ptr::read( &mut(*self.ptr).data )
        ; alloc::alloc::dealloc(self.ptr as *mut u8, Layout::new::<DListNode<T>>())
        
        ; self.ptr = next
        ; Some(out)
        }
        
    }}
    
    pub fn pop_back(&mut self)->Option<T>
    { match self.quantity() {
      DListQuantity::Empty => None
    , DListQuantity::One   => 
      { let out = unsafe {core::ptr::read( &mut(*self.ptr).data )} 
      ; unsafe {alloc::alloc::dealloc(self.ptr as *mut u8, Layout::new::<DListNode<T>>())}
      ; self.ptr = core::ptr::null_mut()

      ; Some(out)
      }
    , DListQuantity::Many  =>
      unsafe {
      ; let prev = (*self.ptr).prev
      ; let prev_prev = (*prev).prev
      ; (*self.ptr).prev = prev_prev
      ; (*prev_prev).next = self.ptr
      
      ; let out = core::ptr::read( &mut(*prev).data )
      ; alloc::alloc::dealloc(prev as *mut u8, Layout::new::<DListNode<T>>())
      
      ; Some(out)
      }
    }}
    
    fn quantity(&self) -> DListQuantity
    { if self.is_empty()                              { DListQuantity::Empty} 
      else if unsafe { (*self.ptr).next } == self.ptr { DListQuantity::One  } 
      else                                            { DListQuantity::Many } 
    }
    pub fn is_empty(&self)->bool {self.ptr.is_null()}
    pub fn iter(&self)-><&Self as IntoIterator>::IntoIter { self.into_iter() }
    pub fn iter_mut(&mut self)-><&mut Self as IntoIterator>::IntoIter { self.into_iter() }
  }
  enum DListQuantity { Empty, One, Many}


  impl<T : core::fmt::Debug> core::fmt::Debug for DList<T>
  { fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result 
    { core::write!(f, "List [")?

    ; if self.is_empty() { return core::write!(f, "]")}

    ; unsafe 
      { core::write!(f, "{:?}", &(*self.ptr).data )?
      ; let end = self.ptr
      ; let mut next = (*self.ptr).next

      ; while next != end 
        { core::write!(f, " ,{:?}", &(*next).data)?
        ; next = (*next).next
        }
        core::write!(f, "]")?
      ; Ok(())
      }
    }
  }
  
  impl<T> core::ops::Drop for DList<T>
  { fn drop(&mut self) 
    { if self.is_empty() {return}

    ; let end = self.ptr
    ; let mut current = self.ptr
    ; let layout = Layout::new::<DListNode<T>>();

    ; loop { unsafe {
        let next = (*current).next

      ; core::ptr::drop_in_place(&mut (*current).data)
      ; alloc::alloc::dealloc(current as *mut u8, layout)

      ; current = next
      ; if current == end {break}
      }}
    }
  }
  pub struct DListConsumingIter<T> 
  { src : DList<T>
  }
  
  impl<T> Iterator for DListConsumingIter<T>
  { type Item = T
  ; fn next(&mut self) -> Option<Self::Item>
    { self.src.pop_front() }
  }

  impl<T> DoubleEndedIterator for DListConsumingIter<T>
  { fn next_back(&mut self) -> Option<Self::Item> 
    { self.src.pop_back() }
  }

  impl<T> IntoIterator for DList<T> 
  { type Item = T
  ; type IntoIter = DListConsumingIter<T>;
    fn into_iter(self) -> Self::IntoIter 
    { DListConsumingIter { src : self } }
  }
  
  #[allow(non_camel_case_types)]
  #[derive(Clone, Copy)]
  enum DListCursor<T> 
  { Null
  , Last(T)
  , First_Last((T,T))
  }

  pub struct DListRefIter<'list, T>
  { cursor : DListCursor<&'list DListNode<T>>
  , src    : &'list DList<T>
  }

  impl<'list, T : 'list> Iterator for DListRefIter<'list, T>
  { type Item = &'list T
  ; fn next(&mut self) -> Option<Self::Item> 
    { match self.cursor {
      DListCursor::Null       => None
    , DListCursor::Last(last) => 
      { self.cursor = DListCursor::Null
      ; Some(&last.data) 
      }
    , DListCursor::First_Last((first,last)) => 
      { self.cursor = 
        if first.next == last as *const _ as *mut _ 
        { DListCursor::Last(last) }
        else
        { DListCursor::First_Last(( unsafe {&*first.next} , last)) }
      ; Some(&first.data)
      }
    }}
  }

  impl<'list, T> IntoIterator for &'list DList<T>
  { type Item = &'list T
  ; type IntoIter = DListRefIter<'list, T>
  ; fn into_iter(self) -> Self::IntoIter 
    { let cursor = match self.quantity() 
      { DListQuantity::Empty => DListCursor::Null
      , DListQuantity::One   => DListCursor::Last(unsafe{&*self.ptr})
      , DListQuantity::Many  => 
        unsafe
        { DListCursor::First_Last((&*self.ptr, &*(*self.ptr).prev)) }
      }
    ; DListRefIter { cursor, src : self }
    }
  }

  impl<'list, T> DoubleEndedIterator for DListRefIter<'list, T>
  { fn next_back(&mut self) -> Option<Self::Item> 
    { match self.cursor {
      DListCursor::Null       => None
    , DListCursor::Last(last) => 
      { self.cursor = DListCursor::Null
      ; Some(&last.data) 
      }
    , DListCursor::First_Last((first,last)) => 
      { self.cursor = 
        if last.prev == first as *const _ as *mut _ 
        { DListCursor::Last(last) }
        else
        { DListCursor::First_Last((first , unsafe {&*last.prev})) }
      ; Some(&last.data)
      }
    }}
  }

  pub struct DListMutRefIter<'list, T>
  { cursor : DListCursor<*mut DListNode<T>>
  , src    : &'list mut DList<T>
  }
  
  
  impl<'list, T : 'list> Iterator for DListMutRefIter<'list, T>
  { type Item = &'list mut T
  ; fn next(&mut self) -> Option<Self::Item> 
    { match self.cursor {
      DListCursor::Null       => None
    , DListCursor::Last(last) => 
      unsafe
      { self.cursor = DListCursor::Null
      ; Some(&mut (*last).data) 
      }
    , DListCursor::First_Last((first,last)) => 
      unsafe
      { self.cursor = 
        if (*first).next == last 
        { DListCursor::Last(last) }
        else
        { DListCursor::First_Last(( (*first).next , last)) }
      ; Some(&mut (*first).data)
      }
    }}
  }

  
  impl<'list, T> IntoIterator for &'list mut DList<T>
  { type Item = &'list mut T
  ; type IntoIter = DListMutRefIter<'list, T>
  ; fn into_iter(self) -> Self::IntoIter 
    { let cursor = match self.quantity() 
      { DListQuantity::Empty => DListCursor::Null
      , DListQuantity::One   => DListCursor::Last(self.ptr)
      , DListQuantity::Many  => 
        unsafe
        { DListCursor::First_Last((self.ptr, (*self.ptr).prev)) }
      }
    ; DListMutRefIter { cursor, src : self }
    }
  }

  
  impl<'list, T> DoubleEndedIterator for DListMutRefIter<'list, T>
  { fn next_back(&mut self) -> Option<Self::Item> 
    { match self.cursor {
      DListCursor::Null       => None
    , DListCursor::Last(last) => 
      unsafe
      { self.cursor = DListCursor::Null
      ; Some(&mut (*last).data) 
      }
    , DListCursor::First_Last((first,last)) => 
      unsafe
      { self.cursor = 
        if (*last).prev == first
        { DListCursor::Last(last) }
        else
        { DListCursor::First_Last((first , (*last).prev)) }
      ; Some(&mut (*last).data)
      }
    }}
  }
  pub fn try_list() 
  { extern crate std
  ; use {std::println, alloc::{vec, vec::Vec}}
  ; let mut list : DList<Vec<i32>> = DList::new()
  ; println!("{:?}", list)
  ;
  ; list.push_front(vec![1,2,3])
        .push_front(vec![0])
        .push_back(vec![10, 20, 30])
        .pop_front()
  
  ; list.pop_back()
  
  ; println!("{:?}\n", list)
  
  ; list.push_front(vec![5, 6, 7])
        .push_front(vec![100])
        .push_back(vec![7, 8, 9])
  
  ; for each in list.iter().rev()
    { println!("{each:?}") }
  
  ; for each in list.iter_mut().rev()
    { each.push(1000)
    ; println!("{each:?}")
    }
  
  ; for each in list.into_iter().rev()
    { println!("{each:?}") }
  }
}

fn main() 
{ doubly_linked_list::try_list()
}