Hi Jason
  • About
  • Keywords
    • keywords - 2021/01
    • Keywords - 2020/08
    • Keywords - 2020/07
  • Note
    • 2021
    • 2020
      • 伊拉克域名.IQ被美国删除的背后以及早期的根域名管理
      • 美国如果把根域名服务器封了,中国会从网络上消失?
      • The Technical Data Guidance
    • 缓慢收藏, 小心整理
      • 泰戈尔诗句节选
    • 金刚经 原文 | 抄经
  • Read
    • 符号
    • 段永平投资问答录
      • 符号的设计
      • 符号形式探寻
      • 作为符号的设计(上篇)
      • 作为符号的设计(下篇)
      • 符号化设计之符号形式探寻
    • Dark Mode
      • Dark Mode的设计要点
      • 一篇吃透 Dark Mode ,搞定“暗黑/深色”适配
    • Apple
      • Apple “无缝”设计之历程
      • Apple 那些“无关紧要”的设计改进
      • HomePod 的设计
      • 解决方案、设计、好设计,Apple UI 设计中的 Tuning
      • Apple 的 Logo 设计
      • J 的艺术,R 的艺术
      • 从圆角到圆角
      • Apple 颜色设计的历程
      • 欲望、逻辑和习惯
      • 反“建筑学”的 Apple Park 将刺激建筑的发展
      • 螺钉,还是胶水?
      • 关于苹果设计的书籍和文章推荐
      • 正面冲撞习惯
      • 从 iOS 7 的电话图标到 polyoxybenzyl…
      • Affordance(可供性)和设计
      • 美的感知力
      • 2010: A Design Odyssey
      • iPad,从 niche 到 mass
  • Source
    • Nginx
      • 前言
      • Nginx入门
      • Nginx 配置文件
      • Nginx 内存池管理
      • Nginx 基本数据结构
      • Nginx 数组结构 ngx_array_t
      • Nginx 链表结构 ngx_list_t
      • Nginx 队列双向链表结构 ngx_queue_t
      • Nginx 哈希表结构 ngx_hash_t
      • Nginx 红黑树结构 ngx_rbtree_t
      • Nginx 模块开发
      • Nginx 启动初始化过程
      • Nginx 配置解析
      • Nginx 中的 upstream 与 subrequest 机制
      • Nginx 源码结构分析
      • Nginx 事件模块
      • Nginx 的 epoll 事件驱动模块
      • Nginx 定时器事件
      • Nginx 事件驱动模块连接处理
      • Nginx 中 HTTP 模块初始化
      • Nginx 中处理 HTTP 请求
      • Untitled
      • Untitled
    • Part 1
      • curl
  • Google Dev
    • 重要概念
      • Google 搜索的工作方式
      • 什么是展示次数、排名和点击次数?
      • 关于我们的统计信息和数据
    • Search Console帮助
      • 指南概览
      • 网站站长指南
      • 常规指南
        • 搜索引擎优化 (SEO) 新手指南
        • 使用 HTTPS 确保网站安全
        • 保持简单的网址结构
        • 向 Google 说明您的出站链接的用意
        • 将网站标记为面向儿童的内容
        • 浏览器兼容性
        • 避免创建重复内容
        • 确保链接可供抓取
        • 借助 Google 搜索进行网站测试的最佳做法
      • 专门面向内容的指南
        • 与 Google 搜索中的 AMP 网页相关的准则
        • AJAX 增强网站
        • 图片和视频
          • Google 图片最佳做法
          • 图片站点地图
          • Google 图片中的图片权限元数据
          • 视频最佳做法
          • 视频 Sitemap 及其替代方案
          • 有关富媒体文件的最佳做法
        • 播客
        • Google 移动
          • 在功能手机上进行移动浏览
          • Web Light:在搜索结果中提供更快速且更精简的移动版网页
          • Google 搜索中的 Web Light 网页对广告网络的支持
          • Google 探索和您的网站
          • 实用资源:面向适合在移动设备上显示的网页的开发者
          • 将移动网络结算费用明确告知用户
          • 将 Android 应用与网站相关联
      • 质量指南
    • Google Cloud CDN
      • 使用拖管实例组设置 Cloud CDN
      • 使用后端存储分区设置 Cloud CDN
      • 使用缓存键
      • 查看日志
  • Guidebook
    • Color Guide
    • Material.io
  • Navigation
    • Google
    • Social & Study
    • Working Tools
Powered by GitBook
On this page
  • 概述
  • 红黑树结构
  • 红黑树的操作
  • 初始化操作
  • 旋转操作
  • 插入操作
  • 删除操作

Was this helpful?

  1. Source
  2. Nginx

Nginx 红黑树结构 ngx_rbtree_t

PreviousNginx 哈希表结构 ngx_hash_tNextNginx 模块开发

Last updated 4 years ago

Was this helpful?

概述

有关红黑树的基础知识在前面文章中已经做了介绍,想要更详细的了解红黑树可以参考文章《》,在这里只是单纯对 Nginx 中红黑树源码的解析,Nginx 红黑树源码是实现跟算法导论中的讲解是一样的。

红黑树结构

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;  
    u_char                 color;   
    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;    
    ngx_rbtree_node_t     *sentinel;
    ngx_rbtree_insert_pt   insert;  
};

红黑树的操作

初始化操作


#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)




#define ngx_rbtree_sentinel_init(node)  ngx_rbt_black(node)



#define ngx_rbtree_init(tree, s, i)                                           \
    ngx_rbtree_sentinel_init(s);                                              \
    (tree)->root = s;                                                         \
    (tree)->sentinel = s;                                                     \
    (tree)->insert = i

旋转操作


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;

    temp = node->right;
    node->right = temp->left;

    if (temp->left != sentinel) {
        temp->left->parent = node;
    }

    temp->parent = node->parent;

    if (node == *root) {
        *root = temp;

    } else if (node == node->parent->left) {
        node->parent->left = temp;

    } else {
        node->parent->right = temp;
    }

    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;
}

插入操作


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;
}



void
ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,
    ngx_rbtree_node_t *node)
{
    ngx_rbtree_node_t  **root, *temp, *sentinel;

    

    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);

    

    
    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 ( ;; ) {

        

        

        p = ((ngx_rbtree_key_int_t) (node->key - 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;

    

    root = (ngx_rbtree_node_t **) &tree->root;
    sentinel = tree->sentinel;

    

    
    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;
        }
    }

    
    if (subst == *root) {
        *root = temp;
        ngx_rbt_black(temp);

        
        node->left = NULL;
        node->right = NULL;
        node->parent = NULL;
        node->key = 0;

        return;
    }

    
    red = ngx_rbt_is_red(subst);

    
    if (subst == subst->parent->left) {
        subst->parent->left = temp;

    } else {
        subst->parent->right = temp;
    }

    
    if (subst == node) {

        temp->parent = subst->parent;

    } else {

        if (subst->parent == node) {
            temp->parent = subst;

        } else {
            temp->parent = subst->parent;
        }

        
        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;
            }
        }

        if (subst->left != sentinel) {
            subst->left->parent = subst;
        }

        if (subst->right != sentinel) {
            subst->right->parent = subst;
        }
    }

    
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    node->key = 0;

    if (red) {
        return;
    }

    
    

    
    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);
}
数据结构-红黑树