Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2498 → Rev 2499

/trunk/kernel/test/avltree/avltree1.c
0,0 → 1,286
/*
* Copyright (c) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
#include <test.h>
#include <print.h>
#include <adt/avl.h>
#include <debug.h>
#include <arch/types.h>
 
#define NODE_COUNT 100
 
static avltree_t avltree;
 
/*
* avl tree nodes in array for faster allocation
*/
static avltree_node_t avltree_nodes[NODE_COUNT];
 
/*
* head of free nodes' list:
*/
static avltree_node_t *first_free_node = NULL;
 
static int test_tree_balance(avltree_node_t *node);
static avltree_node_t *test_tree_parents(avltree_node_t *node);
static void print_tree_structure_flat (avltree_node_t *node, int level);
static avltree_node_t *alloc_avltree_node(void);
 
static avltree_node_t *test_tree_parents(avltree_node_t *node)
{
avltree_node_t *tmp;
if (!node)
return NULL;
 
if (node->lft) {
tmp = test_tree_parents(node->lft);
if (tmp != node) {
printf("Bad parent pointer key: %d, address: %p\n",
tmp->key, node->lft);
}
}
if (node->rgt) {
tmp = test_tree_parents(node->rgt);
if (tmp != node) {
printf("Bad parent pointer key: %d, address: %p\n",
tmp->key,node->rgt);
}
}
return node->par;
}
 
int test_tree_balance(avltree_node_t *node)
{
int h1, h2, diff;
 
if (!node)
return 0;
h1 = test_tree_balance(node->lft);
h2 = test_tree_balance(node->rgt);
diff = h2 - h1;
if (diff != node->balance || (diff != -1 && diff != 0 && diff != 1)) {
printf("Bad balance\n");
}
return h1 > h2 ? h1 + 1 : h2 + 1;
}
 
/**
* Prints the structure of the node, which is level levels from the top of the
* tree.
*/
static void print_tree_structure_flat(avltree_node_t *node, int level)
{
/*
* You can set the maximum level as high as you like.
* Most of the time, you'll want to debug code using small trees,
* so that a large level indicates a loop, which is a bug.
*/
if (level > 16) {
printf("[...]");
return;
}
 
if (node == NULL)
return;
 
printf("%d[%d]", node->key, node->balance);
if (node->lft != NULL || node->rgt != NULL) {
printf("(");
 
print_tree_structure_flat(node->lft, level + 1);
if (node->rgt != NULL) {
printf(",");
print_tree_structure_flat(node->rgt, level + 1);
}
 
printf(")");
}
}
 
static void alloc_avltree_node_prepare(void)
{
int i;
 
for (i = 0; i < NODE_COUNT - 1; i++) {
avltree_nodes[i].par = &avltree_nodes[i + 1];
}
/*
* Node keys which will be used for insertion. Up to NODE_COUNT size of
* array.
*/
 
/* First tree node and same key */
avltree_nodes[0].key = 60;
avltree_nodes[1].key = 60;
avltree_nodes[2].key = 60;
/* LL rotation */
avltree_nodes[3].key = 50;
avltree_nodes[4].key = 40;
avltree_nodes[5].key = 30;
/* LR rotation */
avltree_nodes[6].key = 20;
avltree_nodes[7].key = 20;
avltree_nodes[8].key = 25;
avltree_nodes[9].key = 25;
/* LL rotation in lower floor */
avltree_nodes[10].key = 35;
/* RR rotation */
avltree_nodes[11].key = 70;
avltree_nodes[12].key = 80;
/* RL rotation */
avltree_nodes[13].key = 90;
avltree_nodes[14].key = 85;
/* Insert 0 key */
avltree_nodes[15].key = 0;
avltree_nodes[16].key = 0;
/* Insert reverse */
avltree_nodes[17].key = 600;
avltree_nodes[18].key = 500;
avltree_nodes[19].key = 400;
avltree_nodes[20].key = 300;
 
for (i = 21; i < NODE_COUNT; i++)
avltree_nodes[i].key = i * 3;
avltree_nodes[i].par = NULL;
first_free_node = &avltree_nodes[0];
}
 
static avltree_node_t *alloc_avltree_node(void)
{
avltree_node_t *node;
 
node = first_free_node;
first_free_node = first_free_node->par;
 
return node;
}
 
static void test_tree_insert(avltree_t *tree, count_t node_count, bool quiet)
{
unsigned int i;
avltree_node_t *newnode;
 
avltree_create(tree);
if (!quiet)
printf("Inserting %d nodes...", node_count);
 
for (i = 0; i < node_count; i++) {
newnode = alloc_avltree_node();
avltree_insert(tree, newnode);
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
if (!quiet)
printf("done.\n");
}
 
 
static void test_tree_delete(avltree_t *tree, count_t node_count,
int node_position, bool quiet)
{
avltree_node_t *delnode;
unsigned int i;
switch (node_position) {
case 0:
if (!quiet)
printf("Deleting root nodes...");
while (tree->root != NULL) {
delnode = tree->root;
avltree_delete(tree, delnode);
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
break;
case 1:
if (!quiet)
printf("Deleting nodes according to creation time...");
for (i = 0; i < node_count; i++) {
avltree_delete(tree, &avltree_nodes[i]);
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
break;
}
if (!quiet)
printf("done.\n");
}
 
static void test_tree_delmin(avltree_t *tree, count_t node_count, bool quiet)
{
int i = 0;
if (!quiet)
printf("Deleting minimum nodes...");
while (tree->root != NULL) {
i++;
avltree_delete_min(tree);
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
 
if (!quiet && (i != node_count))
printf("Bad node count. Some nodes have been lost!\n");
 
if (!quiet)
printf("done.\n");
}
 
char *test_avltree1(bool quiet)
{
alloc_avltree_node_prepare();
test_tree_insert(&avltree, NODE_COUNT, quiet);
test_tree_delete(&avltree, NODE_COUNT, 0, quiet);
 
alloc_avltree_node_prepare();
test_tree_insert(&avltree, NODE_COUNT, quiet);
test_tree_delete(&avltree, NODE_COUNT, 1, quiet);
 
alloc_avltree_node_prepare();
test_tree_insert(&avltree, NODE_COUNT, quiet);
test_tree_delmin(&avltree, NODE_COUNT, quiet);
 
return NULL;
}
 
/trunk/kernel/test/avltree/avltree1.def
0,0 → 1,6
{
"avltree1",
"Test Avl tree operations",
&test_avltree1,
true
},
/trunk/kernel/generic/include/adt/avl.h
0,0 → 1,139
/*
* Copyright (C) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
/** @addtogroup genericadt
* @{
*/
/** @file
*/
 
 
#ifndef KERN_AVLTREE_H_
#define KERN_AVLTREE_H_
 
#include <arch/types.h>
 
/**
* Macro for getting a pointer to the structure which contains the avltree
* structure.
*
* @param link Pointer to the avltree structure.
* @param type Name of the outer structure.
* @param member Name of avltree attribute in the outer structure.
*/
#define avltree_get_instance(link, type, member) \
((type *)(((uint8_t *)(link)) - ((uint8_t *) &(((type *) NULL)->member))))
 
 
typedef struct avltree_node avltree_node_t;
typedef struct avltree avltree_t;
 
 
/** AVL tree node structure. */
struct avltree_node
{
/**
* Pointer to the left descendant of this node.
*
* All keys of nodes in the left subtree are less than the key of this
* node.
*/
struct avltree_node *lft;
/**
* Pointer to the right descendant of this node.
*
* All keys of nodes in the right subtree are greater than the key of
* this node.
*/
struct avltree_node *rgt;
/** Pointer to the parent node. Root node has NULL parent. */
struct avltree_node *par;
/** Node's key. */
uint64_t key;
/**
* Difference between the heights of the left and the right subtree of
* this node.
*/
int8_t balance;
};
 
/** AVL tree structure. */
struct avltree
{
/** AVL root node pointer */
struct avltree_node *root;
 
/**
* Base of the tree is a value that is smaller or equal than every value
* in the tree (valid for positive keys otherwise ignore this atribute).
*
* The base is added to the current key when a new node is inserted into
* the tree. The base is changed to the key of the node which is deleted
* with avltree_delete_min().
*/
uint64_t base;
};
 
 
/** Create empty AVL tree.
*
* @param t AVL tree.
*/
static inline void avltree_create (avltree_t *t)
{
t->root = NULL;
t->base = 0;
}
 
/** Initialize node.
*
* @param node Node which is initialized.
*/
static inline void avltree_node_initialize(avltree_node_t *node)
{
node->key = 0;
node->lft = NULL;
node->rgt = NULL;
node->par = NULL;
node->balance = 0;
}
 
extern avltree_node_t *avltree_find_min(avltree_t *t);
extern avltree_node_t *avltree_search(avltree_t *t, uint64_t key);
extern void avltree_insert(avltree_t *t, avltree_node_t *newnode);
extern void avltree_delete(avltree_t *t, avltree_node_t *node);
extern bool avltree_delete_min(avltree_t *t);
 
#endif
 
/** @}
*/
/trunk/kernel/generic/src/adt/avl.c
0,0 → 1,712
/*
* Copyright (c) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
/** @addtogroup genericadt
* @{
*/
 
/**
* @file
* @brief AVL tree implementation.
*
* This file implements AVL tree type and operations.
*
* Implemented AVL tree has the following properties:
* @li It is a binary search tree with non-unique keys.
* @li Difference of heights of the left and the right subtree of every node is
* one at maximum.
*
* Every node has a pointer to its parent which allows insertion of multiple
* identical keys into the tree.
*
* Be careful when using this tree because of the base atribute which is added
* to every inserted node key. There is no rule in which order nodes with the
* same key are visited.
*/
 
#include <adt/avl.h>
#include <debug.h>
 
 
#define LEFT 0
#define RIGHT 1
 
 
/** Search for the first occurence of the given key in an AVL tree.
*
* @param t AVL tree.
* @param key Key to be searched.
*
* @return Pointer to a node or NULL if there is no such key.
*/
avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
{
avltree_node_t *p;
/*
* Iteratively descend to the leaf that can contain the searched key.
*/
p = t->root;
while (p != NULL) {
if (p->key > key)
p = p->lft;
else if (p->key < key)
p = p->rgt;
else
return p;
}
return NULL;
}
 
 
/** Find the node with the smallest key in an AVL tree.
*
* @param t AVL tree.
*
* @return Pointer to a node or NULL if there is no node in the tree.
*/
avltree_node_t *avltree_find_min(avltree_t *t)
{
avltree_node_t *p = t->root;
/*
* Check whether the tree is empty.
*/
if (!p)
return NULL;
/*
* Iteratively descend to the leftmost leaf in the tree.
*/
while (p->lft != NULL)
p = p->lft;
return p;
}
 
/** Insert new node into AVL tree.
*
* @param t AVL tree.
* @param newnode New node to be inserted.
*/
void avltree_insert(avltree_t *t, avltree_node_t *newnode)
{
avltree_node_t *par;
avltree_node_t *gpa;
avltree_node_t *top;
avltree_node_t **dpc;
uint64_t key;
 
ASSERT(t);
ASSERT(newnode);
 
/*
* Creating absolute key.
*/
key = newnode->key + t->base;
/*
* Iteratively descend to the leaf that can contain the new node.
* Last node with non-zero balance in the way to leaf is stored as top -
* it is a place of possible inbalance.
*/
dpc = &t->root;
gpa = NULL;
top = t->root;
while ((par = (*dpc)) != NULL) {
if (par->balance != 0) {
top = par;
}
gpa = par;
dpc = par->key > key ? &par->lft: &par->rgt;
}
 
/*
* Initialize new node.
*/
newnode->key = key;
newnode->lft = NULL;
newnode->rgt = NULL;
newnode->par = gpa;
newnode->balance = 0;
 
/*
* Insert first node into the empty tree.
*/
if (t->root == NULL) {
*dpc = newnode;
return;
}
 
/*
* Insert new node into previously found leaf place.
*/
*dpc = newnode;
 
/*
* If the tree contains one node - end.
*/
if (top == NULL)
return;
 
/*
* Store pointer of top's father which points to the node with
* potentially broken balance (top).
*/
if (top->par == NULL) {
dpc = &t->root;
} else {
if (top->par->lft == top)
dpc = &top->par->lft;
else
dpc = &top->par->rgt;
}
 
/*
* Repair all balances on the way from top node to the newly inserted
* node.
*/
par = top;
while (par != newnode) {
if (par->key > key) {
par->balance--;
par = par->lft;
} else {
par->balance++;
par = par->rgt;
}
}
/*
* To balance the tree, we must check and balance top node.
*/
if (top->balance == -2) {
par = top->lft;
if (par->balance == -1) {
/*
* LL rotation.
*/
top->lft = par->rgt;
if (top->lft != NULL)
top->lft->par = top;
par->par = top->par;
top->par = par;
par->rgt = top;
par->balance = 0;
top->balance = 0;
*dpc = par;
} else {
/*
* LR rotation.
*/
ASSERT(par->balance == 1);
gpa = par->rgt;
par->rgt = gpa->lft;
if (gpa->lft != NULL)
gpa->lft->par = par;
gpa->lft = par;
par->par = gpa;
top->lft = gpa->rgt;
if (gpa->rgt != NULL)
gpa->rgt->par = top;
gpa->rgt = top;
gpa->par = top->par;
top->par = gpa;
if (gpa->balance == -1) {
par->balance = 0;
top->balance = 1;
} else if (gpa->balance == 0) {
par->balance = 0;
top->balance = 0;
} else {
par->balance = -1;
top->balance = 0;
}
gpa->balance = 0;
*dpc = gpa;
}
} else if (top->balance == 2) {
par = top->rgt;
if (par->balance == 1) {
/*
* RR rotation.
*/
top->rgt = par->lft;
if (top->rgt != NULL)
top->rgt->par = top;
par->par = top->par;
top->par = par;
par->lft = top;
par->balance = 0;
top->balance = 0;
*dpc = par;
} else {
/*
* RL rotation.
*/
ASSERT(par->balance == -1);
gpa = par->lft;
par->lft = gpa->rgt;
if (gpa->rgt != NULL)
gpa->rgt->par = par;
gpa->rgt = par;
par->par = gpa;
top->rgt = gpa->lft;
if (gpa->lft != NULL)
gpa->lft->par = top;
gpa->lft = top;
gpa->par = top->par;
top->par = gpa;
 
if (gpa->balance == 1) {
par->balance = 0;
top->balance = -1;
} else if (gpa->balance == 0) {
par->balance = 0;
top->balance = 0;
} else {
par->balance = 1;
top->balance = 0;
}
gpa->balance = 0;
*dpc = gpa;
}
} else {
/*
* Balance is not broken, insertion is finised.
*/
return;
}
 
}
 
/** Repair the tree after reparenting node u.
*
* If node u has no parent, mark it as the root of the whole tree. Otherwise
* node v represents stale address of one of the children of node u's parent.
* Replace v with w as node u parent's child (for most uses, u and w will be the
* same).
*
* @param t AVL tree.
* @param u Node whose new parent has a stale child pointer.
* @param v Stale child of node u's new parent.
* @param w New child of node u's new parent.
* @param dir If not NULL, address of the variable where to store information
* about whether w replaced v in the left or the right subtree of
* u's new parent.
* @param ro Read only operation; do not modify any tree pointers. This is
* useful for tracking direction via the dir pointer.
*
* @return Zero if w became the new root of the tree, otherwise return
* non-zero.
*/
static int
repair(avltree_t *t, avltree_node_t *u, avltree_node_t *v, avltree_node_t *w,
int *dir, int ro)
{
if (u->par == NULL) {
if (!ro)
t->root = w;
return 0;
} else {
if (u->par->lft == v) {
if (!ro)
u->par->lft = w;
if (dir)
*dir = LEFT;
} else {
ASSERT(u->par->rgt == v);
if (!ro)
u->par->rgt = w;
if (dir)
*dir = RIGHT;
}
}
return 1;
}
 
#define REBALANCE(DIR1, DIR2, SIGN) \
if (cur->balance == -1 * SIGN) { \
par->balance = 0; \
gpa->balance = 1 * SIGN; \
if (gpa->DIR1) \
gpa->DIR1->par = gpa; \
par->DIR2->par = par; \
} else if (cur->balance == 0) { \
par->balance = 0; \
gpa->balance = 0; \
if (gpa->DIR1) \
gpa->DIR1->par = gpa; \
if (par->DIR2) \
par->DIR2->par = par; \
} else { \
par->balance = -1 * SIGN; \
gpa->balance = 0; \
if (par->DIR2) \
par->DIR2->par = par; \
gpa->DIR1->par = gpa; \
} \
cur->balance = 0;
 
#define REBALANCE_LR() REBALANCE(lft, rgt, 1)
#define REBALANCE_RL() REBALANCE(rgt, lft, -1)
 
/** Delete a node from the AVL tree.
*
* Because multiple identical keys are allowed, the parent pointers are
* essential during deletion.
*
* @param t AVL tree structure.
* @param node Address of the node which will be deleted.
*/
void avltree_delete(avltree_t *t, avltree_node_t *node)
{
avltree_node_t *cur;
avltree_node_t *par;
avltree_node_t *gpa;
int dir;
 
ASSERT(t);
ASSERT(node);
if (node->lft == NULL) {
if (node->rgt) {
/*
* Replace the node with its only right son.
*
* Balance of the right son will be repaired in the
* balancing cycle.
*/
cur = node->rgt;
cur->par = node->par;
gpa = cur;
dir = RIGHT;
cur->balance = node->balance;
} else {
if (node->par == NULL) {
/*
* The tree has only one node - it will become
* an empty tree and the balancing can end.
*/
t->root = NULL;
return;
}
/*
* The node has no child, it will be deleted with no
* substitution.
*/
gpa = node->par;
cur = NULL;
dir = (gpa->lft == node) ? LEFT: RIGHT;
}
} else {
/*
* The node has the left son. Find a node with the smallest key
* in the left subtree and replace the deleted node with that
* node.
*/
for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt)
;
 
if (cur != node->lft) {
/*
* The rightmost node of the deleted node's left subtree
* was found. Replace the deleted node with this node.
* Cutting off of the found node has two cases that
* depend on its left son.
*/
if (cur->lft) {
/*
* The found node has a left son.
*/
gpa = cur->lft;
gpa->par = cur->par;
dir = LEFT;
gpa->balance = cur->balance;
} else {
dir = RIGHT;
gpa = cur->par;
}
cur->par->rgt = cur->lft;
cur->lft = node->lft;
cur->lft->par = cur;
} else {
/*
* The left son of the node hasn't got a right son. The
* left son will take the deleted node's place.
*/
dir = LEFT;
gpa = cur;
}
if (node->rgt)
node->rgt->par = cur;
cur->rgt = node->rgt;
cur->balance = node->balance;
cur->par = node->par;
}
/*
* Repair the parent node's pointer which pointed previously to the
* deleted node.
*/
(void) repair(t, node, node, cur, NULL, false);
/*
* Repair cycle which repairs balances of nodes on the way from from the
* cut-off node up to the root.
*/
for (;;) {
if (dir == LEFT) {
/*
* Deletion was made in the left subtree.
*/
gpa->balance++;
if (gpa->balance == 1) {
/*
* Stop balancing, the tree is balanced.
*/
break;
} else if (gpa->balance == 2) {
/*
* Bad balance, heights of left and right
* subtrees differ more than by one.
*/
par = gpa->rgt;
 
if (par->balance == -1) {
/*
* RL rotation.
*/
cur = par->lft;
par->lft = cur->rgt;
cur->rgt = par;
gpa->rgt = cur->lft;
cur->lft = gpa;
/*
* Repair balances and paternity of
* children, depending on the balance
* factor of the grand child (cur).
*/
REBALANCE_RL();
/*
* Repair paternity.
*/
cur->par = gpa->par;
gpa->par = cur;
par->par = cur;
 
if (!repair(t, cur, gpa, cur, &dir,
false))
break;
gpa = cur->par;
} else {
/*
* RR rotation.
*/
gpa->rgt = par->lft;
if (par->lft)
par->lft->par = gpa;
par->lft = gpa;
/*
* Repair paternity.
*/
par->par = gpa->par;
gpa->par = par;
if (par->balance == 0) {
/*
* The right child of the
* balanced node is balanced,
* after RR rotation is done,
* the whole tree will be
* balanced.
*/
par->balance = -1;
gpa->balance = 1;
 
(void) repair(t, par, gpa, par,
NULL, false);
break;
} else {
par->balance = 0;
gpa->balance = 0;
if (!repair(t, par, gpa, par,
&dir, false))
break;
}
gpa = par->par;
}
} else {
/*
* Repair the pointer which pointed to the
* balanced node. If it was root then balancing
* is finished else continue with the next
* iteration (parent node).
*/
if (!repair(t, gpa, gpa, NULL, &dir, true))
break;
gpa = gpa->par;
}
} else {
/*
* Deletion was made in the right subtree.
*/
gpa->balance--;
if (gpa->balance == -1) {
/*
* Stop balancing, the tree is balanced.
*/
break;
} else if (gpa->balance == -2) {
/*
* Bad balance, heights of left and right
* subtrees differ more than by one.
*/
par = gpa->lft;
if (par->balance == 1) {
/*
* LR rotation.
*/
cur = par->rgt;
par->rgt = cur->lft;
cur->lft = par;
gpa->lft = cur->rgt;
cur->rgt = gpa;
/*
* Repair balances and paternity of
* children, depending on the balance
* factor of the grand child (cur).
*/
REBALANCE_LR();
 
/*
* Repair paternity.
*/
cur->par = gpa->par;
gpa->par = cur;
par->par = cur;
 
if (!repair(t, cur, gpa, cur, &dir,
false))
break;
gpa = cur->par;
} else {
/*
* LL rotation.
*/
 
gpa->lft = par->rgt;
if (par->rgt)
par->rgt->par = gpa;
par->rgt = gpa;
/*
* Repair paternity.
*/
par->par = gpa->par;
gpa->par = par;
if (par->balance == 0) {
/*
* The left child of the
* balanced node is balanced,
* after LL rotation is done,
* the whole tree will be
* balanced.
*/
par->balance = 1;
gpa->balance = -1;
(void) repair(t, par, gpa, par,
NULL, false);
break;
} else {
par->balance = 0;
gpa->balance = 0;
if (!repair(t, par, gpa, par,
&dir, false))
break;
}
gpa = par->par;
}
} else {
/*
* Repair the pointer which pointed to the
* balanced node. If it was root then balancing
* is finished. Otherwise continue with the next
* iteration (parent node).
*/
if (!repair(t, gpa, gpa, NULL, &dir, true))
break;
gpa = gpa->par;
}
}
}
}
 
 
/** Delete a node with the smallest key from the AVL tree.
*
* @param t AVL tree structure.
*/
bool avltree_delete_min(avltree_t *t)
{
avltree_node_t *node;
/*
* Start searching for the smallest key in the tree starting in the root
* node and continue in cycle to the leftmost node in the tree (which
* must have the smallest key).
*/
node = t->root;
if (!node)
return false;
while (node->lft != NULL)
node = node->lft;
avltree_delete(t, node);
 
return true;
}
 
/** @}
*/