/** Copyright (C) Igor Sysoev* Copyright (C) Nginx, Inc.*/#ifndef _NGX_RBTREE_H_INCLUDED_#define _NGX_RBTREE_H_INCLUDED_#include <ngx_config.h>#include <ngx_core.h>typedef ngx_uint_t ngx_rbtree_key_t;typedef ngx_int_t ngx_rbtree_key_int_t;typedef struct ngx_rbtree_node_s ngx_rbtree_node_t;// 红黑树struct ngx_rbtree_node_s {// 无符号整形的关键字ngx_rbtree_key_t key;// 左子节点ngx_rbtree_node_t *left;// 右子节点ngx_rbtree_node_t *right;// 父节点ngx_rbtree_node_t *parent;// 节点的颜色，0表示黑色，1表示红色u_char color;// 仅1个字节的节点数据。由于表示的空间太小，所以一般很少使用。u_char data;};typedef struct ngx_rbtree_s ngx_rbtree_t;typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);struct ngx_rbtree_s {// 指向树的根节点。ngx_rbtree_node_t *root;// 指向NIL哨兵节点ngx_rbtree_node_t *sentinel;// 表示红黑树添加元素的函数指针，它决定在添加新节点时的行为究竟是替换还是新增ngx_rbtree_insert_pt insert;};#define ngx_rbtree_init(tree, s, i) \ngx_rbtree_sentinel_init(s); \(tree)->root = s; \(tree)->sentinel = s; \(tree)->insert = ivoid ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,ngx_rbtree_node_t *node);void ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree,ngx_rbtree_node_t *node);void ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node,ngx_rbtree_node_t *sentinel);void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root,ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);#define ngx_rbt_red(node) ((node)->color = 1)#define ngx_rbt_black(node) ((node)->color = 0)#define ngx_rbt_is_red(node) ((node)->color)#define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node))#define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color)/* a sentinel must be black */#define ngx_rbtree_sentinel_init(node) ngx_rbt_black(node)static ngx_inline ngx_rbtree_node_t *ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel){while (node->left != sentinel) {node = node->left;}return node;}#endif /* _NGX_RBTREE_H_INCLUDED_ *//** Copyright (C) Igor Sysoev* Copyright (C) Nginx, Inc.*/#include <ngx_config.h>#include <ngx_core.h>/** The red-black tree code is based on the algorithm described in* the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.*/static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);void ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,ngx_rbtree_node_t *node) {ngx_rbtree_node_t **root, *temp, *sentinel;/* a binary tree insert */root = (ngx_rbtree_node_t **) &tree->root;sentinel = tree->sentinel;if (*root == sentinel) { //空树node->parent = NULL;node->left = sentinel;node->right = sentinel;ngx_rbt_black(node);*root = node;return;}tree->insert(*root, node, sentinel);/* re-balance tree */while (node != *root && ngx_rbt_is_red(node->parent)) {if (node->parent == node->parent->parent->left) {temp = node->parent->parent->right;if (ngx_rbt_is_red(temp)) {ngx_rbt_black(node->parent);ngx_rbt_black(temp);ngx_rbt_red(node->parent->parent);node = node->parent->parent;} else {if (node == node->parent->right) {node = node->parent;ngx_rbtree_left_rotate(root, sentinel, node);}ngx_rbt_black(node->parent);ngx_rbt_red(node->parent->parent);ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);}} else {temp = node->parent->parent->left;if (ngx_rbt_is_red(temp)) {ngx_rbt_black(node->parent);ngx_rbt_black(temp);ngx_rbt_red(node->parent->parent);node = node->parent->parent;} else {if (node == node->parent->left) {node = node->parent;ngx_rbtree_right_rotate(root, sentinel, node);}ngx_rbt_black(node->parent);ngx_rbt_red(node->parent->parent);ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);}}}ngx_rbt_black(*root);}void ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,ngx_rbtree_node_t *sentinel) {ngx_rbtree_node_t **p;for (;;) {p = (node->key < temp->key) ? &temp->left : &temp->right;if (*p == sentinel) {break;}temp = *p;}*p = node;node->parent = temp;node->left = sentinel;node->right = sentinel;ngx_rbt_red(node);}void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp,ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) {ngx_rbtree_node_t **p;for (;;) {/** Timer values* 1) are spread in small range, usually several minutes,* 2) and overflow each 49 days, if milliseconds are stored in 32 bits.* The comparison takes into account that overflow.*//* node->key < temp->key */p = ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key< 0) ? &temp->left : &temp->right;if (*p == sentinel) {break;}temp = *p;}*p = node;node->parent = temp;node->left = sentinel;node->right = sentinel;ngx_rbt_red(node);}void ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree,ngx_rbtree_node_t *node) {ngx_uint_t red;ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w;/* a binary tree delete */root = (ngx_rbtree_node_t **) &tree->root;sentinel = tree->sentinel;//找到y和x节点if (node->left == sentinel) {temp = node->right;subst = node;} else if (node->right == sentinel) {temp = node->left;subst = node;} else {subst = ngx_rbtree_min(node->right, sentinel);if (subst->left != sentinel) {temp = subst->left;} else {temp = subst->right;}}//y节点为root节点if (subst == *root) {*root = temp;ngx_rbt_black(temp);/* DEBUG stuff */node->left = NULL;node->right = NULL;node->parent = NULL;node->key = 0;return;}//red = ngx_rbt_is_red(subst);//记录y节点颜色//y父的孩子节点if (subst == subst->parent->left) {subst->parent->left = temp;} else {subst->parent->right = temp;}//y孩子的父节点if (subst == node) {//只有一个孩子节点temp->parent = subst->parent;} else {if (subst->parent == node) {temp->parent = subst;} else {temp->parent = subst->parent;}//y节点copy z节点属性subst->left = node->left;subst->right = node->right;subst->parent = node->parent;ngx_rbt_copy_color(subst, node);if (node == *root) {*root = subst;} else {//删除节点的父节点的孩子节点if (node == node->parent->left) {node->parent->left = subst;} else {node->parent->right = subst;}}//y节点的父节点if (subst->left != sentinel) {subst->left->parent = subst;}if (subst->right != sentinel) {subst->right->parent = subst;}}/* DEBUG stuff */node->left = NULL;node->right = NULL;node->parent = NULL;node->key = 0;if (red) {return;}/* a delete fixup */while (temp != *root && ngx_rbt_is_black(temp)) {if (temp == temp->parent->left) {w = temp->parent->right;if (ngx_rbt_is_red(w)) {ngx_rbt_black(w);ngx_rbt_red(temp->parent);ngx_rbtree_left_rotate(root, sentinel, temp->parent);w = temp->parent->right;}if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {ngx_rbt_red(w);temp = temp->parent;} else {if (ngx_rbt_is_black(w->right)) {ngx_rbt_black(w->left);ngx_rbt_red(w);ngx_rbtree_right_rotate(root, sentinel, w);w = temp->parent->right;}ngx_rbt_copy_color(w, temp->parent);ngx_rbt_black(temp->parent);ngx_rbt_black(w->right);ngx_rbtree_left_rotate(root, sentinel, temp->parent);temp = *root;}} else {w = temp->parent->left;if (ngx_rbt_is_red(w)) {ngx_rbt_black(w);ngx_rbt_red(temp->parent);ngx_rbtree_right_rotate(root, sentinel, temp->parent);w = temp->parent->left;}if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {ngx_rbt_red(w);temp = temp->parent;} else {if (ngx_rbt_is_black(w->left)) {ngx_rbt_black(w->right);ngx_rbt_red(w);ngx_rbtree_left_rotate(root, sentinel, w);w = temp->parent->left;}ngx_rbt_copy_color(w, temp->parent);ngx_rbt_black(temp->parent);ngx_rbt_black(w->left);ngx_rbtree_right_rotate(root, sentinel, temp->parent);temp = *root;}}}ngx_rbt_black(temp);}static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node) {ngx_rbtree_node_t *temp;//1、设置节点ytemp = node->right;//2、将y的左子树作为x的右子树node->right = temp->left;if (temp->left != sentinel) {temp->left->parent = node;}//3、链接y与x的父节点temp->parent = node->parent;if (node == *root) {*root = temp;} else if (node == node->parent->left) {node->parent->left = temp;} else {node->parent->right = temp;}//4、x作为y的左子树temp->left = node;node->parent = temp;}static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node) {ngx_rbtree_node_t *temp;temp = node->left;node->left = temp->right;if (temp->right != sentinel) {temp->right->parent = node;}temp->parent = node->parent;if (node == *root) {*root = temp;} else if (node == node->parent->right) {node->parent->right = temp;} else {node->parent->left = temp;}temp->right = node;node->parent = temp;}以上就是Nginx之红黑树的内容，更多相关内容请关注小兔网（www.zhishitu.com）！