Zephyr链表简介

Creative Commons
本作品采用知识共享署名
发表于 | 分类于 | | 阅读次数：

本文简单介绍Zephyr的链表的分类和区别,不涉及具体操作.

概述

任何一个操作系统的实现都会大量使用到链表，因此在代码实现级别上链表都会被独立成一个模块方便共用。这一点在zephyr上也一样.
zephyr的提供单向链表和双向链表的实现，均放在include/sys/下的头文件内，链表使用宏和函数操作，函数是static定义在头文件中，所以不同的moudle都有自己的链表代码。

单向链表

单向链表分为两种，一种是普通的单向链表，一种是带flag的单向链表

slist

Single-linked list，源文件在include/sys/slist.h

数据结构

每个节点sys_snode_t只含有指向下一个节点的指针next
链表sys_slist_t包含两个sys_snode_t指针分别指向单向链表得头和尾

1
2
3
4
5
6
7
8
9
10
11
12
struct _snode {
	struct _snode *next;
};

typedef struct _snode sys_snode_t;

struct _slist {
	sys_snode_t *head;
	sys_snode_t *tail;
};

typedef struct _slist sys_slist_t;

sflist

flag Single-linked list，源文件在include/sys/sflist.h
sflist也是一个单链表，和flist唯一不同的是该链表的每个节点可以记录一个flag

数据结构

每个节点sys_sfnode_t只含next_and_flags, 对于32/64位系统上结构体会默认4字节对齐，因此指针最低的2位可以被忽略，被用借用做为flag
链表sys_sflist_t包含两个sys_sfnode_t指针分别指向单向链表得头和尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef u32_t unative_t;

struct _sfnode {
	unative_t next_and_flags;
};

typedef struct _sfnode sys_sfnode_t;

struct _sflist {
	sys_sfnode_t *head;
	sys_sfnode_t *tail;
};

typedef struct _sflist sys_sflist_t;

flag操作

sflist由于链表指针的最低两位被作为flag，因此对指针和flag的操作会与slist不一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define SYS_SFLIST_FLAGS_MASK	0x3UL

//设置flag
static inline void sys_sfnode_flags_set(sys_sfnode_t *node, u8_t flags)
{
	__ASSERT((flags & ~SYS_SFLIST_FLAGS_MASK) == 0UL, "flags too large");
	node->next_and_flags = (unative_t)(z_sfnode_next_peek(node)) | flags;
}

//获取flag
static inline u8_t sys_sfnode_flags_get(sys_sfnode_t *node)
{
	return node->next_and_flags & SYS_SFLIST_FLAGS_MASK;
}

//获取下一个节点的地址
static inline sys_sfnode_t *z_sfnode_next_peek(sys_sfnode_t *node)
{
	return (sys_sfnode_t *)(node->next_and_flags & ~SYS_SFLIST_FLAGS_MASK);
}

//串接两个节点, next节点会继承前一个节点的flag
static inline void z_sfnode_next_set(sys_sfnode_t *parent,
				       sys_sfnode_t *child)
{
	u8_t cur_flags = sys_sfnode_flags_get(parent);

	parent->next_and_flags = cur_flags | (unative_t)child;
}

单向链表操作差异

slist和sflist二者只有在flag上的差异，因此在节点上的操作二者都是一致的,zephyr中又抽象出了include/list_gen.h, slist和sflist关于节点的操作均是使用该头文件提供的宏生成，例如节点的插入

1
2
3
4
5
6
7
8
9
10
11
static inline void sys_sflist_insert(sys_sflist_t *list,
				     sys_sfnode_t *prev,
				     sys_sfnode_t *node);

Z_GENLIST_INSERT(sflist, sfnode)

static inline void sys_slist_insert(sys_slist_t *list,
				    sys_snode_t *prev,
				    sys_snode_t *node);

Z_GENLIST_INSERT(slist, snode)

本文不展开分析list_gen.h，有兴趣的小伙伴可以去看源代码，里面其实就是单向列表的操作。

双向链表

双向链表由头文件include/sys/dlist.h提供，数据结构如下, 一个节点含有next和prev分别指向前一个节点和后一个节点
对于头节点，前一个节点是尾节点，对于尾节点后一个节点是头节点

1
2
3
4
5
6
7
8
9
10
11
12
13
struct _dnode {
	union {
		struct _dnode *head; /* ptr to head of list (sys_dlist_t) */
		struct _dnode *next; /* ptr to next node    (sys_dnode_t) */
	};
	union {
		struct _dnode *tail; /* ptr to tail of list (sys_dlist_t) */
		struct _dnode *prev; /* ptr to previous node (sys_dnode_t) */
	};
};

typedef struct _dnode sys_dlist_t;
typedef struct _dnode sys_dnode_t;

双向链表的操作的API也实现在include/sys/dlist.h中，接收节点指针之间的操作，这里不展开了。