linux内核链表的移植与使用

一、
   Linux内核链表为双向循环链表,和数据结构中所学链表类似,具体不再细讲。由于在内核中所实现的函数十分经典,所以移植出来方便后期应用程序中的使用。

/*********************************** 
文件名:kernel link list of linux.h
作者:Bumble Bee
日期:2015-1-31 
功能:移植linux内核链表 
************************************/

/*链表结点数据结构*/
struct list_head 
{
    struct list_head *next, *prev;
};

/***********************************
函数名:  INIT_LIST_HEAD
参数:    指向list_head结构体的指针
返回值:  无
函数功能:通过将前向指针和后向指
          针指向自己来创建一个链表表
          头
***********************************/
static inline void INIT_LIST_HEAD(struct list_head *list)
{
    list->next = list;
    list->prev = list;
}

/***********************************
函数名:  __list_add
参数:    @new:要插入结点的指针域
          @prev:前一个节点的指针域
          @next:后一个节点的指针域
返回值:  无
函数功能:在两个已知节点中插入新节点
***********************************/

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;
}
extern void __list_add(struct list_head *new,
               struct list_head *prev, struct list_head *next);

/**************************************
函数名:  list_add
参数:    @new:要插入结点的指针域
          @head:要插入链表表头的指针域
返回值:  无
函数功能:在已知链表头部插入新节点
**************************************/

static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}


/**************************************
函数名:  list_add_tail
参数:    @new:要插入结点的指针域
          @head:要插入链表表头的指针域
返回值:  无
函数功能:在已知链表尾部插入新节点
**************************************/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

/*************************************
函数名:  list_for_each
参数:    @pos:遍历链表的光标
          @head:要遍历链表的表头
返回值:  无
函数功能:实质为一个for循环,遍历链表
*************************************/
#define list_for_each(pos, head)     for (pos = (head)->next;pos != (head);         pos = pos->next)


/*************************************************
函数名:  list_entry
参数:    @ptr:节点中list_head的地址
          @type:节点的类型
          @member:list_head 在结构体中成员的名字
返回值:  节点的地址,已被强制转化为type型指针
函数功能:将节点最低位置假设为0,此时取成员member
          的地址即为offset,再用list_head的地址将
          offset减去即为节点的地址
**************************************************/
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

#define container_of(ptr, type, member) ({                const typeof(((type *)0)->member) * __mptr = (ptr);        (type *)((char *)__mptr - offsetof(type, member)); })

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)


static inline void __list_del(struct list_head *prev, struct list_head *next)
{
    next->prev = prev;
    prev->next = next;
}
static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
}

二、设计应用程序测试链表

/**************************** 
文件名:homework.c
作者:Bumble Bee
日期:2015-1-31 
功能:测试移植的linux内核链表 
*****************************/

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

struct score
{
    int num;
    int english;
    int math;
    struct list_head list;
};

struct score stu1,stu2,stu3,*temp;

struct list_head score_head,*pos;

int main()
{
    INIT_LIST_HEAD(&score_head);                    //创建链表函数

    stu1.num = 1;
    stu1.english = 0;
    stu1.math = 0;
    list_add_tail(&(stu1.list),&(score_head));

    stu2.num = 2;
    stu2.english = 1;
    stu2.math = 1;
    list_add_tail(&(stu2.list),&(score_head));

    stu3.num = 3;
    stu3.english = 2;
    stu3.math = 2;
    list_add_tail(&(stu3.list),&(score_head));

    list_del(&(stu2.list));

    list_for_each(pos,&(score_head))
    {
        temp = list_entry(pos,struct score,list);
        printf("No %d,english is %d,math is %d\n",temp->num,temp->english,temp->math);
    }

    return 0;

}

三、运行结果

  技术分享

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。