组件linked_list - 侵入式链表

第六节组件 linked_list - 侵入式链表

链表是十分常用的数据结构，从实现方式上大致可以分成两类：

左侧 - 普通链表：每个节点都占用独立的内存，包含指向数据块的指针，例如 Rust 标准库中提供的 LinkedList 类型。
右侧 - 侵入式链表：节点直接存在于目标数据块中，节点本身不需要单独申请内存，这种链表常用于维护空闲块。

本节我们来实现侵入式链表，它在后面内核的开发中非常重要，比如下一章中，我们就会把它作为实现 buddy 内存分配器的基础。

我们的侵入式链表的实现参考了 Sergio Benitez 的工作成果，见 CS140e

// buddy_allocator/src/linked_list.rs
#![no_std]

use core::marker::PhantomData;
use core::ptr;

#[derive(Copy, Clone)]
pub struct LinkedList {
    head: *mut usize,
}

unsafe impl Send for LinkedList {}

impl LinkedList {
    pub const fn new() -> LinkedList {
        LinkedList {
            head: ptr::null_mut(),
        }
    }
    pub fn is_empty(&self) -> bool {
        self.head.is_null()
    }
}

第 9 行：链表本身只有一个成员 head，它指向第一个节点，各节点之间通过指针关联。这方面仍然是典型链表的实现。

// buddy_allocator/src/linked_list.rs
impl LinkedList {
    pub unsafe fn push(&mut self, item: *mut usize) {
        *item = self.head as usize;
        self.head = item;
    }
    pub fn pop(&mut self) -> Option<*mut usize> {
        match self.is_empty() {
            true => None,
            false => {
                let item = self.head;
                self.head = unsafe { *item as *mut usize };
                Some(item)
            }
        }
    }
}

第 3~6 行：push 操作是把新的节点插入到链表的开头。

第 7~17 行：pop 操作先处理链表空的情况；然后如果链表不空，就把第一个节点摘出并返回。

综合来看，push/pop 都是针对链表头这端，即后入先出，该链表相当于栈。

下面为链表实现只读和可修改的迭代器：

// buddy_allocator/src/linked_list.rs
impl LinkedList {
    pub fn iter(&self) -> Iter {
        Iter {
            curr: self.head,
            list: PhantomData,
        }
    }
    pub fn iter_mut(&mut self) -> IterMut {
        IterMut {
            prev: &mut self.head as *mut *mut usize as *mut usize,
            curr: self.head,
            list: PhantomData,
        }
    }
}

第 3~8 行：Iter 迭代器比较简单，只需要一个指向当前位置的指针。

第 9~15 行：IterMut 的迭代器，需要支持把节点弹出链表的操作，为此，除了当前位置指针，还需要前一个节点的指针 prev - 即指向当前位置指针的指针，这样通过简单的修改 prev 就能从链表中删除掉当前节点。

Iter 迭代器的实现：

// buddy_allocator/src/linked_list.rs
pub struct Iter<'a> {
    curr: *mut usize,
    list: PhantomData<&'a LinkedList>,
}
impl<'a> Iterator for Iter<'a> {
    type Item = *mut usize;

    fn next(&mut self) -> Option<Self::Item> {
        if self.curr.is_null() {
            None
        } else {
            let item = self.curr;
            let next = unsafe { *item as *mut usize };
            self.curr = next;
            Some(item)
        }
    }
}

IterMut 迭代器的实现：

// buddy_allocator/src/linked_list.rs
pub struct IterMut<'a> {
    list: PhantomData<&'a mut LinkedList>,
    prev: *mut usize,
    curr: *mut usize,
}
impl<'a> Iterator for IterMut<'a> {
    type Item = ListNode;

    fn next(&mut self) -> Option<Self::Item> {
        if self.curr.is_null() {
            None
        } else {
            let res = ListNode {
                prev: self.prev,
                curr: self.curr,
            };
            self.prev = self.curr;
            self.curr = unsafe { *self.curr as *mut usize };
            Some(res)
        }
    }
}

pub struct ListNode {
    prev: *mut usize,
    curr: *mut usize,
}
impl ListNode {
    pub fn pop(self) -> *mut usize {
        unsafe {
            *(self.prev) = *(self.curr);
        }
        self.curr
    }
    pub fn value(&self) -> *mut usize {
        self.curr
    }
}

第 25~39 行：IterMut 迭代器需要额外定义一个辅助类型 ListNode。

现在我们可以编写一组测试用例，验证侵入式链表的功能：

#[test]
fn test_linked_list() {
    let mut value1: usize = 0;
    let mut value2: usize = 0;
    let mut value3: usize = 0;
    let mut list = linked_list::LinkedList::new();
    unsafe {
        list.push(&mut value1 as *mut usize);
        list.push(&mut value2 as *mut usize);
        list.push(&mut value3 as *mut usize);
    }

    assert_eq!(value3, &value2 as *const usize as usize);
    assert_eq!(value2, &value1 as *const usize as usize);
    assert_eq!(value1, 0);

    let mut iter = list.iter();
    assert_eq!(iter.next(), Some(&mut value3 as *mut usize));
    assert_eq!(iter.next(), Some(&mut value2 as *mut usize));
    assert_eq!(iter.next(), Some(&mut value1 as *mut usize));
    assert_eq!(iter.next(), None);

    let mut iter_mut = list.iter_mut();
    assert_eq!(iter_mut.next().unwrap().pop(), &mut value3 as *mut usize);
    assert_eq!(list.pop(), Some(&mut value2 as *mut usize));
    assert_eq!(list.pop(), Some(&mut value1 as *mut usize));
    assert_eq!(list.pop(), None);
}

执行 make test，看到测试用例执行结果，验证成功！

ArceOS Tutorial Book

第六节 组件 linked_list - 侵入式链表

第六节组件 linked_list - 侵入式链表