/branches/rcu/kernel/generic/src/time/timeout.c |
---|
55,8 → 55,12 |
{ |
spinlock_initialize(&CPU->timeoutlock, "timeout_lock"); |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
#if defined CONFIG_TIMEOUT_AVL_TREE |
avltree_create(&CPU->timeout_active_tree); |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
extavltree_create(&CPU->timeout_active_tree); |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
extavlreltree_create(&CPU->timeout_active_tree); |
#else |
list_initialize(&CPU->timeout_active_head); |
#endif |
75,9 → 79,13 |
t->cpu = NULL; |
t->handler = NULL; |
t->arg = NULL; |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
#if defined CONFIG_TIMEOUT_AVL_TREE |
avltree_node_initialize(&t->node); |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
extavltree_node_initialize(&t->node); |
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE |
extavlreltree_node_initialize(&t->node); |
#else |
t->ticks = 0; |
link_initialize(&t->link); |
98,11 → 106,14 |
timeout_reinitialize(t); |
} |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
#if defined CONFIG_TIMEOUT_AVL_TREE || \ |
defined CONFIG_TIMEOUT_EXTAVL_TREE || \ |
defined CONFIG_TIMEOUT_EXTAVLREL_TREE |
/** Register timeout |
* |
* Insert timeout handler f (with argument arg) |
* to timeout list and make it execute in |
* to timeout ExtAVL tree and make it execute in |
* time microseconds (or slightly more). |
* |
* @param t Timeout structure. |
124,14 → 135,21 |
panic("t->cpu != 0"); |
t->cpu = CPU; |
//tiky nejsou, musim zmenit klice primo v uzlech |
t->handler = f; |
t->arg = arg; |
t->node.key = us2ticks(time); |
/* |
* Put timeout into tree structure. |
*/ |
#if defined CONFIG_TIMEOUT_AVL_TREE |
avltree_insert(&CPU->timeout_active_tree,&t->node); |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
extavltree_insert(&CPU->timeout_active_tree,&t->node); |
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE |
extavlreltree_insert(&CPU->timeout_active_tree,&t->node); |
#endif |
spinlock_unlock(&t->lock); |
spinlock_unlock(&CPU->timeoutlock); |
interrupts_restore(ipl); |
140,7 → 158,7 |
/** Unregister timeout |
* |
* Remove timeout from timeout list. |
* Remove timeout from timeout ExtAVL tree structure. |
* |
* @param t Timeout to unregister. |
* |
163,14 → 181,22 |
interrupts_restore(ipl); |
goto grab_locks; |
} |
/* |
* Now we know for sure that t hasn't been activated yet |
* and is lurking in t->cpu->timeout_active_head queue. |
*/ |
/* |
* Delete timeout from tree structure. |
*/ |
#if defined CONFIG_TIMEOUT_AVL_TREE |
avltree_delete(&CPU->timeout_active_tree,&t->node); |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
extavltree_delete(&CPU->timeout_active_tree,&t->node); |
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE |
extavlreltree_delete(&CPU->timeout_active_tree,&t->node); |
#endif |
spinlock_unlock(&t->cpu->timeoutlock); |
timeout_reinitialize(t); |
/branches/rcu/kernel/generic/src/time/clock.c |
---|
123,7 → 123,8 |
} |
} |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
#if defined CONFIG_TIMEOUT_AVL_TREE || \ |
defined CONFIG_TIMEOUT_EXTAVL_TREE |
/** Clock routine |
* |
138,12 → 139,14 |
timeout_handler_t f; |
void *arg; |
count_t missed_clock_ticks = CPU->missed_clock_ticks; |
uint64_t *i = &(CPU->timeout_active_tree.basetime); |
uint64_t absolute_clock_ticks = *i + |
missed_clock_ticks; |
extavltree_node_t *head = &(CPU->timeout_active_tree.head); |
extavltree_node_t *expnode = head->next; |
uint64_t *i = &(CPU->timeout_active_tree.base); |
uint64_t absolute_clock_ticks = *i + missed_clock_ticks; |
#if defined CONFIG TIMEOUT_AVL_TREE |
avltree_node_t *expnode; |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
extavltree_node_t *expnode; |
#endif |
/* |
* To avoid lock ordering problems, |
* run all expired timeouts as you visit them. |
150,10 → 153,18 |
*/ |
for (; *i <= absolute_clock_ticks; (*i)++) { |
/* |
* Basetime is encreased by missed clock ticks + 1 !! |
*/ |
clock_update_counters(); |
spinlock_lock(&CPU->timeoutlock); |
while ((expnode = head->next) != head) { |
/* |
* Check whether first timeout in list time out. If so perform callback function and try |
* next timeout (more timeouts can have same timeout). |
*/ |
while ((expnode = CPU->timeout_active_tree.head.next) != &(CPU->timeout_active_tree.head)) { |
h = extavltree_get_instance(expnode,timeout_t,node); |
spinlock_lock(&h->lock); |
if (expnode->key != *i) { |
161,7 → 172,15 |
break; |
} |
/* |
* Delete first node in the list and repair tree structure in |
* constant time. |
*/ |
#if defined CONFIG TIMEOUT_AVL_TREE |
avltree_delete_min(&CPU->timeout_active_tree); |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
extavltree_delete_min(&CPU->timeout_active_tree); |
#endif |
f = h->handler; |
arg = h->arg; |
203,7 → 222,93 |
} |
} |
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE |
/** Clock routine |
* |
* Clock routine executed from clock interrupt handler |
* (assuming interrupts_disable()'d). Runs expired timeouts |
* and preemptive scheduling. |
* |
*/ |
void clock(void) |
{ |
extavltree_node_t *expnode; |
timeout_t *h; |
timeout_handler_t f; |
void *arg; |
count_t missed_clock_ticks = CPU->missed_clock_ticks; |
int i; |
/* |
* To avoid lock ordering problems, |
* run all expired timeouts as you visit them. |
*/ |
for (i = 0; i <= missed_clock_ticks; i++) { |
clock_update_counters(); |
spinlock_lock(&CPU->timeoutlock); |
/* |
* Check whether first timeout in list time out. If so perform callback function and try |
* next timeout (more timeouts can have same timeout). |
*/ |
while ((expnode = CPU->timeout_active_tree.head.next) != &(CPU->timeout_active_tree.head)) { |
h = list_get_instance(l, timeout_t, link); |
spinlock_lock(&h->lock); |
if (expnode->key != 0) { |
expnode->key--; |
spinlock_unlock(&h->lock); |
break; |
} |
/* |
* Delete first node in the list and repair tree structure in |
* constant time. Be careful of expnode's key, it must be 0! |
*/ |
extavltree_delete_min(&CPU->timeout_active_tree); |
f = h->handler; |
arg = h->arg; |
timeout_reinitialize(h); |
spinlock_unlock(&h->lock); |
spinlock_unlock(&CPU->timeoutlock); |
f(arg); |
spinlock_lock(&CPU->timeoutlock); |
} |
spinlock_unlock(&CPU->timeoutlock); |
} |
CPU->missed_clock_ticks = 0; |
/* |
* Do CPU usage accounting and find out whether to preempt THREAD. |
*/ |
if (THREAD) { |
uint64_t ticks; |
spinlock_lock(&CPU->lock); |
CPU->needs_relink += 1 + missed_clock_ticks; |
spinlock_unlock(&CPU->lock); |
spinlock_lock(&THREAD->lock); |
if ((ticks = THREAD->ticks)) { |
if (ticks >= 1 + missed_clock_ticks) |
THREAD->ticks -= 1 + missed_clock_ticks; |
else |
THREAD->ticks = 0; |
} |
spinlock_unlock(&THREAD->lock); |
if (!ticks && !PREEMPTION_DISABLED) { |
scheduler(); |
} |
} |
} |
#else |
276,7 → 381,6 |
scheduler(); |
} |
} |
} |
#endif |
/branches/rcu/kernel/generic/src/adt/avl.c |
---|
0,0 → 1,701 |
/* |
* Copyright (c) 2006 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 binary search tree with non-unique keys |
* @li Difference of heights of left and right subtree of every node is max 1. |
* |
* Every node has pointer to its parent which allows insertion of multiple identical keys |
* into tree. |
* |
* Be careful of using this tree because of 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> |
#include <panic.h> |
#define AVLTREE_LEFT 0 |
#define AVLTREE_RIGHT 1 |
/** Search first occurence of given key in AVL tree. |
* |
* @param t AVL tree. |
* @param key Key to be searched. |
* |
* @return Pointer to value 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; |
} |
/** 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 will contain new node. |
* Last node with non-zero balance in the way to leaf is stored as top - |
* it si place of possible balance failure. |
*/ |
dpc = &t->root; |
gpa = NULL; |
top = t->root; |
while (par = *dpc) { |
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 empty tree. |
*/ |
if (t->root == NULL) { |
*dpc = newnode; |
return; |
} |
/* |
* Insert new node into previously found leaf place. |
*/ |
*dpc = newnode; |
/* |
* If tree contains one node - end. |
*/ |
if (top == NULL) return; |
/* |
* Store pointer of top's father which points to the node with potentialy 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 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 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 = 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 = 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 = 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 = top->balance = 0; |
} else { |
par->balance = 1; |
top->balance = 0; |
} |
gpa->balance = 0; |
*dpc = gpa; |
} |
} else { |
/* |
* Balance is not broken, insertion is finised. |
*/ |
return; |
} |
} |
/** Delete node from AVL tree. |
* |
* Because of allowed multiple identical keys parent pointers are essential |
* during deletition. |
* |
* @param t AVL tree structure. |
* @param node Address of 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; |
uint8_t dir; |
ASSERT(t); |
ASSERT(node); |
if (node->lft == NULL) { |
if (node->rgt) { |
/* |
* Replace node with its only right son. |
* |
* Balance of right son will be repaired in balancing cycle. |
*/ |
cur = node->rgt; |
cur->par = node->par; |
gpa = cur; |
dir = AVLTREE_RIGHT; |
cur->balance = node->balance; |
} else { |
if (node->par == NULL) { |
/* |
* Tree has only one node - it will be empty tree and balancing can end. |
*/ |
t->root = NULL; |
return; |
} |
/* |
* Node has no child, will be deleted with no substitution. |
*/ |
gpa = node->par; |
cur = NULL; |
dir = (gpa->lft == node)? AVLTREE_LEFT: AVLTREE_RIGHT; |
} |
} else { |
/* |
* Node has left and right son. Find a node with smallest key in left subtree |
* and replace deleted node with that node. |
*/ |
for (cur = node->lft; cur->rgt != NULL; cur = cur->rgt) |
; |
//cur obsahuje uzel, ktery vlozim misto uzlu node |
if (cur != node->lft) { |
/* |
* The most right node of deleted node's left subtree was found. Replace |
* deleted node with this node. Cutting founded node has two cases in |
* dependence on its left son. |
*/ |
if (cur->lft) { |
/* |
* Founded node has left son. |
*/ |
gpa = cur->lft; |
gpa->par = cur->par; |
dir = AVLTREE_LEFT; |
gpa->balance = cur->balance; |
} else { |
dir = AVLTREE_RIGHT; |
gpa = cur->par; |
} |
cur->par->rgt = cur->lft; |
cur->lft = node->lft; |
cur->lft->par = cur; |
} else { |
/* |
* Left son of node hasn't got right son. Left son will take deleted node's place. |
*/ |
dir = AVLTREE_LEFT; |
gpa = cur; |
} |
if (node->rgt) node->rgt->par = cur; |
cur->rgt = node->rgt; |
cur->balance = node->balance; |
cur->par = node->par; |
} |
/* |
* Repair parent nodes pointer which pointed previously to deleted node. |
*/ |
if (node->par == NULL) { |
t->root = cur; |
} else { |
if (node->par->lft == node) { |
node->par->lft = cur; |
} else { |
node->par->rgt = cur; |
} |
} |
/* |
* Repair cycle which repairs balances of nodes in way from cutted noded down to root. |
*/ |
for(;;) { |
if (dir == AVLTREE_LEFT) { |
/* |
* Deletition was made in left subtree. |
*/ |
gpa->balance++; |
if (gpa->balance == +1) { |
/* |
* Stop balancing, tree is balanced. |
*/ |
break; |
} else if (gpa->balance == +2) { |
/* |
* Bad balance, heights of left and right subtrees differs more then is allowed. |
*/ |
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 childs in dependence on |
* balance factor of grand child (cur). |
*/ |
if (cur->balance == +1) { |
par->balance = 0; |
gpa->balance = -1; |
if (gpa->rgt) gpa->rgt->par = gpa; |
par->lft->par = par; |
} else if (cur->balance == 0) { |
par->balance = gpa->balance = 0; |
if (gpa->rgt) gpa->rgt->par = gpa; |
if (par->lft) par->lft->par = par; |
} else { |
par->balance = +1; |
gpa->balance = 0; |
if (par->lft) par->lft->par = par; |
gpa->rgt->par = gpa; |
} |
cur->balance = 0; |
/* |
* Repair paternity. |
*/ |
cur->par = gpa->par; |
gpa->par = cur; |
par->par = cur; |
/* |
* Repair pointer which pointed to balanced node. If it was root then balancing |
* is finished else continue in next iteration (parent node). |
*/ |
if (cur->par == NULL) { |
t->root = cur; |
break; |
} else |
if (cur->par->lft == gpa) { |
cur->par->lft = cur; |
dir = AVLTREE_LEFT; |
} else { |
cur->par->rgt = cur; |
dir = AVLTREE_RIGHT; |
} |
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) { |
/* |
* Right child of balanced node is balanced, after RR rotation is done, whole |
* tree will be balanced. |
*/ |
par->balance = -1; |
gpa->balance = +1; |
/* |
* Repair pointer which pointed to balanced node and finish balancing. |
*/ |
if (par->par == NULL) { |
t->root = par; |
} else |
if (par->par->lft == gpa) { |
par->par->lft = par; |
} else { |
par->par->rgt = par; |
} |
break; |
} else { |
par->balance = gpa->balance = 0; |
/* |
* Repair pointer which pointed to balanced node. If it was root then balancing |
* is finished else continue in next iteration (parent node). |
*/ |
if (par->par == NULL) { |
t->root = par; |
break; |
} else { |
if (par->par->lft == gpa) { |
par->par->lft = par; |
dir = AVLTREE_LEFT; |
} else { |
par->par->rgt = par; |
dir = AVLTREE_RIGHT; |
} |
} |
} |
gpa = par->par; |
} |
} else { |
/* |
* Repair pointer which pointed to balanced node. If it was root then balancing |
* is finished else continue in next iteration (parent node). |
*/ |
if (!gpa->par) break; |
if (gpa->par->lft == gpa) { |
dir = AVLTREE_LEFT; |
} else { |
dir = AVLTREE_RIGHT; |
} |
gpa = gpa->par; |
} |
} else { |
/* |
* Deletition was made in right subtree. |
*/ |
gpa->balance--; |
if (gpa->balance == -1) { |
/* |
* Stop balancing, tree is balanced. |
*/ |
break; |
} else if (gpa->balance == -2) { |
/* |
* Bad balance, heights of left and right subtrees differs more then is allowed. |
*/ |
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 childs in dependence on |
* balance factor of grand child (cur). |
*/ |
if (cur->balance == -1) { |
par->balance = 0; |
gpa->balance = +1; |
if (gpa->lft) gpa->lft->par = gpa; |
par->rgt->par = par; |
} else if (cur->balance == 0) { |
par->balance = gpa->balance = 0; |
if (gpa->lft) gpa->lft->par = gpa; |
if (par->rgt) par->rgt->par = par; |
} else { |
par->balance = -1; |
gpa->balance = 0; |
if (par->rgt) par->rgt->par = par; |
gpa->lft->par = gpa; |
} |
cur->balance = 0; |
/* |
* Repair paternity. |
*/ |
cur->par = gpa->par; |
gpa->par = cur; |
par->par = cur; |
/* |
* Repair pointer which pointed to balanced node. If it was root then balancing |
* is finished else continue in next iteration (parent node). |
*/ |
if (cur->par == NULL) { |
t->root = cur; |
break; |
} else |
if (cur->par->lft == gpa) { |
cur->par->lft = cur; |
dir = AVLTREE_LEFT; |
} else { |
cur->par->rgt = cur; |
dir = AVLTREE_RIGHT; |
} |
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) { |
/* |
* Left child of balanced node is balanced, after RR rotation is done, whole |
* tree will be balanced. |
*/ |
par->balance = +1; |
gpa->balance = -1; |
/* |
* Repair pointer which pointed to balanced node and finish balancing. |
*/ |
if (par->par == NULL) { |
t->root = par; |
} else |
if (par->par->lft == gpa) { |
par->par->lft = par; |
} else { |
par->par->rgt = par; |
} |
break; |
} else { |
par->balance = gpa->balance = 0; |
/* |
* Repair pointer which pointed to balanced node. If it was root then balancing |
* is finished else continue in next iteration (parent node). |
*/ |
if (par->par == NULL) { |
t->root = par; |
break; |
} else { |
if (par->par->lft == gpa) { //v cyklu jsem ani jednou neskocil - cur nema praveho syna |
par->par->lft = par; |
dir = AVLTREE_LEFT; |
} else { |
par->par->rgt = par; |
dir = AVLTREE_RIGHT; |
} |
} |
} |
gpa = par->par; |
} |
} else { |
/* |
* Repair pointer which pointed to balanced node. If it was root then balancing |
* is finished else continue in next iteration (parent node). |
*/ |
if (!gpa->par) break; |
if (gpa->par->lft == gpa) { |
dir = AVLTREE_LEFT; |
} else { |
dir = AVLTREE_RIGHT; |
} |
gpa = gpa->par; |
} |
} |
} |
} |
/** Delete node from AVL tree with the smallest key and set base of tree to that key. |
* |
* @param t AVL tree structure. |
*/ |
avltree_node_t *avltree_delete_min(avltree_t *t) |
{ |
avltree_node_t *node; |
uint64_t key; |
/* |
* Start search of smallest key in tree in the root node and |
* continue in cycle to the most left node in the tree which |
* must have smallest key. |
*/ |
node = t->root; |
if (!node) return false; |
while (node->lft != NULL) |
node = node->lft; |
/* |
* Store key and use avltree_delete function to delete node from tree. |
*/ |
key = node->key; |
avltree_delete(t,node); |
/* |
* Change base to the key of deleted node. |
*/ |
t->base = key; |
return true; |
} |
/branches/rcu/kernel/generic/src/adt/extavl.c |
---|
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; |
} |
/branches/rcu/kernel/generic/src/adt/extavlrel.c |
---|
0,0 → 1,1029 |
/* |
* 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 with relative keys implementation. |
* |
* This file implements Extended AVL tree with relative keys type and operations. |
* |
* Extended AVL tree with relative keys (ExtAvlrel tree) has the following properties: |
* @li it is binary search tree with unique real 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 real 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 real keys, node key is |
* only difference between previous real node's key and its real node's key |
* @li real key is either equal node key if node is leftmost node in tree or sum of all |
* node keys with smaller real key |
* |
* Be careful of using this tree because node keys are not equal real keys (except leftmost node). |
*/ |
#include <adt/extavlrel.h> |
#include <debug.h> |
#include <panic.h> |
#define AVLTREE_LEFT 0 |
#define AVLTREE_RIGHT 1 |
/* Returns height of tree -1 */ |
#define extavlreltree_tree_height(node) ((node) == NULL) ? (-1) : max(((node)->lft_height),((node)->rgt_height)) |
/** Search first occurence (oldest node with this real key) of given key in ExtAVLrel tree. |
* |
* @param t ExtAVLrel tree. |
* @param key Key to be searched. |
* |
* @return Pointer to value or NULL if there is no such key. |
*/ |
extavlreltree_node_t *extavlreltree_search(extavlreltree_t t, uint64_t key) |
{ |
extavlreltree_node_t *cur; |
uint64_t sum, s; |
/* |
* Find right subtree in way up to the root where can be node with given key. |
* Root node is the last node in the way up, when we reach root, it means, |
* that searched node belongs to the right subtree of root. |
*/ |
sum = 0; |
cur = t->head.next; |
while (1) { |
sum += cur->key + cur->rgt_sum; |
if ((key <= sum) || (cur == t->root)) |
break; |
else |
cur = cur->par; |
} |
/* |
* Sorting for cycle. |
* Search for key in choosen subtree. Searching start at cur node which we have found |
* in previous step. It is common search algorithm for binary search tree. |
*/ |
while (cur != NULL) { |
s = sum - cur->rgt_sum; |
if (key < s) { |
/* |
* Left subtree. Find max value in left subtree of cur. |
*/ |
sum -= cur->key + cur->rgt_sum; |
cur = cur->lft; |
} else if (key > s) { |
/* |
* Right subtree. sum has still max value in the right subtree of cur. |
*/ |
cur = cur->rgt; |
} else { |
/* |
* Equal values. We have found node with given key. |
*/ |
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 extavlreltree_insert(extavlreltree_t *t, extavlreltree_node_t *newnode) |
{ |
extavlreltree_node_t *cur; |
extavlreltree_node_t *son; |
extavlreltree_node_t *gpa; |
extavlreltree_node_t *par; |
uint64_t sum, s; |
uint8_t dir; |
/* |
* Condition var - all rgt_sums in the way down to root must be repaired in condition |
* that we came there from right and on the way from repaired node to new node we |
* never turn to the left. Reparation is done in the reparation cycle. |
*/ |
bool repair_rgt_sum; |
ASSERT(t); |
ASSERT(newnode); |
/* |
* Insert first node into empty tree. Key is left without change (according to definition). |
*/ |
cur = t->head.next; |
if (cur == &t->head) { |
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; |
newnode->rgt_sum = 0; |
t->head.prev = newnode; |
t->head.next = newnode; |
t->root = newnode; |
return; |
} |
/* |
* Find right subtree in way up to the root where newnode will be placed. |
* Root node is the last node in the way up, when we reach root, it means, |
* that newnode belongs to the right subtree of root. |
* |
* When max key of cur's right subtree is inserted, while cycle overjumps |
* right node and stops. But in the next sorting for cycle is this situation |
* solved (for cycle jumps back to the left child). |
*/ |
sum = 0; |
while (1) { |
sum += cur->key + cur->rgt_sum; |
if ((newnode->key <= sum) || (cur == t->root)) |
break; |
else |
cur = cur->par; |
} |
/* |
* Sorting for cycle. |
* Find a place for newnode. Searching start at cur node which we have found |
* in previous step. It is common search algorithm for binary search tree. |
*/ |
for (;;) { |
s = sum - cur->rgt_sum; |
if (newnode->key < s) { |
/* |
* Left subtree. Find max value in left subtree of cur. |
*/ |
sum -= cur->key + cur->rgt_sum; |
if (!cur->lft) { |
/* |
* Insert new node to the left. |
*/ |
cur->lft = newnode; |
newnode->lft = NULL; |
newnode->rgt = NULL; |
newnode->lft_height = 0; |
newnode->rgt_height = 0; |
newnode->par = cur; |
/* |
* Insert newnode to list. |
*/ |
newnode->next = cur; |
newnode->prev = cur->prev; |
cur->prev->next = newnode; |
cur->prev = newnode; |
newnode->key -= sum; |
newnode->rgt_sum = 0; |
/* |
* Repair key of next value (next node always exists). newnode->key |
* has been already set. Needn't check whether newnode->next is head |
* beacause newnode is left child (next node is his father). |
*/ |
newnode->next->key -= newnode->key; |
repair_rgt_sum = false; |
dir = AVLTREE_LEFT; |
break; |
} |
cur = cur->lft; |
} else if (newnode->key > s) { |
/* |
* Right subtree. sum has still max value in the right subtree of cur. |
*/ |
if (!cur->rgt) { |
cur->rgt = newnode; |
newnode->lft = NULL; |
newnode->rgt = NULL; |
newnode->lft_height = 0; |
newnode->rgt_height = 0; |
newnode->par = cur; |
/* |
* Find last node in the chain with the same key as cur node. |
*/ |
gpa = cur->next; |
while (gpa != &t->head && gpa->key == 0) |
gpa = gpa->next; |
/* |
* Insert new node to list. Right place in the list was found in |
* previous cycle. |
*/ |
newnode->prev = gpa->prev; |
newnode->next = gpa; |
gpa->prev->next = newnode; |
gpa->prev = newnode; |
newnode->key -= sum; |
newnode->rgt_sum = 0; |
/* |
* Repair key of next value (next node always exists). newnode->key |
* has been already set. |
*/ |
if (newnode->next != &t->head) |
newnode->next->key -= newnode->key; |
/* |
* All rgt_sums in the way down to root must be repaired in condition |
* that we came there from right and on the way from node to new node we |
* never turn left. |
*/ |
repair_rgt_sum = true; |
dir = AVLTREE_RIGHT; |
break; |
} |
cur = cur->rgt; |
} else { |
/* |
* Equal values. Give newnode to the last position of chain with the cur head and |
* end insertion. |
*/ |
gpa = cur->next; |
while (gpa != &t->head && gpa->key == 0) |
gpa = gpa->next; |
/* |
* Insert new node to list in right place. |
*/ |
newnode->prev = gpa->prev; |
newnode->next = gpa; |
gpa->prev->next = newnode; |
gpa->prev = newnode; |
newnode->par = NULL; |
newnode->lft = NULL; |
newnode->rgt = NULL; |
newnode->lft_height = 0; |
newnode->rgt_height = 0; |
/* |
* Nodes in chains has key equal 0, because difference between previous node and them is 0. |
*/ |
newnode->key = 0; |
newnode->rgt_sum = 0; |
return; |
} |
} |
/* |
* Balancing all nodes from newnode's parent down to root. |
*/ |
cur = newnode->par; |
while (true) { |
if (dir == AVLTREE_LEFT) { |
/* |
* Insertion was made in the left subtree - repair left height, stop |
* repairing rgt_sum and check balance of current node. |
*/ |
cur->lft_height = extavlreltree_tree_height(cur->lft) + 1; |
repair_rgt_sum = false; |
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 = extavlreltree_tree_height(cur) + 1; |
/* |
* Repair rgt_sum. |
*/ |
son->rgt_sum += cur->key + cur->rgt_sum; |
} 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 = extavlreltree_tree_height(cur) + 1; |
gpa->lft_height = extavlreltree_tree_height(son) + 1; |
/* |
* Repair rgt_sums. |
*/ |
son->rgt_sum -= gpa->key + gpa->rgt_sum; |
gpa->rgt_sum += cur->key + cur->rgt_sum; |
} |
/* |
* Repair parent of current node. |
*/ |
gpa->par = par; |
} else { |
/* |
* Balance is correct, continue balancing at parent node. |
*/ |
par = cur->par; |
gpa = cur; |
} |
} else { |
/* |
* Insertion was made in the right subtree - repair right height, try to |
* repair rgt_sum and check balance of current node. |
*/ |
cur->rgt_height = extavlreltree_tree_height(cur->rgt) + 1; |
if (repair_rgt_sum) { |
cur->rgt_sum += newnode->key; |
} |
if ((cur->rgt_height - cur->lft_height) >= 2) { |
/* |
* Balance was corrupted, must be repaired through RL or RR 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 = extavlreltree_tree_height(cur) + 1; |
/* |
* Repair rgt_sum. |
*/ |
cur->rgt_sum -= son->rgt_sum + son->key; |
} 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 = extavlreltree_tree_height(cur) + 1; |
gpa->rgt_height = extavlreltree_tree_height(son) + 1; |
/* |
* Repair rgt_sums. |
*/ |
cur->rgt_sum -= son->key + son->rgt_sum + gpa->key + gpa->rgt_sum; |
gpa->rgt_sum += son->key + son->rgt_sum; |
} |
/* |
* Repair parent of current node. |
*/ |
gpa->par = par; |
} else { |
/* |
* Balance is correct, continue balancing at parent node. |
*/ |
par = cur->par; |
gpa = cur; |
} |
} |
/* |
* Change parent pointers, set direction where is newnode and |
* continue balancing at parent node or if current node |
* is root then change root atribute pointer and stop |
*/ |
if (par) { |
if (par->lft == cur) { |
par->lft = gpa; |
dir = AVLTREE_LEFT; |
} else { |
par->rgt = gpa; |
dir = AVLTREE_RIGHT; |
} |
} else { |
t->root = gpa; |
break; |
} |
cur = par; |
} |
} |
/** Delete node from ExtAVLrel tree. |
* |
* @param t ExtAVLrel tree structure. |
* @param node Address of node which will be deleted. |
*/ |
void extavlreltree_delete(extavlreltree_t *t, extavlreltree_node_t *node) |
{ |
extavlreltree_node_t **gpapar; |
extavlreltree_node_t *cur; |
extavlreltree_node_t *par; |
extavlreltree_node_t *gpa; |
int8_t dir; |
int8_t dir2=0; |
uint64_t key; |
int16_t balance; |
/* |
* Condition var - if true then all rgt_sums in the way down to root must be repaired in condition |
* that we came there from right and on the way from repaired node to new node we |
* never turn to the left. Reparation is done in the reparation cycle. |
*/ |
bool repair_rgt_sum; |
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; |
} |
repair_rgt_sum = false; |
gpapar = &(t->root); |
} else { |
/* |
* Find tree pointer which points to node. |
*/ |
if (node->par->lft == node) { |
gpapar = &(node->par->lft); |
repair_rgt_sum = false; |
} else { |
gpapar = &(node->par->rgt); |
/* |
* Node is right child - rgt_sum might be repaired. |
*/ |
repair_rgt_sum = true; |
} |
} |
if (&t->head != node->next && node->next->key == 0) { |
/* |
* Deleted node has at least one node node with the same key which is closest next |
* neighbor in the list, copy node atributes into next node and end. |
*/ |
cur = node->next; |
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; |
cur->key = node->key; |
cur->rgt_sum = node->rgt_sum; |
return; |
} |
/* |
* Repair next node's key (it must be difference between previous key and its key). |
*/ |
if (node->next != &t->head) { |
node->next->key += node->key; |
} |
/* |
* 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) { |
/* |
* rgt_sum is not corrupted because the biggest key is in right subtree of node |
*/ |
node->rgt->par = gpa; |
repair_rgt_sum = false; |
} else { |
/* |
* node is the biggest key and rgt_sum might be repaired according to which |
* child is node. |
*/ |
key = node->key; |
} |
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. |
*/ |
if (repair_rgt_sum == false && node->rgt_sum == 0) { |
/* |
* node hasn't got right son so right sum is 0. |
*/ |
cur->rgt_sum = 0; |
} else { |
cur->rgt_sum = node->rgt_sum + node->key; //pri node->rgt_sum == 0 bude opraveno v cyklu |
if (repair_rgt_sum == true && node->rgt_sum != 0) { |
/* |
* node has got right son so node's key is not the biggest key in any subtree. |
*/ |
repair_rgt_sum = false; |
} else { |
/* |
* node is the biggest key and predecessors might be repaired. |
*/ |
key = node->key; |
} |
} |
} 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. |
*/ |
/* |
* node must have always rgt child otherwise its malfunction of extavltree definition |
* so we can add node->key. If it was to the contrary, we wouldn't know where |
*/ |
cur->rgt_sum = node->rgt_sum + node->key; |
/* |
* The biggest key in at least one subtree was changed - rgt_sum must be repaired. |
*/ |
repair_rgt_sum = true; |
key = cur->key; |
} |
/* |
* Deleted node is root node. Balancing is finished. |
*/ |
if (!gpa) return; |
} |
/* |
* Repair cycle which goes from gpa node down to root. |
*/ |
for(;;) { |
if (repair_rgt_sum) { |
/* |
* The biggest key in right subtree was deleted so rgt_sum must be changed. |
*/ |
gpa->rgt_sum -= key; |
} |
/* |
* 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; |
repair_rgt_sum = falsi; |
} 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 = extavlreltree_tree_height(gpa) + 1; |
cur->rgt_height = par->rgt_height + 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. |
*/ |
*gpapar = cur; |
/* |
* Repair rgt_sums after rotation was done. |
*/ |
gpa->rgt_sum -= par->key + par->rgt_sum + cur->key + cur->rgt_sum; |
cur->rgt_sum += par->key + par->rgt_sum; |
/* |
* Next balancing at parent node. |
*/ |
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 heights and tree pointer which points to the current node. |
*/ |
balance = par->rgt_height - par->lft_height; |
par->lft_height++; |
*gpapar = par; |
/* |
* Repair rgt_sums after rotation was done. |
*/ |
gpa->rgt_sum -= par->key + par->rgt_sum; |
/* |
* Ends when tree is balanced or do the next step. |
*/ |
if (balance == 0) return; |
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 - (extavlreltree_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 = extavlreltree_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. |
*/ |
*gpapar = cur; |
/* |
* Repair rgt_sums after rotation was done. |
*/ |
par->rgt_sum -= cur->key + cur->rgt_sum; |
cur->rgt_sum += gpa->key + gpa->rgt_sum; |
/* |
* Next balancing at parent node. |
*/ |
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 heights and tree pointer which points to the current node. |
*/ |
balance = par->rgt_height - par->lft_height; |
par->rgt_height = extavlreltree_tree_height(gpa) + 1; |
*gpapar = par; |
/* |
* Repair rgt_sums after rotation was done. |
*/ |
par->rgt_sum += gpa->key + gpa->rgt_sum; |
/* |
* Ends balancing when heights in par nodes are balanced and height |
* of par subtree wasn't decreased due to timeout operation or do |
* the next step. |
*/ |
if (balance == 0 && par->rgt_height == prevlftheight) { |
gpa = par; |
break; |
} |
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; |
} |
/* |
* End balancing. We must continue in repairing rgt_sum until we |
* reach first left child. |
*/ |
if (repair_rgt_sum) { |
cur = gpa; |
gpa = gpa->par; |
while (gpa) { |
if (gpa->lft == cur) |
break; |
gpa->rgt_sum -= key; |
cur = gpa; |
gpa = gpa->par; |
} |
} |
} |
/** Delete node from ExtAVLirel tree with the smallest key. |
* |
* Be careful deleted node must have key equal 0 to perform regular timeout. |
* |
* @param t ExtAVLrel tree structure. |
*/ |
bool extavlreltree_delete_min(extavlreltree_t *t) |
{ |
extavlreltree_node_t *expnode; |
extavlreltree_node_t *nextnode; |
ASSERT(t); |
expnode = t->head.next; |
nextnode = expnode->next; |
if (&t->head == expnode) return false; |
if (nextnode != &t->head) { |
/* |
* Only first node in the list can be tree node and its key can be 0 (nextnode is the second). |
*/ |
if (nextnode->key == 0) { |
/* |
* Next node of expnode is its chain node. Copy expnode into nextnode. |
*/ |
nextnode->lft = expnode->lft; |
nextnode->rgt = expnode->rgt; |
nextnode->par = expnode->par; |
nextnode->lft_height = expnode->lft_height; |
nextnode->rgt_height = expnode->rgt_height; |
if (t->root == expnode) |
t->root = nextnode; |
else |
if (expnode->par->lft == expnode) |
expnode->par->lft = nextnode; |
else |
expnode->par->rgt = nextnode; |
if (expnode->lft) expnode->lft->par = nextnode; |
if (expnode->rgt) expnode->rgt->par = nextnode; |
nextnode->rgt_sum = expnode->rgt_sum; |
} else if (!expnode->par) { |
/* |
* Delete root node which musn't have left son. |
*/ |
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; |
} |
nextnode->key += expnode->key; |
} |
/* |
* Delete node from the list. |
*/ |
t->head.next = nextnode; |
nextnode->prev = &t->head; |
return true; |
} |