zephyr_03_slist

zephyr单向链表

zephyr链表使用静态内联函数, 只有 .h 文件, 没有对应的 .c 文件.

slist.h 位于 /${ZEPHYR_BASE}/include/misc/slist.h

链表定义

#节点定义, 此处添加节点的数据
struct _snode {
    struct _snode *next;
};

#链表定义, 链表头、尾指针
struct _slist {
    sys_snode_t *head;
    sys_snode_t *tail;
};

#重定义节点类型, 兼容之前的定义
typedef struct _snode sys_snode_t;
typedef struct _slist sys_slist_t;

常用链表函数

• 初始化链表

# 将头尾指针置为空
static inline void sys_slist_init(sys_slist_t *list)
{
    list->head = NULL;   
    list->tail = NULL;
}

• 判断链表是否为空

#True: 链表为空, False: 链表不为空 
static inline bool sys_slist_is_empty(sys_slist_t *list)
{
    return (!list->head);
}

• 返回链表头/尾节点

#返回头结点的指针
static inline sys_snode_t *sys_slist_peek_head(sys_slist_t *list)
{
    return list->head;
}

#返回尾结点的指针
static inline sys_snode_t *sys_slist_peek_tail(sys_slist_t *list)
{
    return list->tail;
}

• 返回当前节点的下一个节点

#Note: 此函数速度快, 如不确定函数是否为空，则使用 sys_slist_peek_next()函数
static inline sys_snode_t *sys_slist_peek_next_no_check(sys_snode_t *node)
{
    return node->next;
}

#函数会检测链表是否为空
static inline sys_snode_t *sys_slist_peek_next(sys_node_t * node)
{
    return node ? sys_slist_peek_next_no_check(node) : NULL;
}

• 添加节点到链表头/尾

#表头前插节点
static inline void sys_slist_prepend(sys_slist_t *list, sys_snode_t *node)
{
    node->next = list->head;      #将该节点的next域指向链表头
    list->head = node;            #将该节点设置为头结点

    if (!list->tail)              #链表为空, 则需要将尾重新指向新表头
    {
        list->tail = list->head;  #表尾指向新表头
    }
}

#表尾后插节点
static inline void sys_slist_append(sys_slist_t *list, sys_snode_t *node)
{
    node->next = null; #该节点添加于链表尾, 则它后面没有节点, 需要置空
    if (!list->tail)   #链表为空, 则需将首尾节点均指向该节点
    {
        list->tail = node;
        list->head = node;
    }
    else               #链表不为空, 则将链表尾指向的下一个节点指向该节点, 同时将链表尾指针指向该节点
    {
        list->tail->next = node;
        list->tail = node;
    }
}

• 在原链表尾部添加链表/合并链表

#原链表后插链表
static inline void sys_slist_append_list(sys_slist_t *list, void *head, void *tail)
{
   if (!list->tail)    #链表为空, 则直接将首尾指针赋值为新加链表
   {
       list->head = (sys_snode_t *)head;
       list->tail = (sys_snode_t *)tail;
   }
   else                #链表不为空, 则将其头添加到原链表尾, 同时将原链表尾指向新加链表尾
   {
       list->tail->next = (sys_snode_t *)head;
       list->tail = (sys_snode_t *)tail;
   }
}

#合并链表, 后插链表后, 再将其清空
static inline void sys_slist_merge_slist(sys_slist_t *list, sys_slist_t *list_to_append)
{
    sys_slist_append_list(list, list_to_append->head, list_to_append->tail);
    sys_slist_init(list_to_append);
}

• 指定节点后插入节点

static inline void sys_slist_insert(sys_slist_t *list, sys_snode_t *prev, sys_snode_t *node)
{
    if (!prev)   #指定节点为头节点 则添加到链表头
    {
        sys_slist_prepend(list, node);
    }
    else if (!prev->next)     #指定节点为尾节点, 则添加到链表尾
    {
        sys_slist_append(list, node);
    }
    else     #添加到指定节点后
    {
        node->next = prev->next;
        prev->next = node;
    }
}

• 移除头节点(链表头)

#Note: 调用该函数时, 必须确保链表不为空
static  inline sys_snode_t *sys_slist_not_empty(sys_slist_t *list)
{
    sys_snode_t *node = list->head;     #保存链表头

    list->head = node->next;    #将原链表头的地址复为新链表头
    if (list->tail == node)     #链表只有一个节点, 去掉之后需要更新链表尾
    {
        list->tail = list->head;
    }

    return node;            #返回头节点指针
}

#移除头结点, 空链表将会返回NULL
static inline sys_snode_t *sys_slist_get(sys_slist_t *list)
{
    return sys_slist_empty(list) ? NULL : sys_slist_get_not_empty(list);
}

• 移除指定节点的后一个节点

static inline void sys_slist_remove(sys_slist_t *list, sys_snode_t *prev_node, sys_snode_t *node)
{
    if (!prev_node)     #指定节点为空, 即删除头节点, 将删除节点的下一个节点置为头结点
    {
        list->head = node->next;

        if (list->tail == node)    #链表只有一个节点,  删除该节点前, 需要将尾指针指向头指针
        {
            list->tail = list->head;
        }
    }          
    else     #指定节点不为空, 将指定节点的下一个节点指向删除节点的下一个节点
    {
        prev_node->next = node->next;

        if (list->tail == node)   #删除节点为尾节点, 则将尾指针指向赋值为指定节点
        {
            list->tail = prev_node;
        }
    }

    node->next = NULL;
}

• 从链表找到并移除一个节点

#删除节点存在, 删除并返回True, 未找到则返回False
static inline bool sys_slist_find_and_remove(sys_slist_t *list, sys_snode_t *node)
{
    sys_snode_t *prev = NULL;
    sys_snode_t *test;

    SYS_SLIST_FOR_EACH_NODE(list, test)    #宏定义,用于遍历列表

        if (test == node)   #找到要删除的节点, 调用方法删除, 并返回True
        {
            sys_slist_remove(list, prev, node);
            return true;
        }

        prev = test;   #循环条件, 依次往后遍历链表
    }

    return false;    #未找到删除节点, 返回False
}



#遍历列表宏定义 <使用方法如上所示>
#defiune SYS_SLIST_FOR_EACH_NODE(__s1, __sn)       \
    for (__sn = sys_slist_peek_head(__s1); __sn; __sn = sys_slist_peek_next(__sn))