Linux中的内核链表实例详解

Linux中的内核链表实例详解

链表中一般都要进行初始化、插入、删除、显示、释放链表,寻找节点这几个操作,下面我对这几个操作进行简单的介绍,因为我的能力不足,可能有些东西理解的不够深入,造成一定的错误,请各位博友指出。

A、Linux内核链表中的几个主要函数(下面是内核中的源码拿出来给大家分析一下)

1)初始化:

#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)  // ptr为struct list_head,其中包括两个指针next和prev,这里已经可以看出内核链表是双向循环链表

2)尾部插入:

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
} //尾部插入,传入的参数是新节点中的两个指针和头结点中的两个指针

3)头部插入函数

static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
} //头插入函数,传入的参数是新节点中的两个指针和头结点中的两个指针

4)删除节点函数

static inline void list_del(struct list_head *entry)  //传入要删除节点中的指针域
{
__list_del(entry->prev, entry->next);//两个参数分别为所删除节点前一个节点和后一个节点
entry->next = (void *) 0;//删除节点后置为空
entry->prev = (void *) 0;
}

5)显示函数(如果要打印出链表中的信息的话要自己写成打印的函数,比如printf,因为这个其实是一个遍历的函数,没有显示的功能)

#define list_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)删除链表

#define list_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)寻找节点(这也是用的内核中的遍历函数)

#define list_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<errno.h>
#include<stdio.h>
#include<stdlib.h>

typedef struct list_node
{
int data;
struct list_head list;//节点的指针域是被封装在struct list_head这个结构体内
//这个结构体中包括struct list_head *next,*prev
}*node,node1;

node init_head(node head)//初始化空链表
{
head = (node)malloc(sizeof(node1));//为节点分配空间
if(head == NULL)
{
perror("head");
return NULL;
}
INIT_LIST_HEAD(&(head->list));//#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)//调用内核中的初始化函数,传入的参数是
//节点的中两个指针,即struct list_head结构体中的两个指针
return head;
}

node insert_tail(node head,int data)//尾部插入函数
{
node new = (node)malloc(sizeof(node1));//为新节点分配空间
if(new == NULL)//判断一下分配空间是否成功
{
perror("new:");
return NULL;
}
new->data = data;
list_add_tail(&(new->list),&(head->list));//调用内核中的从尾部插入的函数,传入的参数为新节点中的两个指针
//和头结点中的两个指针
return 0;
}

head_insert_node(node head,int data)//头插入函数
{
node new;//创建一个新节点
new = (node)malloc(sizeof(node1));//为新节点分配空间
if(new == NULL)//判断一下分配空间是否成功
{
perror("new:");
return 0;
}
new->data = data;
list_add(&(new->list),&(head->list));//调用内核中从头插入的函数,传入的参数为新节点的两个指针和头结点的两个指针
return 0;
}

node search_node(node head,int data)//寻找节点函数
{
node p = NULL;
list_for_each_entry(p,&(head->list),list) //内核中的遍历函数
{
if(p->data == data) //p即为需要找的节点
{
printf("found the data:%d\n",p->data);
goto OK;
}
}

puts("not found the data!");
return NULL;

OK:
return p;
}

int show_node(node tmp)
{
if(tmp == NULL)
{
puts("tmp is NULL!");
return -1;
}
printf("the data is %d\n",tmp->data);
return 0;
}

int delete_node(node head,int data)
{
node p = NULL;
list_for_each_entry(p,&(head->list),list)
{
if(p->data == data)
{
printf("found the data which you want to delete!\n");
goto f;
}
}

f:
list_del(&(p->list));
free(p);
return 0;
}

int show_list(node head)
{
node p = NULL;
list_for_each_entry(p,&(head->list),list)
{
printf("data:%d\n",p->data);
}
return 0;
}

int delete_list(node head)//删除链表函数
{
node p,q;
list_for_each_entry_safe(p,q,&(head->list),list)//这是内核中的安全删除函数
{
list_del(&(p->list));
free(p);
}

list_del(&(head->list));
free(head);
return 0;
}
int main(int argc,char **argv)
{
node head;
node tmp;
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);//删除链表函数
return 0;
}

以上就是Linux中的内核链表实例详解的实例如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(0)

相关推荐

  • Linux 内核通用链表学习小结

    描述 在linux内核中封装了一个通用的双向链表库,这个通用的链表库有很好的扩展性和封装性,它给我们提供了一个固定的指针域结构体,我们在使用的时候,只需要在我们定义的数据域结构体中包含这个指针域结构体就可以了,具体的实现.链接并不需要我们关心,只要调用提供给我们的相关接口就可以完成了. 传统的链表结构 struct node{ int key; int val; node* prev; node* next; } linux 内核通用链表库结构 提供给我们的指针域结构体: struct list

  • Linux内核链表实现过程

    关于双链表实现,一般教科书上定义一个双向链表节点的方法如下: 复制代码 代码如下: struct list_node{stuct list_node *pre;stuct list_node *next;ElemType data; } 即一个链表节点包含:一个指向前向节点的指针.一个指向后续节点的指针,以及数据域共三部分.但查看linux内核代码中的list实现时,会发现其与教科书上的方法有很大的差别.来看看linux是如何实现双链表.双链表节点定义 复制代码 代码如下: struct lis

  • Linux中的内核链表实例详解

    Linux中的内核链表实例详解 链表中一般都要进行初始化.插入.删除.显示.释放链表,寻找节点这几个操作,下面我对这几个操作进行简单的介绍,因为我的能力不足,可能有些东西理解的不够深入,造成一定的错误,请各位博友指出. A.Linux内核链表中的几个主要函数(下面是内核中的源码拿出来给大家分析一下) 1)初始化: #define INIT_LIST_HEAD(ptr) do { \ (ptr)->next = (ptr); (ptr)->prev = (ptr); \ } while (0)

  • Linux中对MySQL优化实例详解

    Linux中对MySQL优化实例详解 vim /etc/my.cnf以下只列出my.cnf文件中[mysqld]段落中的内容,其他段落内容对MySQL运行性能影响甚微,因而姑且忽略. [mysqld] port = 3306 serverid = 1 socket = /tmp/mysql.sock skip-locking 避免MySQL的外部锁定,减少出错几率增强稳定性. skip-name-resolve 禁止MySQL对外部连接进行DNS解析,使用这一选项可以消除MySQL进行DNS解析

  • linux 中的ls命令参数详解及ls命令的使用实例

    一.ls命令参数详解 可以通过阅读 ls 的说明书页(man ls)来获得选项的完整列表. -a – 全部(all).列举目录中的全部文件,包括隐藏文件(.filename).位于这个列表的起首处的 .. 和 . 依次是指父目录和你的当前目录. -l – 长(long).列举目录内容的细节,包括权限(模式).所有者.组群.大小.创建日期.文件是否是到系统其它地方的链接,以及链接的指向. -F – 文件类型(File type).在每一个列举项目之后添加一个符号.这些符号包括:/ 表明是一个目录:

  • Linux内存描述符mm_struct实例详解

    Linux对于内存的管理涉及到非常多的方面,这篇文章首先从对进程虚拟地址空间的管理说起.(所依据的代码是2.6.32.60) 无论是内核线程还是用户进程,对于内核来说,无非都是task_struct这个数据结构的一个实例而已,task_struct被称为进程描述符(process descriptor),因为它记录了这个进程所有的context.其中有一个被称为'内存描述符'(memory descriptor)的数据结构mm_struct,抽象并描述了Linux视角下管理进程地址空间的所有信息

  • Linux消息队列实现进程间通信实例详解

    Linux消息队列实现进程间通信实例详解 一.什么是消息队列 消息队列提供了一种从一个进程向另一个进程发送一个数据块的方法.  每个数据块都被认为含有一个类型,接收进程可以独立地接收含有不同类型的数据结构.我们可以通过发送消息来避免命名管道的同步和阻塞问题.但是消息队列与命名管道一样,每个数据块都有一个最大长度的限制. Linux用宏MSGMAX和MSGMNB来限制一条消息的最大长度和一个队列的最大长度. 二.在Linux中使用消息队列 Linux提供了一系列消息队列的函数接口来让我们方便地使用

  • Linux启动与自启动的实例详解

    Linux启动与自启动的实例详解 一 启动与自启动 服务启动:就是在当前系统中让服务运行,并提供功能. 服务自启动:自启动是指让服务在系统开机或重启动之后,随着系统的启动而自动启动服务. 二 查询已安装的服务 三 RPM安装服务和源码包安装服务的区别 RPM安装服务和源码包安装服务的区别就是安装位置的不同 源码包安装在指定位置,一般是/usr/local/ RPM包安装在默认位置上 以上就是Linux 中启动与自启动的实例,如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大

  • Linux C字符串替换函数实例详解

    Linux C字符串替换函数实例详解 最近学习linux 的基础编程知识,字符串替换函数,在网上找下资料,觉得这篇文章写的不错,记录下来,和大家分享一下: 实例代码: #include <stdio.h> #include <string.h> #include <stdlib.h> /** * * @author: cnscn@163.com * @reference: lovesnow1314@http://community.csdn.net/Expert/Top

  • linux更改目录显示颜色实例详解

    linux更改目录显示颜色实例详解 用shell列举目录的时候,文件夹都是蓝色的,背景是黑色,使得无法看清蓝色的文件名称,看起来很痛苦.这个已经好几次遇到这个问题了都没有把解决方法记录下来,导致每次要查一些资料,这次决定把这个方法整理下来,供以后遇到同样的情况之后使用. 针对文件的解决方式 为当前用户配置,在当前用户home目录下的./bashrc中添加下面的参数即可. 在这里简单修改了文件夹的格式为粗体,前景色是黄色,背景色是黑色.还有引用为粗体,青色前景色,黑色背景色. 这里着重调一下di相

  • Linux基础命令last 命令实例详解

    Linux last命令用于显示系统开机以来获是从每月初登入者的讯息. 使用权限:所有使用者. last 显示以前登录过的用户信息,last指令会搜索/var/log/wtmp文件(或者是经过-f选项指定的文件),然后列出文件中所有的用户信息.如果执行last指令时提示"last /var/log/wtmp∶ NO such file or directory",则需要使用指令touch /var/log/wtmp手工创建此文件 lastb指令用来显示登录失败的用户信息,其用法和las

  • Linux中selinux基础配置教程详解

    selinux(Security-Enhanced Linux)安全增强型linux,是一个Linux内核模块,也是Linux的一个安全子系统. 三种模式: Enforcing:强制模式,在selinux运作时,已经开始限制domain/type. permissive: 警告模式,在selinux运作时,会有警告讯息,但不会限制domain/type的存取. disabled: 关闭模式. 可用getenforce查看selinux状态 selinux对文件的作用: 当开启selinux后,s

随机推荐