/*
* 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 Extended AVL tree implementation.
*
* This file implements Extended AVL tree type and operations.
*
* Extended AVL tree (ExtAvl tree) has the following properties:
* @li it is binary search tree with unique keys
* @li right subtree of every node is Avl tree
* @li height of left subtree of every node is not greater then height of right subtree + 1
* @li nodes with the same keys are linked to the tree nodes of the same key, they are not tree nodes
* @li every node is part of doubly linked list with head
* @li nodes are connected in the list ascendentaly according to their keys
*
* Be careful of using this tree because of base atribute, which is added to every inserted
* node key.
*/
#include <adt/extavl.h>
#include <debug.h>
#include <panic.h>
#define AVLTREE_LEFT 0
#define AVLTREE_RIGHT 1
/* Returns height of tree -1 */
#define extavltree_tree_height(node) (((node) == NULL) ? (-1) : (((node)->lft_height>(node)->rgt_height)?(node)->lft_height:(node)->rgt_height))
/** Search first occurence (oldest node with this key) of given key in Extended AVL tree.
*
* @param t Extended AVL tree.
* @param key Key to be searched.
*
* @return Pointer to node or NULL if there is no such key.
*/
extavltree_node_t *extavltree_search(extavltree_t *t, uint64_t key)
{
extavltree_node_t *cur;
cur = t->root;
while (cur != NULL) {
if (cur->key < key) {
cur = cur->rgt;
} else if (cur->key > key) {
cur = cur->lft;
} else {
return cur;
}
}
return NULL;
}
/** Insert new node into ExtAVL tree.
*
* New node's key must be set - to that key will be added base (default 0).
*
* @param t ExtAVL tree structure.
* @param newnode New node to be inserted.
*/
void extavltree_insert(extavltree_t *t, extavltree_node_t *newnode)
{
extavltree_node_t *cur;
extavltree_node_t *son;
extavltree_node_t *gpa;
extavltree_node_t *par;
uint64_t key;
ASSERT(t);
ASSERT(newnode);
/*
* Creating absolute key.
*/
newnode->key = key = newnode->key + t->base;
/*
* Insert first node into empty tree.
*/
if (t->root == NULL) {
newnode->lft = NULL;
newnode->rgt = NULL;
newnode->lft_height = 0;
newnode->rgt_height = 0;
newnode->par = NULL;
newnode->next = &t->head;
newnode->prev = &t->head;
t->head.prev = newnode;
t->head.next = newnode;
t->root = newnode;
return;
}
/*
* Tree is not empty - search for the right place for new node.
*/
cur = t->root;
while(true) {
if (cur->key < key) {
if (!cur->rgt) {
/*
* We have reach leaf. New node will be right son.
*/
cur->rgt = newnode;
newnode->lft = NULL;
newnode->rgt = NULL;
newnode->lft_height = 0;
newnode->rgt_height = 0;
newnode->par = cur;
newnode->prev = cur;
newnode->next = cur->next;
cur->next->prev = newnode;
cur->next = newnode;
break;
}
cur = cur->rgt;
} else if (cur->key > key) {
if (!cur->lft) {
/*
* We have reach leaf. New node will be left son.
*/
cur->lft = newnode;
newnode->lft = NULL;
newnode->rgt = NULL;
newnode->lft_height = 0;
newnode->rgt_height = 0;
newnode->par = cur;
gpa = cur;
while ((gpa != &t->head) && (gpa->key == cur->key))
gpa = gpa->prev;
newnode->next = gpa->next;
newnode->prev = gpa;
gpa->next->prev = newnode;
gpa->next = newnode;
break;
}
cur = cur->lft;
} else {
/*
* Key has been previously inserted into tree. Make new node as a tree node
* and old tree node move to the prev. Old tree node will be list node.
*/
newnode->prev = cur;
newnode->next = cur->next;
cur->next->prev = newnode;
cur->next = newnode;
newnode->par = cur->par;
cur->par = NULL;
newnode->lft = cur->lft;
cur->lft = NULL;
newnode->rgt = cur->rgt;
cur->rgt = NULL;
newnode->lft_height = cur->lft_height;
cur->lft_height = 0;
newnode->rgt_height = cur->rgt_height;
cur->rgt_height = 0;
if (newnode->lft) newnode->lft->par = newnode;
if (newnode->rgt) newnode->rgt->par = newnode;
if (newnode->par) {
if (newnode->par->lft == cur)
newnode->par->lft = newnode;
else
newnode->par->rgt = newnode;
} else {
t->root = newnode;
}
return;
}
}
/*
* Balancing all nodes from newnode's parent down to root. All nodes must be checked
* because delete min operation can corrupt heights and only insert operation can
* repair it.
*/
cur = newnode->par;
while (cur) {
if (cur->key > key) {
/*
* Insertion was made in the left subtree - repair left height
* and check balance of current node.
*/
cur->lft_height = extavltree_tree_height(cur->lft) + 1;
if ((cur->rgt_height - cur->lft_height) <= -2) {
/*
* Balance was corrupted, must be repaired through LL or LR rotation.
*/
par = cur->par;
son = cur->lft;
if ((son->rgt_height - son->lft_height) != 1) {
/*
* LL rotation
*/
gpa = son;
cur->lft = son->rgt;
if (cur->lft != NULL) cur->lft->par = cur;
cur->par = son;
son->rgt = cur;
/*
* Repair heights.
*/
cur->lft_height = son->rgt_height;
son->rgt_height = extavltree_tree_height(cur) + 1;
} else {
/*
* LR rotation
*/
gpa = son->rgt;
son->rgt = gpa->lft;
if (gpa->lft != NULL) gpa->lft->par = son;
gpa->lft = son;
son->par = gpa;
cur->lft = gpa->rgt;
if (gpa->rgt != NULL) gpa->rgt->par = cur;
gpa->rgt = cur;
cur->par = gpa;
/*
* Repair heights.
*/
cur->lft_height = gpa->rgt_height;
son->rgt_height = gpa->lft_height;
gpa->rgt_height = extavltree_tree_height(cur) + 1;
gpa->lft_height = extavltree_tree_height(son) + 1;
}
/*
* Change parent pointers or if current node is root then
* change root atribute pointer.
*/
gpa->par = par;
if (par) {
if (par->lft == cur)
par->lft = gpa;
else
par->rgt = gpa;
} else {
t->root = gpa;
}
cur = par;
} else {
/*
* Current node is balanced, continue balancing of its parent.
*/
cur = cur->par;
}
} else {
/*
* Insertion was made in the right subtree - repair right height
* and check balance of current node.
*/
cur->rgt_height = extavltree_tree_height(cur->rgt) + 1;
if ((cur->rgt_height - cur->lft_height) >= 2) {
/*
* Balance was corrupted, must be repaired through LL or LR rotation.
*/
par = cur->par;
son = cur->rgt;
if ((son->rgt_height - son->lft_height) != -1) {
/*
* RR rotation
*/
gpa = son;
cur->rgt = son->lft;
if (cur->rgt != NULL) cur->rgt->par = cur;
cur->par = son;
son->lft = cur;
/*
* Repair heights.
*/
cur->rgt_height = son->lft_height;
son->lft_height = extavltree_tree_height(cur) + 1;
} else {
/*
* RL rotation
*/
gpa = son->lft;
son->lft = gpa->rgt;
if (gpa->rgt != NULL) gpa->rgt->par = son;
gpa->rgt = son;
son->par = gpa;
cur->rgt = gpa->lft;
if (gpa->lft != NULL) gpa->lft->par = cur;
gpa->lft = cur;
cur->par = gpa;
/*
* Repair heights.
*/
cur->rgt_height = gpa->lft_height;
son->lft_height = gpa->rgt_height;
gpa->lft_height = extavltree_tree_height(cur) + 1;
gpa->rgt_height = extavltree_tree_height(son) + 1;
}
/*
* Change parent pointers or if current node is root then
* change root atribute pointer.
*/
gpa->par = par;
if (par) {
if (par->lft == cur)
par->lft = gpa;
else
par->rgt = gpa;
} else {
t->root = gpa;
}
cur = par;
} else {
/*
* Current node is balanced, continue balancing of its parent.
*/
cur = cur->par;
}
}
}
}
/** Delete node from ExtAVL tree.
*
* @param t ExtAVL tree structure.
* @param node Address of node which will be deleted.
*/
void extavltree_delete(extavltree_t *t, extavltree_node_t *node)
{
extavltree_node_t **gpapar;
extavltree_node_t *cur;
extavltree_node_t *par;
extavltree_node_t *gpa;
int8_t dir;
int8_t dir2=0;
int16_t balance;
ASSERT(t);
ASSERT(node);
/*
* Delete node from list.
*/
node->next->prev = node->prev;
node->prev->next = node->next;
if (!node->par) {
if (t->root != node) {
/*
* It is list node (not a tree node). Needn't repair tree or anything else.
*/
return;
}
gpapar = &(t->root);
} else {
/*
* Find tree pointer which points to node.
*/
if (node->par->lft == node) {
gpapar = &(node->par->lft);
} else {
gpapar = &(node->par->rgt);
}
}
if ((&t->head != node->prev) && (node->prev->key == node->key)) {
/*
* Deleted node has at least one node node with the same key which is closest previous
* neighbor in the list, copy node atributes into previous node and end.
*/
cur = node->prev;
cur->lft = node->lft;
cur->rgt = node->rgt;
cur->par = node->par;
cur->lft_height = node->lft_height;
cur->rgt_height = node->rgt_height;
*gpapar = cur;
if (node->lft) node->lft->par = cur;
if (node->rgt) node->rgt->par = cur;
return;
}
/*
* Check situation in the tree around deleted node.
*/
if (!node->lft) {
/*
* Deleted node has not left son. Right son will take deleted node's place.
*/
gpa = node->par;
if (node->rgt) node->rgt->par = gpa;
if (!gpa) {
/*
* Deleted node is root node. Balancing is finished, change only
* root pointer in extavltree structure.
*/
*gpapar = node->rgt;
return;
}
dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT;
*gpapar = node->rgt;
} else {
/*
* Node has left son.
*/
cur = node->lft;
if (!cur->rgt) {
/*
* Left son of node hasn't got right son. Left son will take deleted node's place.
*/
*gpapar = cur;
cur->par = node->par;
dir = AVLTREE_LEFT;
cur->rgt = node->rgt;
if (node->rgt) node->rgt->par = cur;
gpa = cur;
cur->rgt_height = node->rgt_height;
cur->lft_height = node->lft_height;
/*
* cur->lft_height will be decreased in repair cycle.
*/
} else {
/*
* Node has left and right son. Find a node with smallest key in left subtree
* and change that node with deleted node.
*/
while (cur->rgt != NULL)
cur = cur->rgt;
*gpapar = cur;
cur->rgt = node->rgt;
if (node->rgt) node->rgt->par = cur;
gpa = cur->par;
gpa->rgt = cur->lft;
if (cur->lft) cur->lft->par = gpa;
cur->lft = node->lft;
cur->lft->par = cur;
cur->par = node->par;
dir = AVLTREE_RIGHT;
cur->lft_height = node->lft_height;
cur->rgt_height = node->rgt_height;
/*
* gpa->rgt_height and cur->lft_height will be repaired in repair cycle.
*/
}
/*
* Deleted node is root node. Balancing is finished.
*/
if (!gpa) return;
}
/*
* Repair cycle which goes from gpa node down to root.
*/
for(;;) {
/*
* Find tree pointer which points to the currently balanced node. When balanced
* node is root, root pointer from extavltree structure is taken.
*/
if (!gpa->par)
gpapar = &(t->root);
else {
if (gpa->par->lft == gpa) {
gpapar = &(gpa->par->lft);
dir2 = AVLTREE_LEFT;
} else {
gpapar = &(gpa->par->rgt);
dir2 = AVLTREE_RIGHT;
}
}
if (dir == AVLTREE_LEFT) {
/*
* Deletition was made in left subtree.
*/
gpa->lft_height--;
balance = gpa->rgt_height - gpa->lft_height;
if (balance == 1) {
/*
* Stop balancing, tree is balanced.
*/
break;
} else if (balance == 2) {
/*
* Bad balance, heights of left and right subtrees differs more then is allowed.
*/
par = gpa->rgt;
if ((par->rgt_height - par->lft_height) == -1) {
/*
* RL rotation
*/
cur = par->lft;
par->lft = cur->rgt;
cur->rgt = par;
gpa->rgt = cur->lft;
cur->lft = gpa;
/*
* Repair balances.
*/
par->lft_height = cur->rgt_height;
gpa->rgt_height = cur->lft_height;
cur->lft_height = extavltree_tree_height(gpa) + 1; //POZOR nelze: cur->lft_height = gpa->lft_height + 1; - vyska cur je diky timeoutu nesttabilni
cur->rgt_height = par->rgt_height + 1; //POZOR zmena: cur->rgt_height = extavltree_tree_height(par) + 1;
/*
* Repair paternity.
*/
if (gpa->rgt) gpa->rgt->par = gpa;
if (par->lft) par->lft->par = par;
cur->par = gpa->par;
gpa->par = cur;
par->par = cur;
/*
* Repair tree pointer which points to the current node and do the next step.
*/
*gpapar = cur;
gpa = cur->par;
} else {
/*
* RR rotation
*/
gpa->rgt = par->lft;
gpa->rgt_height = par->lft_height;
if (par->lft) par->lft->par = gpa;
par->lft = gpa;
/*
* Repair paternity.
*/
par->par = gpa->par;
gpa->par = par;
/*
* Repair balances.
*/
balance = par->rgt_height - par->lft_height;
par->lft_height++;
/*
* Repair tree pointer which points to the current node, ends when tree is balanced
* or do the next step.
*/
*gpapar = par;
if (balance == 0) break;
gpa = par->par;
}
} else {
/*
* Current node is balanced - perform balance check of its parent.
*/
gpa = gpa->par;
}
} else {
/*
* Balance right son.
*/
gpa->rgt_height--;
balance = gpa->rgt_height - gpa->lft_height;
if (balance == -1) {
/*
* Stop balancing, tree might be balanced or not, whole tree is repaired only during insertion.
*/
break;
} else if (balance == -2) {
/*
* Balance was corrupted - must be repaired.
*/
par = gpa->lft;
if ((par->rgt_height - par->lft_height) >= +1) {
/*
* If balance is -2 then par node always exists.
*/
if ((gpa->lft_height - (extavltree_tree_height(par))) == 1) {
/*
* LR rotation. Height of par subtree is not decreased due to timeout operation.
*/
cur = par->rgt;
par->rgt = cur->lft;
cur->lft = par;
gpa->lft = cur->rgt;
cur->rgt = gpa;
/*
* Repair balances.
*/
par->rgt_height = cur->lft_height;
gpa->lft_height = cur->rgt_height;
cur->rgt_height = gpa->rgt_height + 1;
cur->lft_height = extavltree_tree_height(par) + 1;
/*
* Repair paternity.
*/
if (gpa->lft) gpa->lft->par = gpa;
if (par->rgt) par->rgt->par = par;
cur->par = gpa->par;
gpa->par = cur;
par->par = cur;
/*
* Repair tree pointer which points to the current node and do the next step.
*/
*gpapar = cur;
gpa = cur->par;
} else {
/*
* Left subtree of cur has been already decreased by timeout operation.
*/
gpa = gpa->par;
}
} else {
/*
* LL rotation.
*/
int prevlftheight = gpa->lft_height;
gpa->lft = par->rgt;
gpa->lft_height = par->rgt_height;
if (par->rgt) par->rgt->par = gpa;
par->rgt = gpa;
/*
* Repair paternity.
*/
par->par = gpa->par;
gpa->par = par;
/*
* Repair height.
*/
balance = par->rgt_height - par->lft_height;
par->rgt_height = extavltree_tree_height(gpa) + 1;
/*
* Repair tree pointer which points to the current node, ends when heights in par nodes are
* balanced and height of par subtree wasn't decreased due to timeout operation orr do
* the next step.
*/
*gpapar = par;
if (balance == 0 && par->rgt_height == prevlftheight) return;
gpa = par->par;
}
} else {
/*
* Current node is balanced - perform balance check of its parent.
*/
gpa = gpa->par;
}
}
/*
* When root is reached then end balancing.
*/
if (!gpa) return;
dir = dir2;
}
}
/** Delete node from ExtAVL tree with the smallest key.
*
* @param t ExtAVL tree structure.
*/
bool extavltree_delete_min(extavltree_t *t)
{
extavltree_node_t *expnode;
ASSERT(t);
expnode = t->head.next;
if (&t->head == expnode) return false;
if (expnode->key != expnode->next->key) {
/*
* Repair tree data structure.
*/
if (!expnode->par) {
/*
* Delete root node which musn't have left son.
*/
ASSERT(!expnode->lft);
t->root = expnode->rgt;
if (expnode->rgt) expnode->rgt->par = NULL;
} else if (expnode->rgt) {
/*
* Always delete parent of left son.
*/
expnode->rgt->par = expnode->par;
expnode->par->lft = expnode->rgt;
expnode->par->lft_height = expnode->rgt_height;
} else {
/*
* Deleted node doesn't have right son.
*/
expnode->par->lft = NULL;
expnode->par->lft_height = 0;
}
} else if (expnode->next == &t->head) {
/*
* Special case of deleting last node with key equal 0.
*/
t->root = NULL;
}
/*
* Delete node from the list.
*/
t->head.next = expnode->next;
expnode->next->prev = &t->head;
return true;
}