Linux内核中的双向循环链表学习

Linux内核中的双向循环链表学习

一、概述

Linux内核中大量使用了链表这个基本数据结构，因此有必要去窥探一下其“葫芦里卖的是什么药”。先来些基本知识点吧：

1.数据元素间是一对一关系；

2.链表中的元素个数是有限的；

3.同一表中各数据元素的类型和长度相同。

二、实现

先上代码，有个感性的认识，后面再解释。

#include<stdio.h>
 #include<malloc.h>
 
 //链表头结构
 struct list_head
 {
     struct list_head *next,*prev;
 };
 
 //#define LIST_HEAD_INIT(name)  {&(name),&(name)}
 //#define LIST_HEAD(name)  struct list_head name = LIST_HEAD_INIT(name)
 
 //链表头初始化
 void INIT_LIST_HEAD(struct list_head *list)
 {
     list->next = list;
     list->prev = list;
 }
 
 //真正实现链表插入操作
 void _list_add(struct list_head *nnew,struct list_head *prev,struct list_head *next)
 {
     next->prev = nnew;
     nnew->next = next;
     nnew->prev = prev;
     prev->next = nnew;
 }
 
 //向链表插入一个节点
 void list_add(struct list_head *nnew,struct list_head *head)
 {
     _list_add(nnew,head,head->next);
 }
 
 
 #define list_for_each(pos,head) \
     for(pos = (head)->next;pos != (head);pos = pos->next)
 
 #define list_for_each_safe(pos,n,head) \
     for(pos = (head)->next,n = pos->next;pos != (head);pos = n,n = pos->next)
 
 //根据节点中的一个成员在节点中的偏移量找到节点的起始地址
 #define list_entry(ptr,type,member) \
     ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
 
 //真正实现链表删除操作
 void _list_del(struct list_head *prev,struct list_head *next)
 {
     next->prev = prev;
     prev->next = next;
 }
 
 //删除链表中的一个节点
 void list_del(struct list_head *entry)
 {
     _list_del(entry->prev,entry->next);
     entry->next = NULL;
     entry->prev = NULL;
 }
 
 ////////////////////////////////////////////////////
 
 //默认链表长度
 #define N  10
 
 //定义节点的数据结构
 struct numlist
 {
     int num;//数据域
     struct list_head list;//指针域
 };
 
 //定义链表头节点
 struct numlist numhead;
 
 
 int main()
 {
 
     struct numlist *listnode;
     struct list_head *pos;
     struct numlist *p;
     struct list_head *t;
     int i;
 
     //初始化链表头节点
     INIT_LIST_HEAD(&numhead.list);
 
     for(i=0;i<N;i++)
     {
         //为新节点分配内存
         listnode = (struct numlist *)malloc(sizeof(struct numlist));
         //为节点数据域赋值
         listnode->num = i;
         //将该节点插入到链表中
         list_add(&listnode->list,&numhead.list);
         printf("Node %d has been added to doublelist\n",i);
     }
 
     printf("\n\n\n\n");
 
     //遍历链表
     list_for_each(pos,&numhead.list)
     {
         i--;
         //找出一个节点
         p = list_entry(pos,struct numlist,list);
         printf("Node %d's data: %d\n",i,p->num);
     }
    
     list_for_each_safe(pos,t,&numhead.list)
     {
         //删除节点
         list_del(pos);
         p = list_entry(pos,struct numlist,list);
         //释放节点的内存
         free(p);
     }
 
     return 0;
 }