-
-
[原创]物联网安全himqtt防火墙数据结构之红黑树源码分析
-
发表于: 2019-11-19 09:50
-
物联网安全himqtt防火墙数据结构之红黑树源码分析
随着5G的发展，物联网安全显得特别重要，himqtt是首款完整源码的高性能MQTT物联网防火墙 - MQTT Application FireWall，C语言编写，采用epoll模式支持IoT数十万的高并发连接，并且兼容ModSecurity部分规则。 代码非常优秀，非常值得收藏和学习。
红黑树是一种特殊的自平衡二叉树数据结构，其自旋和左旋乃天才的设计，linux内核中大量使用。阿里巴巴面试非常看重红黑树，因为从几十万的数据中，用短短的几步就可能查到所要的数据，其原理教程网上很多，今天我们从首款物联网防火墙himqtt里面上分析红黑树源码。
首先在github上下载himqtt的源码：https://github.com/qq4108863/himqtt
找到src目录下的mqtt_rbtree.c和mqtt_rbtree.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; /* 节点的父亲 */
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;/* 指向树的叶子节点NIL */
ngx_rbtree_insert_pt insert; /* 添加元素节点的函数指针，解决具有相同键值，但不同颜色节点的冲突问题；
* 该函数指针决定新节点的行为是新增还是替换原始某个节点*/};
/* 给节点着色，1表示红色，0表示黑色 */
#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)
/* 初始化红黑树，即为空的红黑树 *//* tree 是指向红黑树的指针，
* s 是红黑树的一个NIL节点，
* i 表示函数指针，决定节点是新增还是替换
*/
#define ngx_rbtree_init(tree, s, i) \
ngx_rbtree_sentinel_init(s); \
(tree)->root = s; \
(tree)->sentinel = s; \
(tree)->insert = i
/* 左旋转操作 */
static ngx_inline voidngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
ngx_rbtree_node_t *node){
ngx_rbtree_node_t *temp;
/*
| |
x y
/ \ / \
a y ---left---> x c
/ \ / \
b c a b
*/
/*node = x*/
temp = node->right;/* temp为node节点的右孩子 */
node->right = temp->left;/* 设置node节点的右孩子为temp的左孩子 */
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 voidngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
ngx_rbtree_node_t *node){
ngx_rbtree_node_t *temp;
/*
| |
x y
/ \ / \
a y <---right-- x c
/ \ / \
b c a b
*/
/*node = y*/
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;}
/* 插入节点 *//* 插入节点的步骤：
* 1、首先按照二叉查找树的插入操作插入新节点；
* 2、然后把新节点着色为红色（避免破坏红黑树性质5）；
* 3、为维持红黑树的性质，调整红黑树的节点（着色并旋转），使其满足红黑树的性质；
*/
voidngx_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 */
/* 调整红黑树，使其满足性质，
* 其实这里只是破坏了性质4：若一个节点是红色，则孩子节点都为黑色；
* 若破坏了性质4，则新节点 node 及其父亲节点 node->parent 都为红色；
*/
while (node != *root && ngx_rbt_is_red(node->parent)) {
/* 若node的父亲节点是其祖父节点的左孩子 */
if (node->parent == node->parent->parent->left) {
temp = node->parent->parent->right;/* temp节点为node的叔叔节点 */
/* case1：node的叔叔节点是红色 */
/* 此时，node的父亲及叔叔节点都为红色；
* 解决办法：将node的父亲及叔叔节点着色为黑色，将node祖父节点着色为红色；
* 然后沿着祖父节点向上判断是否会破会红黑树的性质；
*/
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 {
/* case2：node的叔叔节点是黑色且node是父亲节点的右孩子 */
/* 则此时，以node父亲节点进行左旋转，使case2转变为case3；
*/
if (node == node->parent->right) {
node = node->parent;
ngx_rbtree_left_rotate(root, sentinel, node);
}
/* case3：node的叔叔节点是黑色且node是父亲节点的左孩子 */
/* 首先，将node的父亲节点着色为黑色，祖父节点着色为红色；
* 然后以祖父节点进行一次右旋转；
*/
ngx_rbt_black(node->parent);
ngx_rbt_red(node->parent->parent);
ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
}
} else {/* 若node的父亲节点是其祖父节点的右孩子 */
/* 这里跟上面的情况是对称的，就不再进行讲解了
*/
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);}
/* 这里只是将节点插入到红黑树中，并没有判断是否满足红黑树的性质；
* 类似于二叉查找树的插入操作，这个函数为红黑树插入操作的函数指针；
*/
voidngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
ngx_rbtree_node_t *sentinel){
ngx_rbtree_node_t **p;
for ( ;; ) {
/* 判断node节点键值与temp节点键值的大小，以决定node插入到temp节点的左子树还是右子树 */
p = (node->key < temp->key) ? &temp->left : &temp->right;
if (*p == sentinel) {
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
|
|
|---|---|
|
|
|
|
|
|
|
|
提点小建议，我感觉楼主可以说说这个算法有什么优点或者为什么物联网要用到这个算法，更贴合设计方面的思想
|
|
|
|
