nginx data structure 3 - extended red-black tree
Carrying forward my usual style of side task maniac, I completed the red-black tree extended version that I had originally envisioned in one night.
rbtree.h:
/*
* Copyright (C) Bipedal Bit
* Verson 1.0.0.2
*/
#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;
/* count of nodes in the subtree whose root is the current node */
int node_cnt;
};
/* 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);
/* foundational visit function pointer */
typedef void (*rbtree_visit_p) (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); \
(node)->node_cnt = 0
/* 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);
/* get node by key */
rbtree_node_t* rbtree_find(rbtree_t* tree, rbtree_key_t key);
/* get node by order number */
rbtree_node_t* rbtree_index(rbtree_t* tree, int index);
int rbtree_height(rbtree_t* tree, rbtree_node_t* node);
int rbtree_count(rbtree_t* tree);
void rbtree_visit(rbtree_node_t* node);
void rbtree_traversal(rbtree_t* tree, rbtree_node_t* node, rbtree_visit_p);
#endif /* _RBTREE_H_INCLUDED_ */In order to improve the efficiency of finding nodes by serial number, I added a node item node_cnt, which represents the total number of nodes on the subtree where the current node is the root. In this way, the process of searching for nodes by serial number will be a binary search, and the time efficiency is the same as searching by key, which is O(log2n).
The traversal method uses recursive in-order traversal. The default node access method is an empty method, and users can rewrite it by themselves.
rbtree.c:
/*
* Copyright (C) Bipedal Bit
* Verson 1.0.0.2
*/
#include <stddef.h>
#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;
/* fix node_cnt */
node->node_cnt = node->left->node_cnt + tmp->left->node_cnt + 1;
tmp->node_cnt = node->node_cnt + tmp->right->node_cnt + 1;
/* 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;
/* fix node_cnt */
node->node_cnt = node->right->node_cnt + tmp->right->node_cnt + 1;
tmp->node_cnt = node->node_cnt + tmp->left->node_cnt + 1;
/* 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;
/* update node_cnt */
(parent->node_cnt)++;
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_visit(rbtree_node_t* node)
{
/* visiting the current 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;
/* update node_cnt */
rbtree_node_t* tmp = cover->parent;
while(tmp != sentinel)
{
(tmp->node_cnt)--;
tmp = tmp->parent;
}
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;
/* next line is just fot test */
// 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;
}
/* find the node in the tree corresponding to the given order number */
rbtree_node_t* rbtree_index(rbtree_t* tree, int index)
{
if (index < 0 || index >= rbtree_count(tree))
{
return NULL;
}
rbtree_node_t* tmp = tree->root;
int left_cnt = 0;
int sub_left_cnt;
while(tmp->node_cnt > 0)
{
sub_left_cnt = tmp->left->node_cnt;
if (left_cnt + sub_left_cnt == index)
{
return tmp;
}
if (left_cnt + sub_left_cnt < index)
        {
            left_cnt += sub_left_cnt + 1;
            tmp = tmp->right;
}
else
{
tmp = tmp->left;
}
}
}
/* get the height of the subtree */
int rbtree_height(rbtree_t* tree, rbtree_node_t* node)
{
if (node == tree->sentinel)
{
return 0;
}
int left_height = rbtree_height(tree, node->left);
int right_height = rbtree_height(tree, node->right);
int sub_height = (left_height > right_height) ? left_height : right_height;
return sub_height+1;
}
/* get the count of nodes in the tree */
int rbtree_count(rbtree_t* tree)
{
return tree->root->node_cnt;
}
/* visit every node of the subtree whose root is given in order */
void rbtree_traversal(rbtree_t* tree, rbtree_node_t* node, rbtree_visit_p visit)
{
if (node != tree->sentinel)
{
rbtree_traversal(tree, node->left, visit);
visit(node);
rbtree_traversal(tree, node->right, visit);
}
}
test.c:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#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];
n[i].node_cnt = 1;
rbtree_insert(&t, &n[i]);
}
srand( (unsigned int)time(0) );
int no = rand()%cnt;
printf("n[%d]->key = %d\n", no, rbtree_index(&t, no)->key);
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;
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 index_cnt = 1<<10;
for( i = 0 ; i < index_cnt ; i++ )
{
rbtree_index(&t, (rand()%cnt));
}
long time4 = clock();
duration = (double)(time4 - time3) / CLOCKS_PER_SEC;
printf("Indexing %d nodes among %d spends %f seconds.\n", index_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 time5 = clock();
duration = (double)(time5 - time4) / 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 time6 = clock();
duration = (double)(time6 - time5) / CLOCKS_PER_SEC;
printf("Deleting %d nodes among %d spends %f seconds.\n", delete_cnt, cnt, duration);
free(mark);
int h = rbtree_height(&t, t.root);
long time7 = clock();
duration = (double)(time7 - time6) / CLOCKS_PER_SEC;
printf("The height of the tree is %d. Getting it spends %f seconds.\n", h, duration);
rbtree_traversal(&t, t.root, rbtree_visit);
long time8 = clock();
duration = (double)(time8 - time7) / CLOCKS_PER_SEC;
printf("Traversal the tree spends %f seconds.\n", duration);
printf("Count of nodes in the tree is %d.\n", rbtree_count(&t));
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.
Inserting 1048576 nodes costs 48.00MB and spends 0.467859 seconds. Searching 1024 nodes among 1048576 spends 0.001188 seconds. Indexing 1024 nodes among 1048576 spends 0.001484 seconds. Hash 1024 times spends 0.000355 seconds. Deleting 1024 nodes among 1048576 spends 0.001417 seconds. The height of the tree is 28. Getting it spends 0.021669 seconds. Traversal the tree spends 0.023913 seconds. Count of nodes in the tree is 1047552.
1. Inserting nodes is a little slower because one more node_cnt item is maintained during insertion.
2. There is no change in the speed of finding nodes by key.
3. There is no change in hash lookup speed.
4. It takes almost twice as long to delete a node, because node_cnt must be updated all the way up after each deletion, which is almost equivalent to a query by key.
5. Querying by serial number is slightly slower than querying by key, because each time you enter the right subtree, you need to do one more addition.
6. The time it takes to traverse is the same as finding the tree height, because they are essentially traversing the tree, and the time efficiency is of the order of O(n). The specific point is 2n node accesses, respectively when the node is pushed into the stack and popped out of the stack. .
Don’t ask me where max, min, and mid are. Can I check these by serial number? Is this still a problem?
Copyright Statement: This article is an original article by the blogger and may not be reproduced without the blogger's permission.
The above introduces nginx data structure 3 - extended red-black tree, including aspects of the content. I hope it will be helpful to friends who are interested in PHP tutorials.
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
AI Hentai Generator
Generate AI Hentai for free.
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
What are the differences between Huawei GT3 Pro and GT4?
Dec 29, 2023 pm 02:27 PM
Many users will choose the Huawei brand when choosing smart watches. Among them, Huawei GT3pro and GT4 are very popular choices. Many users are curious about the difference between Huawei GT3pro and GT4. Let’s introduce the two to you. . What are the differences between Huawei GT3pro and GT4? 1. Appearance GT4: 46mm and 41mm, the material is glass mirror + stainless steel body + high-resolution fiber back shell. GT3pro: 46.6mm and 42.9mm, the material is sapphire glass + titanium body/ceramic body + ceramic back shell 2. Healthy GT4: Using the latest Huawei Truseen5.5+ algorithm, the results will be more accurate. GT3pro: Added ECG electrocardiogram and blood vessel and safety
How to delete node in nvm
Dec 29, 2022 am 10:07 AM
How to delete node with nvm: 1. Download "nvm-setup.zip" and install it on the C drive; 2. Configure environment variables and check the version number through the "nvm -v" command; 3. Use the "nvm install" command Install node; 4. Delete the installed node through the "nvm uninstall" command.
How to use express to handle file upload in node project
Mar 28, 2023 pm 07:28 PM
How to handle file upload? The following article will introduce to you how to use express to handle file uploads in the node project. I hope it will be helpful to you!
Fix: Snipping tool not working in Windows 11
Aug 24, 2023 am 09:48 AM
Why Snipping Tool Not Working on Windows 11 Understanding the root cause of the problem can help find the right solution. Here are the top reasons why the Snipping Tool might not be working properly: Focus Assistant is On: This prevents the Snipping Tool from opening. Corrupted application: If the snipping tool crashes on launch, it might be corrupted. Outdated graphics drivers: Incompatible drivers may interfere with the snipping tool. Interference from other applications: Other running applications may conflict with the Snipping Tool. Certificate has expired: An error during the upgrade process may cause this issu simple solution. These are suitable for most users and do not require any special technical knowledge. 1. Update Windows and Microsoft Store apps
Pi Node Teaching: What is a Pi Node? How to install and set up Pi Node?
Mar 05, 2025 pm 05:57 PM
Detailed explanation and installation guide for PiNetwork nodes This article will introduce the PiNetwork ecosystem in detail - Pi nodes, a key role in the PiNetwork ecosystem, and provide complete steps for installation and configuration. After the launch of the PiNetwork blockchain test network, Pi nodes have become an important part of many pioneers actively participating in the testing, preparing for the upcoming main network release. If you don’t know PiNetwork yet, please refer to what is Picoin? What is the price for listing? Pi usage, mining and security analysis. What is PiNetwork? The PiNetwork project started in 2019 and owns its exclusive cryptocurrency Pi Coin. The project aims to create a one that everyone can participate
An in-depth analysis of Node's process management tool 'pm2”
Apr 03, 2023 pm 06:02 PM
This article will share with you Node's process management tool "pm2", and talk about why pm2 is needed, how to install and use pm2, I hope it will be helpful to everyone!
Let's talk about how to use pkg to package Node.js projects into executable files.
Dec 02, 2022 pm 09:06 PM
How to package nodejs executable file with pkg? The following article will introduce to you how to use pkg to package a Node project into an executable file. I hope it will be helpful to you!
How to Fix Can't Connect to App Store Error on iPhone
Jul 29, 2023 am 08:22 AM
Part 1: Initial Troubleshooting Steps Checking Apple’s System Status: Before delving into complex solutions, let’s start with the basics. The problem may not lie with your device; Apple's servers may be down. Visit Apple's System Status page to see if the AppStore is working properly. If there's a problem, all you can do is wait for Apple to fix it. Check your internet connection: Make sure you have a stable internet connection as the "Unable to connect to AppStore" issue can sometimes be attributed to a poor connection. Try switching between Wi-Fi and mobile data or resetting network settings (General > Reset > Reset Network Settings > Settings). Update your iOS version:
