物联网
您现在所在的位置:首页>企业动态>物联网

深入分析Linux内核链表之带头双向循环链表

编辑:学到牛牛IT培训    发布日期: 2021-12-27 09:53:52  

上节我们对Linux内核链表的设计原理进行分析,理解了内核链表的设计的优点,并解决内核链表访问问题。本节我们主要将Linux内核中链表的实现库进行分析解释。

// 内核链表数据结构
struct list_head{
    struct list_head *next, *prev;
};
// 初始化内核链表头节点: 头结点的next,prev指针都指向自己的地址
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) 
    struct list_head name = LIST_HEAD_INIT(name)
static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

Linux内核链表分析1.png


图 1 初始化链表头节点

// 将new节点插入到prev之后,next之前
static inline void __list_add(struct list_head *new, struct list_head *prev,  struct list_head *next)
{
    next->prev = new;  // 如图2:(1)
    new->next = next;  // 如图2:(2)
    new->prev = prev;  // 如图2:(3)
    prev->next = new;  // 如图2:(4)
}
// 将new节点插入到头结点之后
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}
// 将new节点插入到头结点之前
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

Linux内核链表分析2.png


图 2 新节点插入

static inline void __list_del(struct list_head * prev, struct list_head * next)
{
    next->prev = prev;
    prev->next = next;
}
static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = LIST_POISON1;
    entry->prev = LIST_POISON2;
}

Linux内核链表分析3.png


图 3 链表节点删除

#define list_entry(ptr, type, member) 
    container_of(ptr, type, member)
// 从头到尾遍历整个链表
#define list_for_each(pos, head) 
    for (pos = (head)->next; pos != (head); pos = pos->next)
// 尾从到头遍历整个链表
#define list_for_each_prev(pos, head) 
    for (pos = (head)->prev; pos != (head); pos = pos->prev)
// 安全的从头到尾遍历整个链表:在遍历的时候可以安全的删除节点
#define list_for_each_safe(pos, n, head) 
    for (pos = (head)->next, n = pos->next; pos != (head); 
        pos = n, n = pos->next)
// 安全的从尾到头遍历整个链表:在遍历的时候可以安全的删除节点
#define list_for_each_prev_safe(pos, n, head) 
    for (pos = (head)->prev, n = pos->prev; 
        pos != (head); 
        pos = n, n = pos->prev)
// 从头到尾遍历整个链表,并用type *pos指针获取节点的首地址
#define list_for_each_entry(pos, head, member)    
    for (pos = list_entry((head)->next, typeof(*pos), member); 
        &pos->member != (head);  
        pos = list_entry(pos->member.next, typeof(*pos), member))
// 从尾到头遍历整个链表,并用type *pos指针获取节点的首地址
#define list_for_each_entry_reverse(pos, head, member)   
        for (pos = list_entry((head)->prev, typeof(*pos), member); 
        &pos->member != (head);  
        pos = list_entry(pos->member.prev, typeof(*pos), member))
测试例程(测试环境centos/ubuntu):
#include "list.h"
#include <stdio.h>
struct stu{
    int val;
    struct list_head lists;
};
int main()
{
    LIST_HEAD( head ); // 初始化头结点
    struct stu s0 = { 10, {NULL, NULL}};
    struct stu s1 = { 20, {NULL, NULL}};
    struct stu s2 = { 30, {NULL, NULL}};
    list_add( &s0.lists, &head ); // 头插法
    list_add( &s1.lists, &head );
    list_add_tail( &s2.lists, &head ); // 尾插法
    struct list_head *ptr = NULL;
     list_for_each(ptr, &head){ // 循环
        struct stu *s = list_entry( ptr, struct stu, lists ); // 获取节点地址
        printf("s->val = %d
", s->val );
    }
    struct list_head *n = NULL;
        list_for_each_safe( ptr, n, &head ){
        struct stu *s = list_entry( ptr, struct stu, lists );
        if( s->val == 20 ){
            list_del( ptr );
        }
    }
    struct stu *str = NULL;
    list_for_each_entry( str, &head, lists ){
        printf("s->val = %d
", str->val );
    }
    return 0;
}
免费试学
课程好不好,不如实地听一听

封闭学习

2

1

联系我们

电话:028-61775817

邮箱:1572396657@qq.com

地址:成都市金牛区西城国际A座8楼

  • 物联网_物联网专题新闻_物联网IOT资讯-学到牛牛
    物联网_物联网专题新闻_物联网IOT资讯-学到牛牛

    扫一扫,免费咨询

  • 物联网_物联网专题新闻_物联网IOT资讯-学到牛牛
    物联网_物联网专题新闻_物联网IOT资讯-学到牛牛

    微信公众号

  • 物联网_物联网专题新闻_物联网IOT资讯-学到牛牛
物联网_物联网专题新闻_物联网IOT资讯-学到牛牛

学一流技术,找高薪工作

物联网_物联网专题新闻_物联网IOT资讯-学到牛牛

7-24小时服务热线:

028-61775817

版权声明 网站地图

蜀ICP备2021001672号

课程问题轻松问