linux的数据结构---链表

cheng029

链表是一种常见的组织有序数据的数据结构，相对于数组，具有更好的动态性，可以高效的在链表的任意位置实时的插入或者删去。在linux的源代码中，大量的使用了链表。通常链表数据结构至少有两个域：数据域和指针域，数据域用于存储数据，指针域用于建立与下一个节点的联系。在数据结构中定义一个指向任意类型为

[Shell] 纯文本查看 复制代码

struct list

{

    void *data;

    struct list *next;

};

而在内核中，定义了一种通用的双向循环链表，链表的定义为：

[Shell] 纯文本查看 复制代码

struct list_head {

    struct list_head *next, *prev;

};

有prev和next两个指针，分别指向链表中的前一节点和后一节点。在初始化的时候，都指向自己本身。

[Shell] 纯文本查看 复制代码

static inline void INIT_LIST_HEAD(struct list_head *list)

{

    list->next = list;

    list->prev = list;

}

向链表中添加节点

[Shell] 纯文本查看 复制代码

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

}

list_add和list_add_tail的区别不大，linux实现两个接口，在表头插入是插入在head后，而在表尾插入是在head->prev之后，只是表明插入到该节点之后或者之前。链表中的节点删去

[Shell] 纯文本查看 复制代码

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 = (void *)0xDEADBEEF;

    entry->prev =(void *)0xBEEFDEAD;

}

被删去entry删去后分别指向两个值，这个设置是为了保持不在链表中的节点项以后不会被访问。

[Shell] 纯文本查看 复制代码

static inline void list_del_init(struct list_head *entry)

{

    __list_del_entry(entry);

    INIT_LIST_HEAD(entry);

}

该函数将节点从链表中解下来后，调用INIT_LIST_HEAD将节点设置为空链表。

[Shell] 纯文本查看 复制代码

static inline void list_replace(struct list_head *old,

                struct list_head *new)

{

    new->next = old->next;

    new->next->prev = new;

    new->prev = old->prev;

    new->prev->next = new;

}



static inline void list_replace_init(struct list_head *old,

                    struct list_head *new)

{

    list_replace(old, new);

    INIT_LIST_HEAD(old);

}

list_replace是将链表中的一个老节点换乘一个新节点，从实现上来看，即使old所在链表只有一个old节点，new也可以成功替换。

[Shell] 纯文本查看 复制代码

static inline void list_move(struct list_head *list, struct list_head *head)


{

    __list_del_entry(list);

    list_add(list, head);

}



static inline void list_move_tail(struct list_head *list,

                 struct list_head *head)

{

    __list_del_entry(list);

    list_add_tail(list, head);

}

list_move的作用是把list节点从原链表中去除，并加入到新的链表中；而list_move_tail只是加入新链表。前者是加到链表的头部，而后者是加入到链表的尾部。

[Shell] 纯文本查看 复制代码

static inline int list_is_last(const struct list_head *list,

const struct list_head *head)

{

    return list->next == head;

}

上面函数主要是判断list是否处于head链表的尾部。

[Shell] 纯文本查看 复制代码

static inline int list_empty(const struct list_head *head)

{

    return head->next == head;

}



static inline int list_empty_careful(const struct list_head *head)

{

    struct list_head *next = head->next;

    return (next == head) &&(next== head->prev);

}

list_empty判断head链表是否为空，而list_empty_careful同样也是判断链表是否为空，只是多了一个检测条件。

• static inline int list_is_singular(const struct list_head *head)
• {
•     return !list_empty(head) && (head->next == head->prev);
• }
  

list_is_singular判断head是否只有一个节点，在检测链表头head外是否只有一个节点。list的操作包括链表的节点添加和删去，节点从一个链表转移到另外一个链表，替换和合并，由于其数据结构中只是定义了两个指针域，没有定义数据域。那么怎么去获得数据域呢？linux中有一种新的方法来获取，通过获取一个结构体中一个成员在这个结构体中的偏移。

• #define list_entry(ptr, type, member) \
•     container_of(ptr, type, member)
  

来个例子，例如

• typedef struct
• {
•     int i;
•     int j;
• }ember;
  

这个ember结构体占用了8个字节，假设声明一个变量ember a;想知道a的地址该如果办呢？只要知道j在a中的偏移量，然后把j的地址减去这个偏移量就是a的地址。list_entry主要用于从list节点查找其内嵌的结构。

• #define list_first_entry(ptr, type, member) \
•     list_entry((ptr)->next, type, member)
  

list_first_entry是将ptr看成一个链表头，取出其中第一个节点对应的结构地址。下面来看看在总线设备驱动模型中大量被使用的list_for_each，循环遍历链表中的每个节点，从链表的头部的第一个节点，一直到链表的尾部。

• #define list_for_each(pos, head) \
•     for (pos = (head)->next; prefetch(pos->next), pos != (head); \
•         pos = pos->next)
  

• #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; prefetch(pos->prev), pos != (head); \
•         pos = pos->prev)
  

list_for_each_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))
  

上面这个函数不是遍历链表的节点，而是遍历链表节点锁嵌套的结构。其等价为list_for_each加list_entry。在list_head，有以上一些通用的链表的形式，但是还有一种klist和hlist也占据了很大的一部分，hlist也就是哈希表。哈希表也是一个哈希数组，为了解决映射冲突的问题，其实哈希组的每一个项做成一个链表，哈希组的项很多，list_head的话每个链表都需要两个指针空间，就发明了hlist，一是它的链表只需要一个指针，二是它的每一项都可以找到前一个节点。

[Shell] 纯文本查看 复制代码

struct klist_node;

struct klist {

    spinlock_t        k_lock;

    struct list_head    k_list;

    void            (*get)(struct klist_node *);

    void            (*put)(struct klist_node *);

} __attribute__ ((aligned (sizeof(void *))));



#define KLIST_INIT(_name, _get, _put)\

{ .k_lock    = __SPIN_LOCK_UNLOCKED(_name.k_lock),\

.k_list    = LIST_HEAD_INIT(_name.k_list),\

.get= _get,\

.put        = _put, }



#define DEFINE_KLIST(_name, _get, _put)\

    struct klist _name = KLIST_INIT(_name, _get, _put)



extern void klist_init(struct klist *k, void (*get)(struct klist_node *),

         void (*put)(struct klist_node *));



struct klist_node {

    void            *n_klist;/* never access directly */

    struct list_head    n_node;

    struct kref        n_ref;

};

可以看到，klist的链表头是一个struct klist结构，链表节点是struct klist_node结构。先看看struct klist，包含链表需要的k_list,用于加锁的k_lock，get()和put（）用于对结构的引用。这样在节点的初始化调用get()，在节点删去时调用put()。在看看struct klist_node，除了链表需要的node，一个引用计数，还有一个n_klist指针。初始化klist

[Shell] 纯文本查看 复制代码

void klist_init(struct klist *k, void (*get)(struct klist_node *),

        void (*put)(struct klist_node *))

{

    INIT_LIST_HEAD(&k->k_list);

    spin_lock_init(&k->k_lock);

    k->get = get;

    k->put = put;

}

wuliuwang

解释就是掩饰，掩饰就是编故事!

神甫

为中华而努力读书!一包中华好多钱啊~~~

wdx1992828

男人偷腥时的智商仅次于爱因斯坦!

FXMAR

花前月下，不如花钱“日”下!*^_^*

huhahapz

不在课堂上沉睡，就在酒桌上埋醉。

sfyhip

微机原理闹危机，随机过程随机过，实变函数学十遍，汇编语言不会编！