概要

腕試しに単方向リストを実装してみた。今回は unsafe 版になります。

環境

rustc 1.57.0 (Rust 2021)
WSL1 (Ubuntu 18.04 LTS)

実行結果の比較

今回で一通りの目的を達したので、振り返って比較します。
それぞれで素朴な実装で、差が出たのは次のケースです。

大雑把にいうと、イテレータの操作中に次ポインタの差す要素を取り除いてしまうケース(下図)ですね。

次のような違いが出ました。

方式
Rc<RefCell>版	None を取得して終了
Box版	コンパイルエラー
unsafe(NonNull)版	解放済みのメモリ参照で実行時エラー

Rc<RefCell>版は、解放済みの場合 None を返してくれるので動きます。
Box版は、イテレータがimutableの参照をしている状態で、pop_back()が更新しようとするのだから所有できずにコンパイルエラーになります
unsafe版は、イテレータでポインターを直に参照している実装としたので実行時エラーとなりました

このNGのパターンは本質的に、複数のアクセス先が共有を行おうとしている時点で、参照カウントやら解放済みのメモリの認識が必要になる訳です。Rc<RefCell>版は自然とこれを実現できていたということですね。

コード(unsafe版)

Cargo.toml

[package]
name = "singly-linked-list-unsafe"
version = "0.1.0"
edition = "2021"
rust-version = "1.57"

[dependencies]

main.rs

コメントアウト部分はNGとなったパターン。

use singly_linked_list_unsafe::SinglyLinkedList;

fn main() {
    let mut list: SinglyLinkedList<u8> = Default::default();
    list.push_back(1);
    // list.push_back(2);
    // let mut iter = list.iter();
    // assert_eq!(iter.next(), Some(1));
    // assert_eq!(list.pop_back(), Some(2));
    // assert_eq!(iter.next(), None);  // NG: Accessing the freed memory!
    // assert_eq!(list.iter().collect::<Vec<_>>(), vec![1]);

    list.push_back(2);
    list.push_back(3);
    println!("{}", list);
    assert_eq!(list.iter().collect::<Vec<_>>(), vec![1, 2, 3]);
    for v in list.iter() {
        println!("{:?}", v);
    }
    assert_eq!(list.pop_back(), Some(3));
    assert_eq!(list.pop_back(), Some(2));
    assert_eq!(list.pop_back(), Some(1));
    assert_eq!(list.pop_back(), None);

    list.push_back(1);
    list.push_back(2);
    assert_eq!(list.pop_front(), Some(1));
    assert_eq!(list.iter().collect::<Vec<_>>(), vec![2]);
}

lib.rs

push_back
- NonNull::>::new() の部分は、Rc\版のようにスタック上の変数を指定すると、呼び出し後にメモリが蒸発するので無限ループに陥ります。なので、ヒープ上の領域を指定する必要があります。
- Box::into_raw<...> でBoxを消費してポインターに変換できるので、それを使っています
pop_back
- cur.as_ptr().value でも値が取得できるのですが、Dropトレイトを見るに ListNode が解放されていないように見えます
- node = unsafe { Box::from_raw(cur.as_ptr()) } と Box に戻してやると、解放されるようになります
  ただ、unsafe版は参照カウンターを持たず、メモリが解放済みであるかを知らないため、NGケースも動かせるようにするには解放させずにリークさせるしかない訳です。

use std::default::Default;
use std::ptr::NonNull;
use std::fmt::{Display, Debug, Formatter, Result};

# [derive(Debug)]
pub struct ListNode<T: Debug> {
    value: T,
    next: Option<NonNull<ListNode<T>>>,
}

# [derive(Default, Debug)]
pub struct SinglyLinkedList<T: Debug> {
    head: Option<NonNull<ListNode<T>>>,
}

impl<T: Debug> ListNode<T> {
    pub fn new(v: T) -> ListNode<T> {
        ListNode { value: v, next: None }
    }
}

impl<T: Debug> Display for ListNode<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        match self.next {
            Some(ref next) => {
                unsafe {
                    write!(f, "ListNode({:?}), {}", self.value, next.as_ref())
                }
            },
            None => write!(f, "ListNode({:?})", self.value)
        }
    }
}

impl<T: Debug> Display for SinglyLinkedList<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        match self.head {
            Some(ref head) => {
                unsafe {
                    write!(f, "SinglyLinkedList[{}]", head.as_ref())
                }
            }
            None => write!(f, "SinglyLinkedList[]")
        }
    }
}

impl<T: Clone + Debug> SinglyLinkedList<T> {
    /// # Examples
    ///
    /// ```
    /// use singly_linked_list_unsafe::SinglyLinkedList;
    /// let mut list: SinglyLinkedList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// ```
    pub fn push_back(&mut self, v: T) {
        let node_new = NonNull::<ListNode<T>>::new(
            Box::into_raw(Box::new(ListNode::<T>::new(v)))
        );
        let mut cur: NonNull<ListNode<T>>;
        cur = match self.head {
            Some(cur) => cur,
            None => {
                self.head = node_new;
                return;
            }
        };

        unsafe {
            while let Some(next) = cur.as_ref().next {
                cur = next;
            }
            cur.as_mut().next = node_new;
        }
        return;
    }

    /// # Examples
    ///
    /// ```
    /// use singly_linked_list_unsafe::SinglyLinkedList;
    /// let mut list: SinglyLinkedList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// assert_eq!(list.pop_back(), Some(2));
    /// assert_eq!(list.pop_back(), Some(1));
    /// assert_eq!(list.pop_back(), None);
    /// ```
    pub fn pop_back(&mut self) -> Option<T> {
        let mut cur: NonNull<ListNode<T>>;
        cur = match self.head {
            Some(cur) => cur,
            None => return None,
        };

        let mut some_prev: Option<NonNull<ListNode<T>>> = None;
        while let Some(next) = unsafe { cur.as_ref().next } {
            some_prev = Some(cur);
            cur = next;
        }

        if let Some(mut prev) = some_prev {
            unsafe {
                println!(
                    "pop_back({:?}): prev(value:{:?}, next: {:?} => None)",
                    cur.as_ref().value,
                    prev.as_ref().value,
                    prev.as_ref().next
                );
                prev.as_mut().next = None;
            }
        } else {
            self.head = None;
        }

        let node : Box<ListNode<T>>;
        node = unsafe { Box::from_raw(cur.as_ptr()) };
        Some(node.value.clone())
    }

    /// # Examples
    ///
    /// ```
    /// use singly_linked_list_unsafe::SinglyLinkedList;
    /// let mut list: SinglyLinkedList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// assert_eq!(list.pop_front(), Some(1));
    /// assert_eq!(list.pop_front(), Some(2));
    /// assert_eq!(list.pop_front(), None);
    /// ```
    pub fn pop_front(&mut self) -> Option<T> {
        let head = match self.head {
            Some(head) => head,
            None => return None,
        };
        self.head = None;
        let node : Box<ListNode<T>> = unsafe {
            Box::from_raw(head.as_ptr())
        };
        self.head = node.next;
        let value = node.value.clone();
        Some(value)
    }

    /// # Examples
    ///
    /// ```
    /// use singly_linked_list_unsafe::SinglyLinkedList;
    /// let mut list: SinglyLinkedList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// let mut iter = list.iter();
    /// assert_eq!(iter.next(), Some(1));
    /// assert_eq!(iter.next(), Some(2));
    /// assert_eq!(iter.next(), None);
    /// ```
    pub fn iter(&self) -> SinglyLinkedListIterator<T> {
        if let Some(head) = self.head {
            SinglyLinkedListIterator {
                cur: Some(head)
            }    
        } else {
            SinglyLinkedListIterator { cur: None }
        }
    }
}

pub struct SinglyLinkedListIterator<T: Debug> {
    cur: Option<NonNull<ListNode<T>>>
}

impl<T: Clone + Debug> Iterator for SinglyLinkedListIterator<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        let cur = match self.cur {
            Some(cur) => cur,
            None => return None,
        };
        let cur_val: T;
        unsafe {
            cur_val = cur.as_ref().value.clone();
            if let Some(next) = cur.as_ref().next {
                self.cur = Some(next);
            } else {
                self.cur = None;
            }
        }
        Some(cur_val)
    }
}

impl<T: Debug> Drop for SinglyLinkedList<T> {
    fn drop(&mut self) {
        println!("> Dropping: SinglyLinkedList");
    }
}

impl<T: Debug> Drop for ListNode<T> {
    fn drop(&mut self) {
        println!("> Dropping: {:p}(value: {:?}, next: {:?})", self, self.value, self.next);
    }
}

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

    #[test]
    fn test_push_pop_1() {
        let mut list: SinglyLinkedList<u8> = Default::default();
        list.push_back(1);
        assert_eq!(list.pop_back(), Some(1));
        assert_eq!(list.pop_back(), None);
        list.push_back(1);
        assert_eq!(list.pop_back(), Some(1));
        assert_eq!(list.pop_back(), None);
    }

    #[test]
    fn test_push_pop_2() {
        let mut list: SinglyLinkedList<&str> = Default::default();
        list.push_back("hello");
        list.push_back("world");
        assert_eq!(list.pop_back(), Some("world"));
        assert_eq!(list.pop_back(), Some("hello"));
        assert_eq!(list.pop_back(), None);
        list.push_back("hello");
        list.push_back("world");
        assert_eq!(list.pop_back(), Some("world"));
        assert_eq!(list.pop_back(), Some("hello"));
        assert_eq!(list.pop_back(), None);
    }

    #[test]
    fn test_pop_front_1() {
        let mut list: SinglyLinkedList<u8> = Default::default();
        assert_eq!(list.pop_front(), None);

        list.push_back(1);
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);

        list.push_back(1);
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);
    }

    #[test]
    fn test_pop_front_2() {
        let mut list: SinglyLinkedList<u8> = Default::default();
        list.push_back(1);
        list.push_back(2);
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), Some(2));
        assert_eq!(list.pop_front(), None);
    }

    #[ignore]
    #[test]
    fn test_iter_unwrap_failed() {
        let mut list: SinglyLinkedList<u8> = Default::default();
        list.push_back(1);
        list.push_back(2);
        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(1));
        assert_eq!(list.pop_back(), Some(2));
        assert_eq!(iter.next(), None);  // NG: Accessing the freed memory!

        list.push_back(2);
        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(1));
        assert_eq!(list.pop_back(), Some(2));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn test_iter_last_add() {
        let mut list: SinglyLinkedList<u8> = Default::default();
        list.push_back(1);
        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(1));
        list.push_back(2);
        assert_eq!(list.pop_back(), Some(2));
        assert_eq!(iter.next(), None);
    }

    #[ignore]
    #[test]
    fn test_iter_and_pop_front_1() {
        let mut list: SinglyLinkedList<u8> = Default::default();
        list.push_back(1);
        list.push_back(2);
        let mut iter = list.iter();             // The next pointer points to 1.
        assert_eq!(list.pop_front(), Some(1));  // node 1 is dropped.
        assert_eq!(iter.next(), None);          // NG: Accessing the freed memory!
    }

    #[test]
    fn test_iter_and_pop_front1() {
        let mut list: SinglyLinkedList<u8> = Default::default();
        list.push_back(1);
        list.push_back(2);
        let mut iter = list.iter();            // The next pointer points to 1.
        assert_eq!(iter.next(), Some(1));      // The next pointer points to 2.
        assert_eq!(list.pop_front(), Some(1)); // node 1 is dropped.
        assert_eq!(iter.next(), Some(2));      // The next pointer points to None.
        assert_eq!(iter.next(), None);
    }
}

あとがき

単方向リストの実装を通じて、Rc, RefCell, Box なりの理解が深まりました。
unsafe版を通じて、 Rc<RefCell>版とBox版に相当するコードで unsafe 版にあるような競合の問題がコンパイル時に分かるのは流石です。

一方で、stdにあるライブラリは性能周りを考慮してか独自にメモリ管理し、生ポインターを使った実装をしています。
まだまだ深淵には程遠いですが、個人でさっと独自のデータ構造を作るなら Rc<RefCell> でやるのが楽そうですね。
Rc<RefCell>版を unsafe版に書き直すのはヒープ確保の部分が分かったあとは簡単だったので、性能で困ってきてから unsafe版に書き換えても良い気もします。