os_kernel/lib/kernel/list.c

#include "list.h"
#include "../../kernel/interrupt.h"

// 初始化双向链表list
void list_init(struct list *plist)
{
    plist->head.prev = NULL;
    plist->head.next = &plist->tail;
    plist->tail.prev = &plist->head;
    plist->tail.next = NULL;
}
// 将链表元素elem 插入在元素before之前
void list_insert_before(struct list_elem *before, struct list_elem *elem)
{
    enum intr_status old_status = intr_disable(); // 关中断

    before->prev->next = elem; // before 暂时脱离链表

    elem->prev = before->prev;
    elem->next = before;

    before->prev = elem; // before重新回到链表

    intr_set_status(old_status); // 恢复中断
}
// 将元素elem添加到链表plist队首,类似栈push操作
void list_push(struct list *plist, struct list_elem *elem)
{
    list_insert_before(plist->head.next, elem); // 在队头插入elem
}
void list_iterate(struct list *plist);
// 添加元素到链表队尾
void list_append(struct list *plist, struct list_elem *elem)
{
    list_insert_before(&plist->tail, elem); // 在队尾的前面插入
}
// 从链表中删除元素pelem
void list_remove(struct list_elem *pelem)
{
    enum intr_status old_status = intr_disable(); // 关中断

    pelem->prev->next = pelem->next;
    pelem->next->prev = pelem->prev;

    intr_set_status(old_status); // 恢复中断
}
// 将链表第一个元素弹出并返回
struct list_elem *list_pop(struct list *plist)
{
    struct list_elem *elem = plist->head.next;
    list_remove(elem);
    return elem;
}
// 判断链表是否为空,空返回true,否则返回false
bool list_empty(struct list *plist)
{
    return (plist->head.next == &plist->tail ? true : false);
}
// 返回链表长度
uint32_t list_len(struct list *plist)
{
    struct list_elem *elem = plist->head.next;
    uint32_t length = 0;
    while (elem != &plist->tail)
    {
        length++;
        elem = elem->next;
    }
    return length;
}
// 把列表plist中的每个元素elem和arg传给func,
// func 判断是否符合条件
// 如果找到符合条件的元素返回元素指针，否则返回NULL
struct list_elem *list_traversal(struct list *plist, trav_func func, int arg)
{
    struct list_elem *elem = plist->head.next;

    // 如果链表为空,直接返回NULL
    if (list_empty(plist))
    {
        return NULL;
    }

    while (elem != &plist->tail)
    {
        if (func(elem, arg))
        {
            // func返回true,直接返回元素指针
            return elem;
        }
        elem = elem->next;
    }
    return NULL;
}
// 查找元素是否在链表中,成功返回true,失败返回false
bool elem_find(struct list *plist, struct list_elem *obj_elem)
{
    struct list_elem *elem = plist->head.next;
    while (elem != &plist->tail)
    {
        if (elem == obj_elem)
        {
            return true;
        }
        elem = elem->next;
    }
    return false;
}