Linux内核代码赏析与应用(三)－链表API之应用

如前文所述，Linux内核中的代码，经过稍加改造后，可以在用户态下使用。
  include/linux/list.h 中的函数和宏，是一组精心设计的API，有比较完整的注释和清晰的思路。在用户态下使用list.h，查看改造后的list.h

1. 举例
    下面是用户态下的例子，用以创建、增加、删除和遍历一个双向链表。

#include <stdio.h>
#include <stdlib.h>

#include "list.h"


struct kool_list{
        int to;
        struct list_head list;
        int from;
        };

int main(int argc, char **argv){

        struct kool_list *tmp;
        struct list_head *pos, *q;
        unsigned int i;

        struct kool_list mylist;
        INIT_LIST_HEAD(&mylist.list); /*初始化链表头*/

        /* 给mylist增加元素 */
        for(i=5; i!=0; --i){
        tmp= (struct kool_list *)malloc(sizeof(struct kool_list));
        
        /* 或者INIT_LIST_HEAD(&tmp->list); */
        printf("enter to and from:");
        scanf("%d %d", &tmp->to, &tmp->from);

        
        list_add(&(tmp->list), &(mylist.list));
        /* 也可以用list_add_tail() 在表尾增加元素*/
        }
        printf("\n");



        printf("traversing the list using list_for_each()\n");
        list_for_each(pos, &mylist.list){

        /* 在这里 pos->next 指向next 节点, pos->prev指向前一个节点.这里的节点是
        struct kool_list类型. 但是，我们需要访问节点本身，        而不是节点中的list字段，宏list_entry()正是为此目的。*/     

2. 关于删除元素的不安全性
   为什么说调用list_del()删除元素有安全隐患？具体看源代码：
/*
* 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;
}
/**
* 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 = LIST_POISON1;
        entry->prev = LIST_POISON2;
}
  可以看出，当执行删除操作的时候， 被删除的节点的两个指针被指向一个固定的位置（entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;）。而list_for_each(pos, head)中的pos指针在遍历过程中向后移动，即pos = pos->next，如果执行了list_del()操作，pos将指向这个固定位置的next, prev,而此时的next, prev没有任何意义，别无选择，出错。
  而list_for_each_safe(p, n, head) 宏解决了上面的问题：
   
/**
* list_for_each_safe    -    iterate over a list safe against removal of list entry
* @pos:    the &struct list_head to use as a loop counter.
* @n:        another &struct list_head to use as temporary storage
* @head:    the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)

  它采用了一个同pos同样类型的指针n 来暂存将要被删除的节点指针pos，从而使得删除操作不影响pos指针！

实际上，list.h的设计可谓精益求精，煞费苦心，用简洁的代码突破计算机科学中传统的链表实际机制，不仅考虑了单处理机，还利用了Paul E. McKenney提出的RCU（读拷贝更新）的技术，从而提高了多处理机环境下的性能。关于RCU，请看http://www.rdrop.com/users/paulmck/rclock/

后记：

实际上，链表，是一个古老而没有新意的话题，关于其分析的文章，也随处可见。之所以重提旧话题，是因为在讲课的过程中，每当我对那些复杂的事物进行剖析时，剥去一层层外衣，发现，最终的实现都掉落在计算机科学最根本的问题上，比如各种最基本的数据结构，可这些，往往又是学生们不屑一顾的。在此，把链表拿出来分析，是希冀学子们有时间关注计算机科学的根本问题。