Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@penta2019

Rustでの双方向リストとイテレータの実装.

Last updated at Posted at 2024-09-12

はじめに

Rustでの双方向リストの実装例です。基本的にはC/C++とやることは一緒ですが、所々にRust特有の利点や注意点があるのでそういった部分を重点的に解説します。
イテレータについては別記事で詳しく解説しています。

Nodeの実装

Listの内部で使用するNodeのデータ構造を定義します。
Rustで双方向リストのような相互参照を含むデータ構造を表現しようとすると所有権の問題が発生するため、以下の２択を迫られます。

  • RcとRefCell、または、ArcとMutexを使って所有権を動的に管理する方法
  • unsafeを使って直接ポインタを操作する方法

それぞれ一長一短ですが今回は後者の方法で実装しました。
unsafeブロック内では、通常の文脈では所有権システムやメモリ安全を確保するために無効化されている機能を使用できます。主な機能は以下の２つです。

  • 生のポインタのデリファレンス(参照外し)
  • unsafeな関数の呼び出し

何をもってunsafeであるかは諸説あるようですが、基本的には「使い方を間違えると未定義な振る舞いを起こすもの」という認識で良いと思います。

use std::alloc::{alloc, dealloc, Layout};
use std::ptr::{null_mut, read, write};

#[derive(Debug)]
struct Node<T> {
    value: T,
    prev: *mut Node<T>,
    next: *mut Node<T>,
}

impl<T> Node<T> {
    const LAYOUT: Layout = Layout::new::<Node<T>>();

    fn alloc(t: T) -> *mut Node<T> {
        unsafe {
            let ptr = alloc(Self::LAYOUT) as *mut Node<T>;
            write(&mut (*ptr).value, t);
            ptr
        }
    }

    fn dealloc(ptr: *mut Node<T>) -> T {
        unsafe {
            let value = read(&(*ptr).value);
            dealloc(ptr as *mut u8, Self::LAYOUT);
            value
        }
    }
}

allocはメモリを確保して引数として受け取ったT型でNodeを初期化する関数でdeallocはその逆です。
allocで確保した生のメモリのポインタは通常のrustの所有権のルールから外れた存在で、普通に値をmoveしようとするとおかしなことが起きるため、write,readを使って値を読み書きします。
例えば、writeを使用している部分で (*ptr).value = t などとすると、初期化されていない value: T のDropが呼び出されて、Tの型によっては未定義の振る舞い(バグ）を引き起こします。

Listの実装

上で定義したNodeを使用して双方向(循環)リストを実装します。
一般的な実装方法では番兵(ダミーのNode)を最初に作成しますが、型引数を使用する場合、番兵のvalueにどのような値を入れるべきかという問題が発生するので、番兵を使用しない実装にしました。この方法はリストの先頭(front)がnullであるかどうかで場合分けが必要になります。
番兵を使用したい場合、はNodeの value: T を value: Option<T> に変更して番兵はNoneにしておくといった実装でしょうか。
Defaultトレイトやゼロ埋めによる実装は型引数Tに対する制約が発生するのでいい方法ではないと思います。

struct List<T> {
    front: *mut Node<T>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        Self { front: null_mut() }
    }

    pub fn is_empty(&self) -> bool {
        self.front.is_null()
    }

    pub fn push_front(&mut self, t: T) {
        let n = Node::alloc(t);
        let next = self.front;
        self.front = n;
        unsafe {
            if next.is_null() {
                (*n).next = n;
                (*n).prev = n;
            } else {
                let prev = (*next).prev;
                (*n).next = next;
                (*n).prev = prev;
                (*prev).next = n;
                (*next).prev = n;
            }
        }
    }

    pub fn push_back(&mut self, t: T) {
        self.push_front(t);
        self.front = unsafe { (*self.front).next };
    }

    pub fn pop_front(&mut self) -> Option<T> {
        if self.front.is_null() {
            return None;
        }

        let n = self.front;
        unsafe {
            if (*n).next == n {
                self.front = null_mut();
            } else {
                let next = (*n).next;
                let prev = (*n).prev;
                (*prev).next = next;
                (*next).prev = prev;
                self.front = next;
            }
        }
        Some(Node::dealloc(n))
    }

    pub fn pop_back(&mut self) -> Option<T> {
        if self.front.is_null() {
            return None;
        }

        self.front = unsafe { (*self.front).prev };
        self.pop_front()
    }
}

Dropトレイトの実装

Listが破棄された際に確保したメモリが開放されるようにDropトレイトを実装します。

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        while !self.is_empty() {
            self.pop_front();
        }
    }
}

Iteratorの実装

要素に安全にアクセスするためにIteratorを実装します。
本来は List<T>、&List<T>、&mut List<T> の３つそれぞれに対してIteratorを実装するのですが、今回は簡単のため&mut List<T> (IterMut)のみにします。
双方向リストなので通常のIteratorに加えて、要素を後ろから辿れるようにDoubleEndedIteratorも実装しています。
最後のFusedIteratorは終端に達した後、何度呼び出してもNoneを返すことを保証するマーカートレイトです。
無くても良いですがそういう実装になっているなら付け得なのでついでに付けておきましょう。

使用していない_target とそのライフタイム 'a は無くても動作はするのですが、借用していることを明確にすることで、Listの操作によって無効になったIteratorを誤って使用する間違いを静的に検知できます。
他言語では無効なIteratorを操作するコードを平気でかける上に、後々になって奇妙なバグの原因になることが稀に良くあるので、これはRustの良いところですね。

struct IterMut<'a, T> {
    _target: &'a mut List<T>,
    front: *mut Node<T>,
    back: *mut Node<T>,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        if self.front.is_null() {
            return None;
        }

        let n = unsafe { &mut *self.front };
        if n.next == self.back {
            self.front = null_mut();
            self.back = null_mut();
        } else {
            self.front = n.next;
        };
        Some(&mut n.value)
    }
}

impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.back.is_null() {
            return None;
        }

        let n = unsafe { &mut *self.back };
        if n.prev == self.front {
            self.front = null_mut();
            self.back = null_mut();
        } else {
            self.back = n.prev;
        };
        Some(unsafe { &mut (*n.prev).value })
    }
}

impl<'a, T> std::iter::FusedIterator for IterMut<'a, T> {}

ListにIterMutを返すiter_mut()を定義します。

impl<T> List<T> {
    // 中略

    pub fn iter_mut(&mut self) -> IterMut<T> {
        let front = self.front;
        IterMut {
            _target: self,
            front: front,
            back: front,
        }
    }
}

for文で自動的にiter_mut()が呼び出されるようにIntorIteratorを定義します。

impl<'a, T> IntoIterator for &'a mut List<T> {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

動作確認

debug_print関数はListの中身を表示する関数で、Listの要素に使用するAには破棄されるタイミングが分かるようにDropトレイトを実装しています。
mainでは0から9までの値をリストにpush_backした後、すべての要素に10を足して、前後から交互に表示しています。

fn debug_print<T: std::fmt::Debug>(l: &List<T>) {
    let mut n = l.front;
    unsafe {
        loop {
            println!("{:?}: {:?}", n, *n);
            n = (*n).next;
            if n == l.front {
                break;
            }
        }
    }
}

#[derive(Debug)]
struct A(i32);

impl Drop for A {
    fn drop(&mut self) {
        println!("drop: {self:?}");
    }
}

fn main() {
    let mut l = List::new();
    for i in 0..10 {
        l.push_back(A(i));
    }

    for a in &mut l {
        (*a).0 += 10;
    }

    debug_print(&l);

    let mut it = l.iter_mut();
    loop {
        if let Some(i) = it.next() {
            println!("{i:?}");
        } else {
            break;
        }
        if let Some(i) = it.next_back() {
            println!("{i:?}");
        } else {
            break;
        }
    }
}

自分の環境では以下のような実行結果になりました。

0x63e275ab3b80: Node { value: A(10), prev: 0x63e275ab3ca0, next: 0x63e275ab3ba0 }
0x63e275ab3ba0: Node { value: A(11), prev: 0x63e275ab3b80, next: 0x63e275ab3bc0 }
0x63e275ab3bc0: Node { value: A(12), prev: 0x63e275ab3ba0, next: 0x63e275ab3be0 }
0x63e275ab3be0: Node { value: A(13), prev: 0x63e275ab3bc0, next: 0x63e275ab3c00 }
0x63e275ab3c00: Node { value: A(14), prev: 0x63e275ab3be0, next: 0x63e275ab3c20 }
0x63e275ab3c20: Node { value: A(15), prev: 0x63e275ab3c00, next: 0x63e275ab3c40 }
0x63e275ab3c40: Node { value: A(16), prev: 0x63e275ab3c20, next: 0x63e275ab3c60 }
0x63e275ab3c60: Node { value: A(17), prev: 0x63e275ab3c40, next: 0x63e275ab3c80 }
0x63e275ab3c80: Node { value: A(18), prev: 0x63e275ab3c60, next: 0x63e275ab3ca0 }
0x63e275ab3ca0: Node { value: A(19), prev: 0x63e275ab3c80, next: 0x63e275ab3b80 }
A(10)
A(19)
A(11)
A(18)
A(12)
A(17)
A(13)
A(16)
A(14)
A(15)
drop: A(10)
drop: A(11)
drop: A(12)
drop: A(13)
drop: A(14)
drop: A(15)
drop: A(16)
drop: A(17)
drop: A(18)
drop: A(19)

おわりに

今回はListの前後から出し入れする機能のみを実装しましたが、これだけであれば標準ライブラリのVecDequeを使えばよいし、その方が効率的です。
Listが真価を発揮するのはデータの挿入や並び替えが頻繁に発生するようなアルゴリズムを実装する場合ですが、大抵のものは探せば見つかるので学習目的以外で自前実装することはおすすめしません。

最後に、説明のためにコードを細切れにしてしまったので一連のコードを載せておきます。

use std::alloc::{alloc, dealloc, Layout};
use std::ptr::{null_mut, read, write};

#[derive(Debug)]
struct Node<T> {
    value: T,
    prev: *mut Node<T>,
    next: *mut Node<T>,
}

impl<T> Node<T> {
    const LAYOUT: Layout = Layout::new::<Node<T>>();

    fn alloc(t: T) -> *mut Node<T> {
        unsafe {
            let ptr = alloc(Self::LAYOUT) as *mut Node<T>;
            write(&mut (*ptr).value, t);
            ptr
        }
    }

    fn dealloc(ptr: *mut Node<T>) -> T {
        unsafe {
            let value = read(&(*ptr).value);
            dealloc(ptr as *mut u8, Self::LAYOUT);
            value
        }
    }
}

struct List<T> {
    front: *mut Node<T>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        Self { front: null_mut() }
    }

    pub fn is_empty(&self) -> bool {
        self.front.is_null()
    }

    pub fn push_front(&mut self, t: T) {
        let n = Node::alloc(t);
        let next = self.front;
        self.front = n;
        unsafe {
            if next.is_null() {
                (*n).next = n;
                (*n).prev = n;
            } else {
                let prev = (*next).prev;
                (*n).next = next;
                (*n).prev = prev;
                (*prev).next = n;
                (*next).prev = n;
            }
        }
    }

    pub fn push_back(&mut self, t: T) {
        self.push_front(t);
        self.front = unsafe { (*self.front).next };
    }

    pub fn pop_front(&mut self) -> Option<T> {
        if self.front.is_null() {
            return None;
        }

        let n = self.front;
        unsafe {
            if (*n).next == n {
                self.front = null_mut();
            } else {
                let next = (*n).next;
                let prev = (*n).prev;
                (*prev).next = next;
                (*next).prev = prev;
                self.front = next;
            }
        }
        Some(Node::dealloc(n))
    }

    pub fn pop_back(&mut self) -> Option<T> {
        if self.front.is_null() {
            return None;
        }

        self.front = unsafe { (*self.front).prev };
        self.pop_front()
    }

    pub fn iter_mut(&mut self) -> IterMut<T> {
        let front = self.front;
        IterMut {
            _target: self,
            front: front,
            back: front,
        }
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        while !self.is_empty() {
            self.pop_front();
        }
    }
}

impl<'a, T> IntoIterator for &'a mut List<T> {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

struct IterMut<'a, T> {
    _target: &'a mut List<T>,
    front: *mut Node<T>,
    back: *mut Node<T>,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        if self.front.is_null() {
            return None;
        }

        let n = unsafe { &mut *self.front };
        if n.next == self.back {
            self.front = null_mut();
            self.back = null_mut();
        } else {
            self.front = n.next;
        };
        Some(&mut n.value)
    }
}

impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.back.is_null() {
            return None;
        }

        let n = unsafe { &mut *self.back };
        if n.prev == self.front {
            self.front = null_mut();
            self.back = null_mut();
        } else {
            self.back = n.prev;
        };
        Some(unsafe { &mut (*n.prev).value })
    }
}

impl<'a, T> std::iter::FusedIterator for IterMut<'a, T> {}

fn debug_print<T: std::fmt::Debug>(l: &List<T>) {
    let mut n = l.front;
    unsafe {
        loop {
            println!("{:?}: {:?}", n, *n);
            n = (*n).next;
            if n == l.front {
                break;
            }
        }
    }
}

#[derive(Debug)]
struct A(i32);

impl Drop for A {
    fn drop(&mut self) {
        println!("drop: {self:?}");
    }
}

fn main() {
    let mut l = List::new();
    for i in 0..10 {
        l.push_back(A(i));
    }

    for a in &mut l {
        (*a).0 += 10;
    }

    debug_print(&l);

    let mut it = l.iter_mut();
    loop {
        if let Some(i) = it.next() {
            println!("{i:?}");
        } else {
            break;
        }
        if let Some(i) = it.next_back() {
            println!("{i:?}");
        } else {
            break;
        }
    }
}
1
0
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
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?