单项链表 链接到标题

Zephyr 单向链表实现在下列文件中：zephyr/include/zephyr/sys/slist.h。

Zephyr 以 sys_slist_t 存储单向链表数据 ( 即每个链表元素存储指向下一个元素的指针，而不是前一个元素的数据 ) 。

/** @cond INTERNAL_HIDDEN */
struct _slist {
    sys_snode_t *head;
    sys_snode_t *tail;
};

/** Single-linked list structure. */
typedef struct _slist sys_slist_t;

这种结构可以对链表的第一个 ( head ) 和最后一个 ( tail ) 元素进行 O ( 1 ) 访问:

  • 在链表的头部前或尾部后插入
  • 删除 head 头部

删除/插入指定节点，需要从头遍历链表节点，其时间复杂度为 O ( n ) 。

Zephyr 以 sys_snode_t 存储单向链表的节点，内部只含有一个指向下一个节点的指针：

struct _snode {
    struct _snode *next;
};
/** @endcond */

/** Single-linked list node structure. */
typedef struct _snode sys_snode_t;

节点空间应该由用户分配，通常是嵌入到用户容器节点的结构中，例如用户有一组 void *data 的数据想以单链表的形式组织起来，需要定义用户节点结构

struct container_node {
    sys_snode_t node;
    void *data;
};

struct container_node *msg = malloc ( sizeof ( struct container_node )) ;

通过访问用户节点成员 msg->node 访问链表节点，当有链表节点 node 时 可以使用 SYS_SLIST_CONTAINER 获取用户节点:

sys_snode_t *list_node = sys_slist_get ( &test_list ) ;
struct container_node *msg = SYS_SLIST_CONTAINER ( list_node, msg, node ) ;

单项链表及其节点的组织关系如下

初始化 链接到标题

sys_slist_t 由用户从可访问的内存中分配，通过 sys_slist_init() 或 SYS_SLIST_STATIC_INIT 的静态赋值进行初始化。sys_slist_t 其内部字段对用户不透明，不应由用户代码访问。

static sys_slist_t test_list;

sys_slist_init(&test_list);

或者

static sys_slist_t test_list = SYS_SLIST_STATIC_INIT(&test_list);

操作 链接到标题

节点增删 链接到标题

  • sys_slist_prepend() 在链表头部添加节点
  • sys_slist_append() 在链表尾部添加节点
  • sys_slist_insert() 在链表中指定节点后插入新节点
  • sys_slist_remove() 删除指定节点后的节点
  • sys_slist_find_and_remove() 删除指定节点
static struct container_node test_node_1;
static struct container_node test_node_2;
static struct container_node test_node_3;
static struct container_node test_node_4;

//test_node_1 ( head/tail )
sys_slist_prepend ( &test_list, &test_node_1.node ) ;

//test_node_1 ( head ) ->test_node_2 ( tail )
sys_slist_append ( &test_list, &test_node_2.node ) ;

//test_node_1 ( head ) ->-test_node_3>test_node_2 ( tail )
sys_slist_insert ( &test_list, &test_node_1.node, &test_node_3.node ) ;

//test_node_1 ( head ) ->test_node_4->test_node_3->test_node_2 ( tail )
sys_slist_insert ( &test_list, &test_node_1.node, &test_node_4.node ) ;

//test_node_1 ( head ) ->test_node_4->test_node_2 ( tail )
sys_slist_remove ( &test_list, &test_node_4.node, &test_node_3.node ) ;

//test_node_1 ( head ) ->test_node_2 ( tail )
sys_slist_find_and_remove ( &test_list, &test_node_3.node ) ；

节点访问 链接到标题

可以使用 sys_slist_peek_head() 和 sys_slist_peek_tail() peek 头和尾节点，sys_slist_peek_next() peek 指定节点的下一个节点，如果列表为空，则返回 NULL，否则返回指向 sys_snode_t 的指针。

//假设链表为 test_node_1 ( head ) ->test_node_4->test_node_3->test_node_2 ( tail )
//hnode = test_node_1
sys_snode_t *hnode = sys_slist_peek_head ( list ) ;

//tnode = test_node_2
sys_snode_t *tnode = sys_slist_peek_tail ( list ) ;

//nnode = test_node_4
sys_snode_t *nnode = sys_slist_peek_next ( &test_node_1.node ) ;

slist 另外提供了一组「for each」宏，允许直接遍历单项链表，无需手动遍历下一个指针。 SYS_SLIST_FOR_EACH_NODE 将枚举链表中的每个节点，给定一个局部变量来存储节点指针。 SYS_SLIST_FOR_EACH_NODE_SAFE 行为类似，但需要额外的暂存变量进行节点存储，这样做可以允许用户在遍历期间删除被遍历的节点。这两个宏存在对应的「CONTAINEROF」变体 ( SYS_SLIST_FOR_EACH_CONTAINER 和 SYS_SLIST_FOR_EACH_CONTAINER_SAFE ) 中，该变体分配一个与用户定义的容器结构局部变量，在内部执行所需的偏移量。SYS_SLIST_FOR_EACH_NODE 是从链表的头开始遍历所有链表，而 SYS_SLIST_ITERATE_FROM_NODE 可以从指定节点开始遍历链表。通常情况下我们都是用用户容器节点

struct container_node *cnode;
struct container_node *s_cnode;

//参数：链表 ( test_list ) ， 容器节点执政 ( cnode ) ， 链表在节点容器结构中的名称 ( node, 参考 struct container_node )
SYS_SLIST_FOR_EACH_CONTAINER ( test_list, cnode, node ) {
        //修改节点内容
    }

//参数：链表 ( test_list ) ， 容器节点执政 ( cnode ) ，容器安全节点指针 ( s_cnode ) ， 链表在节点容器结构中的名称 ( node, 参考 struct container_node )
SYS_SLIST_FOR_EACH_CONTAINER_SAFE ( test_list, cnode, s_cnode, node ) {
    //删除节点
    sys_slist_find_and_remove ( &test_list, &cnode-》node ) ；
    }

在使用 SYS_SLIST_FOR_EACH_CONTAINER_SAFE 宏时，可以通过额外的 s_cnode 来保存下一个节点的引用。这样在删除当前节点后，仍然可以安全地访问并遍历下一个节点，而不会影响遍历的正确性。而在使用 SYS_SLIST_FOR_EACH_CONTAINER 宏时，删除当前节点会导致遍历过程出错，因为没有保存下一个节点的引用。

链表操作 链接到标题

链表 list 是否为空

static inline bool sys_slist_is_empty ( sys_slist_t *list ) ;

将一条 ( 头尾分别为 head,tail ) 链表添加到 list 的后面

static inline void sys_slist_append_list ( sys_slist_t *list,
                     void *head, void *tail ) ;

将 sys_slist_merge_slist 添加到 list 后面

static inline void sys_slist_merge_slist ( sys_slist_t *list,
                     sys_slist_t *list_to_append ) ;

获取 list 中节点的数量

static inline size_t sys_slist_len ( sys_slist_t *list ) ;

带符号单向链表 链接到标题

带符号链表 sys_sflist_t 实现在 zephyr/include/zephyr/sys/sflist.h, 其原理和普通单向链表 sys_slist_t 一样，区别在于带符号链表，可以设置 2bit 的符号。Zephyr 都是针对 32 位及上的 soc，因此为节点分配出来的内存至少都是 4 字节对齐，因此对于一个节点指针，低 2 位是没有实际作用的，带符号链表就是将这没有用处的 2 位利用起来作为符号位。

# ifdef __LP64__
typedef uint64_t unative_t;
# else
typedef uint32_t unative_t;
# endif

/** @cond INTERNAL_HIDDEN */
struct _sfnode {
    unative_t next_and_flags;
};
/** @endcond */

/** Flagged single-linked list node structure. */
typedef struct _sfnode sys_sfnode_t;

# define SYS_SFLIST_FLAGS_MASK    0x3UL

通过 sys_sfnode_flags_get 和 sys_sfnode_flags_set 来操作符号位， 通过 z_sfnode_next_peek 来取得下一个节点的地址。

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

static inline uint8_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 ) ;
}

参考 链接到标题

https://docs.zephyrproject.org/3.5.0/kernel/data_structures/slist.html