summaryrefslogtreecommitdiffhomepage
path: root/src/test/nxt_rbtree1.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/test/nxt_rbtree1.c')
-rw-r--r--src/test/nxt_rbtree1.c382
1 files changed, 382 insertions, 0 deletions
diff --git a/src/test/nxt_rbtree1.c b/src/test/nxt_rbtree1.c
new file mode 100644
index 00000000..1ae059ab
--- /dev/null
+++ b/src/test/nxt_rbtree1.c
@@ -0,0 +1,382 @@
+
+/*
+ * Copyright (C) Igor Sysoev
+ * Copyright (C) Nginx, Inc.
+ */
+
+
+#include <nxt_main.h>
+#include "nxt_rbtree1.h"
+
+
+/*
+ * The red-black tree code is based on the algorithm described in
+ * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
+ */
+
+
+nxt_inline void nxt_rbtree1_left_rotate(nxt_rbtree1_node_t **root,
+ nxt_rbtree1_node_t *sentinel, nxt_rbtree1_node_t *node);
+nxt_inline void nxt_rbtree1_right_rotate(nxt_rbtree1_node_t **root,
+ nxt_rbtree1_node_t *sentinel, nxt_rbtree1_node_t *node);
+
+
+void
+nxt_rbtree1_insert(nxt_rbtree1_t *tree, nxt_rbtree1_node_t *node)
+{
+ nxt_rbtree1_node_t **root, *temp, *sentinel;
+
+ /* a binary tree insert */
+
+ root = (nxt_rbtree1_node_t **) &tree->root;
+ sentinel = tree->sentinel;
+
+ if (*root == sentinel) {
+ node->parent = NULL;
+ node->left = sentinel;
+ node->right = sentinel;
+ nxt_rbtree1_black(node);
+ *root = node;
+
+ return;
+ }
+
+ tree->insert(*root, node, sentinel);
+
+ /* re-balance tree */
+
+ while (node != *root && nxt_rbtree1_is_red(node->parent)) {
+
+ if (node->parent == node->parent->parent->left) {
+ temp = node->parent->parent->right;
+
+ if (nxt_rbtree1_is_red(temp)) {
+ nxt_rbtree1_black(node->parent);
+ nxt_rbtree1_black(temp);
+ nxt_rbtree1_red(node->parent->parent);
+ node = node->parent->parent;
+
+ } else {
+ if (node == node->parent->right) {
+ node = node->parent;
+ nxt_rbtree1_left_rotate(root, sentinel, node);
+ }
+
+ nxt_rbtree1_black(node->parent);
+ nxt_rbtree1_red(node->parent->parent);
+ nxt_rbtree1_right_rotate(root, sentinel, node->parent->parent);
+ }
+
+ } else {
+ temp = node->parent->parent->left;
+
+ if (nxt_rbtree1_is_red(temp)) {
+ nxt_rbtree1_black(node->parent);
+ nxt_rbtree1_black(temp);
+ nxt_rbtree1_red(node->parent->parent);
+ node = node->parent->parent;
+
+ } else {
+ if (node == node->parent->left) {
+ node = node->parent;
+ nxt_rbtree1_right_rotate(root, sentinel, node);
+ }
+
+ nxt_rbtree1_black(node->parent);
+ nxt_rbtree1_red(node->parent->parent);
+ nxt_rbtree1_left_rotate(root, sentinel, node->parent->parent);
+ }
+ }
+ }
+
+ nxt_rbtree1_black(*root);
+}
+
+
+void
+nxt_rbtree1_insert_value(nxt_rbtree1_node_t *temp, nxt_rbtree1_node_t *node,
+ nxt_rbtree1_node_t *sentinel)
+{
+ nxt_rbtree1_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;
+ nxt_rbtree1_red(node);
+}
+
+
+void
+nxt_rbtree1_insert_timer_value(nxt_rbtree1_node_t *temp,
+ nxt_rbtree1_node_t *node, nxt_rbtree1_node_t *sentinel)
+{
+ nxt_rbtree1_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 = ((nxt_rbtree1_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;
+ nxt_rbtree1_red(node);
+}
+
+
+void
+nxt_rbtree1_delete(nxt_rbtree1_t *tree, nxt_rbtree1_node_t *node)
+{
+ nxt_uint_t red;
+ nxt_rbtree1_node_t **root, *sentinel, *subst, *temp, *w;
+
+ /* a binary tree delete */
+
+ root = (nxt_rbtree1_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 = nxt_rbtree1_min(node->right, sentinel);
+
+ if (subst->left != sentinel) {
+ temp = subst->left;
+ } else {
+ temp = subst->right;
+ }
+ }
+
+ if (subst == *root) {
+ *root = temp;
+ nxt_rbtree1_black(temp);
+
+ /* DEBUG stuff */
+ node->left = NULL;
+ node->right = NULL;
+ node->parent = NULL;
+ node->key = 0;
+
+ return;
+ }
+
+ red = nxt_rbtree1_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;
+ nxt_rbtree1_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;
+ }
+ }
+
+ /* DEBUG stuff */
+ node->left = NULL;
+ node->right = NULL;
+ node->parent = NULL;
+ node->key = 0;
+
+ if (red) {
+ return;
+ }
+
+ /* a delete fixup */
+
+ while (temp != *root && nxt_rbtree1_is_black(temp)) {
+
+ if (temp == temp->parent->left) {
+ w = temp->parent->right;
+
+ if (nxt_rbtree1_is_red(w)) {
+ nxt_rbtree1_black(w);
+ nxt_rbtree1_red(temp->parent);
+ nxt_rbtree1_left_rotate(root, sentinel, temp->parent);
+ w = temp->parent->right;
+ }
+
+ if (nxt_rbtree1_is_black(w->left) && nxt_rbtree1_is_black(w->right))
+ {
+ nxt_rbtree1_red(w);
+ temp = temp->parent;
+
+ } else {
+ if (nxt_rbtree1_is_black(w->right)) {
+ nxt_rbtree1_black(w->left);
+ nxt_rbtree1_red(w);
+ nxt_rbtree1_right_rotate(root, sentinel, w);
+ w = temp->parent->right;
+ }
+
+ nxt_rbtree1_copy_color(w, temp->parent);
+ nxt_rbtree1_black(temp->parent);
+ nxt_rbtree1_black(w->right);
+ nxt_rbtree1_left_rotate(root, sentinel, temp->parent);
+ temp = *root;
+ }
+
+ } else {
+ w = temp->parent->left;
+
+ if (nxt_rbtree1_is_red(w)) {
+ nxt_rbtree1_black(w);
+ nxt_rbtree1_red(temp->parent);
+ nxt_rbtree1_right_rotate(root, sentinel, temp->parent);
+ w = temp->parent->left;
+ }
+
+ if (nxt_rbtree1_is_black(w->left) && nxt_rbtree1_is_black(w->right))
+ {
+ nxt_rbtree1_red(w);
+ temp = temp->parent;
+
+ } else {
+ if (nxt_rbtree1_is_black(w->left)) {
+ nxt_rbtree1_black(w->right);
+ nxt_rbtree1_red(w);
+ nxt_rbtree1_left_rotate(root, sentinel, w);
+ w = temp->parent->left;
+ }
+
+ nxt_rbtree1_copy_color(w, temp->parent);
+ nxt_rbtree1_black(temp->parent);
+ nxt_rbtree1_black(w->left);
+ nxt_rbtree1_right_rotate(root, sentinel, temp->parent);
+ temp = *root;
+ }
+ }
+ }
+
+ nxt_rbtree1_black(temp);
+}
+
+
+nxt_inline void
+nxt_rbtree1_left_rotate(nxt_rbtree1_node_t **root, nxt_rbtree1_node_t *sentinel,
+ nxt_rbtree1_node_t *node)
+{
+ nxt_rbtree1_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;
+}
+
+
+nxt_inline void
+nxt_rbtree1_right_rotate(nxt_rbtree1_node_t **root,
+ nxt_rbtree1_node_t *sentinel, nxt_rbtree1_node_t *node)
+{
+ nxt_rbtree1_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;
+}
generated by cgit (git 2.34.1) at 2024-11-16 22:22:08 +0000