Nginx之红黑树-php教程-PHP中文网

首页

后端开发

php教程

Nginx之红黑树

PHP中文网

Aug 08, 2016 am 09:20 AM

Nginx之红黑树

/*
* 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 = i
void 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、设置节点y
temp = 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之红黑树的内容，更多相关内容请关注PHP中文网（www.php.cn）！

本站声明

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

热AI工具

热工具

热门话题

gmail邮箱登陆入口在哪里

7529

CakePHP 教程

1378

steam的账户名称是什么格式

win11激活密钥永久

NYT连接提示和答案

显示更多

Related knowledge

linux怎么查看nginx是否启动 Apr 14, 2025 pm 12:48 PM

在 Linux 中，使用以下命令检查 Nginx 是否已启动：systemctl status nginx根据命令输出进行判断：如果显示 "Active: active (running)"，则 Nginx 已启动。如果显示 "Active: inactive (dead)"，则 Nginx 已停止。

nginx在windows中怎么配置 Apr 14, 2025 pm 12:57 PM

如何在 Windows 中配置 Nginx？安装 Nginx 并创建虚拟主机配置。修改主配置文件并包含虚拟主机配置。启动或重新加载 Nginx。测试配置并查看网站。选择性启用 SSL 并配置 SSL 证书。选择性设置防火墙允许 80 和 443 端口流量。

怎么查看nginx是否启动 Apr 14, 2025 pm 01:03 PM

确认 Nginx 是否启动的方法：1. 使用命令行：systemctl status nginx（Linux/Unix）、netstat -ano | findstr 80（Windows）；2. 检查端口 80 是否开放；3. 查看系统日志中 Nginx 启动消息；4. 使用第三方工具，如 Nagios、Zabbix、Icinga。

linux怎么启动nginx Apr 14, 2025 pm 12:51 PM

在 Linux 中启动 Nginx 的步骤：检查 Nginx 是否已安装。使用 systemctl start nginx 启动 Nginx 服务。使用 systemctl enable nginx 启用在系统启动时自动启动 Nginx。使用 systemctl status nginx 验证启动是否成功。在 Web 浏览器中访问 http://localhost 查看默认欢迎页面。

nginx403怎么解决 Apr 14, 2025 am 10:33 AM

如何解决 Nginx 403 Forbidden 错误？检查文件或目录权限；2. 检查 .htaccess 文件；3. 检查 Nginx 配置文件；4. 重启 Nginx。其他可能原因还包括防火墙规则、SELinux 设置或应用程序问题。

怎么启动nginx服务器 Apr 14, 2025 pm 12:27 PM

启动 Nginx 服务器需要按照不同操作系统采取不同的步骤：Linux/Unix 系统：安装 Nginx 软件包（例如使用 apt-get 或 yum）。使用 systemctl 启动 Nginx 服务（例如 sudo systemctl start nginx）。Windows 系统：下载并安装 Windows 二进制文件。使用 nginx.exe 可执行文件启动 Nginx（例如 nginx.exe -c conf\nginx.conf）。无论使用哪种操作系统，您都可以通过访问服务器 IP