aboutsummaryrefslogtreecommitdiffstats
path: root/src/framework/common/data_struct/eprb_tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/framework/common/data_struct/eprb_tree.c')
-rw-r--r--src/framework/common/data_struct/eprb_tree.c492
1 files changed, 492 insertions, 0 deletions
diff --git a/src/framework/common/data_struct/eprb_tree.c b/src/framework/common/data_struct/eprb_tree.c
new file mode 100644
index 0000000..c8af17c
--- /dev/null
+++ b/src/framework/common/data_struct/eprb_tree.c
@@ -0,0 +1,492 @@
+/*
+*
+* Copyright (c) 2018 Huawei Technologies Co.,Ltd.
+* Licensed under the Apache License, Version 2.0 (the "License");
+* you may not use this file except in compliance with the License.
+* You may obtain a copy of the License at:
+*
+* http://www.apache.org/licenses/LICENSE-2.0
+*
+* Unless required by applicable law or agreed to in writing, software
+* distributed under the License is distributed on an "AS IS" BASIS,
+* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+* See the License for the specific language governing permissions and
+* limitations under the License.
+*/
+
+#include "eprb_tree.h"
+
+#ifdef __cplusplus
+/* *INDENT-OFF* */
+extern "C" {
+/* *INDENT-ON* */
+#endif
+
+/*
+ * This function returns the first node (in sort order) of the tree.
+ */
+struct ep_rb_node *
+ep_rb_first (const struct ep_rb_root *root)
+{
+ if (NULL == root)
+ return NULL;
+
+ struct ep_rb_node *n;
+ n = (struct ep_rb_node *) ADDR_SHTOL (root->rb_node);
+
+ if (!n)
+ {
+ return NULL;
+ }
+
+ while (n->rb_left)
+ {
+ n = (struct ep_rb_node *) ADDR_SHTOL (n->rb_left);
+ }
+
+ return n;
+}
+
+void
+__ep_rb_rotate_left (struct ep_rb_node *X, struct ep_rb_root *root)
+{
+ /**************************
+ * rotate Node X to left *
+ **************************/
+ struct ep_rb_node *Y = (struct ep_rb_node *) ADDR_SHTOL (X->rb_right);
+
+ /* estblish X->Right link */
+ X->rb_right = Y->rb_left;
+
+ if (Y->rb_left != NULL)
+ {
+ ((struct ep_rb_node *) ADDR_SHTOL (Y->rb_left))->rb_parent =
+ (struct ep_rb_node *) ADDR_LTOSH_EXT (X);
+ }
+
+ /* estblish Y->Parent link */
+ Y->rb_parent = X->rb_parent;
+
+ if (X->rb_parent)
+ {
+ struct ep_rb_node *xParent =
+ (struct ep_rb_node *) ADDR_SHTOL (X->rb_parent);
+
+ if (X == ADDR_SHTOL (xParent->rb_left))
+ {
+ xParent->rb_left = (struct ep_rb_node *) ADDR_LTOSH_EXT (Y);
+ }
+ else
+ {
+ xParent->rb_right = (struct ep_rb_node *) ADDR_LTOSH_EXT (Y);
+ }
+ }
+ else
+ {
+ root->rb_node = (struct ep_rb_node *) ADDR_LTOSH_EXT (Y);
+ }
+
+ /* link X and Y */
+ Y->rb_left = (struct ep_rb_node *) ADDR_LTOSH_EXT (X);
+ X->rb_parent = (struct ep_rb_node *) ADDR_LTOSH_EXT (Y);
+
+ return;
+}
+
+void
+__ep_rb_rotate_right (struct ep_rb_node *X, struct ep_rb_root *root)
+{
+ /****************************
+ * rotate Node X to right *
+ ****************************/
+ struct ep_rb_node *Y = (struct ep_rb_node *) ADDR_SHTOL (X->rb_left);
+
+ /* estblish X->Left link */
+ X->rb_left = Y->rb_right;
+
+ if (Y->rb_right != NULL)
+ {
+ ((struct ep_rb_node *) ADDR_SHTOL (Y->rb_right))->rb_parent =
+ (struct ep_rb_node *) ADDR_LTOSH_EXT (X);
+ }
+
+ /* estblish Y->Parent link */
+ Y->rb_parent = X->rb_parent;
+
+ if (X->rb_parent)
+ {
+ struct ep_rb_node *xParent =
+ (struct ep_rb_node *) ADDR_SHTOL (X->rb_parent);
+
+ if (X == (struct ep_rb_node *) ADDR_SHTOL (xParent->rb_right))
+ {
+ xParent->rb_right = (struct ep_rb_node *) ADDR_LTOSH_EXT (Y);
+ }
+ else
+ {
+ xParent->rb_left = (struct ep_rb_node *) ADDR_LTOSH_EXT (Y);
+ }
+ }
+ else
+ {
+ root->rb_node = (struct ep_rb_node *) ADDR_LTOSH_EXT (Y);
+ }
+
+ /* link X and Y */
+ Y->rb_right = (struct ep_rb_node *) ADDR_LTOSH_EXT (X);
+ X->rb_parent = (struct ep_rb_node *) ADDR_LTOSH_EXT (Y);
+
+ return;
+}
+
+#define EP_RBTREE_PARENT(X) ((struct ep_rb_node*) ADDR_SHTOL((X)->rb_parent))
+#define EP_RBTREE_GRANDF(X) EP_RBTREE_PARENT(EP_RBTREE_PARENT(X))
+
+/* X, Y are for application */
+void
+ep_rb_insert_color (struct ep_rb_node *X, struct ep_rb_root *root)
+{
+ /*************************************
+ * maintain red-black tree balance *
+ * after inserting node X *
+ *************************************/
+ /* check red-black properties */
+ while (X != (struct ep_rb_node *) ADDR_SHTOL (root->rb_node)
+ && EP_RBTREE_PARENT (X)->color == EP_RB_RED)
+ {
+ /* we have a violation */
+ if (X->rb_parent == EP_RBTREE_GRANDF (X)->rb_left)
+ {
+ struct ep_rb_node *Y =
+ (struct ep_rb_node *) ADDR_SHTOL (EP_RBTREE_GRANDF (X)->rb_right);
+
+ if (Y && Y->color == EP_RB_RED)
+ {
+
+ /* uncle is red */
+ EP_RBTREE_PARENT (X)->color = EP_RB_BLACK;
+ Y->color = EP_RB_BLACK;
+ EP_RBTREE_GRANDF (X)->color = EP_RB_RED;
+ X = EP_RBTREE_GRANDF (X);
+ }
+ else
+ {
+
+ /* uncle is black */
+ if (X ==
+ (struct ep_rb_node *)
+ ADDR_SHTOL (EP_RBTREE_PARENT (X)->rb_right))
+ {
+ /* make X a left child */
+ X = EP_RBTREE_PARENT (X);
+ __ep_rb_rotate_left (X, root);
+ }
+
+ /* recolor and rotate */
+ EP_RBTREE_PARENT (X)->color = EP_RB_BLACK;
+ EP_RBTREE_GRANDF (X)->color = EP_RB_RED;
+ __ep_rb_rotate_right (EP_RBTREE_GRANDF (X), root);
+ }
+ }
+ else
+ {
+ /* miror image of above code */
+ struct ep_rb_node *Y =
+ (struct ep_rb_node *) ADDR_SHTOL (EP_RBTREE_GRANDF (X)->rb_left);
+
+ if (Y && (Y->color == EP_RB_RED))
+ {
+
+ /* uncle is red */
+ EP_RBTREE_PARENT (X)->color = EP_RB_BLACK;
+ Y->color = EP_RB_BLACK;
+ EP_RBTREE_GRANDF (X)->color = EP_RB_RED;
+ X = EP_RBTREE_GRANDF (X);
+ }
+ else
+ {
+
+ /* uncle is black */
+ if (X ==
+ (struct ep_rb_node *)
+ ADDR_SHTOL (EP_RBTREE_PARENT (X)->rb_left))
+ {
+ X = EP_RBTREE_PARENT (X);
+ __ep_rb_rotate_right (X, root);
+ }
+
+ EP_RBTREE_PARENT (X)->color = EP_RB_BLACK;
+ EP_RBTREE_GRANDF (X)->color = EP_RB_RED;
+ __ep_rb_rotate_left (EP_RBTREE_GRANDF (X), root);
+ }
+ }
+ }
+
+ ((struct ep_rb_node *) ADDR_SHTOL (root->rb_node))->color = EP_RB_BLACK;
+
+ return;
+}
+
+void
+__ep_rb_erase_color (struct ep_rb_node *X, struct ep_rb_node *Parent,
+ struct ep_rb_root *root)
+{
+ /*************************************
+ * maintain red-black tree balance *
+ * after deleting node X *
+ *************************************/
+ while (X != (struct ep_rb_node *) ADDR_SHTOL (root->rb_node)
+ && (!X || X->color == EP_RB_BLACK))
+ {
+
+ if (Parent == NULL)
+ {
+ break;
+ }
+
+ if (X == (struct ep_rb_node *) ADDR_SHTOL (Parent->rb_left))
+ {
+ struct ep_rb_node *W =
+ (struct ep_rb_node *) ADDR_SHTOL (Parent->rb_right);
+
+ if (W->color == EP_RB_RED)
+ {
+ W->color = EP_RB_BLACK;
+ Parent->color = EP_RB_RED; /* Parent != NIL? */
+ __ep_rb_rotate_left (Parent, root);
+ W = (struct ep_rb_node *) ADDR_SHTOL (Parent->rb_right);
+ }
+
+ if ((!W->rb_left
+ || ((struct ep_rb_node *) ADDR_SHTOL (W->rb_left))->color ==
+ EP_RB_BLACK) && (!W->rb_right
+ || ((struct ep_rb_node *)
+ ADDR_SHTOL (W->rb_right))->color ==
+ EP_RB_BLACK))
+ {
+ W->color = EP_RB_RED;
+ X = Parent;
+ Parent = (struct ep_rb_node *) ADDR_SHTOL (X->rb_parent);
+ }
+ else
+ {
+ if (!W->rb_right
+ || ((struct ep_rb_node *) ADDR_SHTOL (W->rb_right))->color
+ == EP_RB_BLACK)
+ {
+ if (W->rb_left != NULL)
+ {
+ ((struct ep_rb_node *) ADDR_SHTOL (W->rb_left))->color
+ = EP_RB_BLACK;
+ }
+
+ W->color = EP_RB_RED;
+ __ep_rb_rotate_right (W, root);
+ W = (struct ep_rb_node *) ADDR_SHTOL (Parent->rb_right);
+ }
+
+ W->color = Parent->color;
+ Parent->color = EP_RB_BLACK;
+
+ if (((struct ep_rb_node *) ADDR_SHTOL (W->rb_right))->color !=
+ EP_RB_BLACK)
+ {
+ ((struct ep_rb_node *) ADDR_SHTOL (W->rb_right))->color =
+ EP_RB_BLACK;
+ }
+
+ __ep_rb_rotate_left (Parent, root);
+ X = (struct ep_rb_node *) ADDR_SHTOL (root->rb_node);
+ break;
+ }
+ }
+ else
+ {
+
+ struct ep_rb_node *W =
+ (struct ep_rb_node *) ADDR_SHTOL (Parent->rb_left);
+
+ if (W->color == EP_RB_RED)
+ {
+ W->color = EP_RB_BLACK;
+ Parent->color = EP_RB_RED; /* Parent != NIL? */
+ __ep_rb_rotate_right (Parent, root);
+ W = (struct ep_rb_node *) ADDR_SHTOL (Parent->rb_left);
+ }
+
+ if ((!W->rb_left
+ || (((struct ep_rb_node *) ADDR_SHTOL (W->rb_left))->color ==
+ EP_RB_BLACK)) && (!W->rb_right
+ ||
+ (((struct ep_rb_node *)
+ ADDR_SHTOL (W->rb_right))->color ==
+ EP_RB_BLACK)))
+ {
+ W->color = EP_RB_RED;
+ X = Parent;
+ Parent = (struct ep_rb_node *) ADDR_SHTOL (X->rb_parent);
+ }
+ else
+ {
+ if (!W->rb_left
+ || ((struct ep_rb_node *) ADDR_SHTOL (W->rb_left))->color
+ == EP_RB_BLACK)
+ {
+ if (W->rb_right != NULL)
+ {
+ ((struct ep_rb_node *)
+ ADDR_SHTOL (W->rb_right))->color = EP_RB_BLACK;
+ }
+
+ W->color = EP_RB_RED;
+ __ep_rb_rotate_left (W, root);
+ W = (struct ep_rb_node *) ADDR_SHTOL (Parent->rb_left);
+ }
+
+ W->color = Parent->color;
+ Parent->color = EP_RB_BLACK;
+
+ if (((struct ep_rb_node *) ADDR_SHTOL (W->rb_left))->color !=
+ EP_RB_BLACK)
+ {
+ ((struct ep_rb_node *) ADDR_SHTOL (W->rb_left))->color =
+ EP_RB_BLACK;
+ }
+
+ __ep_rb_rotate_right (Parent, root);
+ X = (struct ep_rb_node *) ADDR_SHTOL (root->rb_node);
+ break;
+ }
+ }
+ }
+
+ if (X)
+ {
+ X->color = EP_RB_BLACK;
+ }
+
+ return;
+}
+
+void
+ep_rb_erase (struct ep_rb_node *node, struct ep_rb_root *root)
+{
+ struct ep_rb_node *child, *parent;
+ int color;
+
+ if (!node->rb_left)
+ {
+ child = (struct ep_rb_node *) ADDR_SHTOL (node->rb_right);
+ }
+ else if (!node->rb_right)
+ {
+ child = (struct ep_rb_node *) ADDR_SHTOL (node->rb_left);
+ }
+ else
+ {
+ struct ep_rb_node *old = node, *left;
+
+ node = (struct ep_rb_node *) ADDR_SHTOL (node->rb_right);
+
+ while ((left =
+ (struct ep_rb_node *) ADDR_SHTOL (node->rb_left)) != NULL)
+ {
+ node = left;
+ }
+
+ if (old->rb_parent)
+ {
+ struct ep_rb_node *oldParent =
+ (struct ep_rb_node *) ADDR_SHTOL (old->rb_parent);
+
+ if (oldParent->rb_left ==
+ (struct ep_rb_node *) ADDR_LTOSH_EXT (old))
+ {
+ oldParent->rb_left =
+ (struct ep_rb_node *) ADDR_LTOSH_EXT (node);
+ }
+ else
+ {
+ oldParent->rb_right =
+ (struct ep_rb_node *) ADDR_LTOSH_EXT (node);
+ }
+ }
+ else
+ {
+ root->rb_node = (struct ep_rb_node *) ADDR_LTOSH_EXT (node);
+ }
+
+ child = (struct ep_rb_node *) ADDR_SHTOL (node->rb_right);
+ parent = (struct ep_rb_node *) ADDR_SHTOL (node->rb_parent);
+ color = node->color;
+
+ if (parent == old)
+ {
+ parent = node;
+ }
+ else
+ {
+ if (child)
+ {
+ child->rb_parent =
+ (struct ep_rb_node *) ADDR_LTOSH_EXT (parent);
+ }
+
+ parent->rb_left = (struct ep_rb_node *) ADDR_LTOSH_EXT (child);
+
+ node->rb_right = old->rb_right;
+ ((struct ep_rb_node *) ADDR_SHTOL (old->rb_right))->rb_parent =
+ (struct ep_rb_node *) ADDR_LTOSH_EXT (node);
+ }
+
+ node->color = old->color;
+ node->rb_parent = old->rb_parent;
+ node->rb_left = old->rb_left;
+ ((struct ep_rb_node *) ADDR_SHTOL (old->rb_left))->rb_parent =
+ (struct ep_rb_node *) ADDR_LTOSH_EXT (node);
+
+ if (color == EP_RB_BLACK)
+ {
+ __ep_rb_erase_color (child, parent, root);
+ }
+
+ return;
+
+ }
+
+ parent = (struct ep_rb_node *) ADDR_SHTOL (node->rb_parent);
+ color = node->color;
+
+ if (child)
+ {
+ child->rb_parent = (struct ep_rb_node *) ADDR_LTOSH_EXT (parent);
+ }
+
+ if (parent)
+ {
+ if (parent->rb_left == (struct ep_rb_node *) ADDR_LTOSH_EXT (node))
+ {
+ parent->rb_left = (struct ep_rb_node *) ADDR_LTOSH_EXT (child);
+ }
+ else
+ {
+ parent->rb_right = (struct ep_rb_node *) ADDR_LTOSH_EXT (child);
+ }
+ }
+ else
+ {
+ root->rb_node = (struct ep_rb_node *) ADDR_LTOSH_EXT (child);
+ }
+
+ if (color == EP_RB_BLACK)
+ {
+ __ep_rb_erase_color (child, parent, root);
+ }
+ return;
+}
+
+#ifdef __cplusplus
+/* *INDENT-OFF* */
+}
+/* *INDENT-ON* */
+#endif