Linux中的内核链表实例详解
Linux中的内核链表实例详解
链表中一般都要进行初始化、插入、删除、显示、释放链表，寻找节点这几个操作，下面我对这几个操作进行简单的介绍，因为我的能力不足，可能有些东西理解的不够深入，造成一定的错误，请各位博友指出。
A、Linux内核链表中的几个主要函数(下面是内核中的源码拿出来给大家分析一下)
1）初始化：
#defineINIT_LIST_HEAD(ptr)do{\
(ptr)->next=(ptr);(ptr)->prev=(ptr);\
}while(0)//ptr为structlist_head，其中包括两个指针next和prev，这里已经可以看出内核链表是双向循环链表
2）尾部插入：
staticinlinevoidlist_add_tail(structlist_head*new,structlist_head*head)
{
__list_add(new,head->prev,head);
}//尾部插入,传入的参数是新节点中的两个指针和头结点中的两个指针
3）头部插入函数
staticinlinevoidlist_add(structlist_head*new,structlist_head*head)
{
__list_add(new,head,head->next);
}//头插入函数,传入的参数是新节点中的两个指针和头结点中的两个指针
4）删除节点函数
staticinlinevoidlist_del(structlist_head*entry)//传入要删除节点中的指针域
{
__list_del(entry->prev,entry->next);//两个参数分别为所删除节点前一个节点和后一个节点
entry->next=(void*)0;//删除节点后置为空
entry->prev=(void*)0;
}
5）显示函数（如果要打印出链表中的信息的话要自己写成打印的函数，比如printf，因为这个其实是一个遍历的函数，没有显示的功能）
#definelist_for_each_entry(pos,head,member)\ for(pos=list_entry((head)->next,typeof(*pos),member);\ &pos->member!=(head);\ pos=list_entry(pos->member.next,typeof(*pos),member)) /*这个函数用于遍历链表 pos为节点指针， head是头结点中的两个指针的地址 member为各节点中的指针域 */
6）删除链表
#definelist_for_each_safe(pos,n,head)\ for(pos=(head)->next,n=pos->next;pos!=(head);\ pos=n,n=pos->next) //这里面的pos和n都是list_head指针，n指针是用于在删除时不让链表断链
7）寻找节点（这也是用的内核中的遍历函数）
#definelist_for_each_entry(pos,head,member)\ for(pos=list_entry((head)->next,typeof(*pos),member);\ &pos->member!=(head);\ pos=list_entry(pos->member.next,typeof(*pos),member))
B.下面来段代码给大家看看具体的运用方法
#include"kernel.h" #include#include #include typedefstructlist_node { intdata; structlist_headlist;//节点的指针域是被封装在structlist_head这个结构体内 //这个结构体中包括structlist_head*next,*prev }*node,node1; nodeinit_head(nodehead)//初始化空链表 { head=(node)malloc(sizeof(node1));//为节点分配空间 if(head==NULL) { perror("head"); returnNULL; } INIT_LIST_HEAD(&(head->list));//#defineINIT_LIST_HEAD(ptr)do{\ (ptr)->next=(ptr);(ptr)->prev=(ptr);\ }while(0)//调用内核中的初始化函数，传入的参数是 //节点的中两个指针，即structlist_head结构体中的两个指针 returnhead; } nodeinsert_tail(nodehead,intdata)//尾部插入函数 { nodenew=(node)malloc(sizeof(node1));//为新节点分配空间 if(new==NULL)//判断一下分配空间是否成功 { perror("new:"); returnNULL; } new->data=data; list_add_tail(&(new->list),&(head->list));//调用内核中的从尾部插入的函数，传入的参数为新节点中的两个指针 //和头结点中的两个指针 return0; } head_insert_node(nodehead,intdata)//头插入函数 { nodenew;//创建一个新节点 new=(node)malloc(sizeof(node1));//为新节点分配空间 if(new==NULL)//判断一下分配空间是否成功 { perror("new:"); return0; } new->data=data; list_add(&(new->list),&(head->list));//调用内核中从头插入的函数，传入的参数为新节点的两个指针和头结点的两个指针 return0; } nodesearch_node(nodehead,intdata)//寻找节点函数 { nodep=NULL; list_for_each_entry(p,&(head->list),list)//内核中的遍历函数 { if(p->data==data)//p即为需要找的节点 { printf("foundthedata:%d\n",p->data); gotoOK; } } puts("notfoundthedata!"); returnNULL; OK: returnp; } intshow_node(nodetmp) { if(tmp==NULL) { puts("tmpisNULL!"); return-1; } printf("thedatais%d\n",tmp->data); return0; } intdelete_node(nodehead,intdata) { nodep=NULL; list_for_each_entry(p,&(head->list),list) { if(p->data==data) { printf("foundthedatawhichyouwanttodelete!\n"); gotof; } } f: list_del(&(p->list)); free(p); return0; } intshow_list(nodehead) { nodep=NULL; list_for_each_entry(p,&(head->list),list) { printf("data:%d\n",p->data); } return0; } intdelete_list(nodehead)//删除链表函数 { nodep,q; list_for_each_entry_safe(p,q,&(head->list),list)//这是内核中的安全删除函数 { list_del(&(p->list)); free(p); } list_del(&(head->list)); free(head); return0; } intmain(intargc,char**argv) { nodehead; nodetmp; head=init_head(head);//初始化空链表函数 insert_tail(head,45);//从末尾插入函数 insert_tail(head,55); insert_tail(head,65); head_insert_node(head,75);//从头插入函数 show_list(head);//显示链表函数 tmp=search_node(head,55);//寻找结点函数 show_node(head); delete_node(head,55); //show_list(head); delete_list(head);//删除链表函数 return0; }
以上就是Linux中的内核链表实例详解的实例如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。