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

时间:2009-03-05 22:52:11  来源:本站收集整理  作者:陈莉君

如前文所述,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()正是为此目的。*/     


   tmp= list_entry(pos, struct kool_list, list);

        
        printf("to= %d from= %d\n", tmp->to, tmp->from);

        }
        printf("\n");
        /* 因为这是循环链表,也可以以相反的顺序遍历它,
        *为此,只需要用'list_for_each_prev'代替'list_for_each',   
       * 也可以调用list_for_each_entry() 对给定类型的节点进行遍历。
        * 例如:
        */
        printf("traversing the list using list_for_each_entry()\n");
        list_for_each_entry(tmp, &mylist.list, list)
        printf("to= %d from= %d\n", tmp->to, tmp->from);
        printf("\n");
        

        /*现在,我们可以释放 kool_list节点了.我们本可以调用 list_del()删除节点       
    * 但为了避免遍历链表的过程中删除元素出错,因此调用另一个更加安全的宏 list_for_each_safe(),    
    * 具体原因见后面的分析 */

        printf("deleting the list using list_for_each_safe()\n");
        list_for_each_safe(pos, q, &mylist.list){
        tmp= list_entry(pos, struct kool_list, list);
        printf("freeing item to= %d from= %d\n", tmp->to, tmp->from);
        list_del(pos);
        free(tmp);
        }

        return 0;
}

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/

后记:

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

相关文章

文章评论

共有  1  位网友发表了评论 此处只显示部分留言 点击查看完整评论页面