zephyr 单链表

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

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;
}
 
static inline void  sys_sflist_insert(sys_sflist_t *list,        
                   sys_sfnode_t *prev,        
                   sys_sfnode_t *node)        
    {                                
        if (!prev) {                        
            sys_sflist_prepend(list, node);    
        } else if (!z_sfnode_next_peek(prev)) {    
            sys_sflist_append(list, node);       
        } else {                        
            z_sfnode_next_set(node,   z_sfnode_next_peek(prev));
            z_sfnode_next_set(prev, node);        
        }                            
    }

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 指针分别指向单向链表得头和尾

ypedef 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 不一样

//设置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);
}
 

#define Z_GENLIST_INSERT(__lname, __nname)                \
    static inline void                        \
    sys_ ## __lname ## _insert(sys_ ## __lname ## _t *list,        \
                   sys_ ## __nname ## _t *prev,        \
                   sys_ ## __nname ## _t *node)        \
    {                                \
        if (!prev) {                        \
            sys_ ## __lname ## _prepend(list, node);    \
        } else if (!z_ ## __nname ## _next_peek(prev)) {    \
            sys_ ## __lname ## _append(list, node);        \
        } else {                        \
            z_ ## __nname ## _next_set(node,        \
                z_ ## __nname ## _next_peek(prev));    \
            z_ ## __nname ## _next_set(prev, node);        \
        }                            \
    }

slist

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

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

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;