libuv tree的实现

作者: 转角遇见一直熊 | 来源:发表于2016-06-30 17:32 被阅读472次

    看libuv源码的时候,发现不仅代码中使用了双向链表,还有一个伸展树和红黑树的实现,全部是linux内核风格的,数据和操作分开,通过宏封装了指针的操作,实现的非常精妙。

    把树的源码copy出来,发现使用起来也非常的简单。看看如何使用的吧。

    源码在这里https://github.com/libuv/libuv/blob/v1.x/include/tree.h

    由于红黑树比伸展树牛逼,libuv也没有使用伸展树,下面就只聊聊红黑树了。

    如何使用libuv的红黑树

    下面的代码是一个完整的例子。测试了插入,遍历,查找,删除,逆向遍历。

    
    #include "stdafx.h"
    #include "tree.h"
    #include <malloc.h>
    
    struct node {
        RB_ENTRY(node) entry;
        int i;
    };
    
    int
    intcmp(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(testdata) / 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("%d\t", n->i);
        }
    
        printf("====================RB_NFIND=========================\n");
        {
        struct node theNode;
        theNode.i = 28;
        n = RB_NFIND(inttree, &head, &theNode);
        printf("%d\n", n->i);
        }
    
        printf("====================RB_FIND=========================\n");
        {
        struct node theNode;
        theNode.i = 20;
        n = RB_FIND(inttree, &head, &theNode);
        printf("%d\n", n->i);
        }
    
        printf("====================RB_REMOVE=========================\n");
        {
            struct node theNode;
            theNode.i = 20;
            n = RB_FIND(inttree, &head, &theNode);
            printf("find %d first\n", n->i);
            n = RB_REMOVE(inttree, &head, n);
            printf("remove %d success\n", n->i);
        }
    
        printf("====================RB_FOREACH_REVERSE=========================\n");
        RB_FOREACH_REVERSE(n, inttree, &head) {
            printf("%d\t", n->i);
        }
        printf("\n");
    
        getchar();
        return (0);
    }
    

    程序运行结果

    红黑树运行结果

    可以注意以下几点

    1. 数据结构的定义
      使用RB_ENTRY插入了树的数据结构,而自己的数据可以任意定义
    struct node {
        RB_ENTRY(node) entry;
        int i;
    };
    
    1. 比较函数
      intcmp实现了整数的比较,红黑树可以用来排序,可以按优先级取出数据,比队列的查找速度快。libuv中的timer和signal都使用了rbt。

    2. RB_GENERATE产生代码
      由于c语言没有模板,也不是面向对象,也不是弱类型的,所以通过宏生成各个不同名字的红黑树代码是非常巧妙的,实际上和cpp的模板是一个效果啊。不过用宏来展开代码没法用断点调试,我想作者是先写好测试用例,或者通过打印来调试,最后没问题在转成宏的吧。另外,这种方式导致生成的代码比较多,和模板的缺点是一样的。

    3. 宏的技巧
      这里的宏都需要传入名字,使用了字符串拼接的技术:比如RB_ENTRY(node) entry;

    红黑树插入删除算法

    由于算法确实比较复杂,以前研究过几次,现在都记不清楚了,说明记住算法的步奏确实是没有必要的,如果想研究算法,确认他的效率和正确性,有兴趣的可以去看看这篇文章,我觉得讲的还是很清楚的。https://zh.wikipedia.org/wiki/红黑树

    另外《算法导论》中也对红黑树讲的比较多。

    疑问

    对源码中一个无用的宏RB_AUGMENT感觉很奇怪,不知道干什么的。有知道的同学留言啊。

    #ifndef RB_AUGMENT
    #define RB_AUGMENT(x)  do {} while (0)
    #endif
    

    相关文章

      网友评论

        本文标题:libuv tree的实现

        本文链接:https://www.haomeiwen.com/subject/nplxjttx.html