搜索
首页后端开发php教程nginx的数据结构2——自己动手重写红黑树
nginx的数据结构2——自己动手重写红黑树
WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Jul 30, 2016 pm 01:31 PM
nodeparentquot

    费话不多说，上重写代码，这次姑且用英语写的注释当复习英语了。

    rbtree.h：

/*
 * Copyright (C) Bipedal Bit
 * Verson 1.0.0.1
 */

#ifndef _RBTREE_H_INCLUDED_
#define _RBTREE_H_INCLUDED_

/* the node structure of the red-black tree */
typedef struct rbtree_node_s rbtree_node_t;
/* Using type int means its range is -0x7fffffff-1~0x7fffffff. */
typedef int rbtree_key_t;
/* Abstract type is complicated to achieve with C so I use char* instead. */
typedef char* rbtree_data_t;

struct rbtree_node_s
{
	/* key of the node */
	rbtree_key_t	key;
	/* pointer of the parent of the node */
	rbtree_node_t*	parent;
	/* pointer of the left kid of the node */
	rbtree_node_t*	left;
	/* pointer of the right kid of the node */
	rbtree_node_t*	right;
	/* color of the node */
	unsigned char	color;
	/* pointer of the value of the node corresponding to the key */
	rbtree_data_t	value;
};

/* the tree object stucture of the red-black tree */
typedef struct rbtree_s rbtree_t;
/* foundational insert function pointer*/
typedef void (*rbtree_insert_p) (rbtree_t* root, rbtree_node_t* node);

struct rbtree_s
{
	/* the pointer of the root node of the tree */
	rbtree_node_t* root;
	/* black leaf nodes as sentinel */
	rbtree_node_t* sentinel;
	/* the polymorphic insert function pointer */
	rbtree_insert_p insert;
};

/* macros */
#define rbtree_init(tree, s, i)		\
rbtree_sentinel_init(s);			\
(tree)->root = s;				\
(tree)->sentinel = s;			\
(tree)->insert = i

#define rbtree_red(node)	((node)->color = 1)
#define rbtree_black(node)	((node)->color = 0)
#define rbtree_is_red(node)	((node)->color)
#define rbtree_is_black(node)	(!rbtree_is_red(node))
 /* copy n2's color to n1 */
#define rbtree_copy_color(n1, n2)	(n1->color = n2->color)
/* sentinel must be black cuz it's leaf node */
#define rbtree_sentinel_init(node)	rbtree_black(node)

/* statements of public methods */
void rbtree_insert_value(rbtree_t* tree, rbtree_node_t* node);
void rbtree_insert(rbtree_t* tree, rbtree_node_t* node);
void rbtree_delete(rbtree_t* tree, rbtree_node_t* node);
rbtree_node_t* rbtree_find(rbtree_t* tree, rbtree_key_t key);

#endif	/* _RBTREE_H_INCLUDED_ */

    看过nginx源码的有心人会发现，我的头文件相对于ngx_rbree.h改动不大，非常像。

    关键的rbtree.c：

/*
 * Copyright (C) Bipedal Bit
 * Verson 1.0.0.1
 */

#include <stddef.h>
#include "rbtree.h"

/* inline methods */
/* get the node with the minimum key in a subtree of the red-black tree */
static inline rbtree_node_t*
rbtree_subtree_min(rbtree_node_t* node, rbtree_node_t* sentinel)
{
    while(node->left != sentinel)
    {
        node = node->left;
    }

    return node;
}

/* replace the node "node" in the tree with node "tmp" */
static inline void rbtree_replace(rbtree_t* tree,
    rbtree_node_t* node, rbtree_node_t* tmp)
{
    /* upward: p[node] parent = node->parent;

    if (node == tree->root)
    {
        tree->root = tmp;
    }
    else if (node == node->parent->left)
    {
        /* downward: left[p[node]] parent->left = tmp;
    }
    else
    {
        /* downward: right[p[node]] parent->right = tmp;
    }

    node->parent = tmp;
}

/* change the topologic structure of the tree keeping the order of the nodes */
static inline void rbtree_left_rotate(rbtree_t* tree, rbtree_node_t* node)
{
    /* node as the var x in CLRS while tmp as the var y */
    rbtree_node_t* tmp = node->right;

    /* replace y with left[y] */
    /* downward: right[x] right = tmp->left;
    /* if left[[y] is not NIL it has a parent */
    if (tmp->left != tree->sentinel)
    {
        /* upward: p[left[y]] left->parent = node;
    }

    /* replace x with y */
    rbtree_replace(tree, node, tmp);
    tmp->left = node;
}

static inline void rbtree_right_rotate(rbtree_t* tree, rbtree_node_t* node)
{
    rbtree_node_t* tmp = node->left;

    /* replace y with right[y] */
    node->left = tmp->right;
    if (tmp->right != tree->sentinel)
    {
        tmp->right->parent = node;
    }

    /* replace x with y */
    rbtree_replace(tree, node, tmp);
    tmp->right = node;
}

/* static methods */
/* fix the red-black tree after the new node inserted */
static void rbtree_insert_fixup(rbtree_t* tree, rbtree_node_t* node)
{
    while(rbtree_is_red(node->parent))
    {
        if (node->parent == node->parent->parent->left)
        {
            /* case 1: node's uncle is red */
            if (rbtree_is_red(node->parent->parent->right))
            {
                rbtree_black(node->parent);
                rbtree_black(node->parent->parent->right);
                rbtree_red(node->parent->parent);
                node = node->parent->parent;
                /* Then we can consider the whole subtree */
                /* which is represented by the new "node" as the "node" before */
                /* and keep looping till "node" become the root. */
            }
            /* case 2: node's uncle is black */
            else
            {
                /* ensure node is the left kid of its parent */
                if (node == node->parent->right)
                {
                    node = node->parent;
                    rbtree_left_rotate(tree, node);
                }
                /* case 2 -> case 1 */
                rbtree_black(node->parent);
                rbtree_red(node->parent->parent);
                rbtree_right_rotate(tree, node->parent->parent);
            }
        }
        /* same as the "if" clause before with "left" and "right" exchanged */
        else
        {
            if (rbtree_is_red(node->parent->parent->left))
            {
                rbtree_black(node->parent);
                rbtree_black(node->parent->parent->left);
                rbtree_red(node->parent->parent);
                node = node->parent->parent;
            }
            else
            {
                if (node == node->parent->left)
                {
                    node = node->parent;
                    rbtree_right_rotate(tree, node);
                }
                rbtree_black(node->parent);
                rbtree_red(node->parent->parent);
                rbtree_left_rotate(tree, node->parent->parent);
            }
        }
    }
    /* ensure the root node being black */
    rbtree_black(tree->root);
}

static void rbtree_delete_fixup(rbtree_t* tree, rbtree_node_t* node)
{
    rbtree_node_t* brother = NULL;

    while(node != tree->root && rbtree_is_black(node))
    {
        if (node == node->parent->left)
        {
            brother = node->parent->right;
            if (rbtree_is_red(brother))
            {
                rbtree_black(brother);
                rbtree_red(node->parent);
                rbtree_left_rotate(tree, node->parent);
                /* update brother after topologic change of the tree */
                brother = node->parent->right;
            }

            if (rbtree_is_black(brother->left) && rbtree_is_black(brother->right))
            {
                rbtree_red(brother);
                /* go upward and keep on fixing color */
                node = node->parent;
            }
            else
            {
                if (rbtree_is_black(brother->right))
                {
                    rbtree_black(brother->left);
                    rbtree_red(brother);
                    rbtree_right_rotate(tree, brother);
                    /* update brother after topologic change of the tree */
                    brother = node->parent->right;
                }
                rbtree_copy_color(brother, node->parent);
                rbtree_black(node->parent);
                rbtree_black(brother->right);
                rbtree_left_rotate(tree, node->parent);
                /* end the loop and ensure root is black */
                node = tree->root;
            }
        }
        /* same as the "if" clause before with "left" and "right" exchanged */
        else
        {
            brother = node->parent->left;
            if (rbtree_is_red(brother))
            {
                rbtree_black(brother);
                rbtree_red(node->parent);
                rbtree_left_rotate(tree, node->parent);
                brother = node->parent->left;
            }

            if (rbtree_is_black(brother->left) && rbtree_is_black(brother->right))
            {
                rbtree_red(brother);
                node = node->parent;
            }
            else
            {
                if (rbtree_is_black(brother->left))
                {
                    rbtree_black(brother->right);
                    rbtree_red(brother);
                    rbtree_right_rotate(tree, brother);
                    brother = node->parent->left;
                }
                rbtree_copy_color(brother, node->parent);
                rbtree_black(node->parent);
                rbtree_black(brother->left);
                rbtree_left_rotate(tree, node->parent);
                node = tree->root;
            }
        }
    }

    rbtree_black(node);
}

/* public methods */
void rbtree_insert_value(rbtree_t* tree, rbtree_node_t* node)
{
    /* Using ** to know wether the new node will be a left kid */
    /* or a right kid of its parent node. */
    rbtree_node_t** tmp = &tree->root;
    rbtree_node_t* parent;

    while(*tmp != tree->sentinel)
    {
        parent = *tmp;
        tmp = (node->key key) ? &parent->left : &parent->right;
    }

    /* The pointer knows wether the node should be on the left side */
    /* or on the right one. */
    *tmp = node;
    node->parent = parent;
    node->left = tree->sentinel;
    node->right = tree->sentinel;
    rbtree_red(node);
}

void rbtree_insert(rbtree_t* tree, rbtree_node_t* node)
{
    rbtree_node_t* sentinel = tree->sentinel;

    /* if the tree is empty */
    if (tree->root == sentinel)
    {
        tree->root = node;
        node->parent = sentinel;
        node->left = sentinel;
        node->right = sentinel;
        rbtree_black(node);

        return;
    }

    /* generally */
    tree->insert(tree, node);
    rbtree_insert_fixup(tree, node);
}

void rbtree_delete(rbtree_t* tree, rbtree_node_t* node)
{
    rbtree_node_t* sentinel = tree->sentinel;
    /* wether "node" is on the left side or the right one */
    rbtree_node_t** ptr_to_node = NULL;
    /* "cover" is the node which is going to cover "node" */
    rbtree_node_t* cover = NULL;
    /* wether we lossing a red node on the edge of the tree */
    int loss_red = rbtree_is_red(node);
    int is_root = (node == tree->root);

    /* get "cover" & "loss_red"  */
    /* sentinel in "node"'s kids */
    if (node->left == sentinel)
    {
        cover = node->right;
    }
    else if (node->right == sentinel)
    {
        cover = node->left;
    }
    /* "node"'s kids are both non-sentinel */
    else
    {
        /* update "node" & "loss_red" & "is_root" & "cover" */
        cover = rbtree_subtree_min(node->right, sentinel);
        node->key = cover->key;
        node->value = cover->value;
        node = cover;
        loss_red = rbtree_is_red(node);
        is_root = 0;
        /* move "cover"'s kids */
        /* "cover" can only be a left kid */
        /* and can only have a right non-sentinel kid */
        /* because of function "rbtree_subtree_min" */
        cover = node->right;
    }

    if (is_root)
    {
        /* update root */
        tree->root = cover;
    }
    else
    {
        /* downward link */
        if (node == node->parent->left)
        {
            node->parent->left = cover;
        }
        else
        {
            node->parent->right = cover;
        }
    }
    /* upward link */
    cover->parent = node->parent;
    /* "cover" may be a sentinel */
    if (cover != sentinel)
    {
        /* set "cover" */
        cover->left = node->left;
        cover->right = node->right;
        rbtree_copy_color(cover, node);
    }

    /* clear "node" since it's useless */
    node->key = -1;
    node->parent = NULL;
    node->left = NULL;
    node->right = NULL;
    node->value = NULL;

    if (loss_red)
    {
        return;
    }

    /* When lossing a black node on edge */
    /* the fifth rule of red-black tree will be broke. */
    /* So the tree need to be fixed. */
    rbtree_delete_fixup(tree, cover);
}

/* find the node in the tree corresponding to the given key value */
rbtree_node_t* rbtree_find(rbtree_t* tree, rbtree_key_t key)
{
    rbtree_node_t* tmp = tree->root;
    int step_cnt = 0;

    /* search the binary tree */
    while(tmp != tree->sentinel)
    {
        /* next line is just fot test */
        // step_cnt++;
        if(key == tmp->key)
        {
            /* next line is just for test */
            // printf("step count: %d, color: %s, ", step_cnt, rbtree_is_red(tmp) ? "red" : "black");
            return tmp;
        }

        tmp = (key key) ? tmp->left : tmp->right;
    }

    return NULL;
}
 </stddef.h>

    虽然明白nginx源码中100+行的长函数体也是一种避免太多函数调用增加时间空间开销的优化，我还是把所有函数都分类分割成100行以下。增加可读性是一方面，可能也是有点强迫症吧。之后会扩展几个统计方法，像max、min和mid，还会扩展一个遍历方法。

    下面是调用测试，test.c：

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

int main(int argc, char const *argv[])
{
    rbtree_t t = {};
    rbtree_node_t s = {};
    rbtree_init(&t, &s, rbtree_insert_value);

    const int cnt = 10;
    const int max_len = 15;

#define TEST_VALUES {"apple", "banana", "cherry", "grape", "lemon", "mango", "pear", "pineapple", "strawberry", "watermelon"}

    /* for gcc */
    char* v[] = TEST_VALUES;
    /* for g++ */
    // char v[][max_len] = TEST_VALUES;

    rbtree_node_t n[cnt];
    int i;
    for (i = 0; i value : "?");
    }

    rbtree_delete(&t, &n[5]);

    printf("\nafter delete 6->mango:\n\n");

    for (i = 1; i value : "?");
    }

    return 0;
}
</stdio.h>

    解开rbtree_find方法里的测试行注释，顺利执行：

key: 1
step count: 3, color: black, value: apple
key: 2
step count: 2, color: black, value: banana
key: 3
step count: 3, color: black, value: cherry
key: 4
step count: 1, color: black, value: grape
key: 5
step count: 3, color: black, value: lemon
key: 6
step count: 2, color: black, value: mango
key: 7
step count: 4, color: black, value: pear
key: 8
step count: 3, color: red, value: pineapple
key: 9
step count: 4, color: black, value: strawberry
key: 10
step count: 5, color: red, value: watermelon

after delete 6->mango:

key: 1
step count: 3, color: black, value: apple
key: 2
step count: 2, color: black, value: banana
key: 3
step count: 3, color: black, value: cherry
key: 4
step count: 1, color: black, value: grape
key: 5
step count: 3, color: black, value: lemon
key: 6
value: ?
key: 7
step count: 2, color: black, value: pear
key: 8
step count: 4, color: black, value: pineapple
key: 9
step count: 3, color: red, value: strawberry
key: 10
step count: 4, color: black, value: watermelon
    下面分别是删除6->mango前的红黑树和删除后的红黑树示意图：

    下面我们来做个大量数据的压力测试，注意把rbtree_find方法里的测试行注释掉，不然后果恐怕会比较吓人：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "rbtree.h"

int main(int argc, char const *argv[])
{
    double duration;
    double room;

    rbtree_t t = {};
    rbtree_node_t s = {};
    rbtree_init(&t, &s, rbtree_insert_value);

    const int cnt = 1<br>    来看看结果：<p></p>
<pre name="code">Inserting 1048576 nodes costs 48.00MB and spends 0.425416 seconds.
Searching 1024 nodes among 1048576 spends 0.001140 seconds.
Hash 1024 times spends 0.000334 seconds.
Deleting 1024 nodes among 1048576 spends 0.000783 seconds.
    删除比查找还快，耗时只有哈希查找的两倍多点，上百万的插入也耗时不足半秒，嗯我还挺满意的。

    写统计和遍历方法去了。

版权声明：本文为博主原创文章，未经博主允许不得转载。

以上就介绍了nginx的数据结构2——自己动手重写红黑树，包括了方面的内容，希望对PHP教程有兴趣的朋友有所帮助。

声明
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn
相关文章
node、nvm与npm有什么区别node、nvm与npm有什么区别Jul 04, 2022 pm 04:24 PM

node、nvm与npm的区别：1、nodejs是项目开发时所需要的代码库，nvm是nodejs版本管理工具，npm是nodejs包管理工具；2、nodejs能够使得javascript能够脱离浏览器运行，nvm能够管理nodejs和npm的版本，npm能够管理nodejs的第三方插件。

Vercel是什么？怎么部署Node服务？Vercel是什么？怎么部署Node服务？May 07, 2022 pm 09:34 PM

Vercel是什么？本篇文章带大家了解一下Vercel，并介绍一下在Vercel中部署 Node 服务的方法，希望对大家有所帮助！

node爬取数据实例：聊聊怎么抓取小说章节node爬取数据实例：聊聊怎么抓取小说章节May 02, 2022 am 10:00 AM

node怎么爬取数据？下面本篇文章给大家分享一个node爬虫实例，聊聊利用node抓取小说章节的方法，希望对大家有所帮助！

node导出模块有哪两种方式node导出模块有哪两种方式Apr 22, 2022 pm 02:57 PM

node导出模块的两种方式：1、利用exports，该方法可以通过添加属性的方式导出，并且可以导出多个成员；2、利用“module.exports”，该方法可以直接通过为“module.exports”赋值的方式导出模块，只能导出单个成员。

安装node时会自动安装npm吗安装node时会自动安装npm吗Apr 27, 2022 pm 03:51 PM

安装node时会自动安装npm；npm是nodejs平台默认的包管理工具，新版本的nodejs已经集成了npm，所以npm会随同nodejs一起安装，安装完成后可以利用“npm -v”命令查看是否安装成功。

聊聊V8的内存管理与垃圾回收算法聊聊V8的内存管理与垃圾回收算法Apr 27, 2022 pm 08:44 PM

本篇文章带大家了解一下V8引擎的内存管理与垃圾回收算法，希望对大家有所帮助！

node中是否包含dom和bomnode中是否包含dom和bomJul 06, 2022 am 10:19 AM

node中没有包含dom和bom；bom是指浏览器对象模型，bom是指文档对象模型，而node中采用ecmascript进行编码，并且没有浏览器也没有文档，是JavaScript运行在后端的环境平台，因此node中没有包含dom和bom。

聊聊Node.js path模块中的常用工具函数聊聊Node.js path模块中的常用工具函数Jun 08, 2022 pm 05:37 PM

本篇文章带大家聊聊Node.js中的path模块，介绍一下path的常见使用场景、执行机制，以及常用工具函数，希望对大家有所帮助！

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序，用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

显示更多

热门文章

R.E.P.O.能量晶体解释及其做什么（黄色晶体）
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
刺客信条阴影：贝壳谜语解决方案
1 周前ByDDD
R.E.P.O.如果您听不到任何人，如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌
在哪里可以找到原子中的起重机控制钥匙卡
1 周前ByDDD
显示更多

热工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

PhpStorm Mac 版本

PhpStorm Mac 版本

最新（2018.2.1 ）专业的PHP集成开发工具

Atom编辑器mac版下载

Atom编辑器mac版下载

最流行的的开源编辑器

mPDF

mPDF

mPDF是一个PHP库，可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件，并处理不同的语言。与原始脚本如HTML2FPDF相比，它的速度较慢，并且在使用Unicode字体时生成的文件较大，但支持CSS样式等，并进行了大量增强。支持几乎所有语言，包括RTL（阿拉伯语和希伯来语）和CJK（中日韩）。支持嵌套的块级元素（如P、DIV），

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

显示更多

热门话题

gmail邮箱登陆入口在哪里
7444
15
CakePHP 教程
1371
52
steam的账户名称是什么格式
76
11
win11激活密钥永久
38
19
NYT连接提示和答案
9
6
显示更多