nginx的数据结构3——扩展红黑树

发扬我一贯的支线任务狂魔的作风，一晚上就完成了之前设想的红黑树扩展版本。

rbtree.h：

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

#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;
	/* count of nodes in the subtree whose root is the current node */
	int node_cnt;
};

/* 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);
/* foundational visit function pointer */
typedef void (*rbtree_visit_p) (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);			\
(node)->node_cnt = 0

/* 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);
/* get node by key */
rbtree_node_t* rbtree_find(rbtree_t* tree, rbtree_key_t key);
/* get node by order number */
rbtree_node_t* rbtree_index(rbtree_t* tree, int index);
int rbtree_height(rbtree_t* tree, rbtree_node_t* node);
int rbtree_count(rbtree_t* tree);
void rbtree_visit(rbtree_node_t* node);
void rbtree_traversal(rbtree_t* tree, rbtree_node_t* node, rbtree_visit_p);

#endif	/* _RBTREE_H_INCLUDED_ */

可以看到，我增加了按序号查找结点、求树高、求结点数、可重写访问节点方法的遍历，这么几个功能。

为了提高按序号查找结点的效率，我增加了一个结点项node_cnt，代表当前结点为根的子树上的结点总数。这样按序号查找结点的过程将是一个二分查找，时间效率与按key查找相同，都是O(log2n)。

遍历方法使用递归的中序遍历，默认的结点访问方法是个空方法，用户可以自行重写。

rbtree.c：

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

#include 
#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] <- p[tmp] */
    tmp->parent = node->parent;

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

    /* fix node_cnt */
    node->node_cnt = node->left->node_cnt + tmp->left->node_cnt + 1;
    tmp->node_cnt = node->node_cnt + tmp->right->node_cnt + 1;

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

    /* fix node_cnt */
    node->node_cnt = node->right->node_cnt + tmp->right->node_cnt + 1;
    tmp->node_cnt = node->node_cnt + tmp->left->node_cnt + 1;

    /* 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;

        /* update node_cnt */
        (parent->node_cnt)++;

        tmp = (node->key < parent->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_visit(rbtree_node_t* node)
{
    /* visiting the current 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;

    /* update node_cnt */
    rbtree_node_t* tmp = cover->parent;
    while(tmp != sentinel)
    {
        (tmp->node_cnt)--;
        tmp = tmp->parent;
    }

    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;
    /* next line is just fot test */
    // 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 < tmp->key) ? tmp->left : tmp->right;
    }

    return NULL;
}

/* find the node in the tree corresponding to the given order number */
rbtree_node_t* rbtree_index(rbtree_t* tree, int index)
{
    if (index < 0 || index >= rbtree_count(tree))
    {
        return NULL;
    }

    rbtree_node_t* tmp = tree->root;
    int left_cnt = 0;
    int sub_left_cnt;

    while(tmp->node_cnt > 0)
    {
        sub_left_cnt = tmp->left->node_cnt;
        if (left_cnt + sub_left_cnt == index)
        {
            return tmp;
        }

        if (left_cnt + sub_left_cnt < index)
        {
            left_cnt += sub_left_cnt + 1;
            tmp = tmp->right;
        }
        else
        {
            tmp = tmp->left;
        }
    }
}

/* get the height of the subtree */
int rbtree_height(rbtree_t* tree, rbtree_node_t* node)
{
    if (node == tree->sentinel)
    {
        return 0;
    }

    int left_height = rbtree_height(tree, node->left);
    int right_height = rbtree_height(tree, node->right);
    int sub_height = (left_height > right_height) ? left_height : right_height;
    return sub_height+1;
}

/* get the count of nodes in the tree */
int rbtree_count(rbtree_t* tree)
{
    return tree->root->node_cnt;
}

/* visit every node of the subtree whose root is given in order */
void rbtree_traversal(rbtree_t* tree, rbtree_node_t* node, rbtree_visit_p visit)
{
    if (node != tree->sentinel)
    {
        rbtree_traversal(tree, node->left, visit);
        visit(node);
        rbtree_traversal(tree, node->right, visit);
    }
}

还是做个压力测试。

test.c：

#include 
#include 
#include 
#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<<20;
	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;

	/* Default stack size in Ubuntu Kylin 14.04 is 8MB. */
	/* It's not enough. So I use memory in heap which offers a lot larger room. */
	rbtree_node_t* n = (rbtree_node_t*)calloc(cnt, sizeof(rbtree_node_t));
	int i;

	long time1 = clock();

	for (i = 0; i < cnt; i++)
	{
		n[i].key = i+1;
		n[i].value = v[i%10];
		n[i].node_cnt = 1;
		rbtree_insert(&t, &n[i]);
	}

	srand( (unsigned int)time(0) );
	int no = rand()%cnt;
	printf("n[%d]->key = %d\n", no, rbtree_index(&t, no)->key);

	long time2 = clock();
	room = 48.0*cnt/(1<<20);
	duration = (double)(time2 - time1) / CLOCKS_PER_SEC;
	printf("Inserting %d nodes costs %.2fMB and spends %f seconds.\n", cnt, room, duration);

	const int search_cnt = 1<<10;
	for( i = 0 ; i < search_cnt ; i++ )
	{
		rbtree_find(&t, (rand()%cnt)+1);
	}

	long time3 = clock();
	duration = (double)(time3 - time2) / CLOCKS_PER_SEC;
	printf("Searching %d nodes among %d spends %f seconds.\n", search_cnt, cnt, duration);

	const int index_cnt = 1<<10;
	for( i = 0 ; i < index_cnt ; i++ )
	{
		rbtree_index(&t, (rand()%cnt));
	}

	long time4 = clock();
	duration = (double)(time4 - time3) / CLOCKS_PER_SEC;
	printf("Indexing %d nodes among %d spends %f seconds.\n", index_cnt, cnt, duration);

	const int delete_cnt = 1<<10;
	int nums[delete_cnt];
	int num;
	/* Let's hash! */
	char* mark = (char*)calloc(cnt, sizeof(char));
	memset(mark, 0, cnt*sizeof(char));
	for(i = 0; i < delete_cnt; i++)
	{
		for(;;)
		{
			num = rand()%cnt;
			if (mark[num] == 0)
			{
				mark[num] = 1;
				nums[i] = num;
				break;
			}
		}
	}

	long time5 = clock();
	duration = (double)(time5 - time4) / CLOCKS_PER_SEC;
	printf("Hash %d times spends %f seconds.\n", delete_cnt, duration);

	for(i = 0; i < delete_cnt; i++)
	{
		rbtree_delete(&t, &n[nums[i]]);
	}

	long time6 = clock();
	duration = (double)(time6 - time5) / CLOCKS_PER_SEC;
	printf("Deleting %d nodes among %d spends %f seconds.\n", delete_cnt, cnt, duration);
	free(mark);

	int h = rbtree_height(&t, t.root);
	long time7 = clock();
	duration = (double)(time7 - time6) / CLOCKS_PER_SEC;
	printf("The height of the tree is %d. Getting it spends %f seconds.\n", h, duration);

	rbtree_traversal(&t, t.root, rbtree_visit);
	long time8 = clock();
	duration = (double)(time8 - time7) / CLOCKS_PER_SEC;
	printf("Traversal the tree spends %f seconds.\n", duration);

	printf("Count of nodes in the tree is %d.\n", rbtree_count(&t));

	free(n);

	return 0;
}

上一个版本的压力测试结果：

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.

扩展版本的压力测试结果：

Inserting 1048576 nodes costs 48.00MB and spends 0.467859 seconds.
Searching 1024 nodes among 1048576 spends 0.001188 seconds.
Indexing 1024 nodes among 1048576 spends 0.001484 seconds.
Hash 1024 times spends 0.000355 seconds.
Deleting 1024 nodes among 1048576 spends 0.001417 seconds.
The height of the tree is 28. Getting it spends 0.021669 seconds.
Traversal the tree spends 0.023913 seconds.
Count of nodes in the tree is 1047552.

比较一下可以发现：

1.插入结点略慢了一点，因为插入时多维护了一个node_cnt项。

2.按key查找结点速度没有变化。

3.哈希查找速度没有变化。

4.删除结点花的时间几乎是原来的两倍，因为每次删除后都要一路向上更新node_cnt，几乎相当于包含了一次按key查询。

5.按序号查询比按key查询略慢，因为每次进入右子树需要多做一次加法。

6.遍历花的时间与求树高相同，因为它们的实质都是遍历树，时间效率O(n)数量级，具体点为2n次结点访问，分别为结点入栈和出栈时。

别问我max、min、mid在哪，能按序号查询了这些还是问题吗？

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

以上就介绍了nginx的数据结构3——扩展红黑树，包括了方面的内容，希望对PHP教程有兴趣的朋友有所帮助。