nginx的数据结构2——自己动手重写红黑树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了nginx的数据结构2——自己动手重写红黑树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含18197字，纯文字阅读大概需要26分钟。
内容图文
费话不多说，上重写代码，这次姑且用英语写的注释当复习英语了。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#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; /* 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; /* 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 < 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_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 < tmp->key) ? tmp->left : tmp->right; } return NULL; }
虽然明白nginx源码中100+行的长函数体也是一种避免太多函数调用增加时间空间开销的优化，我还是把所有函数都分类分割成100行以下。增加可读性是一方面，可能也是有点强迫症吧。之后会扩展几个统计方法，像max、min和mid，还会扩展一个遍历方法。
下面是调用测试，test.c：
#include#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 < cnt; i++) { n[i].key = i+1; n[i].value = v[i]; rbtree_insert(&t, &n[i]); } rbtree_node_t* p[cnt]; for (i = 1; i <= cnt; i++) { printf("key: %d\n", i); p[i] = rbtree_find(&t, i); printf("value: %s\n", (p[i] != NULL) ? p[i]->value : "?"); } rbtree_delete(&t, &n[5]); printf("\nafter delete 6->mango:\n\n"); for (i = 1; i <= cnt; i++) { printf("key: %d\n", i); p[i] = rbtree_find(&t, i); printf("value: %s\n", (p[i] != NULL) ? p[i]->value : "?"); } return 0; }
解开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#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]; rbtree_insert(&t, &n[i]); } 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; srand( (unsigned int)time(0) ); 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 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 time4 = clock(); duration = (double)(time4 - time3) / 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 time5 = clock(); duration = (double)(time5 - time4) / CLOCKS_PER_SEC; printf("Deleting %d nodes among %d spends %f seconds.\n", delete_cnt, cnt, duration); free(mark); 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.删除比查找还快，耗时只有哈希查找的两倍多点，上百万的插入也耗时不足半秒，嗯我还挺满意的。
写统计和遍历方法去了。
版权声明：本文为博主原创文章，未经博主允许不得转载。
以上就介绍了nginx的数据结构2——自己动手重写红黑树，包括了方面的内容，希望对PHP教程有兴趣的朋友有所帮助。
内容总结
以上是互联网集市为您收集整理的nginx的数据结构2——自己动手重写红黑树全部内容，希望文章能够帮你解决nginx的数据结构2——自己动手重写红黑树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】