Skip to content

Instantly share code, notes, and snippets.

@kimhoki

kimhoki/AVLtree.c

Created June 16, 2015 11:26
Show Gist options
  • Save kimhoki/f3b5e9d3b6c21ae57c3a to your computer and use it in GitHub Desktop.
Save kimhoki/f3b5e9d3b6c21ae57c3a to your computer and use it in GitHub Desktop.
Download ZIP
[AVL] 리눅스 내에 AVL tree
Raw
AVLtree.c
#if 1
//
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int data;
struct _node *left;
struct _node *right;
}NODE;
NODE *root;
typedef enum{LEFT, RIGHT}TYPE;
void insert_data(int data){
NODE *temp;
NODE **p = &root;
temp = (NODE *)malloc(sizeof(NODE));
temp->data = data;
temp->left = temp->right =0;
while(*p){
if((*p)->data > data)
p = &(*p)->left;
else if((*p)->data < data)
p = &(*p)->right;
else
return;
}
*p = temp;
}
void __display(NODE *temp, int (*a)[10], int *row, int *col){
if(temp ==0) return ;
++*row;
__display(temp->left, a, row, col);
a[*row][(*col)++] = temp->data;
__display(temp->right, a, row, col);
--*row;
return;
}
void display(NODE *temp){
int i,j;
int row = -1;
int col = 0;
int a[10][10] = {0,};
system("clear");
__display(temp, a, &row, &col);
for(i=0; i<10; i++){
for(j=0; j<10; j++){
if(a[i][j]!=0)
printf("%4d", a[i][j]);
else
printf("%4c", ' ');
}
printf("\n");
}
getchar();
}
NODE *__fill(NODE *temp, int *a, int *n){
if(temp ==0)
return;
__fill(temp->left, a, n);
a[(*n)++] = temp->data;
__fill(temp->right, a, n);
}
NODE *__bal(int *a, int n){
int mid = n/2;
NODE *temp;
if(n<1) return 0;
temp = malloc(sizeof(NODE));
temp->data = a[mid];
temp->left = __bal(a, mid);
temp->right = __bal(a+mid+1, n-mid-1);
return temp;
}
void bal(NODE *temp){
int a[100];
int n = 0;
__fill(temp, a, &n);
root = __bal(a, n);
}
NODE *search(NODE *node, int key){
if(node == NULL) return NULL;
printf("%d-> ",node->data);
if(key == node->data) return node ;
else if(key < node->data) search(node->left, key);
else search(node->right, key);
}
NODE *rotate_RR(NODE *parent){
NODE *child = parent->right;
parent->right = child->left;
child->left = parent;
return child;
}
NODE *rotate_LL(NODE *parent){
NODE *child = parent->left;
parent->left = child->right;
child->right = parent;
return child;
}
/*
NODE *rotate_LR(NODE *parent){
NODE *child = parent->left;
NODE *child_R = child->right;
child->right = child_R->left;
child_R->left = child;
parent->left = child_R->right;
child_R->right = parent;
return child_R;
}*/
NODE *rotate_LR(NODE *parent){
NODE *child = parent->left;
parent->left = rotate_RR(child);
uu return rotate_LL(parent);
}
NODE *rotate_RL(NODE *parent){
NODE *child = parent->right;
parent->right = rotate_LL(child);
return rotate_RR(parent);
}
/*
NODE *rotate_RL(NODE *parent){
NODE *child = parent->right;
NODE *child_L = child->left;
parent->right = NULL;
child->left = child_L->right;
//child->left = child->left->right;
child_L->right = child;
child_L->left = parent;
return child_L;
}
*/
#define max(a,b) (((a) > (b)) ? (a) : (b))
int get_height(NODE *node){
int height = 0;
if(node != NULL)
height = 1 + max(get_height(node->left), get_height(node->right));
return height;
}
int main(){
NODE *node = 0;
int i;
int height;
int in;
//RR Rotation
/* int a[] = {6,3,1,5,7,11};
display(root);
for(i=0; i<6; i++){
insert_data(a[i]);
display(root);
}
insert_data(12);
display(root);
printf("RR rotation test \n");
getchar();
node = search(root, 6);
node->right = rotate_RR(node->right);
*/
//LL rotation
/* int a[] = {7,6,3,12};
display(root);
for(i=0; i<4; i++){
insert_data(a[i]);
display(root);
}
insert_data(1);
display(root);
printf("LL rotation test \n");
getchar();
node = search(root, 3);
node->left = rotate_LL(node->left);
*/
//LR Rotation
/* int a[] = {7,3,6,1,12};
display(root);
for(i=0; i<5; i++){
insert_data(a[i]);
display(root);
}
insert_data(5);
display(root);
printf("LR Rotation test \n");
getchar();
node = search(root,7);
root = rotate_LR(node);
display(root);
*/
/*//RL Rotation
int a[] = {5,3,9,6};
display(root);
for(i=0; i<5; i++){
insert_data(a[i]);
display(root);
}
insert_data(7);
display(root);
printf("RL Rotation test \n");
getchar();
//node = search(root, 3);
root = rotate_RL(root);
display(root);
*/
int a[] = {6,3,1,5,7,12};
display(root);
for(i=0; i<6; i++){
insert_data(a[i]);
display(root);
}
insert_data(9);
display(root);
printf("Tree height test\n");
getchar();
height = get_height(root);
printf("root height : %d\n", height);
return 0;
}
#endif
Raw
AVLtree_height.c
#if 1
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int data;
struct _node *left;
struct _node *right;
}NODE;
NODE *root;
typedef enum{LEFT, RIGHT}TYPE;
NODE *balance_tree(NODE **node);
void insert_data(int data){
NODE *temp;
NODE **p = &root;
temp = (NODE *)malloc(sizeof(NODE));
temp->data = data;
temp->left = temp->right =0;
while(*p){
if((*p)->data > data)
p = &(*p)->left;
else if((*p)->data < data)
p = &(*p)->right;
else
return;
}
*p = temp;
}
NODE *insert(NODE **root, int data){
NODE **p = root;
if(*p == NULL){
*p = (NODE *)malloc(sizeof(NODE));
if(*p == NULL){
printf("메모리 할당 실패 \n");
exit(-1);
}
(*p)->data = data;
(*p)->left = (*p)->right = NULL;
}else if(data < (*p)->data)
{
(*p)->left = insert(&((*p)->left),data);
(*p) = balance_tree(p);
}else if(data > (*p)->data){
(*p)->right = insert(&((*p)->right), data);
(*p) = balance_tree(p);
}
else{
printf("중복데이터 입력\n");
exit(-1);
}
return *p;
}
void __display(NODE *temp, int (*a)[10], int *row, int *col){
if(temp ==0) return ;
++*row;
__display(temp->left, a, row, col);
a[*row][(*col)++] = temp->data;
__display(temp->right, a, row, col);
--*row;
return;
}
void display(NODE *temp){
int i,j;
int row = -1;
int col = 0;
int a[10][10] = {0,};
system("clear");
__display(temp, a, &row, &col);
for(i=0; i<10; i++){
for(j=0; j<10; j++){
if(a[i][j]!=0)
printf("%4d", a[i][j]);
else
printf("%4c", ' ');
}
printf("\n");
}
getchar();
}
NODE *__fill(NODE *temp, int *a, int *n){
if(temp ==0)
return;
__fill(temp->left, a, n);
a[(*n)++] = temp->data;
__fill(temp->right, a, n);
}
NODE *__bal(int *a, int n){
int mid = n/2;
NODE *temp;
if(n<1) return 0;
temp = malloc(sizeof(NODE));
temp->data = a[mid];
temp->left = __bal(a, mid);
temp->right = __bal(a+mid+1, n-mid-1);
return temp;
}
void bal(NODE *temp){
int a[100];
int n = 0;
__fill(temp, a, &n);
root = __bal(a, n);
}
NODE *search(NODE *node, int key){
if(node == NULL) return NULL;
if(node->data == key)
printf("%d\n",node->data);
else
printf("%d-> ",node->data);
if(key == node->data) return node ;
else if(key < node->data) search(node->left, key);
else search(node->right, key);
}
NODE *rotate_RR(NODE *parent){
NODE *child = parent->right;
parent->right = child->left;
child->left = parent;
return child;
}
NODE *rotate_LL(NODE *parent){
NODE *child = parent->left;
parent->left = child->right;
child->right = parent;
return child;
}
NODE *rotate_LR(NODE *parent){
NODE *child = parent->left;
parent->left = rotate_RR(child);
return rotate_LL(parent);
}
NODE *rotate_RL(NODE *parent){
NODE *child = parent->right;
parent->right = rotate_LL(child);
return rotate_RR(parent);
}
#define max(a,b) (((a) > (b)) ? (a) : (b))
int get_height(NODE *node){
int height = 0;
if(node != NULL)
height = 1 + max(get_height(node->left), get_height(node->right));
return height;
}
int get_balance(NODE *node){
if(node ==NULL) return 0;
return get_height(node->left) - get_height(node->right);
//왼쪽에서 오른쪾 빼서 음수면 오른쪽이 크고, 양수면 왼쪽큼
}
NODE *balance_tree(NODE **node){
int height_diff;
height_diff = get_balance(*node);
printf("밸런스 값 : %d\n", height_diff);
if(height_diff > 1){
if(get_balance((*node)->left) > 0)
*node = rotate_LL(*node);
else
*node = rotate_LR(*node);
}
else if(height_diff < -1){
if(get_balance((*node)->left) < 0)
*node = rotate_RR(*node);
else
*node = rotate_RL(*node);
}
display(root);
return *node;
}
NODE *search_parent(NODE *node , int key){
if(node->left->data == key) return node;
if(node->right->data == key) return node;
if(key < node->data) search_parent(node->left, key);
else search_parent(node->right, key);
}
int main(){
NODE *node = 0;
int i;
int height;
int in;
NODE *temp = 0;
int a[] = {6,3,1,5,7,12};
display(root);
for(i=0; i<6; i++){
insert_data(a[i]);
display(root);
}
insert_data(9);
display(root);
printf("Tree height test\n");
getchar();
//height = get_height(root);
//printf("root height : %d\n", height);
/*while(1){
printf("input the node data(exit -1):");
scanf("%d",&in);
if(in == -1){
printf("exit\n");
break;
}
temp->data = in;
height = get_height(temp);
printf("%d의 높이: %d\n", temp->data, height);
temp = 0;
height = 0;
}*/
while(1){
printf("input the node data(exit -1) : ");
scanf("%d", &in);
fflush(stdin);
if(in==-1) break;
node = search(root, in);
height = get_height(node);
//node = balance_tree(&node);
printf("%d의 높이는 %d\n", in, height);
height = get_balance(node);
printf("%d의 밸런스 값 : %d\n", in ,height);
getchar();
/////////////////////////////////////////////////////////////////
if(height < -1 || height > 1){
node = search_parent(root, in);
if(node->data < in)
node->right = balance_tree(&(node->right));
else
node->left = balance_tree(&(node->left));
}
}
return 0;
}
#endif
Raw
AVLtree_insert.c
#if 1
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int data;
struct _node *left;
struct _node *right;
}NODE;
NODE *root;
typedef enum{LEFT, RIGHT}TYPE;
NODE *balance_tree(NODE **node);
void insert_data(int data){
NODE *temp;
NODE **p = &root;
temp = (NODE *)malloc(sizeof(NODE));
temp->data = data;
temp->left = temp->right =0;
while(*p){
if((*p)->data > data)
p = &(*p)->left;
else if((*p)->data < data)
p = &(*p)->right;
else
return;
}
*p = temp;
}
NODE *insert(NODE **root, int data){
NODE **p = root;
if(*p == NULL){
*p = (NODE *)malloc(sizeof(NODE));
if(*p == NULL){
printf("메모리 할당 실패 \n");
exit(-1);
}
(*p)->data = data;
(*p)->left = (*p)->right = NULL;
}else if(data < (*p)->data)
{
(*p)->left = insert(&((*p)->left),data);
(*p) = balance_tree(p);
}else if(data > (*p)->data){
(*p)->right = insert(&((*p)->right), data);
(*p) = balance_tree(p);
}
else{
printf("중복데이터 입력\n");
exit(-1);
}
return *p;
}
void __display(NODE *temp, int (*a)[10], int *row, int *col){
if(temp ==0) return ;
++*row;
__display(temp->left, a, row, col);
a[*row][(*col)++] = temp->data;
__display(temp->right, a, row, col);
--*row;
return;
}
void display(NODE *temp){
int i,j;
int row = -1;
int col = 0;
int a[10][10] = {0,};
system("clear");
__display(temp, a, &row, &col);
for(i=0; i<10; i++){
for(j=0; j<10; j++){
if(a[i][j]!=0)
printf("%4d", a[i][j]);
else
printf("%4c", ' ');
}
printf("\n");
}
getchar();
}
NODE *__fill(NODE *temp, int *a, int *n){
if(temp ==0)
return;
__fill(temp->left, a, n);
a[(*n)++] = temp->data;
__fill(temp->right, a, n);
}
NODE *__bal(int *a, int n){
int mid = n/2;
NODE *temp;
if(n<1) return 0;
temp = malloc(sizeof(NODE));
temp->data = a[mid];
temp->left = __bal(a, mid);
temp->right = __bal(a+mid+1, n-mid-1);
return temp;
}
void bal(NODE *temp){
int a[100];
int n = 0;
__fill(temp, a, &n);
root = __bal(a, n);
}
NODE *search(NODE *node, int key){
if(node == NULL) return NULL;
if(node->data == key)
printf("%d\n",node->data);
else
printf("%d-> ",node->data);
if(key == node->data) return node ;
else if(key < node->data) search(node->left, key);
else search(node->right, key);
}
NODE *rotate_RR(NODE *parent){
NODE *child = parent->right;
parent->right = child->left;
child->left = parent;
return child;
}
NODE *rotate_LL(NODE *parent){
NODE *child = parent->left;
parent->left = child->right;
child->right = parent;
return child;
}
NODE *rotate_LR(NODE *parent){
NODE *child = parent->left;
parent->left = rotate_RR(child);
return rotate_LL(parent);
}
NODE *rotate_RL(NODE *parent){
NODE *child = parent->right;
parent->right = rotate_LL(child);
return rotate_RR(parent);
}
#define max(a,b) (((a) > (b)) ? (a) : (b))
int get_height(NODE *node){
int height = 0;
if(node != NULL)
height = 1 + max(get_height(node->left), get_height(node->right));
return height;
}
int get_balance(NODE *node){
if(node ==NULL) return 0;
return get_height(node->left) - get_height(node->right);
//왼쪽에서 오른쪾 빼서 음수면 오른쪽이 크고, 양수면 왼쪽큼
}
NODE *balance_tree(NODE **node){
int height_diff;
height_diff = get_balance(*node);
printf("밸런스 값 : %d\n", height_diff);
if(height_diff > 1){
if(get_balance((*node)->left) > 0)
*node = rotate_LL(*node);
else
*node = rotate_LR(*node);
}
else if(height_diff < -1){
if(get_balance((*node)->left) < 0)
*node = rotate_RR(*node);
else
*node = rotate_RL(*node);
}
display(root);
return *node;
}
NODE *search_parent(NODE *node , int key){
if(node->left->data == key) return node;
if(node->right->data == key) return node;
if(key < node->data) search_parent(node->left, key);
else search_parent(node->right, key);
}
int main(){
int a[] = {6,4,1,5,7,12,8,2};
int i;
display(root);
for(i=0; i<8; i++){
insert(&root, a[i]);
display(root);
}
return 0;
}
#endif
Raw
rb_s.c
/*
Red Black Trees
(C) 1999 Andrea Arcangeli <andrea@suse.de>
(C) 2002 David Woodhouse <dwmw2@infradead.org>
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
linux/lib/rbtree.c
*/
#include <linux/rbtree.h>
#include <linux/export.h>
static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
{
struct rb_node *right = node->rb_right;
struct rb_node *parent = rb_parent(node);
if ((node->rb_right = right->rb_left))
rb_set_parent(right->rb_left, node);
right->rb_left = node;
rb_set_parent(right, parent);
if (parent)
{
if (node == parent->rb_left)
parent->rb_left = right;
else
parent->rb_right = right;
}
else
root->rb_node = right;
rb_set_parent(node, right);
}
static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
{
struct rb_node *left = node->rb_left;
struct rb_node *parent = rb_parent(node);
if ((node->rb_left = left->rb_right))
rb_set_parent(left->rb_right, node);
left->rb_right = node;
rb_set_parent(left, parent);
if (parent)
{
if (node == parent->rb_right)
parent->rb_right = left;
else
parent->rb_left = left;
}
else
root->rb_node = left;
rb_set_parent(node, left);
}
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
struct rb_node *parent, *gparent;
while ((parent = rb_parent(node)) && rb_is_red(parent))
{
gparent = rb_parent(parent);
if (parent == gparent->rb_left)
{
{
register struct rb_node *uncle = gparent->rb_right;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
if (parent->rb_right == node)
{
register struct rb_node *tmp;
__rb_rotate_left(parent, root);
tmp = parent;
parent = node;
node = tmp;
}
rb_set_black(parent);
rb_set_red(gparent);
__rb_rotate_right(gparent, root);
} else {
{
register struct rb_node *uncle = gparent->rb_left;
if (uncle && rb_is_red(uncle))
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
if (parent->rb_left == node)
{
register struct rb_node *tmp;
__rb_rotate_right(parent, root);
tmp = parent;
parent = node;
node = tmp;
}
rb_set_black(parent);
rb_set_red(gparent);
__rb_rotate_left(gparent, root);
}
}
rb_set_black(root->rb_node);
}
EXPORT_SYMBOL(rb_insert_color);
static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
struct rb_root *root)
{
struct rb_node *other;
while ((!node || rb_is_black(node)) && node != root->rb_node)
{
if (parent->rb_left == node)
{
other = parent->rb_right;
if (rb_is_red(other))
{
rb_set_black(other);
rb_set_red(parent);
__rb_rotate_left(parent, root);
other = parent->rb_right;
}
if ((!other->rb_left || rb_is_black(other->rb_left)) &&
(!other->rb_right || rb_is_black(other->rb_right)))
{
rb_set_red(other);
node = parent;
parent = rb_parent(node);
}
else
{
if (!other->rb_right || rb_is_black(other->rb_right))
{
rb_set_black(other->rb_left);
rb_set_red(other);
__rb_rotate_right(other, root);
other = parent->rb_right;
}
rb_set_color(other, rb_color(parent));
rb_set_black(parent);
rb_set_black(other->rb_right);
__rb_rotate_left(parent, root);
node = root->rb_node;
break;
}
}
else
{
other = parent->rb_left;
if (rb_is_red(other))
{
rb_set_black(other);
rb_set_red(parent);
__rb_rotate_right(parent, root);
other = parent->rb_left;
}
if ((!other->rb_left || rb_is_black(other->rb_left)) &&
(!other->rb_right || rb_is_black(other->rb_right)))
{
rb_set_red(other);
node = parent;
parent = rb_parent(node);
}
else
{
if (!other->rb_left || rb_is_black(other->rb_left))
{
rb_set_black(other->rb_right);
rb_set_red(other);
__rb_rotate_left(other, root);
other = parent->rb_left;
}
rb_set_color(other, rb_color(parent));
rb_set_black(parent);
rb_set_black(other->rb_left);
__rb_rotate_right(parent, root);
node = root->rb_node;
break;
}
}
}
if (node)
rb_set_black(node);
}
void rb_erase(struct rb_node *node, struct rb_root *root)
{
struct rb_node *child, *parent;
int color;
if (!node->rb_left)
child = node->rb_right;
else if (!node->rb_right)
child = node->rb_left;
else
{
struct rb_node *old = node, *left;
node = node->rb_right;
while ((left = node->rb_left) != NULL)
node = left;
if (rb_parent(old)) {
if (rb_parent(old)->rb_left == old)
rb_parent(old)->rb_left = node;
else
rb_parent(old)->rb_right = node;
} else
root->rb_node = node;
child = node->rb_right;
parent = rb_parent(node);
color = rb_color(node);
if (parent == old) {
parent = node;
} else {
if (child)
rb_set_parent(child, parent);
parent->rb_left = child;
node->rb_right = old->rb_right;
rb_set_parent(old->rb_right, node);
}
node->rb_parent_color = old->rb_parent_color;
node->rb_left = old->rb_left;
rb_set_parent(old->rb_left, node);
goto color;
}
parent = rb_parent(node);
color = rb_color(node);
if (child)
rb_set_parent(child, parent);
if (parent)
{
if (parent->rb_left == node)
parent->rb_left = child;
else
parent->rb_right = child;
}
else
root->rb_node = child;
color:
if (color == RB_BLACK)
__rb_erase_color(child, parent, root);
}
EXPORT_SYMBOL(rb_erase);
static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
{
struct rb_node *parent;
up:
func(node, data);
parent = rb_parent(node);
if (!parent)
return;
if (node == parent->rb_left && parent->rb_right)
func(parent->rb_right, data);
else if (parent->rb_left)
func(parent->rb_left, data);
node = parent;
goto up;
}
/*
* after inserting @node into the tree, update the tree to account for
* both the new entry and any damage done by rebalance
*/
void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
{
if (node->rb_left)
node = node->rb_left;
else if (node->rb_right)
node = node->rb_right;
rb_augment_path(node, func, data);
}
EXPORT_SYMBOL(rb_augment_insert);
/*
* before removing the node, find the deepest node on the rebalance path
* that will still be there after @node gets removed
*/
struct rb_node *rb_augment_erase_begin(struct rb_node *node)
{
struct rb_node *deepest;
if (!node->rb_right && !node->rb_left)
deepest = rb_parent(node);
else if (!node->rb_right)
deepest = node->rb_left;
else if (!node->rb_left)
deepest = node->rb_right;
else {
deepest = rb_next(node);
if (deepest->rb_right)
deepest = deepest->rb_right;
else if (rb_parent(deepest) != node)
deepest = rb_parent(deepest);
}
return deepest;
}
EXPORT_SYMBOL(rb_augment_erase_begin);
/*
* after removal, update the tree to account for the removed entry
* and any rebalance damage.
*/
void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
{
if (node)
rb_augment_path(node, func, data);
}
EXPORT_SYMBOL(rb_augment_erase_end);
/*
* This function returns the first node (in sort order) of the tree.
*/
struct rb_node *rb_first(const struct rb_root *root)
{
struct rb_node *n;
n = root->rb_node;
if (!n)
return NULL;
while (n->rb_left)
n = n->rb_left;
return n;
}
EXPORT_SYMBOL(rb_first);
struct rb_node *rb_last(const struct rb_root *root)
{
struct rb_node *n;
n = root->rb_node;
if (!n)
return NULL;
while (n->rb_right)
n = n->rb_right;
return n;
}
EXPORT_SYMBOL(rb_last);
struct rb_node *rb_next(const struct rb_node *node)
{
struct rb_node *parent;
if (rb_parent(node) == node)
return NULL;
/* If we have a right-hand child, go down and then left as far
as we can. */
if (node->rb_right) {
node = node->rb_right;
while (node->rb_left)
node=node->rb_left;
return (struct rb_node *)node;
}
/* No right-hand children. Everything down and left is
smaller than us, so any 'next' node must be in the general
direction of our parent. Go up the tree; any time the
ancestor is a right-hand child of its parent, keep going
up. First time it's a left-hand child of its parent, said
parent is our 'next' node. */
while ((parent = rb_parent(node)) && node == parent->rb_right)
node = parent;
return parent;
}
EXPORT_SYMBOL(rb_next);
struct rb_node *rb_prev(const struct rb_node *node)
{
struct rb_node *parent;
if (rb_parent(node) == node)
return NULL;
/* If we have a left-hand child, go down and then right as far
as we can. */
if (node->rb_left) {
node = node->rb_left;
while (node->rb_right)
node=node->rb_right;
return (struct rb_node *)node;
}
/* No left-hand children. Go up till we find an ancestor which
is a right-hand child of its parent */
while ((parent = rb_parent(node)) && node == parent->rb_left)
node = parent;
return parent;
}
EXPORT_SYMBOL(rb_prev);
void rb_replace_node(struct rb_node *victim, struct rb_node *new,
struct rb_root *root)
{
struct rb_node *parent = rb_parent(victim);
/* Set the surrounding nodes to point to the replacement */
if (parent) {
if (victim == parent->rb_left)
parent->rb_left = new;
else
parent->rb_right = new;
} else {
root->rb_node = new;
}
if (victim->rb_left)
rb_set_parent(victim->rb_left, new);
if (victim->rb_right)
rb_set_parent(victim->rb_right, new);
/* Copy the pointers/colour from the victim to the replacement */
*new = *victim;
}
EXPORT_SYMBOL(rb_replace_node);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment