/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 |
76,8 → 80,12 |
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,13 → 135,20 |
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); |
140,7 → 158,7 |
/** Unregister timeout |
* |
* Remove timeout from timeout list. |
* Remove timeout from timeout ExtAVL tree structure. |
* |
* @param t Timeout to unregister. |
* |
163,13 → 181,21 |
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); |
/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,11 → 139,13 |
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, |
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 |