os_kernel/lib/kernel/list.h

// 双向链表结构
#ifndef __LIB_KERNEL_LIST_H
#define __LIB_KERNEL_LIST_H
#include "../stdint.h"

#define offset(struct_type, member) (int)(&((struct_type *)0)->member)

#define node2entry(struct_type, struct_member_name, node_ptr) \
    (struct_type *)((int)node_ptr - offset(struct_type, struct_member_name))

// 链表节点, 节点中不需要数据成员, 只要求前驱和后继指针
struct list_elem
{
    struct list_elem *prev; // 前驱节点
    struct list_elem *next; // 后继节点
};

// 链表结构, 用来实现队列
struct list
{
    struct list_elem head; // 链表头, 链表起始元素, 不是第一个元素
    struct list_elem tail; // 链表尾, 链表终止元素, 不是最后一个元素
};

// 自定义函数类型 trav_func, 用于在list_traversal中做回调函数
typedef bool trav_func(struct list_elem *, int arg);

/****************************** function声明 ******************************/
// 初始化双向链表list
void list_init(struct list *);
// 将链表元素elem 插入在元素before之前
void list_insert_before(struct list_elem *before, struct list_elem *elem);
// 将元素elem添加到链表plist队首,类似栈push操作
void list_push(struct list *plist, struct list_elem *elem);
void list_iterate(struct list *plist);
void list_append(struct list *plist, struct list_elem *elem);
// 从链表中删除元素pelem
void list_remove(struct list_elem *pelem);
// 将链表第一个元素弹出并返回
struct list_elem *list_pop(struct list *plist);
// 判断链表是否为空,空返回true,否则返回false
bool list_empty(struct list *plist);
// 返回链表长度
uint32_t list_len(struct list *plist);
// 把列表plist中的每个元素elem和arg传给func,
// func 判断是否符合条件
// 如果找到符合条件的元素返回元素指针，否则返回NULL
struct list_elem *list_traversal(struct list *plist, trav_func func, int arg);
// 查找元素是否在链表中,成功返回true,失败返回false
bool elem_find(struct list *plist, struct list_elem *obj_elem);
/****************************** function声明  END ******************************/

#endif // __LIB_KERNEL_LIST_H