这里我们实现双向链表。

/lib/kernel/list.h

#ifndef __LIB_KERNEL_LIST_H
#define __LIB_KERNEL_LIST_H

#include "global.h"

// 获取 member 在 struct_type结构体中的偏移量
#define offset(struct_type, member) (int) (&((struct_type*) 0)->member)

// 获取 pcb 首地址, 用 mem 当前地址 - mem偏移量, 然后强制类型转换
#define elem2entry(struct_type, struct_mem_name, elem_ptr) \
                  (struct_type*) ((int) elem_ptr - offset(struct_type, struct_mem_name))


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


/* 链表结构, 用来实现队列 */
struct list {
    // head 队首, 固定不变, 第 1 个元素为 head.next
    struct list_elem head;
    // tail 队尾, 固定不变
    struct list_elem tail;
};


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


void list_init(struct list*);

void list_insert_before(struct list_elem* before, struct list_elem* elem);

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);

void list_remove(struct list_elem* pelem);

struct list_elem* list_pop(struct list* plist);

bool list_empty(struct list* plist);

uint32_t list_len(struct list* plist);

struct list_elem* list_traversal(struct list* plist, function func, int arg);

bool elem_find(struct list* plist, struct list_elem* obj_elem);

#endif

结构体 struct list_elem，它是链表中结点的结构，这是链表的核心。

一般的链表结点中除了前驱或后继结点的指针外，还包括数据成员，即链表结点是数据的存储单元。

list 是定义双向链表的结构体，链表都有访问的起始入口，我们这里定义首尾两个入口，用head 表示链表开头，tail表示链表结尾， head和tail的数据类型都是struct list_elem，head. next是链表中第1个元素结点， tail. prev是链 表中最后一个元素结点。

文件开头定义的两个宏elem2entry和offset，这是为了将结点元素转换成实际元素项。

list.c中用到了关中断的函数intr_disable，系统中有些数据是公共资源，对于它的修改应该保证是原子操作。将来的进程调度机制依靠时钟中断，此处把中断关闭，就避免了在检索位图时被换下CPU的可能。所以，一定要保证是在关中断的情况下进行。实现原子操作，关中断只是一种方式，将来会用锁来保证。

/lib/kernel/list.c代码如下：

#include "list.h"
#include "interrupt.h"
#include "stdint.h"
#include "string.h"

/*初始化双向链表list*/
void list_init(struct list* list){
    list->head.prev = NULL;
    list->head.next = &list->tail;  //list->tail.prev表示访问链表尾节点的prev指针。而&list->head表示获取链表头节点的地址。
    list->tail.prev = &list->head;
    list->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;
    elem->prev = before->prev;
    elem->next = before;
    before->prev = elem;

    intr_set_status(old_status);    //恢复中断
}

/*添加元素到队列队首，类似栈push操作*/
void list_push(struct list* plist,struct list_elem* elem){
    list_insert_before(plist->head.next,elem);
}

/*追加元素到链表队尾，类似队列的先进先出操作*/
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);
}

/*将链表的第一个元素弹出并返回，类似栈的pop操作*/
struct list_elem* list_pop(struct list* plist){
    struct list_elem* elem = plist->head.next;
    list_remove(elem);
    return elem;
}

/*从链表中查找元素obj_elem，成功返回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;
}

/*把列表plist中的每个元素elem和arg传给回调函数func，
arg给func用来判断elem是否符合条件
本函数的功能是遍历列表内所有元素，逐个判断是否有符合条件的元素
找到符合条件的元素返回元素指针，否则返回NULL*/
struct list_elem* list_traversal(struct list* plist,function func,int arg){
    if(list_empty(plist))
        return NULL;
    struct list_elem* elem = plist->head.next;
    while (elem != &plist->tail){
        if(func(elem,arg))
            return elem;
        elem = elem->next;
    }
    return NULL;
}

/*返回链表长度*/
uint32_t list_len(struct list* plist){
    uint32_t length = 0;
    struct list_elem* elem = plist->head.next;
    while(elem != &plist->tail){
        length++;
        elem = elem->next;
    }
    return length;
}

/*判断链表是否为空*/
bool list_empty(struct list* plist){
    return (plist->head.next == &plist->tail ? true : false);
}

函数list_init只接受一个参数list，功能是初始化双向链表list。 此时链表是空的，因此函数内部的初始化工作就是把表头head和表尾tail连接起来，即”list->head.next= &list->tail”和”list->tail. prev = &list->head”。

函数list_insert_before接受两个参数，before和elem，它们皆为链表结点的指针，此函数功能是把链表元素 elem 插入在元素 before 之前。 由于队列是公共资源，对于它的修改一定要保证为原子操作，所以通过 intr_disable将中断关闭，旧中断状态用变量old_status保存，以此保证下面的4个操作的原子性(不可拆分、连续性)，操作结束后在通过“intr_set_status(old_status)”将中断恢复。 其他代码就是双向列表。

函数list_push接受两个参数，plist是链表，elem是链表结点，功能是添加元素elem到列表plist的队首，其实这就是栈的特性，后进先出，因此相当于用链表实现了栈。其内部是调用“list_insert_before(plist->head.next, elem)”实现的，即在队头head. next的前面插入 elem。

函数list_append接受两个参数，plist是链表，elem是链表结点，功能是添加元素elem到列表plist 的队尾，其实这就是队列的特性，先进先出，因此相当于用链表实现了线性队列。 其内部是调用”list_insert_before(&plist->tail, elem)”实现的，就是在队尾 tail 的前面插入 elem。

函数list_remove接受一个参数，链表结点pelem，功能是将pelem从链表中去除。此函数也是对链表修改，所以为了保证原子性，同样先将中断关闭，完成操作后再恢复。

函数elem_find接受两个参数，链表plist和待查找的结点obj_elem，功能是从链表plist中查找元素obj_elem，成功时返回true，失败时返回false，实现原理是把链表的第一个结点作为入口，通过while循环遍历链表中所有结点，如果找到就返回true，否则遍历完整个链表后都没有找到的话就返回false。

函数list_pop只接受一个参数，链表plist，功能是将链表plist的第一个结点弹出，类似出栈操作。

函数list_traversal接受三个参数，链表plist、回调函数func及回调函数的参数arg，功能是遍历列表内所有元素，逐个判断是否有符合“条件”的元素结点，找到符合条件的结点返回结点指针，否则返回NULL，其中的”条件”是由回调函数func来判断的，如果条件成立， func(arg)会返回true，否则会返回false，内部实现也是遍历所有结点，用变量elem保存每一个结点，对各个结点都调用”func(elem, arg)”，如果func返回true，则表示找到了目标结点，不再继续遍历，通过return elem返回找到的结点指针。否则整个链表遍历结束也没有找到符合条件的结点时就返回NULL。

函数list_len只接受一个参数，链表plist，功能是返回链表长度，即链表中结点的个数。实现原理也是通过循环遍历所有结点，用变量length计数，最后再将计数返回。

函数list_empty只接受一个参数，链表plist，功能是判断链表plist是否为空，空时返回true，否则返回false，其内部实现较直接，就一句代码，即”return (plist->head.next==&plist->tail ? true : false)”，原理是判断链表plist第一个结点是否指向链表plist的尾。

参考

郑钢著操作系统真象还原

田宇著一个64位操作系统的设计与实现

丁渊著ORANGE’S：一个操作系统的实现