首页 未命名正文

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

admin001 未命名 2008-12-27 87 3

如前文所述,Linux内核中的代码,经过稍加改造后,可以在用户态下使用。 linclude/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/ 后记:
链表,是一个古老而没有新意的话题,关于其分析的文章,也随处可见。之所以重提旧话题,是因为在讲课的过程中,每当我对那些复杂的事物进行剖析 时,剥去一层层外衣,发现,最终的实现都掉落在计算机科学最根本的问题上,比如各种最基本的数据结构,可这些,往往又是学生们不屑一顾的。在此,把链表那拿出来分析,是希冀学子们有时间关注计算机科学的根本问题。
.

版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。

评论

精彩评论