Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2415 → Rev 2416

/branches/rcu/kernel/test/extavltree/extavltree1.def
0,0 → 1,6
{
"extavltree1",
"Test Extended Avl tree operations",
&test_extavltree1,
true
},
/branches/rcu/kernel/test/extavltree/extavltree1.c
0,0 → 1,427
/*
* Copyright (c) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
#include <test.h>
#include <print.h>
#include <adt/extavl.h>
#include <debug.h>
 
#include <panic.h>
 
 
#define NODE_COUNT 100
 
/*
* wrapper structure with a pointer to extended avl tree root
*/
static extavltree_t exttree;
 
/*
* extavltree nodes in array for faster allocating
*/
static extavltree_node_t extavltree_nodes[NODE_COUNT];
 
/*
* head of free nodes' list:
*/
static extavltree_node_t *first_free_node = NULL;
 
 
 
static int exttree_test_height(extavltree_node_t *node,bool timeout);
static extavltree_node_t *exttree_test_parents(extavltree_node_t *node);
static void print_exttree_structure_flat (extavltree_node_t *node, int level);
static bool exttree_test_link(int node_count);
static void print_exttree_link(int node_count);
static extavltree_node_t *alloc_extavltree_node(void);
 
 
 
//vraci hloubku stromu
static int exttree_test_height(extavltree_node_t *node,bool timeout)
{
int h1, h2;
 
if (!node) return -1;
 
h1 = exttree_test_height(node->lft,timeout) + 1;
if (!timeout && node->lft_height != h1) {
printf("Bad height: %d of LEFT subtree in node: %d with address: %p\n",h1,node->key,node);
}
h2 = exttree_test_height(node->rgt,0) + 1;
if (node->rgt_height != h2) {
printf("Bad height: %d of RIGHT subtree in node: %d with address: %p\n",h2,node->key,node);
}
if (!timeout && (((h1-h2)>0?h1-h2:h2-h1) > 1)) {
printf("Bad height: error in definition of avltree: %d with address: %p\n",node->key,node);
}
 
return (node->lft_height > node->rgt_height? node->lft_height: node->rgt_height);
}
 
 
/** Tests par atribute of every tree node
*
*/
static extavltree_node_t *exttree_test_parents(extavltree_node_t *node)
{
extavltree_node_t *tmp;
if (!node) return NULL;
 
if (node->lft) {
tmp = exttree_test_parents(node->lft);
if (tmp != node) {
printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->lft);
}
}
if (node->rgt) {
tmp = exttree_test_parents(node->rgt);
if (tmp != node) {
printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->rgt);
}
}
return node->par;
}
 
/** Checks list of nodes
*
*/
static bool exttree_test_link(int node_count)
{
extavltree_node_t *node;
int i;
bool test_link = true;
 
for (i = 0,node = exttree.head.next; node != &(exttree.head); i++,node = node->next) {
if ((node->next != &(exttree.head)) && (node->key > node->next->key)) {
printf("\nList is not sorted (forward direction) at key: %d\n",node->key);
test_link = false;
}
}
if (node_count && i != node_count) {
printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
test_link = false;
}
for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev) {
if ((node->prev != &(exttree.head)) && (node->key < node->prev->key)) {
printf("\nList is not sorted (backward direction) at key: %d\n",node->key);
test_link = false;
}
}
if (node_count && i != node_count) {
printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
test_link = false;
}
return test_link;
}
 
/** Prints the structure of node, which is level levels from the top of the tree.
*
*/
static void print_exttree_structure_flat (extavltree_node_t *node, int level)
{
extavltree_node_t *tmp;
int i;
 
if (level > 16)
{
printf ("[...]");
return;
}
 
if (node == NULL)
return;
for (tmp = node,i = 0; tmp->key == node->key; tmp = tmp->next,i++)
;
 
printf ("%d[%d,%d,(%d)]", node->key,node->lft_height,node->rgt_height,i);
if (node->lft != NULL || node->rgt != NULL)
{
printf("(");
 
print_exttree_structure_flat (node->lft, level + 1);
if (node->rgt != NULL)
{
printf(",");
print_exttree_structure_flat (node->rgt, level + 1);
}
 
printf(")");
}
}
 
/** Prints list of nodes
*
*/
static void print_exttree_link(int node_count)
{
extavltree_node_t *node;
printf("\n");
for (node = exttree.head.next; node != &(exttree.head); node = node->next) {
printf(" %d,",node->key);
}
for (node = exttree.head.prev; node != &(exttree.head); node = node->prev) {
printf(" %d,",node->key);
}
}
 
//****************************************************************
static void alloc_extavltree_node_prepare(void)
{
int i;
 
for (i = 0; i < NODE_COUNT - 1; i++) {
extavltree_nodes[i].next = &(extavltree_nodes[i+1]);
}
/*
* Node keys which will be used for insertion. Up to NODE_COUNT size of array.
*/
 
// First tree node and same key
extavltree_nodes[0].key = 60;
extavltree_nodes[1].key = 60;
extavltree_nodes[2].key = 60;
//LL rotation
extavltree_nodes[3].key = 50;
extavltree_nodes[4].key = 40;
extavltree_nodes[5].key = 30;
//LR rotation
extavltree_nodes[6].key = 20;
extavltree_nodes[7].key = 20;
extavltree_nodes[8].key = 25;
extavltree_nodes[9].key = 25;
//LL rotation in lower floor
extavltree_nodes[10].key = 35;
//RR rotation
extavltree_nodes[11].key = 70;
extavltree_nodes[12].key = 80;
//RL rotation
extavltree_nodes[13].key = 90;
extavltree_nodes[14].key = 85;
extavltree_nodes[15].key = 100;
extavltree_nodes[16].key = 200;
extavltree_nodes[17].key = 300;
extavltree_nodes[18].key = 400;
extavltree_nodes[19].key = 500;
extavltree_nodes[20].key = 600;
 
for (i = 21; i < NODE_COUNT; i++)
extavltree_nodes[i].key = i * 3;
extavltree_nodes[i].next = NULL;
first_free_node = &(extavltree_nodes[0]);
}
 
static extavltree_node_t *alloc_extavltree_node(void)
{
extavltree_node_t *node;
 
node = first_free_node;
first_free_node = first_free_node->next;
 
return node;
}
//****************************************************************
 
static void test_exttree_insert(extavltree_t *tree, unsigned int node_count, int quiet)
{
unsigned int i;
extavltree_node_t *newnode;
 
/*
* Initialize tree before using.
*/
extavltree_create(tree);
if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count);
 
for (i = 0; i < node_count; i++) {
newnode = alloc_extavltree_node();
//if (!quiet) printf("[[[%d]]]\n",newnode->key);
extavltree_insert(tree, newnode);
if (!quiet) {
if (!exttree_test_link(i+1)) {
print_exttree_link(i+1);
printf("\n");
}
exttree_test_parents(tree->root);
exttree_test_height(tree->root,1);
}
}
if (!quiet) printf("Inserting was finished\n");
}
 
/*
static extavltree_node_t *exttree_random_delete_node(extavltree_t *tree, int node_count, int r, bool quiet)
{
extavltree_node_t *delnode;
int i;
 
for (i = 0,delnode = tree->head.next; i < (r-1); i++)
delnode = delnode->next;
if (delnode == &tree->head) {
if (!quiet) printf("Try to delete head! Node count: %d, number of deleted node: %d\n",node_count,r);
return NULL;
}
 
extavltree_delete(tree, delnode);
 
return delnode;
}
*/
 
static void test_exttree_delete(extavltree_t *tree, int node_count, int node_position, bool quiet)
{
extavltree_node_t *delnode;
unsigned int i;
//aktualni pocet tiku:
if (!quiet) printf("Deleting tree...\n");
 
switch(node_position) {
case 0: //mazani vzdy korene
if (!quiet) printf("\n\nDelete root nodes\n");
i = node_count;
while(tree->root != NULL) {
delnode = tree->root;
extavltree_delete(tree,delnode);
if (!quiet) {
if (!exttree_test_link(i)) {
print_exttree_link(i);
printf("\n");
}
exttree_test_parents(tree->root);
exttree_test_height(tree->root,1);
}
i--;
}
break;
case 1:
if (!quiet) printf("\n\nDelete nodes according to their time of origin\n");
for (i = 0; i < node_count; i++) {
extavltree_delete(tree,&(extavltree_nodes[i]));
if (!quiet) {
if (!exttree_test_link(i+1)) {
print_exttree_link(i+1);
printf("\n");
}
exttree_test_parents(tree->root);
exttree_test_height(tree->root,1);
}
}
 
break;
}
if (!quiet) printf("Deletion was finished\n");
}
 
static void timeout_exttree(extavltree_t *tree, int node_count, bool quiet)
{
int i = node_count;
if (!quiet) printf("Timeout tree ...\n");
while(tree->head.next != &(tree->head)) {
extavltree_delete_min(tree);
if (!quiet) {
if (!exttree_test_link(i)) {
print_exttree_link(i);
printf("\n");
}
exttree_test_parents(tree->root);
exttree_test_height(tree->root,1);
}
i--;
}
 
if (!quiet && (i != 0)) printf("Bad node count. Some nodes have been lost!");
 
if (!quiet) printf("Timeout tree finished\n");
}
 
/*
void timeout_exttree_run(extavltree_t *tree, int operation_count, int verbal)
{
int i;
extavltree_node_t *node;
int r;
int count;
//inicializace stromu:
extavltree_create(tree);
for(i = 0, count = 0; i < operation_count; i++) {
if (tree->count && ((rand() % NODE_COUNT) <= tree->count)) {
if ((r = rand()) % DELETE_PROB == 1) { //mazu nahodne
node = exttree_random_delete_node(tree,(r % tree->count));
//printf("DELETE key: %d, number: %d,address: %p\n",node->key,r % (tree->count+1),node);
node->next = first_free_node;
first_free_node = node;
} else {
node = tree->head.next;
extavltree_delete_min(tree);
//printf("TIMEOUT key: %d, address: %p\n",node->key,node);
node->next = first_free_node;
first_free_node = node;
}
} else {
node = alloc_extavltree_node_random();
//printf("INSERT key: %d, address: %p\n",node->key + tree->basetime,node);
extavltree_insert(tree, node);
}
//test_exttree_height(tree->root,1);
//exttree_test_parents(tree->root);
//print_exttree_link(tree->count);
//print_exttree_structure_flat(tree->root,0); putchar('\n'); putchar('\n');
}
}
*/
 
char * test_extavltree1(bool quiet)
{
alloc_extavltree_node_prepare();
test_exttree_insert(&exttree, NODE_COUNT, quiet);
test_exttree_delete(&exttree, NODE_COUNT, 0, quiet);
 
alloc_extavltree_node_prepare();
test_exttree_insert(&exttree, NODE_COUNT, quiet);
test_exttree_delete(&exttree, NODE_COUNT, 1, quiet);
 
alloc_extavltree_node_prepare();
test_exttree_insert(&exttree, NODE_COUNT, quiet);
timeout_exttree(&exttree, NODE_COUNT, quiet);
 
return NULL;
}
/branches/rcu/kernel/test/extavlreltree/extavlreltree1.def
0,0 → 1,6
{
"extavlreltree1",
"Test Extended Avl tree with relative keys operations",
&test_extavlreltree1,
true
},
/branches/rcu/kernel/test/extavlreltree/extavlreltree1.c
0,0 → 1,393
/*
* Copyright (c) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
#include <test.h>
#include <print.h>
#include <adt/extavlreltree.h>
#include <debug.h>
 
#include <panic.h>
 
 
#define NODE_COUNT 100
 
/*
* wrapper structure with a pointer to extended avl tree root
*/
static extavlreltree_t extreltree;
 
/*
* extavltree nodes in array for faster allocating
*/
static extavlreltree_node_t extavlreltree_nodes[NODE_COUNT];
 
/*
* head of free nodes' list:
*/
static extavlreltree_node_t *first_free_node = NULL;
 
 
 
static int extreltree_test_height(extrelavltree_node_t *node,bool timeout);
static extavlreltree_node_t *extreltree_test_parents(extavlireltree_node_t *node);
static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level);
static bool extreltree_test_link(int node_count);
static void print_extreltree_link(int node_count);
static extavlreltree_node_t *alloc_extavlreltree_node(void);
 
 
 
//vraci hloubku stromu
static int extreltree_test_height(extavltree_node_t *node,bool timeout)
{
int h1, h2;
 
if (!node) return -1;
 
h1 = extreltree_test_height(node->lft,timeout) + 1;
if (!timeout && node->lft_height != h1) {
printf("Bad height: %d of LEFT subtree in node: %d with address: %p\n",h1,node->key,node);
}
h2 = extreltree_test_height(node->rgt,0) + 1;
if (node->rgt_height != h2) {
printf("Bad height: %d of RIGHT subtree in node: %d with address: %p\n",h2,node->key,node);
}
if (!timeout && (((h1-h2)>0?h1-h2:h2-h1) > 1)) {
printf("Bad height: error in definition of avltree: %d with address: %p\n",node->key,node);
}
 
return (node->lft_height > node->rgt_height? node->lft_height: node->rgt_height);
}
 
 
/** Tests par atribute of every tree node
*
*/
static extavlreltree_node_t *extreltree_test_parents(extavlreltree_node_t *node)
{
extavltree_node_t *tmp;
if (!node) return NULL;
 
if (node->lft) {
tmp = extreltree_test_parents(node->lft);
if (tmp != node) {
printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->lft);
}
}
if (node->rgt) {
tmp = extreltree_test_parents(node->rgt);
if (tmp != node) {
printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->rgt);
}
}
return node->par;
}
 
/** Checks list of nodes
*
*/
static bool extreltree_test_link(int node_count)
{
extavltree_node_t *node;
int i;
bool test_link = true;
 
for (i = 0,node = exttree.head.next; node != &(exttree.head); i++,node = node->next)
;
if (node_count && i != node_count) {
printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
test_link = false;
}
for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev)
;
if (node_count && i != node_count) {
printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
test_link = false;
}
return test_link;
}
 
static int _sum_extreltree(extavlreltree_node_t *node)
{
int sum = 0;
 
if (node->rgt)
sum += _sum_extreltree(node->rgt);
if (node->lft)
sum += _sum_extreltree(node->lft);
return sum + node->key;
}
 
static int extreltree_test_maxsum(extavlreltree_node_t *node)
{
int rs, ls;
if (!node) return 0;
rs = extreltree_test_maxsum(node->rgt);
ls = extreltree_test_maxsum(node->lft);
 
if (rs != node->rgt_max_key) {
printf("\nBad RGT_SUM: %d, should be: %d node: %d, address: %p\n",node->rgt_max_key,rs,node->key,node);
getchar();
}
return rs + ls + node->key;
}
 
/** Prints the structure of node, which is level levels from the top of the tree.
*
*/
static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level)
{
extavlreltree_node_t *tmp;
int i;
 
if (level > 16)
{
printf ("[...]");
return;
}
 
if (node == NULL)
return;
for (tmp = node->next,i = 0; (tmp->key == 0) && (tmp != &(extreltree.head)); tmp = tmp->next,i++)
;
 
printf ("%d[%d,%d]", node->key,node->rgt_max_key,i);
if (node->lft != NULL || node->rgt != NULL)
{
putchar ('(');
 
print_extreltree_structure_flat (node->lft, level + 1);
if (node->rgt != NULL)
{
putchar (',');
print_extreltree_structure_flat (node->rgt, level + 1);
}
 
putchar (')');
}
}
 
/** Prints list of nodes
*
*/
static void print_extreltree_link(int node_count)
{
extavltree_node_t *node;
printf("\n");
for (node = exttree.head.next; node != &(exttree.head); node = node->next) {
printf(" %d,",node->key);
}
for (node = exttree.head.prev; node != &(exttree.head); node = node->prev) {
printf(" %d,",node->key);
}
}
 
//****************************************************************
static void alloc_extavltree_node_prepare(void)
{
int i;
 
for (i = 0; i < NODE_COUNT - 1; i++) {
extavlreltree_nodes[i].next = &(extavlreltree_nodes[i+1]);
}
/*
* Node keys which will be used for insertion. Up to NODE_COUNT size of array.
*/
 
// First tree node and same key
extavlreltree_nodes[0].key = 60;
extavlreltree_nodes[1].key = 60;
extavlreltree_nodes[2].key = 60;
//LL rotation
extavlreltree_nodes[3].key = 50;
extavlreltree_nodes[4].key = 40;
extavlreltree_nodes[5].key = 30;
//LR rotation
extavlreltree_nodes[6].key = 20;
extavlreltree_nodes[7].key = 20;
extavlreltree_nodes[8].key = 25;
extavlreltree_nodes[9].key = 25;
//LL rotation in lower floor
extavlreltree_nodes[10].key = 35;
//RR rotation
extavlreltree_nodes[11].key = 70;
extavlreltree_nodes[12].key = 80;
//RL rotation
extavlreltree_nodes[13].key = 90;
extavlreltree_nodes[14].key = 85;
extavlreltree_nodes[15].key = 100;
extavlreltree_nodes[16].key = 200;
extavlreltree_nodes[17].key = 300;
extavlreltree_nodes[18].key = 400;
extavlreltree_nodes[19].key = 500;
extavlreltree_nodes[20].key = 600;
 
for (i = 21; i < NODE_COUNT; i++)
extavlreltree_nodes[i].key = i * 3;
extavlreltree_nodes[i].next = NULL;
first_free_node = &(extavlreltree_nodes[0]);
}
 
static extavlreltree_node_t *alloc_extavlreltree_node(void)
{
extavlreltree_node_t *node;
 
node = first_free_node;
first_free_node = first_free_node->next;
 
return node;
}
//****************************************************************
 
static void test_extreltree_insert(extavlreltree_t *tree, unsigned int node_count, int quiet)
{
unsigned int i;
extavlreltree_node_t *newnode;
 
/*
* Initialize tree before using.
*/
extavlreltree_create(tree);
if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count);
 
for (i = 0; i < node_count; i++) {
newnode = alloc_extavlreltree_node();
//if (!quiet) printf("[[[%d]]]\n",newnode->key);
extavlreltree_insert(tree, newnode);
if (!quiet) {
if (!extreltree_test_link(i+1)) {
print_extreltree_link(i+1);
printf("\n");
}
extreltree_test_parents(tree->root);
extreltree_test_height(tree->root,1);
extreltree_test_rgtsum(tree->root);
}
}
if (!quiet) printf("Inserting was finished\n");
}
 
static void test_extreltree_delete(extavlreltree_t *tree, int node_count, int node_position, bool quiet)
{
extavlreltree_node_t *delnode;
unsigned int i;
//aktualni pocet tiku:
if (!quiet) printf("Deleting tree...\n");
 
switch(node_position) {
case 0: //mazani vzdy korene
if (!quiet) printf("\n\nDelete root nodes\n");
i = node_count;
while(tree->root != NULL) {
delnode = tree->root;
extavlreltree_delete(tree,delnode);
if (!quiet) {
if (!extreltree_test_link(i)) {
print_extreltree_link(i);
printf("\n");
}
extreltree_test_parents(tree->root);
extreltree_test_height(tree->root,1);
extreltree_test_rgtsum(tree->root);
}
i--;
}
break;
case 1:
if (!quiet) printf("\n\nDelete nodes according to their time of origin\n");
for (i = 0; i < node_count; i++) {
extavlreltree_delete(tree,&(extavlreltree_nodes[i]));
if (!quiet) {
if (!extreltree_test_link(i+1)) {
print_extreltree_link(i+1);
printf("\n");
}
extreltree_test_parents(tree->root);
extreltree_test_height(tree->root,1);
extreltree_test_rgtsum(tree->root);
}
}
 
break;
}
if (!quiet) printf("Deletion was finished\n");
}
 
static void timeout_extreltree(extavlreltree_t *tree, int node_count, bool quiet)
{
int i = node_count;
if (!quiet) printf("Timeout tree ...\n");
while(tree->head.next != &(tree->head)) {
extavlreltree_delete_min(tree);
if (!quiet) {
if (!extreltree_test_link(i)) {
print_extreltree_link(i);
printf("\n");
}
extreltree_test_parents(tree->root);
extreltree_test_height(tree->root,1);
extreltree_test_rgtsum(tree->root);
}
i--;
}
 
if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!");
 
if (!quiet) printf("Timeout tree finished\n");
}
 
char * test_extavlreltree1(bool quiet)
{
alloc_extavlreltree_node_prepare();
test_extreltree_insert(&extreltree, NODE_COUNT, quiet);
test_extreltree_delete(&extreltree, NODE_COUNT, 0, quiet);
 
alloc_extavlreltree_node_prepare();
test_extreltree_insert(&extreltree, NODE_COUNT, quiet);
test_extreltree_delete(&extreltree, NODE_COUNT, 1, quiet);
 
alloc_extavlreltree_node_prepare();
test_extreltree_insert(&extreltree, NODE_COUNT, quiet);
timeout_extreltree(&extreltree, NODE_COUNT, quiet);
 
return NULL;
}
/branches/rcu/kernel/test/test.c
59,6 → 59,9
#include <sysinfo/sysinfo1.def>
#include <tasklet/tasklet1.def>
#include <synch/rcu1.def>
#include <avltree/avltree1.def>
#include <extavltree/extavltree1.def>
#include <extavlreltree/extavlreltree1.def>
{NULL, NULL, NULL}
};
 
/branches/rcu/kernel/test/avltree/avltree1.def
0,0 → 1,6
{
"avltree1",
"Test Avl tree operations",
&test_avltree1,
true
},
/branches/rcu/kernel/test/avltree/avltree1.c
0,0 → 1,346
/*
* Copyright (c) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
#include <test.h>
#include <print.h>
#include <adt/avl.h>
#include <debug.h>
 
#include <panic.h>
 
 
#define NODE_COUNT 100
 
/*
* wrapper structure with a pointer to avl tree root
*/
static avltree_t avltree;
 
/*
* avl tree nodes in array for faster allocating
*/
static avltree_node_t avltree_nodes[NODE_COUNT];
 
/*
* head of free nodes' list:
*/
static avltree_node_t *first_free_node = NULL;
 
 
 
static int test_tree_balance(avltree_node_t *node);
static avltree_node_t *tree_test_parents(avltree_node_t *node);
static void print_tree_structure_flat (avltree_node_t *node, int level);
static avltree_node_t *alloc_avltree_node(void);
 
 
 
static avltree_node_t *test_tree_parents(avltree_node_t *node)
{
avltree_node_t *tmp;
if (!node) return NULL;
 
if (node->lft) {
tmp = test_tree_parents(node->lft);
if (tmp != node) {
printf("Bad parent pointer key: %d, address: %p\n",tmp->key,node->lft);
}
}
if (node->rgt) {
tmp = test_tree_parents(node->rgt);
if (tmp != node) {
printf("Bad parent pointer key: %d, address: %p\n",tmp->key,node->rgt);
}
}
return node->par;
}
 
int test_tree_balance(avltree_node_t *node)
{
int h1, h2, diff;
 
if (!node) return 0;
h1 = test_tree_balance(node->lft);
h2 = test_tree_balance(node->rgt);
diff = h2 - h1;
if (diff != node->balance || (diff != -1 && diff != 0 && diff != 1)) {
printf("Bad balance\n");
}
return h1 > h2 ? h1 + 1 : h2 + 1;
}
 
/**
* Prints the structure of node, which is level levels from the top of the tree.
*/
static void print_tree_structure_flat (const avltree_node_t *node, int level)
{
/* You can set the maximum level as high as you like.
Most of the time, you'll want to debug code using small trees,
so that a large level indicates a loop, which is a bug. */
if (level > 16)
{
printf ("[...]");
return;
}
 
if (node == NULL)
return;
 
printf ("%d[%d]", node->key,node->balance);
if (node->lft != NULL || node->rgt != NULL)
{
putchar ('(');
 
print_tree_structure_flat (node->lft, level + 1);
if (node->rgt != NULL)
{
putchar (',');
print_tree_structure_flat (node->rgt, level + 1);
}
 
putchar (')');
}
}
 
 
//****************************************************************
static void alloc_avltree_node_prepare(void)
{
int i;
 
for (i = 0; i < NODE_COUNT - 1; i++) {
avltree_nodes[i].n = &(avltree_nodes[i+1]);
}
/*
* Node keys which will be used for insertion. Up to NODE_COUNT size of array.
*/
 
// First tree node and same key
avltree_nodes[0].key = 60;
avltree_nodes[1].key = 60;
avltree_nodes[2].key = 60;
//LL rotation
avltree_nodes[3].key = 50;
avltree_nodes[4].key = 40;
avltree_nodes[5].key = 30;
//LR rotation
avltree_nodes[6].key = 20;
avltree_nodes[7].key = 20;
avltree_nodes[8].key = 25;
avltree_nodes[9].key = 25;
//LL rotation in lower floor
avltree_nodes[10].key = 35;
//RR rotation
avltree_nodes[11].key = 70;
avltree_nodes[12].key = 80;
//RL rotation
avltree_nodes[13].key = 90;
avltree_nodes[14].key = 85;
avltree_nodes[15].key = 100;
avltree_nodes[16].key = 200;
avltree_nodes[17].key = 300;
avltree_nodes[18].key = 400;
avltree_nodes[19].key = 500;
avltree_nodes[20].key = 600;
 
for (i = 21; i < NODE_COUNT; i++)
avltree_nodes[i].key = i * 3;
avltree_nodes[i].n = NULL;
first_free_node = &(avltree_nodes[0]);
}
 
static avltree_node_t *alloc_avltree_node(void)
{
avltree_node_t *node;
 
node = first_free_node;
first_free_node = first_free_node->n;
 
return node;
}
//****************************************************************
 
static void test_tree_insert(avltree_t *tree, unsigned int node_count, int quiet)
{
unsigned int i;
avltree_node_t *newnode;
 
/*
* Initialize tree before using.
*/
avltree_create(tree);
if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count);
 
for (i = 0; i < node_count; i++) {
newnode = alloc_avltree_node();
//if (!quiet) printf("[[[%d]]]\n",newnode->key);
avltree_insert(tree, newnode);
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
if (!quiet) printf("Inserting was finished\n");
}
 
/*
static avltree_node_t *tree_random_delete_node(avltree_t *tree, int node_count, int r, bool quiet)
{
avltree_node_t *delnode;
int i;
 
for (i = 0,delnode = tree->head.n; i < (r-1); i++)
delnode = delnode->n;
if (delnode == &tree->head) {
if (!quiet) printf("Try to delete head! Node count: %d, number of deleted node: %d\n",node_count,r);
return NULL;
}
 
avltree_delete(tree, delnode);
 
return delnode;
}
*/
 
static void test_tree_delete(avltree_t *tree, int node_count, int node_position, bool quiet)
{
avltree_node_t *delnode;
unsigned int i;
//aktualni pocet tiku:
if (!quiet) printf("Deleting tree...\n");
 
switch(node_position) {
case 0: //mazani vzdy korene
if (!quiet) printf("\n\nDelete root nodes\n");
while(tree->root != NULL) {
delnode = tree->root;
avltree_delete(tree,delnode);
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
break;
case 1:
if (!quiet) printf("\n\nDelete nodes according to their time of origin\n");
for (i = 0; i < node_count; i++) {
avltree_delete(tree,&(avltree_nodes[i]));
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
 
break;
}
if (!quiet) printf("Deletion was finished\n");
}
 
static void timeout_tree(avltree_t *tree, int node_count, bool quiet)
{
int i = 0;
if (!quiet) printf("Timeout tree ...\n");
while(tree->head.n != &(tree->head)) {
i++;
avltree_delete_min(tree);
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
 
if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!");
 
if (!quiet) printf("Timeout tree finished\n");
}
 
/*
void timeout_tree_run(avltree_t *tree, int operation_count, int verbal)
{
int i;
avltree_node_t *node;
int r;
int count;
//inicializace stromu:
avltree_create(tree);
for(i = 0, count = 0; i < operation_count; i++) {
if (tree->count && ((rand() % NODE_COUNT) <= tree->count)) {
if ((r = rand()) % DELETE_PROB == 1) { //mazu nahodne
node = tree_random_delete_node(tree,(r % tree->count));
//printf("DELETE key: %d, number: %d,address: %p\n",node->key,r % (tree->count+1),node);
node->n = first_free_node;
first_free_node = node;
} else {
node = tree->head.n;
avltree_delete_min(tree);
//printf("TIMEOUT key: %d, address: %p\n",node->key,node);
node->n = first_free_node;
first_free_node = node;
}
} else {
node = alloc_avltree_node_random();
//printf("INSERT key: %d, address: %p\n",node->key + tree->basetime,node);
avltree_insert(tree, node);
}
//test_tree_height(tree->root,1);
//tree_test_parents(tree->root);
//print_tree_link(tree->count);
//print_tree_structure_flat(tree->root,0); putchar('\n'); putchar('\n');
}
}
*/
 
char * test_avltree1(bool quiet)
{
alloc_avltree_node_prepare();
test_tree_insert(&tree, NODE_COUNT, quiet);
test_tree_delete(&tree, NODE_COUNT, 0, quiet);
 
alloc_avltree_node_prepare();
test_tree_insert(&tree, NODE_COUNT, quiet);
test_tree_delete(&tree, NODE_COUNT, 1, quiet);
 
alloc_avltree_node_prepare();
test_tree_insert(&tree, NODE_COUNT, quiet);
timeout_tree(&tree, NODE_COUNT, quiet);
 
return NULL;
}
/branches/rcu/kernel/test/test.h
71,6 → 71,9
extern char * test_sysinfo1(bool quiet);
extern char * test_tasklet1(bool quiet);
extern char * test_rcu1(bool quiet);
extern char * test_avltree1(bool quiet);
extern char * test_extavltree1(bool quiet);
extern char * test_extavlreltree1(bool quiet);
 
extern test_t tests[];
 
/branches/rcu/kernel/kernel.config
137,5 → 137,6
# Timeout data structure
@ "doubly-linked-list" Doubly linked list
@ "avl-tree" Avl tree
@ "extended-avl-tree" Extended Avl tree
@ "ext-avl-tree" Extended Avl tree
@ "extrel-avl-tree" Extended Avl tree with relative keys
! CONFIG_TIMEOUT_DATA_STRUCTURE (choice)
/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;
}
/branches/rcu/kernel/Makefile
59,10 → 59,14
DEFS += -DCONFIG_TIMEOUT_AVL_TREE
endif
 
ifeq ($(CONFIG_TIMEOUT_DATA_STRUCTURE),extended-avl-tree)
ifeq ($(CONFIG_TIMEOUT_DATA_STRUCTURE),ext-avl-tree)
DEFS += -DCONFIG_TIMEOUT_EXTAVL_TREE
endif
 
ifeq ($(CONFIG_TIMEOUT_DATA_STRUCTURE),extrel-avl-tree)
DEFS += -DCONFIG_TIMEOUT_EXTAVLREL_TREE
endif
 
ifeq ($(CONFIG_DEBUG),y)
DEFS += -DCONFIG_DEBUG
endif
150,7 → 154,9
generic/src/adt/btree.c \
generic/src/adt/hash_table.c \
generic/src/adt/list.c \
generic/src/adt/avl.c \
generic/src/adt/extavl.c \
generic/src/adt/extavlrel.c \
generic/src/console/chardev.c \
generic/src/console/console.c \
generic/src/console/kconsole.c \
248,7 → 254,8
test/print/print1.c \
test/tasklet/tasklet1.c \
test/thread/thread1.c \
test/sysinfo/sysinfo1.c
test/sysinfo/sysinfo1.c \
test/extavltree/extavltree1.c
endif
 
## Experimental features
/branches/rcu/uspace/tester/Makefile
53,6 → 53,7
ipc/answer.c \
ipc/hangup.c
 
 
OBJECTS := $(addsuffix .o,$(basename $(SOURCES)))
 
.PHONY: all clean depend disasm