Linux 內(nèi)核通用鏈表學習小結(jié)

struct node{
  int key;
  int val;
  node* prev;
  node* next;
 }

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

struct node{
  int val;
  int key;
  struct list_head* head;
}

//初始化頭指針
#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
  struct list_head name = LIST_HEAD_INIT(name)

//遍歷鏈表
#define __list_for_each(pos, head) \
  for (pos = (head)->next; pos != (head); pos = pos->next)

//獲取節(jié)點首地址(不是list_head地址，是數(shù)據(jù)層節(jié)點首地址)
#define list_entry(ptr, type, member) \
  container_of(ptr, type, member)

//container_of在Linux內(nèi)核中是一個常用的宏，用于從包含在某個
//結(jié)構(gòu)中的指針獲得結(jié)構(gòu)本身的指針，通俗地講就是通過結(jié)構(gòu)體變
//量中某個成員的首地址進而獲得整個結(jié)構(gòu)體變量的首地址
#define container_of(ptr, type, member) ({     \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);  \
    (type *)( (char *)__mptr - offsetof(type,member) );})

#define offsetof(s,m) (size_t)&(((s *)0)->m)

typedef struct node{
  int val;
  int key;
  struct list_head* list;
}node;

//初始化頭指針
LIST_HEAD(head);

//創(chuàng)建節(jié)點
node* a = malloc(sizeof(node));
node* b = malloc(sizeof(node));

//插入鏈表 方式一
list_add(&a->list,&head);
list_add(&b->list,&head);

//插入鏈表 方式二
list_add_tail(&a->list,&head);
list_add_tail(&b->list,&head);

//遍歷鏈表  
struct list_head* p;
struct node* n;
__list_for_each(p,head){
  //返回list_head地址，然后再通過list_head地址反推
  //節(jié)點結(jié)構(gòu)體首地址.
  n = list_entry(pos,struct node,list);
}

#include <linux/kernel.h> 
#include <linux/module.h> 
#include <linux/init.h> 
#include <linux/slab.h> 
#include <linux/list.h> 
 
MODULE_LICENSE("GPL"); 
MODULE_AUTHOR("David Xie"); 
MODULE_DESCRIPTION("List Module"); 
MODULE_ALIAS("List module"); 
 
struct student //代表一個實際節(jié)點的結(jié)構(gòu) 
{ 
  char name[100]; 
  int num; 
  struct list_head list;  //內(nèi)核鏈表里的節(jié)點結(jié)構(gòu) 
}; 
 
struct student *pstudent;    
struct student *tmp_student; 
struct list_head student_list;  
struct list_head *pos; 
 
int mylist_init(void) 
{ 
  int i = 0; 
   
  //初始化一個鏈表，其實就是把student_list的prev和next指向自身 
  INIT_LIST_HEAD(&student_list);  
   
  pstudent = kmalloc(sizeof(struct student)*5,GFP_KERNEL);//向內(nèi)核申請5個student結(jié)構(gòu)空間 
  memset(pstudent,0,sizeof(struct student)*5); //清空，這兩個函數(shù)可以由kzalloc單獨做到 
   
  for(i=0;i<5;i++) 
  { //為結(jié)構(gòu)體屬性賦值 
    sprintf(pstudent[i].name,"Student%d",i+1); 
    pstudent[i].num = i+1;  
    //加入鏈表節(jié)點，list_add的話是在表頭插入，list_add_tail是在表尾插入 
    list_add( &(pstudent[i].list), &student_list);//參數(shù)1是要插入的節(jié)點地址，參數(shù)2是鏈表頭地址 
  }  
   
  list_for_each(pos,&student_list) //list_for_each用來遍歷鏈表，這是個宏定義 
                   //pos在上面有定義 
  { 
    //list_entry用來提取出內(nèi)核鏈表節(jié)點對應的實際結(jié)構(gòu)節(jié)點，即根據(jù)struct list_head來提取struct student 
    //第三個參數(shù)list就是student結(jié)構(gòu)定義里的屬性list 
    //list_entry的原理有點復雜，也是linux內(nèi)核的一個經(jīng)典實現(xiàn)，這個在上面那篇鏈接文章里也有講解 
    tmp_student = list_entry(pos,struct student,list); 
    //打印一些信息，以備驗證結(jié)果 
    printk("<0>student %d name: %s/n",tmp_student->num,tmp_student->name); 
  } 
   
  return 0; 
} 
 
 
void mylist_exit(void) 
{   
  int i ; 
  /* 實驗：將for換成list_for_each來遍歷刪除結(jié)點，觀察要發(fā)生的現(xiàn)象，并考慮解決辦法 */ 
  for(i=0;i<5;i++) 
  { 
    //額，刪除節(jié)點，只要傳個內(nèi)核鏈表節(jié)點就行了 
    list_del(&(pstudent[i].list));    
  } 
  //釋放空間 
  kfree(pstudent); 
} 
 
module_init(mylist_init); 
module_exit(mylist_exit);