0,0 → 1,759 |
/* |
* 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 value 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. |
* |
* @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 and set base of tree to that 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; |
} |
} |
|
/* |
* Delete node from the list. |
*/ |
t->head.next = expnode->next; |
expnode->next->prev = &t->head; |
|
return true; |
} |