This is my code:
Code: Select all
struct RBTreeNode_t *rbTreeGrandparent(struct RBTreeNode_t *node) {
return node->parent->parent;
}
struct RBTreeNode_t *rbTreeUncle(struct RBTreeNode_t *node) {
return (node->parent == rbTreeGrandparent(node)->left) ? rbTreeGrandparent(node)->right : rbTreeGrandparent(node)->left;
}
void rbTreeRotateLeft(struct RBTreeNode_t *node) {
struct RBTreeNode_t *ptr1= node->right->left, *ptr2= node->right;
if(likely(node->parent != 0)) {
if(node->parent->left == node) {
node->parent->left= ptr2;
} else {
node->parent->right= ptr2;
}
}
ptr2->parent= node->parent;
ptr2->left= node;
node->right= ptr1;
if(node->right != 0)
node->right->parent= node;
node->parent= ptr2;
if(unlikely(node == kernelArgs.kernelSymTab)) {
kernelArgs.kernelSymTab= ptr2;
}
}
void rbTreeRotateRight(struct RBTreeNode_t *node) {
struct RBTreeNode_t *ptr1= node->left->right, *ptr2= node->left;
if(likely(node->parent != 0)) {
if(node->parent->left == node) {
node->parent->left= ptr2;
} else {
node->parent->right= ptr2;
}
}
ptr2->parent= node->parent;
ptr2->right= node;
node->left= ptr1;
if(node->left != 0)
node->left->parent= node;
node->parent= ptr2;
if(unlikely(node == kernelArgs.kernelSymTab)) {
kernelArgs.kernelSymTab= ptr2;
}
}
void rbTreeInsertCheck(struct RBTreeNode_t *node) {
if(unlikely(node->parent == 0)) {
node->color= RBTREE_BLACK;
} else {
if(unlikely(node->parent->color == RBTREE_BLACK)) {
return;
} else {
if(unlikely(rbTreeUncle(node) != 0 && rbTreeUncle(node)->color == RBTREE_RED)) {
node->parent->color= RBTREE_RED;
rbTreeUncle(node)->color= RBTREE_BLACK;
rbTreeGrandparent(node)->color= RBTREE_RED;
rbTreeInsertCheck(rbTreeGrandparent(node));
} else {
if(node == node->parent->right && node->parent == rbTreeGrandparent(node)->left) {
rbTreeRotateLeft(node->parent);
node= node->left;
} else if (node == node->parent->left && node->parent == rbTreeGrandparent(node)->right) {
rbTreeRotateRight(node->parent);
node= node->right;
}
node->parent->color= RBTREE_BLACK;
rbTreeGrandparent(node)->color= RBTREE_RED;
if(node == node->parent->left && node->parent == rbTreeGrandparent(node)->left) {
rbTreeRotateRight(rbTreeGrandparent(node));
} else {
rbTreeRotateLeft(rbTreeGrandparent(node));
}
}
}
}
}
void rbTreeInsert(struct RBTreeNode_t *startNode, struct RBTreeNode_t *insertNode) {
uint32t res;
if(unlikely(startNode == 0)) {
insertNode->left= 0;
insertNode->right= 0;
insertNode->parent= 0;
insertNode->color= RBTREE_BLACK;
kernelArgs.kernelSymTab= insertNode;
}
if(unlikely(!(res= strcmp(startNode->str,insertNode->str))))
return;
if(res > 0) {
if(likely(startNode->right != 0)) {
rbTreeInsert(startNode->right,insertNode);
} else {
insertNode->left= 0;
insertNode->right= 0;
insertNode->parent= startNode;
insertNode->color= RBTREE_RED;
startNode->right= insertNode;
rbTreeInsertCheck(insertNode);
}
} else {
if(likely(startNode->left != 0)) {
rbTreeInsert(startNode->left,insertNode);
} else {
insertNode->left= 0;
insertNode->right= 0;
insertNode->parent= startNode;
insertNode->color= RBTREE_RED;
startNode->left= insertNode;
rbTreeInsertCheck(insertNode);
}
}
}
void rbTreeDebug(struct RBTreeNode_t *node) {
if(likely(node != 0)) {
rbTreeDebug(node->left);
printf("str: %s, val: %#X, left: %#X, right: %#X\n",node->str,node->value,node->left,node->right);
rbTreeDebug(node->right);
}
}