123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367 |
- /*
- * Copyright [2021] JD.com, Inc.
- *
- * 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 "da_rbtree.h"
- #include "da_log.h"
- void rbtree_node_init(struct rbnode *node) {
- node->left = NULL;
- node->right = NULL;
- node->parent = NULL;
- node->key = 0ULL;
- node->data = NULL;
- /* color is left uninitialized */
- }
- void rbtree_init(struct rbtree *tree, struct rbnode *node) {
- rbtree_node_init(node);
- rbtree_black(node);
- tree->root = node;
- tree->sentinel = node;
- }
- static struct rbnode *
- rbtree_node_min(struct rbnode *node, struct rbnode *sentinel) {
- /* traverse left links */
- while (node->left != sentinel) {
- node = node->left;
- }
- return node;
- }
- struct rbnode *rbtree_min(struct rbtree *tree) {
- struct rbnode *node = tree->root;
- struct rbnode *sentinel = tree->sentinel;
- /* empty tree */
- if (node == sentinel) {
- return NULL;
- }
- return rbtree_node_min(node, sentinel);
- }
- struct rbnode *rbtree_search(struct rbtree *tree,struct rbnode *tnode) {
- struct rbnode *node = tree->root;
- struct rbnode *sentinel = tree->sentinel;
- if (node == sentinel) {
- return NULL;
- }
- while (node != sentinel)
- {
- if(!node || !tnode)
- return NULL;
- if(tnode->key == node->key)
- {
- break;
- }
- else if(tnode->key > node->key)
- {
- node = node->right;
- }
- else if(tnode->key < node->key)
- {
- node = node->left;
- }
- }
- if(node==sentinel)
- {
- return NULL;
- }
- else
- {
- return node;
- }
- }
- static void rbtree_left_rotate(struct rbnode **root, struct rbnode *sentinel,
- struct rbnode *node) {
- struct rbnode *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;
- }
- static void rbtree_right_rotate(struct rbnode **root, struct rbnode *sentinel,
- struct rbnode *node) {
- struct rbnode *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;
- }
- void rbtree_insert(struct rbtree *tree, struct rbnode *node) {
- struct rbnode **root = &tree->root;
- struct rbnode *sentinel = tree->sentinel;
- struct rbnode *temp, **p;
- /* empty tree */
- if (*root == sentinel) {
- node->parent = NULL;
- node->left = sentinel;
- node->right = sentinel;
- rbtree_black(node);
- *root = node;
- return;
- }
- /* a binary tree insert */
- temp = *root;
- 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;
- rbtree_red(node);
- /* re-balance tree */
- while (node != *root && rbtree_is_red(node->parent)) {
- if (node->parent == node->parent->parent->left) {
- temp = node->parent->parent->right;
- if (rbtree_is_red(temp)) {
- rbtree_black(node->parent);
- rbtree_black(temp);
- rbtree_red(node->parent->parent);
- node = node->parent->parent;
- } else {
- if (node == node->parent->right) {
- node = node->parent;
- rbtree_left_rotate(root, sentinel, node);
- }
- rbtree_black(node->parent);
- rbtree_red(node->parent->parent);
- rbtree_right_rotate(root, sentinel, node->parent->parent);
- }
- } else {
- temp = node->parent->parent->left;
- if (rbtree_is_red(temp)) {
- rbtree_black(node->parent);
- rbtree_black(temp);
- rbtree_red(node->parent->parent);
- node = node->parent->parent;
- } else {
- if (node == node->parent->left) {
- node = node->parent;
- rbtree_right_rotate(root, sentinel, node);
- }
- rbtree_black(node->parent);
- rbtree_red(node->parent->parent);
- rbtree_left_rotate(root, sentinel, node->parent->parent);
- }
- }
- }
- rbtree_black(*root);
- }
- void rbtree_delete(struct rbtree *tree, struct rbnode *node) {
- struct rbnode **root = &tree->root;
- struct rbnode *sentinel = tree->sentinel;
- struct rbnode *subst, *temp, *w;
- uint8_t red;
- /* a binary tree delete */
- if (node->left == sentinel) {
- temp = node->right;
- subst = node;
- } else if (node->right == sentinel) {
- temp = node->left;
- subst = node;
- } else {
- subst = rbtree_node_min(node->right, sentinel);
- if (subst->left != sentinel) {
- temp = subst->left;
- } else {
- temp = subst->right;
- }
- }
- if (subst == *root) {
- *root = temp;
- rbtree_black(temp);
- rbtree_node_init(node);
- return;
- }
- red = rbtree_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;
- rbtree_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;
- }
- }
- rbtree_node_init(node);
- if (red) {
- return;
- }
- /* a delete fixup */
- while (temp != *root && rbtree_is_black(temp)) {
- if (temp == temp->parent->left) {
- w = temp->parent->right;
- if (rbtree_is_red(w)) {
- rbtree_black(w);
- rbtree_red(temp->parent);
- rbtree_left_rotate(root, sentinel, temp->parent);
- w = temp->parent->right;
- }
- if (rbtree_is_black(w->left) && rbtree_is_black(w->right)) {
- rbtree_red(w);
- temp = temp->parent;
- } else {
- if (rbtree_is_black(w->right)) {
- rbtree_black(w->left);
- rbtree_red(w);
- rbtree_right_rotate(root, sentinel, w);
- w = temp->parent->right;
- }
- rbtree_copy_color(w, temp->parent);
- rbtree_black(temp->parent);
- rbtree_black(w->right);
- rbtree_left_rotate(root, sentinel, temp->parent);
- temp = *root;
- }
- } else {
- w = temp->parent->left;
- if (rbtree_is_red(w)) {
- rbtree_black(w);
- rbtree_red(temp->parent);
- rbtree_right_rotate(root, sentinel, temp->parent);
- w = temp->parent->left;
- }
- if (rbtree_is_black(w->left) && rbtree_is_black(w->right)) {
- rbtree_red(w);
- temp = temp->parent;
- } else {
- if (rbtree_is_black(w->left)) {
- rbtree_black(w->right);
- rbtree_red(w);
- rbtree_left_rotate(root, sentinel, w);
- w = temp->parent->left;
- }
- rbtree_copy_color(w, temp->parent);
- rbtree_black(temp->parent);
- rbtree_black(w->left);
- rbtree_right_rotate(root, sentinel, temp->parent);
- temp = *root;
- }
- }
- }
- rbtree_black(temp);
- }
|