| 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; |
| } |