Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2415 → Rev 2416

/branches/rcu/kernel/generic/include/time/timeout.h
36,20 → 36,44
#define KERN_TIMEOUT_H_
 
#include <arch/types.h>
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE
#if defined CONFIG_TIMEOUT_AVL_TREE
#include <adt/avl.h>
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
#include <adt/extavl.h>
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
#include <adt/extavlrel.h>
#else
#include <adt/list.h>
#endif
#include <adt/list.h>
#include <cpu.h>
 
typedef void (* timeout_handler_t)(void *arg);
 
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE
 
#if defined CONFIG_TIMEOUT_AVL_TREE
 
typedef struct {
SPINLOCK_DECLARE(lock);
/**
* AVL tree node structure holds information
* about connections with other timeouts.
*/
avltree_node_t node;
/** Function that will be called on timeout activation. */
timeout_handler_t handler;
/** Argument to be passed to handler() function. */
void *arg;
/** On which processor is this timeout registered. */
cpu_t *cpu;
} timeout_t;
 
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
 
typedef struct {
SPINLOCK_DECLARE(lock);
/**
* Extended AVL tree node structure holds information
* about connections with other timeouts.
*/
62,6 → 86,24
cpu_t *cpu;
} timeout_t;
 
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
 
typedef struct {
SPINLOCK_DECLARE(lock);
/**
* Extended AVL tree with relative keys node structure holds information
* about connections with other timeouts.
*/
extavlreltree_node_t node;
/** Function that will be called on timeout activation. */
timeout_handler_t handler;
/** Argument to be passed to handler() function. */
void *arg;
/** On which processor is this timeout registered. */
cpu_t *cpu;
} timeout_t;
 
#else
 
typedef struct {
/branches/rcu/kernel/generic/include/cpu.h
64,9 → 64,15
volatile count_t needs_relink;
 
SPINLOCK_DECLARE(timeoutlock);
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE
#if defined CONFIG_TIMEOUT_AVL_TREE
/** AVL tree structure. */
avltree_t timeout_active_tree;
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
/** Extended AVL tree structure. */
extavltree_t timeout_active_tree;
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
/** Extended AVL tree structure with relative keys. */
extavlreltree_t timeout_active_tree;
#else
/** Head of list of timeouts. */
link_t timeout_active_head;
/branches/rcu/kernel/generic/include/adt/avl.h
0,0 → 1,131
/*
* 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
*/
 
 
#ifndef KERN_AVLTREE_H_
#define KERN_AVLTREE_H_
 
#include <arch/types.h>
 
/*
* Makro for getting pointer to structure which enclosure avltree structure.
*
* @param link Pointer to avltree structure.
* @param type Name of outer structure.
* @param member Name of avltree atribute in outer structure.
*/
#define avltree_get_instance(link,type,member) \
((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
 
 
typedef struct avltree_node avltree_node_t;
typedef struct avltree avltree_t;
 
 
/** AVL tree node structure. */
struct avltree_node
{
/**
* Pointer to left descendand of this node.
*
* All keys of nodes in the left subtree are less then key of this node.
*/
struct avltree_node *lft;
/**
* Pointer to right descendand of this node.
*
* All keys of nodes in the right subtree are greater then key of this node.
*/
struct avltree_node *rgt;
/** Pointer to parent node. Root node has NULL parent. */
struct avltree_node *par;
/** Nodes key. */
uint64_t key;
/** Difference between heights of left and right subtree of this node.*/
short balance;
};
 
/** AVL tree structure. */
struct avltree
{
/** AVL root node pointer */
struct avltree_node *root;
 
/**
* Base of tree is value that is smaller or equal then every value in tree.
*
* Base is added to current key when new node is inserted into tree.
* Base is changed to the key of node which is deleted with function
* avltree_delete_min.
*/
uint64_t base; /**< POZOR: Base time for inserting new nodes */
};
 
 
/** Create empty AVL tree.
*
* @param t AVL tree.
*/
static inline void avltree_create (avltree_t *t)
{
t->root = NULL;
t->base = 0;
}
 
/** Initialize node.
*
* @param Node which is initialized.
*/
static inline void avltree_node_initialize(avltree_node_t *node)
{
node->key = 0;
node->lft = NULL;
node->rgt = NULL;
node->par = NULL;
node->balance = 0;
}
 
avltree_node_t *avltree_search(avltree_t *t, uint64_t key);
void avltree_insert(avltree_t *t, avltree_node_t *newnode);
void avltree_delete(avltree_t *t, avltree_node_t *node);
avltree_node_t *avltree_delete_min(avltree_t *t);
 
#endif
 
/** @}
*/
/branches/rcu/kernel/generic/include/adt/extavl.h
0,0 → 1,145
/*
* 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
*/
 
 
#ifndef KERN_EXTAVLTREE_H_
#define KERN_EXTAVLTREE_H_
 
#include <arch/types.h>
 
/*
* Makro for getting pointer to structure which enclosure extavltree structure.
*
* @param link Pointer to extavltree structure.
* @param type Name of outer structure.
* @param member Name of extavltree atribute in outer structure.
*/
#define extavltree_get_instance(link,type,member) \
((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
 
 
typedef struct extavltree_node extavltree_node_t;
typedef struct extavltree extavltree_t;
 
/** Extended AVL tree node structure. */
struct extavltree_node
{
/**
* Pointer to left descendand of this node.
*
* All keys of nodes in the left subtree are less then key of this node.
*/
extavltree_node_t *lft;
 
/**
* Pointer to right descendand of this node.
*
* All keys of nodes in the right subtree are greater then key of this node.
*/
extavltree_node_t *rgt;
/** Pointer to parent node. Root node has NULL parent. */
extavltree_node_t *par;
 
/** Pointer to next node which has equal or the closest greater key or head. */
extavltree_node_t *next;
/** Pointer to previous node which has equal or the closest lesser key or head. */
extavltree_node_t *prev;
/** Height of left subtree. */
int16_t lft_height;
 
/** Height of right subtree. */
int16_t rgt_height;
 
/** Nodes key. */
uint64_t key;
};
 
/** Extended AVL tree structure. */
struct extavltree
{
/** Extended AVL root node pointer. */
extavltree_node_t *root;
 
/** Head of doubly linked list of nodes. */
extavltree_node_t head;
 
/**
* Base of tree is value that is smaller or equal then every value in tree.
*
* Base is added to current key when new node is inserted into tree.
* Base is changed to the key of node which is deleted with function
* extavltree_delete_min.
*/
uint64_t base;
};
 
/** Initialize node.
*
* @param node Node which is initialized.
*/
static inline void extavltree_node_initialize(extavltree_node_t *node)
{
node->lft = NULL;
node->rgt = NULL;
node->lft_height = 0;
node->rgt_height = 0;
node->par = NULL;
node->next = node;
node->prev = node;
node->key = 0;
};
 
/** Create empty Extended AVL tree.
*
* @param t Extended AVL tree structure.
*/
static inline void extavltree_create (extavltree_t *t) //jen inicializace
{
t->root = NULL;
t->base = 0;
extavltree_node_initialize(&t->head);
};
 
extavltree_node_t *extavltree_search(extavltree_t *t, uint64_t key);
void extavltree_insert(extavltree_t *t, extavltree_node_t *newnode);
void extavltree_delete(extavltree_t *t, extavltree_node_t *node);
bool extavltree_delete_min(extavltree_t *t);
 
#endif
 
/** @}
*/
/branches/rcu/kernel/generic/include/adt/extavlrel.h
0,0 → 1,149
/*
* 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
*/
 
 
#ifndef KERN_EXTAVLRELTREE_H_
#define KERN_EXTAVLRELTREE_H_
 
#include <arch/types.h>
 
typedef struct extavlreltree_node extavlreltree_node_t;
typedef struct extavlreltree extavlreltree_t;
 
 
/*
* Makro for getting pointer to structure which enclosure extavlreltree structure.
*
* @param link Pointer to extavlreltree structure.
* @param type Name of outer structure.
* @param member Name of extavlreltree atribute in outer structure.
*/
#define extavlreltree_get_instance(link,type,member) \
((type *)(((uint8_t *)(link)) - ((uint8_t *)&(((type *)NULL)->member))))
 
 
 
/** Relative key Extended AVL tree node structure. */
struct extavlreltree_node
{
/**
* Pointer to left descendand of this node.
*
* All keys of nodes in the left subtree are less then key of this node.
*/
extavlreltree_node_t *lft;
 
/**
* Pointer to right descendand of this node.
*
* All keys of nodes in the right subtree are greater then key of this node.
*/
extavlreltree_node_t *rgt;
/** Pointer to parent node. Root node has NULL parent. */
extavlreltree_node_t *par;
 
/** Pointer to next node which has equal or the closest greater key or head. */
extavlreltree_node_t *next;
/** Pointer to previous node which has equal or the closest lesser key or head. */
extavlreltree_node_t *prev;
/** Height of left subtree. */
int16_t lft_height;
 
/** Height of right subtree. */
int16_t rgt_height;
 
/** Nodes key. */
uint64_t key;
 
/** Sum of all keys in the right subtree. */
uint64_t rgt_sum;
};
 
/** Relative key Extended AVL tree structure (ExtAvlrel). */
#ifdef AVLTREE_TEST
struct extavlreltree
{
/*
* ExtAvlrel root node pointer.
*
* Important only for recognition of non tree node.
*/
extavlreltree_node_t *root;
 
/** Head of doubly linked list of nodes. It is entrance point to the tree. */
extavlreltree_node_t head;
};
 
 
 
/** Create empty Extended AVL tree.
*
* @param t Extended AVL tree structure.
*/
void extavlreltree_create (extavlreltree_t *t)
{
t->root = NULL;
 
t->head.next = &t->head;
t->head.prev = &t->head;
}
 
/** Initialize node.
*
* @param node Node which is initialized.
*/
void extavlreltree_node_initialize(extavlreltree_node_t *node)
{
node->lft = NULL;
node->rgt = NULL;
node->lft_height = 0;
node->rgt_height = 0;
node->par = NULL;
node->next = node;
node->prev = node;
node->rgt_sum = 0;
}
 
extavlreltree_node_t *extavlreltree_search(extavlreltree_t *t, uint64_t key);
void extavlreltree_insert(extavlreltree_t *t, extavlreltree_node_t *newnode);
void extavlreltree_delete(extavlreltree_t *t, extavlreltree_node_t *node);
bool extavlreltree_delete_min(extavlreltree_t *t);
 
#endif
 
/** @}
*/
/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;
}