【官方澳门新永利下载】深入浅出Linux之内核数据结构

看libuv源码的时候,开采不但代码中选取了双向链表,还大概有四人作品打开树和红黑树的达成,全部都以linux内核风格的,数据和操作分开,通过宏封装了指针的操作,实现的要命精美。

基础使用的数据结构有双向链表,单向链表和hash链表。其余,基树和红黑树也是内核使用的数据结构。实际上,那也是程序代码中平日选择的数据结构,一些偏僻难的数据结构并不经常见。

把树的源码copy出来,发掘使用起来也特别的轻松。看看哪些利用的啊。

  1. container

源码在此间

 
container是linux很首要的一个定义。有了container方法,本领完结对指标的包装。

是因为红黑树比伸展树牛逼,libuv也未曾运用伸展树,上面就只聊聊红黑树了。

  解析一下container方法。

下边包车型大巴代码是一个整机的例证。测验了插入,遍历,查找,删除,逆向遍历。

======================================================================

#include "stdafx.h"#include "tree.h"#include <malloc.h>struct node { RB_ENTRY entry; int i;};intintcmp(struct node *e1, struct node *e2){ return (e1->i < e2->i ? -1 : e1->i > e2->i);}RB_HEAD(inttree, node) head = RB_INITIALIZER(&head);RB_GENERATE(inttree, node, entry, intcmp)int testdata[] = { 20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 10, 19, 5, 9, 12, 15, 18, 7, 11, 14,30,31,32,33};int main(){ int i; struct node *n; for (i = 0; i < sizeof / sizeof(testdata[0]); i++) { if ((n = (struct node *)malloc(sizeof(struct node))) == NULL) { printf("malloc return null!!!n"); return -1; } n->i = testdata[i]; RB_INSERT(inttree, &head, n); } printf("====================RB_FOREACH=========================n"); RB_FOREACH(n, inttree, &head) { printf("%dt", n->i); } printf("====================RB_NFIND=========================n"); { struct node theNode; theNode.i = 28; n = RB_NFIND(inttree, &head, &theNode); printf("%dn", n->i); } printf("====================RB_FIND=========================n"); { struct node theNode; theNode.i = 20; n = RB_FIND(inttree, &head, &theNode); printf("%dn", n->i); } printf("====================RB_REMOVE=========================n"); { struct node theNode; theNode.i = 20; n = RB_FIND(inttree, &head, &theNode); printf("find %d firstn", n->i); n = RB_REMOVE(inttree, &head, n); printf("remove %d successn", n->i); } printf("====================RB_FOREACH_REVERSE=========================n"); RB_FOREACH_REVERSE(n, inttree, &head) { printf("%dt", n->i); } printf; getchar(); return ;}

#define container_of(ptr, type, member) ({              

程序运转结果

        const typeof( ((type *)0)->member ) *__mptr = (ptr);     

官方澳门新永利下载 1红黑树运营结果

        (type *)( (char *)__mptr – offsetof(type,member) );})

能够小心以下几点

 
那些主意美妙的达成了通过结构的贰个分子找到任何结构的地方。有了container方法,list才

  1. 数据结构的定义使用RB_ENTRY插入了树的数据结构,而团结的数据足以自由定义

产生了多少个通用的数据结构,通过container方法,还是能完毕基础的包装,程序之间不揭破

内部的数据。

struct node { RB_ENTRY entry; int i;};

 

  1. 正如函数intcmp福寿康宁了整数的相比,红黑树能够用来排序,能够按优先级抽取数据,比队列的查究速度快。libuv中的timer和signal都采纳了rbt。

  2. RB_GENERATE发出代码由于c语言未有模板,亦不是面向对象,亦不是弱类型的,所以通过宏生成梯次差异名字的红黑树代码是丰盛抢眼的,实际上和cpp的模版是四个功力啊。但是用宏来张开代码没有办法用断点调节和测验,笔者想笔者是先写好测量检验用例,或许通过打字与印刷来调度,最终没难点在转成宏的呢。别的,这种方法导致变化的代码非常多,和模板的劣点是平等的。

  3. 宏的工夫这里的宏都需求传入名字,使用了字符串拼接的技巧:譬如RB_ENTRY entry;

  1. 双向链表list

出于算法确实比较复杂,从前钻探过三回,以往都记不知晓了,表明记住算法的步奏确实是从未有过须求的,假设想商量算法,确认他的成效和正确,有意思味的能够去拜望那篇作品,作者觉着讲的依然很明亮的。

  List定义在/include/linux目录下。首先走访list的布局定义:

其余《算法导论》中也对红黑树讲的可比多。

  struct list_head {

对源码中一个空头的宏RB_AUGMENT备感很意外,不知道为何的。有通晓的同窗留言啊。

       struct list_head *next, *prev;

#ifndef RB_AUGMENT#define RB_AUGMENT do {} while #endif

  };

 
List是双向链表的二个虚幻,list库提供了list_entry,使用了container方法,通过container
能够从list找到任何数据对象,那样list就成为了一种通用的数据结构。

======================================================================

#define list_entry(ptr, type, member)

       container_of(ptr, type, member)

 

  内核定义了广大对list结构操作的内联函数和宏,计有:

  •    LIST_HEAD:定义并开端化四个list链表
  •    list_add_tail:加三个分子到链表尾
  •    list_del:删除贰个list成员

  •    list_empty:检查链表是还是不是为空

  •    list_for_each:遍历链表。获得链表指针。
  •   
    list_for_each_safe:遍历链表。和list_for_each不相同是能够去除遍历的分子
  •    list_for_each_entry:遍历链表,通过container方法重回结构指针。

3.  hash list

  Hash list和双向链表list很相像,它适用于hash表。看一下hash
list的head定义:

 struct hlist_head {

       struct hlist_node *first;

};

 
和平日的list相比,hlist头只有一个指针,这样就节省了贰个指南针的内部存款和储蓄器。即便hash表极其

壮大,那么种种hash
表头节省一个指南针,整个hash表节省的内部存款和储蓄器就很惊人了。那便是根本

中等专门的工作高校门定义hash list的来头。

 

Hash list库提供的函数和list很日常,计有:

发表评论

电子邮件地址不会被公开。 必填项已用*标注