/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[]; |