1、ARM Linux内核链表概述

    在ARM Linux中，链表是为基本的数据结构，也是为常用的数据结构。在本文中尽管使用2.6内核作为讲解的基础，但实际上2.4内核中的链表结构和2.6并没有太大区别。二者不同之处在于2.6扩充了两种链表数据结构：链表的读拷贝更新（rcu）和HASH链表（hlist）。这两种扩展都是基于基本的list结构。因此，在此处主要介绍基本链表结构。

    链表数据结构的定义很简单（<include/linux/list.h>，以下所有代码除非加以说明，其余均取自该文件）：

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

    list_head结构包含两个指向list_head结构的指针prev和next，由此可见，内核的链表具备双链表功能，实际上，通常它都组织成双循环链表。

    和之前介绍的双链表结构模型不同，这里的list_head没有数据域。在Linux内核链表中，不是在链表结构中包含数据，而是在数据结构中包含链表节点。由于链表数据类型差别很大，如果对每一种数据项类型都需要定义各自的链表结构，不利于抽象成为公共的模板。

    在Linux内核链表中，需要用链表组织起来的数据通常会包含一个struct list_head成员，例如在<include/linux/netfilter.h>中定义了一个nf_sockopt_ops结构来描述netfilter为某一协议族准备的getsockopt/setsockopt接口，其中就有一个（struct list_head list）成员，各个协议族的nf_sockopt_ops结构都通过这个list成员组织在一个链表中，表头是定义在<net/core/netfilter.c>中的nf_sockopts（struct list_head）。读者可以看到，Linux的简捷实用、不求完美和标准的风格在这里体现得相当充分。

    2、Linux内核链表接口

    （1）声明和初始化

    实际上Linux只定义了链表节点，并没有专门定义链表头，那么一个链表结构是如何建立起来的呢？这里是使用LIST_HEAD()这个宏来构建的。

    #define LIST_HEAD_INIT(name) { &(name), &(name) }
    #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

    这样，当需要用LIST_HEAD(nf_sockopts)声明一个名为nf_sockopts的链表头时，它的next、prev指针都初始化为指向自己。这样就构建了一个空链表，因为Linux用头指针的next是否指向自己来判断链表是否为空。

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

    除了用LIST_HEAD()宏在声明的时候创建一个链表以外，Linux还提供了一个INIT_LIST_HEAD宏用于运行时创建链表：

    #define INIT_LIST_HEAD(ptr) do { (ptr)->next = (ptr);
    (ptr)->prev = (ptr); } while (0)

    （2）插入

    对链表的插入操作有两种：在表头插入和在表尾插入。Linux为此提供了两个接口：

    static inline void list_add(struct list_head *new, struct list_head *head);
    static inline void list_add_tail(struct list_head *new, struct list_head *head);

    因为Linux链表是循环表，且表头的next、prev分别指向链表中的第一个和末一个节点，所以，list_add()和list_add_tail()的区别并不大，实际上，Linux分别用以下两个函数来实现接口。

    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;
    }
    static inline void list_add(struct list_head *new, struct list_head *head)
    {
        __list_add(new, head, head->next);
    }
    static inline void list_add_tail(struct list_head *new, struct list_head *head)
    {
        __list_add(new, head->prev, head);
    }

    （3）删除

    Linux中删除的代码也是类似的，通过__list_del来实现list_del接口，读者可以自行分析以下代码段：

    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;
    }

    从接口函数中可以看到，被删除下来的prev、next指针分别被设为LIST_POSITION2和LIST_POSITION1两个特殊值，这样设置是为了保证不在链表中的节点项不可访问，对LIST_POSITION1和LIST_POSITION2的访问都将引起页故障。与之相对应，list_del_init()函数将节点从链表中解下来之后，调用LIST_INIT_HEAD()将节点置为空链状态。

   热点链接：

   1、嵌入式linux内核数据结构之循环链表
   2、嵌入式linux内核数据结构之双向链表
   3、嵌入式linux内核数据结构之单向链表

更多新闻>>