|
前言：在linux源代码中有个头文件为list.h。很多linux下的源代码都会使用这个头文件，它里面定义了一个结构,以及定义了和其相关的一组函数，这个结构是这样的：struct list_head{ struct list_head *next, *prev; };那么这个头文件又是有什么样的作用呢，这篇文章就是用来解释它的作用，虽然这是linux下的源代码，但对于学习C语言的人来说，这是算法和平台没有什么关系。一、双向链表学习计算机的人都会开一门课程《数据结构》，里面都会有讲解双向链表的内容。什么是双向链表，它看起来是这样的：struct dlist { int no; void* data; struct dlist *prev, *next; };他的图形结构图：现在有几个结构体，它们是：表示人的：struct person { int age; int weight; };表示动物的：struct animal{ int age; int weight;};如果有一组filename变量和filedata变量，把它们存起来，我们会怎么做，当然就用数组了，但我们想使用双向链表，让它们链接起来，那该怎么做，唯一可以做的就是给每个结构加如两个成员，如下：表示人的：struct person{ int age; int weight; struct person *next, *prev;};表示动物的：struct animal{ int age; int weight; struct animal *next, *prev;};现在有一个人的一个链表的链头指针person_head （循环双向链表）和动物的链表的链头指针ainimal_head ，我们要获得特定年龄和特定体重的人或动物（假设不考虑重叠），那么代码看起来可能是这样：struct person * get_percent(int age, int weight){….... struct person *p; for(p = person_head->next; p != person_head; p=p->next) { if(p->age == age && p->weight == weight) return p; }…...}那同理,要获得一个特定年龄和重量的动物的函数get_animal(int age, int weight)的代码也是和上面的类似。我们再回过头来看这两个结构，它们的指向前和指向后的指针其实都差不多，那把它们综合起来吧，所以看起来如下面：struct list_head{ struct list_head *next, *prev;};表示人的：struct person{ int age; int weight; struct list_head list;};动物的：struct animal{ int age; int weight; struct list_head list;};可能又会有些人会问了，struct list_head都不是struct persion和struct animal类型，怎么可以做链表的指针呢？其实，无论是什么样的指针，它的大小都是一样的，32位的系统中，指针的大小都是32位（即4个字节），只是不同类型的指针在解释的时候不一样而已，那么这个struct list_head又是怎么去做这些结构的链表指针呢，那么就请看下一节吧：）。二、struct list_head结构的操作首先，让我们来看下和struct list_head有关的两个宏，它们定义在list.h文件中。#define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)#define INIT_LIST_HEAD(ptr) do { \ (ptr)->next = (ptr); (ptr)->prev = (ptr); \} while (0)这两个宏是用了定义双向链表的头节点的，定义一个双向链表的头节点，我们可以这样：struct list_head head;LIST_HEAD_INIT(head);又或者直接这样：LIST_HEAD(head);这样，我们就定义并初始化了一个头节点。#define LIST_HEAD_INIT(name) { &(name), &(name) }就是用head的地址初始化其两个成员next和prev ，使其都指向自己。我们再看下和其相关的几个函数，这些函数都作为内联函数也都定义list.h中，这里要说明一下linux源码的一个风格，在下面的这些函数中以下划线开始的函数是给内部调用的函数，而以符开始的函数就是对外使用的函数，这些函数一般都是调用以下划线开始的函数，或是说是对下划线开始的函数的封装。2.1 增加节点的函数static inline void __list_add();static inline void list_add();static inline void list_add_tail();其实看源代码是最好的讲解了，这里我再简单的讲一下。/*** __list_add - Insert a new entry between two known consecutive entries.* @new:* @prev:* @next:** This is only for internal list manipulation where we know the prev/next* entries*/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;}//这个函数在prev和next间插入一个节点new。/*** list_add - add a new entry* @new: new entry to be added* @head: list head to add it after** Insert a new entry after the specified head.* This is good for implementing stacks.*/static __inline__ void list_add(struct list_head *new, struct list_head *head){ __list_add(new, head, head->next);}//这个函数在head节点后面插入new节点。/*** list_add_tail - add a new entry* @new: new entry to be added* @head: list head to add it before** Insert a new entry before the specified head.* This is useful for implementing queues.*/static __inline__ void list_add_tail(struct list_head *new, struct list_head *head){ __list_add(new, head->prev, head);}这个函数和上面的那个函数相反，它在head节点的前面插入new节点。
(以上内容不代表本站观点。) --------------------------------- |
本網站是"非商業"(non-commercial)。
