精华内容
下载资源
问答
  • LINUX下链表

    2014-09-05 09:13:56
    LINUX下链表,讲解了链表的创建,插入,删除等操作
  • 看了下Linux链表的实现,发现真的是把“驱动和设备分离”的思想发挥的淋漓尽致啊! 之前我写链表是这么写的: Linux链表是这样: 这两者有什么不同呢? 当然,我不是想说双向链表的事,而是指针域与数据域分离...

    你好!这里是风筝的博客,

    欢迎和我一起多多交流。

    看了下Linux链表的实现,发现真的是把“驱动和设备分离”的思想发挥的淋漓尽致啊!
    之前我写链表是这么写的:
    这里写图片描述

    Linux下链表是这样:
    这里写图片描述

    这两者有什么不同呢?
    当然,我不是想说双向链表的事,而是指针域与数据域分离的事情。
    把链表的底层实现封装起来进行屏蔽,只留出数据域。这样,当链表有改动时,只需修改数据域即可,底层链表实现不需要改动。

    Linux中的list.h文件:

    #ifndef LIST_H
    #define LIST_H
    
    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
    
    /**
     * container_of - cast a member of a structure out to the containing structure
     * @ptr:        the pointer to the member.
     * @type:       the type of the container struct this is embedded in.
     * @member:     the name of the member within the struct.
     *
     */
    #define container_of(ptr, type, member) ({                      \
            const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
            (type *)( (char *)__mptr - offsetof(type,member) );})
    
    /*指针域节点*/
    struct list_head {
            struct list_head *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;
    }
    
    /**
     * list_entry - get the struct for this entry
     * @ptr:        the &struct list_head pointer.
     * @type:       the type of the struct this is embedded in.
     * @member:     the name of the list_head within the struct.
     */
    #define list_entry(ptr, type, member) \
            container_of(ptr, type, member)
    
    /**
     * list_for_each_entry  -       iterate over list of given type
     * @pos:        the type * to use as a loop cursor.
     * @head:       the head for your list.
     * @member:     the name of the list_head within the struct.
     */
     /*遍历链表*/
    #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))
    
    /**
     * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
     * @pos:        the type * to use as a loop cursor.
     * @n:          another type * to use as temporary storage
     * @head:       the head for your list.
     * @member:     the name of the list_head within the struct.
     */
    #define list_for_each_entry_safe(pos, n, head, member)                  \
            for (pos = list_entry((head)->next, typeof(*pos), member),      \
                    n = list_entry(pos->member.next, typeof(*pos), member); \
                 &pos->member != (head);                                    \
                 pos = n, n = list_entry(n->member.next, typeof(*n), member))
    
    /**
     * list_empty - tests whether a list is empty
     * @head: the list to test.
     */
     /*链表判空*/
    static inline int list_empty(const struct list_head *head)
    {
            return head->next == head;
    }
    
    /*
     * Insert a new entry between two known consecutive entries.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
     /*链表底层实现*/
    static inline void __list_add(struct list_head *_new,
                                  struct list_head *prev,
                                  struct list_head *next)
    {
            next->prev = _new;
            _new->next = next;
            _new->prev = prev;
            prev->next = _new;
    }
    /**
     * list_add_tail - add a new entry
     * @new: new entry to be added
     * @head: list head to add it before
     *
     * Insert a new entry before the specified head.
     * This is useful for implementing queues.
     */
    static inline void list_add_tail(struct list_head *_new, struct list_head *head)
    {
            __list_add(_new, head->prev, head);
    }
    
    /*
     * Delete a list entry by making the prev/next entries
     * point to each other.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    static inline void __list_del(struct list_head *prev, struct list_head *next)
    {
            next->prev = prev;
            prev->next = next;
    }
    
    #define LIST_POISON1  ((void *) 0x00100100)
    #define LIST_POISON2  ((void *) 0x00200200)
    /**
     * list_del - deletes entry from list.
     * @entry: the element to delete from the list.
     * Note: list_empty() on entry does not return true after this, the entry is
     * in an undefined state.
     */
     /*删除节点*/
    static inline void list_del(struct list_head *entry)
    {
            __list_del(entry->prev, entry->next);
            entry->next = (struct list_head*)LIST_POISON1;
            entry->prev = (struct list_head*)LIST_POISON2;
    }
    #endif

    这里面有个很奇妙的宏:container_of
    作用是根据结构体成员的地址,得到整个结构体的地址,具体的实现方法可以自己Google下,这里不多描述。

    根据这个list.h文件,这是链表的底层实现,我们不需要更改,
    我们写链表时,直接包含这个文件即可:
    自己写的链表:
    my_list.h:

    #ifndef _MY_LIST_H
    #define _MY_LIST_H
    
    #include "list.h"
    
    typedef struct list_info
    {
            int  id;
            struct list_head list_node;
    }list_info;
    
    struct list_head * Create_list(void);
    void Add_list_node(struct list_head * head,int id );
    void list_for_each(struct list_head * head);
    void Del_list_tail(struct list_head * head);
    void Destroy_list(struct list_head * head);
    
    #endif

    my_list.c:

    #include <stdio.h>
    #include <stdlib.h>
    #include "my_list.h"
    #include "list.h"
    struct list_head * Create_list(void)
    {
             struct list_head * head = (struct list_head *)malloc( sizeof(struct list_head) );
            if(head == NULL)
                    printf("create list failed !\n");
            else 
                    INIT_LIST_HEAD(head);
            return head;
    }
    
    void Add_list_node(struct list_head * head,int id )
    {
            list_info * node = (list_info *)malloc( sizeof(list_info) );
            if(node == NULL)
                    printf("add list_node failed !\n");
            else
            {
                    node->id = id;
                    list_add_tail(&node->list_node,head);
            }
    
    
    }
    
    void list_for_each(struct list_head * head)
    {
            list_info * pos;
            list_for_each_entry(pos, head, list_node)
                    printf("list_info:%d\n",pos->id);
    }
    
    void Del_list_tail(struct list_head * head)
    {
            struct list_head *pos = head->prev;
            if(list_empty(head))
            {
                    printf("list is empyty,delete failed !");
                    return ;
            }
            list_del(pos);
            free(container_of(pos,list_info,list_node));
    }
    
    void Destroy_list(struct list_head * head)
    {
            struct list_head *pos = head->prev;
            while(pos != head)
            {
                    list_del(pos);
                    free(container_of(pos,list_info,list_node));
                    pos = head->prev;
            }
    }

    main.c:

    #include "my_list.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
            struct list_head * head;
    
            head = Create_list();
            Add_list_node(head,5 );
            Add_list_node(head,6 );
            Add_list_node(head,7 );
            printf("list node info :\n");
            list_for_each(head);
            printf("then delete list tail node info :\n");
            Del_list_tail(head);
            list_for_each(head);
    
            Destroy_list(head);
            return 0;
    }

    运行结果:
    这里写图片描述

    展开全文
  • 在上一篇我们介绍了内核下链表的基本原理,接下来从应用角度出发介绍常用的接口函数。 1.1container_of /* 原型 */ #define container_of(ptr, type, member) /* 功能 */ 已知某一个成员变量的名字、指针和...

     在上一篇我们介绍了内核下链表的基本原理,接下来从应用角度出发介绍常用的接口函数。

     

    1.1 container_of

    /* 原型 */  
    #define container_of(ptr, type, member) 
    
    /* 功能 */
    已知某一个成员变量的名字、指针和结构体类型的情况下,计算结构体的指针,也就是计算结构体的起始地址。
    
    /* 参数 */
    ptr:   某一个成员的指针
    type:  结构体类型
    member:成员变量名字

     

    1.2 offsetof

    /* 原型 */
    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
    
    /* 功能 */
    在已知某一个成员变量的名字和结构体类型的情况下,计算该成员相对于结构体的起始地址的偏移量
    
    /* 参数 */
    TYPE:  结构体类型名称
    MEMBER:结构体中成员
    
    /* 返回 */
    该成员相对于结构体的起始地址的偏移量

     

    1.3 LIST_HEAD_INIT

    /* 原型 */
    #define LIST_HEAD_INIT(name) { &(name), &(name); }
    
    /* 功能 */
    初始化一个结点名字为name的双向循环链表的头结点
    
    /* 参数 */
    name:结点名字

     

    1.4 LIST_HEAD

    /* 原型 */
    #define LIST_HEAD(name)
    
    /* 功能 */
    初始化一个结点名字为name的双向循环链表的头结点
    
    /* 参数 */
    name:结点名字

     

    1.5  INIT_LIST_HEAD

    /* 原型 */
    static inline void INIT_LIST_HEAD(struct list_head *list)
    
    /* 功能 */
    初始化一个结点名字为name的双向循环链表的头结点
    
    /* 参数 */
    list:结点名字

     

    1.6 list_add

    //原型
    static inline void list_add(struct list_head *new, struct list_head *head)
    
    //功能
    添加结点new到链表头
    
    //参数
    new:新的结点
    head:链表头

     

    1.7 list_add_tail

    //原型
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    
    //功能
    添加结点new到链表尾
    
    //参数
    new:新的结点
    head:链表头

     

    1.8 list_del 

    //原型
    static inline void list_del(struct list_head *entry)
    
    //功能
    删除结点entry,将entry的prev指向LIST_POISON1,next指向LIST_POISON2.
    
    //参数
    entry:被删除结点
    
    //说明
    指向LIST_POISON不会引起缺页错误。
    

     

    1.9 list_move

    //原型
    static inline void list_move(struct list_head *list, struct list_head *head)
    
    //功能
    先将list节点从原链表中删除,然后将其添加到head链表的表头
    
    //参数
    list:移除结点
    head:链表表头。

     

    1.10 list_empty

    //原型
    static inline int list_empty(const struct list_head *head)
    
    //功能
    判断head链表是否为空链表,是返回1,否则返回为0;
    
    //参数
    head:链表表头。
    
    //返回
    0或1

     

    1.11 list_entry

    //原型
    #define list_entry(ptr, type, member)
    
    //功能
    获取type类型结构体的起始指针
    
    //参数
    ptr:type类型的结构体中member成员的指针
    type:结构体类型
    member:结构体中成员
    
    //返回
    结构体的起始指针

     

    1.12 list_for_each

    //原型
    #define list_for_each(pos, head)
    
    //功能
    从head节点开始(不包括head节点!)遍历它的每一个节点!
    
    //参数
    pos:循环指针
    head:链表头

     

    1.13 list_for_each_safe

    //原型
    #define list_for_each_safe(pos, n, head)
    
    //功能
    从head节点开始(不包括head节点!)遍历它的每一个节点!它用n先将下一个要遍历的节点保存起来,
    防止删除本节点后,无法找到下一个节点,而出现错误!
    
    //参数
    pos:循环指针
    n:缓存节点
    head:链表头

     

    1.14 list_for_each_entry

    //原型
    #define list_for_each_entry(pos, head, member)                  
    
    //功能
    已知指向某个结构体的指针pos,以及指向它中member成员的指针head,从下一个结构体开始向后遍历这个结构体链
    
    //参数
    pos:结构体指针
    head:链表头
    member:结构体成员

     

    1.15 list_for_each_entry_safe

    //原型
    #define list_for_each_entry_safe(pos, n, head, member)        
    
    //功能
    先保存下一个要遍历的节点!从head下一个节点向后遍历链表。
    
    //参数
    pos:结构体指针
    n:缓冲节点
    head:链表头
    member:结构体成员

     

    以上列出了常用的一些链表操作接口,更多接口定义请参考内核代码 /include/linux/list.h

     

    本文参考以下博客https://blog.csdn.net/lmjjw/article/details/9833025.

    展开全文
  • linux下链表要初始化

    2013-03-03 21:16:09
    linux下使用链表很频繁,但是不要忘记初始化,否则会有segment fault,如下:struct list_head osd_oobinfo_list[OOBINO_LIST_LEN];   因为忘记了这个初始化过程: for(i=0; i ; i++) INIT_LIST_HEAD(&osd_...
    linux下使用链表很频繁,但是不要忘记初始化,否则会有segment fault,如下:
    struct list_head osd_oobinfo_list[OOBINO_LIST_LEN]; 

     

    因为忘记了这个初始化过程:

    for(i=0; i < OOBINO_LIST_LEN; i++)
      INIT_LIST_HEAD(&osd_oobinfo_list[i]);
    
    偶纠结了好久~~~当然,使用
    LIST_HEAD(name)
    
    

    这个宏声明的本身就顺带初始化了的例外。

    展开全文
  • Linux下链表使用介绍一:list_head

    千次阅读 2018-06-28 22:31:18
    在看这个知识点的时候我相信大家对数据结构已经有所了解,尤其是对链表的了解,因此在这里不过多讲解传统的链表基本知识,这里只给出通常双向链表的数据结构。struct list_node{ struct list_node *next,*prev; ...

          在看这个知识点的时候我相信大家对数据结构已经有所了解,尤其是对链表的了解,因此在这里不过多讲解传统的链表基本知识,这里只给出通常双向链表的数据结构。

    struct list_node{
        struct list_node *next,*prev;
        type1 m1;
        type2 m2;
    };

         在Linux内核编程中为什么不使用通常的链表呢?因为它的缺点是:对每种类型串起来的链表,我们需要编写一系列的函数实现对链表的操作,在复杂的项目中,结构体会很多,对它们实现链表功能,那需要我们为每种类型的链表编写一套函数,我们时间会浪费,可维护性差。在Linux中内核中链表是如何使用的呢?

    Linux中使用了侵入式链表“list_head”

    struct list_head {
        struct list_head *next, *prev;
    };

    在我们需要某种数据结构的双向链表时,可以这样定义:

    struct kobject {
        const char        *name;
        unsigned int      age;
        struct list_head  entry;
    };

    这个结构体类型生成的双向链表结构如下图所示:

    那我们如何构建起这个链表,如何对链表中的数据访问,如何遍历链表呢?见下篇

     

    展开全文
  • 并定义了结构体节点,如何把该类型的结构体节点串成一个链表呢?1、必须专门定义一个链表头,并初始化:struct list_head ListHead; INIT_LIST_HEAD(&amp;ListHead);其中INIT_LIST_HEAD的定义为#define INIT_...
  • linux内核链表

    2018-09-22 13:59:32
    博客详细讲解Linux内核链表,教你看懂Linux内核链表与普通链表有什么不一样
  • LINUX内核链表

    2017-07-18 13:03:09
    Linux 内核链表
  • linux内核链表实现

    2018-12-28 11:21:26
    linux内核链表的实现,包括内核链表的定义,以及内核链表相关的操作
  • Linux内核链表

    2020-11-22 16:44:58
    链表都是第一个接触的内容,笔者也不列外,虽然自己实现过几种链表,但是在实际工作中,还是Linux内核的链表最为常用(同时笔者也建议大家使用内核链表,因为会了这个,其他的都会了),故总结一篇Linux内核链表的...
  • 博客详细讲解Linux内核链表,教你看懂Linux内核链表与普通链表有什么不一样,并且有测试代码
  • linux内核链表

    2018-12-12 20:48:07
    linux内核链表插入,排序函数库,库里面包含了一些宏。可以进行链表的插入,,删减。与一般链表不同的是,可以连接不同类型的数据。
  • linux链表的使用

    千次阅读 2012-10-15 22:38:10
    linux下链表的使用方法跟我们常规的不一样,通常情况链表的next指针都指向节点的起始位置,但linux链表指向的是一个节点中链表所在的地址,这是一种很好的处理方法,不用每换一种数据结构就处理,这种方法的...
  • Linux内核链表Linux内核最经典的数据结构之一,Linux内核链表最大的优点就是节省内存,对链表的各项操作较快,实现的思路耳目一新,而且在Linux内核里频繁使用,比如:内存管理,进程调度等。 Linux内核链表是一个...
  • LINUX 的内核链表

    2019-04-01 13:29:06
    LINUX 的内核链表,简单的应用了以下,Linux下的内核链表函数
  • linux内核链表结构

    2016-11-04 22:33:49
    linux链表结构定义在include/linux/list.h中struct list_head{ struct list_head *next, *prev; };list_head结构包含着指向list_head结构的指针prev和next,由此可见,内核链表具备双链表功能,实际上,通常它都...
  • Linux 内核链表

    2015-09-24 15:49:55
    Linux 内核已经同时有几个链表实现。为减少复制代码的数量, 内核已经创建了一个标准环形双向链表,并鼓励需要操作链表的人使用这个设施. 使用链表接口时,应当记住列表函数没做加锁。若驱动可能同一个列表并发操作...
  • Linux 内核链表移植

    千次阅读 2013-04-23 14:49:24
    Linux 内核链表移植我参考网上的文章修改了移植后的Linux内核的双向链表和HASH链表, 使之适用于Linux和Windows平台. 可以在用户态使用. 任何后果, 本人概不负责!下面是全部代码:/** * dhlist.h * - deque list ...
  • 移植Linux内核链表

    2018-02-07 16:53:13
      Linux内核源码中的链表是一个双向循环链表,该链表的设计具有优秀的封装性和可扩展性。本文将从2.6.39版本内核的内核链表移植到Windows平台的visual studio2010环境中。链表的源码位于内核源码的include/linux/...
  • linux 内核链表的应用

    2015-10-20 09:46:23
    linux 内核链表学习
  • 目录 1. 简介 1.1 内核链表的思想 ...在Linux源代码树的include/linux/list.h文件中,采用了一种类型无关的双循环链表实现方式。其思想是将指针prev和next从具体的数据结构中提取出来构成一种通用的"...
  • Linux内核链表测试

    2013-11-11 10:28:17
    linux2.4.18版本源码 内核链表 用户态移植 vc6.0测试

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 112,819
精华内容 45,127
关键字:

linux下的链表

linux 订阅