0,0 → 1,289 |
/* |
* 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/favl.h> |
#include <debug.h> |
|
|
#define NODE_COUNT 100 |
|
/* |
* wrapper structure with a pointer to favl tree root |
*/ |
static favltree_t favltree; |
|
/* |
* favl tree nodes in array for faster allocating |
*/ |
static favltree_node_t favltree_nodes[NODE_COUNT]; |
|
/* |
* head of free nodes' list: |
*/ |
static favltree_node_t *first_free_node = NULL; |
|
|
|
static int test_tree_balance(favltree_node_t *node); |
static favltree_node_t *test_tree_parents(favltree_node_t *node); |
static void print_tree_structure_flat (favltree_node_t *node, int level); |
static favltree_node_t *alloc_favltree_node(void); |
|
|
|
static favltree_node_t *test_tree_parents(favltree_node_t *node) |
{ |
favltree_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(favltree_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 (favltree_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) |
{ |
printf("("); |
|
print_tree_structure_flat (node->lft, level + 1); |
if (node->rgt != NULL) |
{ |
printf(","); |
print_tree_structure_flat (node->rgt, level + 1); |
} |
|
printf(")"); |
} |
} |
|
|
//**************************************************************** |
static void alloc_favltree_node_prepare(void) |
{ |
int i; |
|
for (i = 0; i < NODE_COUNT - 1; i++) { |
favltree_nodes[i].par = &(favltree_nodes[i+1]); |
} |
/* |
* Node keys which will be used for insertion. Up to NODE_COUNT size of array. |
*/ |
|
// First tree node and same key |
favltree_nodes[0].key = 60; |
favltree_nodes[1].key = 60; |
favltree_nodes[2].key = 60; |
//LL rotation |
favltree_nodes[3].key = 50; |
favltree_nodes[4].key = 40; |
favltree_nodes[5].key = 30; |
//LR rotation |
favltree_nodes[6].key = 20; |
favltree_nodes[7].key = 20; |
favltree_nodes[8].key = 25; |
favltree_nodes[9].key = 25; |
//LL rotation in lower floor |
favltree_nodes[10].key = 35; |
//RR rotation |
favltree_nodes[11].key = 70; |
favltree_nodes[12].key = 80; |
//RL rotation |
favltree_nodes[13].key = 90; |
favltree_nodes[14].key = 85; |
//Insert 0 key |
favltree_nodes[15].key = 0; |
favltree_nodes[16].key = 0; |
//Insert reverse |
favltree_nodes[17].key = 600; |
favltree_nodes[18].key = 500; |
favltree_nodes[19].key = 400; |
favltree_nodes[20].key = 300; |
|
for (i = 21; i < NODE_COUNT; i++) |
favltree_nodes[i].key = i * 3; |
|
favltree_nodes[i].par = NULL; |
first_free_node = &(favltree_nodes[0]); |
} |
|
static favltree_node_t *alloc_favltree_node(void) |
{ |
favltree_node_t *node; |
|
node = first_free_node; |
first_free_node = first_free_node->par; |
|
return node; |
} |
//**************************************************************** |
|
static void test_tree_insert(favltree_t *tree, unsigned int node_count, int quiet) |
{ |
unsigned int i; |
favltree_node_t *newnode; |
|
/* |
* Initialize tree before using. |
*/ |
favltree_create(tree); |
|
if (!quiet) printf("\nInserting %d nodes ...\n", node_count); |
|
for (i = 0; i < node_count; i++) { |
newnode = alloc_favltree_node(); |
//if (!quiet) printf("[[[%d]]]\n",newnode->key); |
|
favltree_insert(tree, newnode); |
if (!quiet) { |
test_tree_parents(tree->root); |
test_tree_balance(tree->root); |
} |
} |
|
if (!quiet) printf("Inserting was finished\n"); |
} |
|
|
static void test_tree_delete(favltree_t *tree, int node_count, int node_position, bool quiet) |
{ |
favltree_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("\nDelete root nodes\n"); |
while(tree->root != NULL) { |
delnode = tree->root; |
favltree_delete(tree,delnode); |
if (!quiet) { |
test_tree_parents(tree->root); |
test_tree_balance(tree->root); |
} |
} |
|
break; |
case 1: |
if (!quiet) printf("\nDelete nodes according to their time of origin\n"); |
for (i = 0; i < node_count; i++) { |
favltree_delete(tree,&(favltree_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(favltree_t *tree, int node_count, bool quiet) |
{ |
int i = 0; |
|
if (!quiet) printf("\nTimeout tree ...\n"); |
|
while(tree->root != NULL) { |
i++; |
favltree_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!\n"); |
|
if (!quiet) printf("Timeout tree finished\n"); |
} |
|
char * test_favltree1(bool quiet) |
{ |
alloc_favltree_node_prepare(); |
test_tree_insert(&favltree, NODE_COUNT, quiet); |
test_tree_delete(&favltree, NODE_COUNT, 0, quiet); |
|
alloc_favltree_node_prepare(); |
test_tree_insert(&favltree, NODE_COUNT, quiet); |
test_tree_delete(&favltree, NODE_COUNT, 1, quiet); |
|
alloc_favltree_node_prepare(); |
test_tree_insert(&favltree, NODE_COUNT, quiet); |
timeout_tree(&favltree, NODE_COUNT, quiet); |
|
return NULL; |
} |