[linux内核笔记-2]linux中的数据结构（1）---- list_head

/* @author = s1n */

/*文中出现的源码均来自linux 3.16.41内核*/

1.实现双向循环链表的一般方法：

struct list_node1{
    struct list_node1 *next,*prev;
    type1 m1;
    type2 m2;
};
struct list_node2{
    struct list_node2 *next,*prev;
    type1 m1;
    type2 m2;
};

如果对于每一种数据结构都定义了其特定的实现和对应的方法，对于具有大量不同数据结构，都要使用链表的系统中，无疑使代码变得重复和臃肿。因此需要实现一种通用的双向链表方法，对各种数据结构都能适用。

2.list_head的实现：

struct list_head {
    struct list_head *next, *prev;
};

1).list_head头节点定义的两个宏，定义在/linux/list.h中

1 #define LIST_HEAD_INIT(name) { &(name), &(name) } //就是用head的地址初始化其两个成员next和prev ，使其都指向自己。 
2 #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name) 
3 #define INIT_LIST_HEAD(ptr) do { \ 
4       (ptr)->next = (ptr); (ptr)->prev = (ptr); \ 
5 } while (0)

则定义一个双向链表的头节点：

/*方法1*/
struct list_head head; 
LIST_HEAD_INIT(head);

/*方法2*/
LIST_HEAD(head);

这样，我们就定义并初始化了一个头节点

3.list_head操作：

这些函数都作为内联函数也都定义list.h中，这里要说明一下linux源码 的一个风格，在下面的这些函数中以下划线开始的函数是给内部调用的函数，而以符开始的函数就是对外使用的函数，这些函数一般都是调用以下划线开始的函数，或是说是对下划线开始的函数的封装

 

1).增加节点操作：

/** 
 * __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);
}

 

2).删除节点操作：

/** 
 * __list_del - 
 * @prev: 
 * @next: 
 * 
 * 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 
 */ 
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); 
} 

/** 
 * list_del_init - deletes entry from list and reinitialize it. 
 * @entry: the element to delete from the list. 
 */ 
static __inline__ void list_del_init(struct list_head *entry) 
{ 
      __list_del(entry->prev, entry->next); 
       INIT_LIST_HEAD(entry); 
}

list_del(struct list_head *entry)是从链表中删除entry节点。 

list_del_init(struct list_head *entry) 不但从链表中删除节点，还把这个节点的向前向后指针都指向自己，即初始化。

 

3).判断链表是否为空操作：

/** 
 * list_empty - tests whether a list is empty 
 * @head: the list to test. 
 */ 
static __inline__ int list_empty(struct list_head *head) 
{ 
      return head->next == head; 
}

 

4.一个结构体通过list_head实现双链表

1).如果某种结构体需要双向链表结构，则将list_head作为其中的成员：

struct kobject {
    const char        *name;
    struct list_head    entry;
    struct kobject        *parent;
    struct kset        *kset;
}

形成了如下的结构：

2).list_entry()

该函数是通过kobject 链表结构中的 list_head 成员entry访问下一个成员的宏：

 ,ptr : 是指向当前kobject结构对象中的数据成员entry，(char *)(ptr)：entry成员地址,

 ,(char *)(ptr)：entry成员地址----地址A;

 ,(unsigned long)(&((type *)0)->member)) : 将地址0转化为类型为type（struct kobject ）对象，取member（entry）成员的地址----地址B

 ,(type *)(地址A-地址B)： 得到kobject结构对象的首地址，转化为kobject对象

 

/**  * list_entry - get the struct for this entry  
* @ptr: the &struct list_head pointer.  
* @type: the type of the struct this is embedded in.  
* @member: the name of the list_struct within the struct.  */ 

 #define list_entry(ptr, type, member) \ 
         ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) 
 
 //访问链表成员
 kobject *obj  = objList;
 kobject *nextObj = (kobject *)list_entry(obj->entry->next,struct kobject,entry);

 

即为如下结构：

3).一个实例：

首先，定义如下结构体：

struct person 
{ 
      int age; 
      int weight; 
      struct list_head list; 
};

现定义一指针：

struct list_head *pos = person;

则获取这个指针所指向的结构的变量：

struct person *one = list_entry(pos, struct person, list);

代入到宏中：

((struct person *)((char *)(pos)-(unsigned long)(&((struct person *)0)->list)))

整个过程分成两部分：

PartI.(char *)(pos)减去(unsigned long)(&((struct person *)0)- >list)

PartII.转成(struct person *)类型的指针

解释：

(char *)(pos)：将pos由struct list_head*转 成char*  

(unsigned long)(&((struct person *)0)->list)：

StepI. (struct person *)0)，把0 地址转成struct person指针

StepII.(struct person *)0)->list就是指向list变量

StepIII.&((struct person *)0)->list是取这个变量的地址

StepIIII.(unsigned long)(&((struct person *)0)->list)把这个变量的地址值转换成一个整形

 

总结一下，(unsigned long)(&((struct person *)0)->list)的意思就是取list 变量在struct person结构中的偏移量。

 

更进一步：

((char *)(pos) - (unsigned long)(&((struct person *)0)->list))

就是将pos指针往前移动所获取的偏移量的位置位置，即是本来pos是struct list_head类型，它即是list。即是把 pos指针往struct person结构的头地址位置移动过去，当pos移到struct person结构头后就转成(struct person *)指针，这样就可以得到struct person *变量了。 

 

5.list_head的遍历：

list_head的遍历宏定义如下：

/** 
 * list_for_each - iterate over a list 
 * @pos: the &struct list_head to use as a loop counter. 
 * @head: the head for your list. 
 */ 
#define list_for_each(pos, head) \ 
      for (pos = (head)->next; pos != (head); pos = pos->next) 

/** 
 * 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)

list_for_each()遍历整个head链表中的每个元素，每个元素都用pos指向。 

而后者list_for_each_safe()使用了n作为一个临时的指针。若进行删除操作，当pos被删除后，还可以用n来获得下一个元素的位置。

6.总例：

#include <stdio.h> 
#include "list.h" 

struct person 
{ 
      int age; 

      int weight; 
      struct list_head list; 
}; 

int main(int argc, char* argv[]) 
{ 
      struct person *tmp; 
      struct list_head *pos, *n; 
      int age_i, weight_j; 

      // 定义并初始化一个链表头 
      struct person person_head; 
      INIT_LIST_HEAD(&person_head.list); 

      for(age_i = 10, weight_j = 35; age_i < 40; age_i += 5, weight_j += 5) 
      { 
            tmp =(struct person*)malloc(sizeof(struct person)); 
            tmp->age = age_i; 
            tmp->weight = weight_j; 

            // 把这个节点链接到链表后面 
            // 这里因为每次的节点都是加在person_head的后面，所以先加进来的节点就在链表里的最 
后面 

            // 打印的时候看到的顺序就是先加进来的就在最后面打印 
            list_add(&(tmp->list), &(person_head.list)); 

      } 

      // 下面把这个链表中各个节点的值打印出来 
      printf("\n"); 
      printf("=========== print the list ===============\n"); 
      list_for_each(pos, &person_head.list) 
      { 
            // 这里我们用list_entry来取得pos所在的结构的指针 
            tmp = list_entry(pos, struct person, list); 
            printf("age:%d, weight: %d \n", tmp->age, tmp->weight); 
      } 
      printf("\n"); 

      // 下面删除一个节点中，age为20的节点 
      printf("========== print list after delete a node which age is 20 
==========\n"); 
      list_for_each_safe(pos, n, &person_head.list) 
      { 

        tmp = list_entry(pos, struct person, list); 
              if(tmp->age == 20) 
              { 
                    list_del_init(pos); 
                    free(tmp); 
              } 

       } 

       list_for_each(pos, &person_head.list) 
       { 
              tmp = list_entry(pos, struct person, list); 
              printf("age:%d, weight: %d \n", tmp->age, tmp->weight); 
       } 

       // 释放资源 
       list_for_each_safe(pos, n, &person_head.list) 
       { 
              tmp = list_entry(pos, struct person, list); 
              list_del_init(pos); 
              free(tmp); 
       } 

       return 0; 
}