侵入式链表实现

先来看2个宏

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

假设：
struct Foo
{
    int a;
    int b;
    Foo* next;
};

offset(struct Foo, a);    // 0
offset(struct Foo, b);    // 4
offset(struct Foo, next); // 8 

offset 宏的目的是推算出一个成员的偏移量。

Foo.png

(struct_type*)0 将0x0 强制转为struct_type的首地址。
((struct_type*)0)->member)为目标成员。
(int)(&((struct_type*)0)->member))将目标成员取地址，因为是从0x0开始，所以这个地址也就恰好成为了目标成员的偏移地址。

#define elem2entry(struct_type, struct_member_name, elem_ptr) \
     (struct_type*)((int)elem_ptr - offset(struct_type, struct_member_name))

假设：
struct link 
{
    struct link* next;
};

struct Foo
{
    int a; 
    struct link link_tag;
};

struct Foo foo;
foo.a = 20; foo.link_tag.next = NULL;
    
struct link* linkptr = &(foo.link_tag);
 
struct Foo* fp = elem2entry(struct Foo, link_tag, linkptr);
   
printf("%d\n", fp->a);

image.png

struct list_elem
{
    struct list_elem* prev;
    struct list_elem* next;
};

/* 实现队列 */
struct list
{
    struct list_elem head;  // head 队首，固定不变. 第一个元素是head.next
    struct list_elem tail;  // tail 队尾，固定不变.
};

• 初始化双向链表

/* 初始化双向链表 */
void list_init(struct list* list)
{
    list->head.prev = NULL;
    list->head.next = &(list->tail);
    list->tail.prev = &(list->head);
    list->tail.next = NULL;
}

image.png

• 把elem插入在元素before之前

void list_insert_before(struct list_elem* before, struct list_elem* elem)
{
    before->prev->next = elem;

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

    before->prev = elem;
}

/* 添加元素到列表队首,类似push_front操作 */
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脱离链表

/* 使元素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;
}