linux内核数据结构---链表(1)

梦里梦外; 2022-02-13 14:54 304阅读 0赞

**Linux**内核有一些基本的数据结构，这些数据结构是Linux实现的基础，对于链表相信大家都不陌生，但是Linux内核中的链表与平常平常我们所使用的链表略有不同，第一次遇到或许会感到困惑。

先来看一个链表的节点，对于一个节点，分为两部分，一部分是数据，另一部分是串联数据的指针。**[Linux][]**链表节点的定义如下(以下代码皆为3.5版本)：

// include/linux/types.h
    struct list_head {
            struct list_head *next, *prev;
    };

这里的定义有些奇怪，因为仅有前后节点的指针，并没有数据，就像一串链子，只有线没有线上的珠子，肯定是无法使用，那Linux内核如何把这些“珠子”附着到线上的呢？

来看一个简单的例子：

struce simple {
    	int data;
    	struct list_head list;
    };

simple结构体的list成员指向下一个或者上一个simple的list，这样便把节点串联起来了，data作为“珠子”附着在list线上，但这样仍然有一个问题，list成员仅仅指向下一个simple的list成员，那从list成员如何得到simple节点的地址呢？

答案是根据list成员的地址以及list成员在simple的位置便可以计算出simple对象的地址，这样有些繁琐，Linux提供了一个宏，可以简化这个过程：

// include/linux/list.h
    /**
     * 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_struct within the struct.
     */
    #define list_entry(ptr, type, member) \
            container_of(ptr, type, member)
    
    // include/linux/kernel.h
    #define container_of(ptr, type, member) ({                      \
            const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
            (type *)( (char *)__mptr - offsetof(type,member) );})
    
    #undef offsetof
    #ifdef __compiler_offsetof
    #define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
    #else
    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
    #endif
    #endif /* __KERNEL__ */

可以看到，list\_entry直接调用了container\_of，container\_of分为两句，((type \*)0)->member可以获得member在结构体type中的偏移，假设有一个结构体在地址0的位置，那么成员的地址便是成员对结构体的偏移，typeof是gcc的扩展，用于获取变量的类型，offsetof(type,member) 获取member成员在type中的偏移，然后使用member成员的指针ptr（复制成\_\_mptr）减去偏移，即是结构体的地址。在我们的例子中，从list成员的地址获取simple结构的地址如下：

simple * p = list_entry(ptr, struct simple, list);

这样便解决了从list\_head上获取附着的数据的问题。接下来需要解决对链表的增删改查的问题：

一、初始化链表：  
初始化链表有两种方法，LIST\_HEAD\_INIT和LIST\_HEAD

#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\_add\_tail，和在节点前插入新节点list\_add：

/**
     * list_add - add a new entry
     * @new: new entry to be added
     * @head: list head to add it after
     *
     * Insert a new entry after the specified head.
     * This is good for implementing stacks.
     */
    static inline void list_add(struct list_head *new, struct list_head *head)
    {
            __list_add(new, head, head->next);
    }
    
    /**     
     * 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);
    }

其中 \_\_list\_add 只是普通的链表操作，并无特别之处，可参见Linux源码查看实现。

三、删除节点：

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

\_\_list\_del 把entry从链表中删除，之后把entry链表指针复制成非空指针（如果使用会出现段错误）

四、检查是否空链表  
判断一个链表是否为空，只需要看头节点是否指向自己便可：

static inline int list_empty(const struct list_head *head)
    {
            return head->next == head;
    }

五、遍历  
遍历是这几种操作中最为复杂的，有四个函数：

#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_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))
    
    #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))

list\_for\_each 和 list\_for\_each\_prev 较为简单，一个向后遍历，另一个向前遍历，list\_for\_each\_entry和list\_for\_each\_entry\_reverse功能相似，不过不是对list\_head操作，而是直接对结构体操作，如我们这里的simple结构。根据之前的叙述也不难理解函数实现，只是在list\_head上调用了list\_entry获取了完整结构。

六、实例  
千言万语不如一个例子来的直观，我们通过一个简单的例子说明一下如何使用内核链表：

#include <linux/list.h>
    #include <linux/kernel.h>
    #include <stdio.h>
    
    struct simple {
        int data;
        struct list_head list;
    };
    
    int main()
    {
        int i = 0;
        struct simple * p;
        struct list_head * pos;
        LIST_HEAD(head);
        for (i = 0; i < 10; i++) {
            p = (struct simple*)malloc(sizeof(struct simple));
            p->data = i * 10;
            list_add_tail(&p->list, &head);
        }
    
        list_for_each_entry(p, &head, list) {
            printf("for %d\n", p->data);
        }
    
        while (!list_empty(&head)) {
            pos = head.next;
            p = (struct simple*)list_entry(pos,
                    struct simple, list);
            list_del(pos);
            printf("del %d\n", p->data);
            free(p);
        }
        return 0;
    }

编译参数为

gcc -D__KERNEL__ -I/usr/src/linux-headers-3.2.0-27-generic/include/ -I/usr/src/linux-headers-3.2.0-27-generic/arch/ia64/include/ simple.c

其中头文件中都是内核函数，需要宏\_\_KERNEL\_\_，否则大部分定义会被忽略。

转载自：http://tech.fancymore.com/page/143.html\#more-143

[Linux]: http://blog.csdn.net/shanzhizi