ITKeyword,专注技术干货聚合推荐

注册 | 登录

Linux内核数据结构(一)

LifeProgramming 分享于

2020腾讯云10周年活动,优惠非常大!(领取2860元代金券),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1040

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

推荐:Linux内核数据结构

分类:  Linux内核学习  Linux设备驱动2011-01-05 11:55 107人阅读  评论(0)  收藏  举报   链表,队列,映射,二叉树等数据结构是程序设计中常用的数据结构。为

 

链表,队列,映射,二叉树等数据结构是程序设计中常用的数据结构。为了统一这些数据结构的操作接口,Linux内核开发者实现了一些标准的操作接口及实现(使用了大量的GNU扩展特性),以达到代码重用,开发者应该尽量使用这些标准接口,避免实现自己的再创造,虽然那样看起来很酷,很有劲。

 

有关链表

 

传统的双向链表实现方法是在链表元素中加入两个指针,然后用这些指针来构造双向链表。如下所示

struct node{ value_type value; struct element *prev; struct element *next; }node, *list_head;

其示意图如下:NULL为空指针。

 

如果将双向链表中的首尾两个元素进行链接,则会形成循环双向链表。示意图如下:

 

由上可以看出,如果想得到链表中某个指定节点,必须要遍历链表。所以,对于那些需要随机存取的数据,尽量使用数组,而不是链表,当然也可以配合一个哈希表来使用链表,有兴趣的同志可以看看。

 

上面的实现方法没有问题,但是对于内核来说,如果每个内核对象都采用这种方法,那么要为每个结构体添加相应代码,还要实现其链表操作函数。这样很麻烦,而且也不能达到代码复用以及提供统一的接口。所以内核开发者采用了另外一种巧妙的方法:声明list_head这么一个结构,然后只要嵌入这么一个数据结构就可以实现双向链表了。

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


假设你想以链表形式存储自己的课程与成绩,则可以采用下面的形式

struct cource_score{ int num; int score; struct list_head list; };

这样,就利用成员变量list将所有的链表节点连接起来,当然,一般还要设置一个头结点。


除此之外,开发者还提供了一些函数和宏用于链表操作。如使用container_of()可以通过list成员获得course_score结构体的地址。

#define container_of(ptr, type, member) ({ / const typeof( ((type *)0)->member ) *_mptr = (ptr); / (type *)( (char *)_mptr - offsetof(type, member) ) ;}) #define offsetof(type, member) ((ssize_t)&(type *)0)->member) #define list_entry(ptr, type, member) / constainer_of(ptr, type, member)

宏container_of使用了GNU扩展。分析一下这个宏定义,首先注意ptr为指向容器结构体的指针,type为容器结构体的类型,而member则是其内嵌的list_head成员变量的名称,如上例,type为course_score,而member则为list。

(type *)0将地址0转换为结构type的地址

(type *)0->member获取type机构体中member成员变量的偏移地址。由于容器结构体的地址为0,这就是member成员的偏移地址,所以宏offsetof也就是这个作用。

typeof(  ((type *)0->member)返回member成员的类型,然后将指针_mptr声明为该类型的指针,并赋值为ptr。

(type *)((char *)_mptr - offsetof(type, member));})则根据member成员的实际_mptr以及偏移量offsetof()则可以得到容器结构体的地址。

 

当有两种方法可以初始化链表,静态初始化和动态初始化。

 

 

#define LIST_HEAD_INIT(name) {&(name),&name)} #define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name) #define INIT_LIST_HEAD(ptr) do{/ (ptr)->next = (ptr);(ptr)->next = (ptr);/ }while (0) static inline void INIT_LIST_HEAD(struct list_head * list) { list->next = list; list->prev = list; }

如果在编码时初始化链表,则可以使用宏LIST_HEAD_INIT,如上例中,则可以

推荐:linux内核数据结构之kfifo

1、前言   最近项目中用到一个环形缓冲区(ring buffer),代码是由linux内核的kfifo改过来的。缓冲区在文件系统中经常用到,通过缓冲区缓解cpu读写内存和读写

struct course_score math = { num = 1; score = 60; list = LIST_HEAD_INIT(math.list); };

 

如果是运行时初始化链表,则可以使用宏INIT_LIST_HEAD或者内联函数INIT_LIST_HEAD来初始化,两者功能一样,只是内联函数提供了类型检测。如下所示

struct course_score *math; math = kmalloc(sizeof(struct course_score)); math->num = 1; math->score = 60; INIT_HEAD_LIST(&math->list);

 


链表的其他操作包括添加、删除、合并、遍历等。

插入节点

static inline void list_add(struct list_head * new , struct list_head * head) { __list_add(new , head, head->next); } static inline void list_add_tail(struct list_head * new ,struct list_head * head) { __list_add(new , head->prev, head); } struct 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 ; }

插入操作有两种:表头插入和表尾插入。实际上,两种插入的方法是一样的,只是内部函数调用时,参数不同而已。

 

 

删除节点

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); entry->next = LIST_POSITION; entry->prev = LIST_POSITION; }

 

对 LIST_POISON1,LIST_POISON2 的解释:

These are non-NULL pointers that will result in page faults under normal circumstances, used to verify that nobody uses  non-initialized list entries.

#define LIST_POISON1 ((void *) 0x00100100) #define LIST_POISON2 ((void *) 0x00200200)

 

 

移动节点

static inline void list_move(struct list_head * list, struct list_head * head) { __list_del(list->prev, list->next); list_add(list, head); } static inline void list_move_tail(struct list_head * list, struct list_head * head) { __list_del(list->prev, list->next); list_add_tail(list, head); }

 

链表合并

static inline void _list_splice(struct list_head * list, struct list_head * head) { struct list_head * first = list->next; struct list_head * last = list->prev; struct list_head * at = head->next; first->prev = head; head->next = first; last->next = at; at->prev = last; } static inline void list_splice(struct list_head * list, struct list_head * head) { if(!list_empty(list)) __list_splice(list, head); }   

 

将一个非空链表插入到另外一个链表中。先做链表是否为空的检查,因为每个链表只有一个头节点,将空链表插入到另外一个链表中是没有意义的。但被插入的链表可以是空的。两个链表有两个头结点,在函数中要去掉一个头结点。

 

链表遍历

#define list_for_each(pos, head)/ for(pos = (head)->next; prefetch(pos->next), pos != (head); static inline void prefetch(void *x) { asm volatile("prefetch0 %0": : "m"(* unsigned long *)x)); } #define list_for_each_entry(pos, head, member) / for(pos = list_entry((head)->next, typeof(*pos),member); / prefetch(pos->member.next), &pos->member != (head); / pos = list_entry(pos->member.next, typeof(*pos),member))


prefetch为预取函数,提前预取下一指令,能提高程序执行速度。

 

推荐:Linux内核数据结构——链表

目录 目录 简介 单向链表 双向链表 环形链表 Linux内核中的链表实现 offsetof container_of container_of 第一部分 container_of 第二部分 链表初始化 向链表中

  链表,队列,映射,二叉树等数据结构是程序设计中常用的数据结构。为了统一这些数据结构的操作接口,Linux内核开发者实现了一些标准的操作接口及实现(使用了大量的GNU扩展特性),以达到代码

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。