LoginSignup
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@syuuu

Rustで単方向リストを実装する(unsafe版)

Last updated at Posted at 2022-01-11

概要

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

環境

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

実行結果の比較

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

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

list.png

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

方式
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版に書き換えても良い気もします。

1
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?