【从零开始写RTOS】内核双向链表

Posted by Sourcelink on December 16, 2019

一. 数据结构

1.1 成员

struct list_head {
	struct list_head *next, *prev;
};

示意图如下:

1.2 初始化

  • 静态初始化
#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)
  • 动态初始化
static __inline void list_head_init(struct list_head *list)
{
	list->next = list;
	list->prev = list;
}

初始化完以后的示意图如下:

PS:node不具备成员含义,在这只是表示一个节点;

二. add

  • 示意代码
static __inline void __list_add(struct list_head *new, struct list_head *prev, struct list_head *next)
{
	next->prev = new;
	new->next = next;
	new->prev = prev;
	prev->next = new;
}

static __inline void list_add(struct list_head *head, struct list_head *new)
{
	__list_add(new, head, head->next);
}

ps: 以一个初始化完的节点情况下添加一个节点,head->next == head == next->prev;

  • 执行next->prev = new;

  • 执行new->next = next;

  • 执行new->prev = prev;

  • 执行prev->next = new;

三. delete

  • 示意代码
static __inline void __list_delete(struct list_head *prev, struct list_head *next)
{
	next->prev = prev;
	prev->next = next;
}

static __inline void list_delete(struct list_head *del)
{
	__list_delete(del->prev, del->next);
}

假设链表情况如下, 删除红框节点:

  • 执行next->prev = prev;

  • 执行prev->next = next;

但是可以看到被删除的节点,prevnext还是指向原节点,但是已经在链表中被删除;

使用下面代码可以删除的同时初始化节点

static __inline void list_delete_init(struct list_head *node)
{
	list_delete(node);
	list_head_init(node);
}

四. container

#define container_of(ptr, type, member) \
	((type *)(((unsigned char *)(ptr)) - ((unsigned int)(&((type *)0)->member))))

可以根据链表节点获取到结构体的地址(变量地址)

接设有个数据结构如下:

struct test_container {
    unsigned int val;
    struct list_head slot;
    unsigned int data;
    unsigned int time;
}

exp:

struct test_container _cont;

void fun(void) {

    struct test_container *tmp_container = NULL;
    struct list_head *curr = &_cont.slot;

    tmp_container = container_of(curr,  struct test_container, slot);
}

上面的函数可以计算出tmp_container指针指向全局变量_cont;

计算偏移值大小:

根据curr传进来的值:

根据偏移值与节点地址就可以计算出结构体变量的地址(0x20008800 - 0x04)。


欢迎大家纠错讨论: Sourcelink@126.com 我的邮箱