Subversion Repositories HelenOS

Rev

Rev 2416 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * Copyright (c) 2007 Vojtech Mencl
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  *
  9.  * - Redistributions of source code must retain the above copyright
  10.  *   notice, this list of conditions and the following disclaimer.
  11.  * - Redistributions in binary form must reproduce the above copyright
  12.  *   notice, this list of conditions and the following disclaimer in the
  13.  *   documentation and/or other materials provided with the distribution.
  14.  * - The name of the author may not be used to endorse or promote products
  15.  *   derived from this software without specific prior written permission.
  16.  *
  17.  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18.  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20.  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23.  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24.  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25.  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26.  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27.  */
  28.  
  29. #include <test.h>
  30. #include <print.h>
  31. #include <adt/extavl.h>
  32. #include <debug.h>
  33.  
  34. #include <panic.h>
  35.  
  36.  
  37. #define NODE_COUNT 100
  38.  
  39. /*
  40.  * wrapper structure with a pointer to extended avl tree root
  41.  */
  42. static extavltree_t exttree;
  43.  
  44. /*
  45.  * extavltree nodes in array for faster allocating
  46.  */
  47. static extavltree_node_t extavltree_nodes[NODE_COUNT];
  48.  
  49. /*
  50.  * head of free nodes' list:
  51.  */
  52. static extavltree_node_t *first_free_node = NULL;
  53.  
  54.  
  55.  
  56. static int exttree_test_height(extavltree_node_t *node,bool timeout);
  57. static extavltree_node_t *exttree_test_parents(extavltree_node_t *node);
  58. static void print_exttree_structure_flat (extavltree_node_t *node, int level);
  59. static bool exttree_test_link(int node_count);
  60. static void print_exttree_link(void);
  61. static extavltree_node_t *alloc_extavltree_node(void);
  62.  
  63.  
  64.  
  65. //vraci hloubku stromu
  66. static int exttree_test_height(extavltree_node_t *node,bool timeout)
  67. {
  68.     int h1, h2;
  69.  
  70.     if (!node) return -1;
  71.  
  72.     h1 = exttree_test_height(node->lft,timeout) + 1;
  73.     if (!timeout && node->lft_height != h1) {
  74.         printf("Bad height: %d of LEFT subtree in node: %d with address: %p\n",h1,node->key,node);
  75.     }
  76.     h2 = exttree_test_height(node->rgt,0) + 1;
  77.     if (node->rgt_height != h2) {
  78.         printf("Bad height: %d of RIGHT subtree in node: %d with address: %p\n",h2,node->key,node);
  79.     }
  80.     if (!timeout && (((h1-h2)>0?h1-h2:h2-h1) > 1)) {
  81.         printf("Bad height: error in definition of avltree: %d with address: %p\n",node->key,node);
  82.     }
  83.  
  84.     return (node->lft_height > node->rgt_height? node->lft_height: node->rgt_height);
  85. }
  86.  
  87.  
  88. /** Tests par atribute of every tree node
  89.  *
  90.  */
  91. static extavltree_node_t *exttree_test_parents(extavltree_node_t *node)
  92. {
  93.     extavltree_node_t *tmp;
  94.    
  95.     if (!node) return NULL;
  96.  
  97.     if (node->lft) {
  98.         tmp = exttree_test_parents(node->lft);
  99.         if (tmp != node) {
  100.             printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->lft);
  101.         }
  102.     }
  103.     if (node->rgt) {
  104.         tmp = exttree_test_parents(node->rgt);
  105.         if (tmp != node) {
  106.             printf("Bad parent pointer at node with key: %d, address: %p\n",tmp->key,node->rgt);
  107.         }
  108.     }
  109.     return node->par;
  110. }
  111.  
  112. /** Checks list of nodes
  113.  *
  114.  */
  115. static bool exttree_test_link(int node_count)
  116. {
  117.     extavltree_node_t *node;
  118.     int i;
  119.     bool test_link = true;
  120.  
  121.     for (i = 0,node = exttree.head.next; node != &(exttree.head); i++,node = node->next) {
  122.         if ((node->next != &(exttree.head)) && (node->key > node->next->key)) {
  123.             printf("\nList is not sorted (forward direction) at key: %d\n",node->key);
  124.             test_link = false;
  125.         }
  126.     }
  127.     if (i != node_count) {
  128.         printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
  129.         test_link = false;
  130.     }
  131.     for (i = 0,node = exttree.head.prev; node != &(exttree.head); i++,node = node->prev) {
  132.         if ((node->prev != &(exttree.head)) && (node->key < node->prev->key)) {
  133.             printf("\nList is not sorted (backward direction) at key: %d\n",node->key);
  134.             test_link = false;
  135.         }
  136.     }
  137.     if (i != node_count) {
  138.         printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
  139.         test_link = false;
  140.     }
  141.     return test_link;
  142. }
  143.  
  144. /** Prints the structure of node, which is level levels from the top of the tree.
  145.  *
  146.  */
  147. static void print_exttree_structure_flat (extavltree_node_t *node, int level)
  148. {
  149.     extavltree_node_t *tmp;
  150.     int i;
  151.  
  152.     if (level > 16)
  153.     {
  154.         printf ("[...]");
  155.         return;
  156.     }
  157.  
  158.     if (node == NULL)
  159.         return;
  160.    
  161.     for (tmp = node,i = 0; tmp->key == node->key; tmp = tmp->next,i++)
  162.         ;
  163.  
  164.     printf ("%d[%d,%d,(%d)]", node->key,node->lft_height,node->rgt_height,i);
  165.     if (node->lft != NULL || node->rgt != NULL)
  166.     {
  167.         printf("(");
  168.  
  169.         print_exttree_structure_flat (node->lft, level + 1);
  170.         if (node->rgt != NULL)
  171.         {
  172.             printf(",");
  173.             print_exttree_structure_flat (node->rgt, level + 1);
  174.         }
  175.  
  176.         printf(")");
  177.     }
  178. }
  179.  
  180. /** Prints list of nodes
  181.  *
  182.  */
  183. static void print_exttree_link(void)
  184. {
  185.     extavltree_node_t *node;
  186.     printf("\n");
  187.     for (node = exttree.head.next; node != &(exttree.head); node = node->next) {
  188.         printf(" %d,",node->key);
  189.     }
  190.     for (node = exttree.head.prev; node != &(exttree.head); node = node->prev) {
  191.         printf(" %d,",node->key);
  192.     }
  193. }
  194.  
  195. //****************************************************************
  196. static void alloc_extavltree_node_prepare(void)
  197. {
  198.     int i;
  199.  
  200.     for (i = 0; i < NODE_COUNT - 1; i++) {
  201.         extavltree_nodes[i].next = &(extavltree_nodes[i+1]);
  202.     }
  203.     /*
  204.      * Node keys which will be used for insertion. Up to NODE_COUNT size of array.
  205.      */
  206.  
  207.     // First tree node and same key
  208.     extavltree_nodes[0].key = 60;
  209.     extavltree_nodes[1].key = 60;
  210.     extavltree_nodes[2].key = 60;
  211.     //LL rotation
  212.     extavltree_nodes[3].key = 50;
  213.     extavltree_nodes[4].key = 40;
  214.     extavltree_nodes[5].key = 30;
  215.     //LR rotation
  216.     extavltree_nodes[6].key = 20;
  217.     extavltree_nodes[7].key = 20;
  218.     extavltree_nodes[8].key = 25;
  219.     extavltree_nodes[9].key = 25;
  220.     //LL rotation in lower floor
  221.     extavltree_nodes[10].key = 35;
  222.     //RR rotation
  223.     extavltree_nodes[11].key = 70;
  224.     extavltree_nodes[12].key = 80;
  225.     //RL rotation
  226.     extavltree_nodes[13].key = 90;
  227.     extavltree_nodes[14].key = 85;
  228.     extavltree_nodes[15].key = 100;
  229.     extavltree_nodes[16].key = 200;
  230.     extavltree_nodes[17].key = 300;
  231.     extavltree_nodes[18].key = 400;
  232.     extavltree_nodes[19].key = 500;
  233.     extavltree_nodes[20].key = 600;
  234.  
  235.     for (i = 21; i < NODE_COUNT; i++)
  236.         extavltree_nodes[i].key = i * 3;
  237.    
  238.     extavltree_nodes[i].next = NULL;
  239.     first_free_node = &(extavltree_nodes[0]);
  240. }
  241.  
  242. static extavltree_node_t *alloc_extavltree_node(void)
  243. {
  244.     extavltree_node_t *node;
  245.  
  246.     node = first_free_node;
  247.     first_free_node = first_free_node->next;
  248.  
  249.     return node;
  250. }
  251. //****************************************************************
  252.  
  253. static void test_exttree_insert(extavltree_t *tree, unsigned int node_count, int quiet)
  254. {
  255.     unsigned int i;
  256.     extavltree_node_t *newnode;
  257.  
  258.     /*
  259.      * Initialize tree before using.
  260.      */
  261.     extavltree_create(tree);
  262.    
  263.     if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
  264.  
  265.     for (i = 0; i < node_count; i++) {
  266.         newnode = alloc_extavltree_node();
  267.         //if (!quiet) printf("[[[%d]]]\n",newnode->key);
  268.        
  269.         extavltree_insert(tree, newnode);
  270.         if (!quiet) {
  271.             if (!exttree_test_link(i+1)) {
  272.                 print_exttree_link();
  273.                 printf("\n");
  274.             }
  275.             exttree_test_parents(tree->root);
  276.             exttree_test_height(tree->root,1);
  277.         }
  278.     }
  279.        
  280.     if (!quiet) printf("Inserting was finished\n");
  281. }
  282.  
  283. /*
  284. static extavltree_node_t *exttree_random_delete_node(extavltree_t *tree, int node_count, int r, bool quiet)
  285. {
  286.     extavltree_node_t *delnode;
  287.     int i;
  288.  
  289.     for (i = 0,delnode = tree->head.next; i < (r-1); i++)
  290.         delnode = delnode->next;
  291.    
  292.     if (delnode == &tree->head) {
  293.         if (!quiet) printf("Try to delete head! Node count: %d, number of deleted node: %d\n",node_count,r);
  294.         return NULL;
  295.     }
  296.  
  297.     extavltree_delete(tree, delnode);
  298.  
  299.     return delnode;
  300. }
  301. */
  302.  
  303. static void test_exttree_delete(extavltree_t *tree, int node_count, int node_position, bool quiet)
  304. {
  305.     extavltree_node_t *delnode;
  306.     unsigned int i;
  307.    
  308.     //aktualni pocet tiku:
  309.     if (!quiet) printf("Deleting tree...\n");
  310.  
  311.     switch(node_position) {
  312.         case 0: //mazani vzdy korene
  313.             if (!quiet) printf("\nDelete root nodes\n");
  314.             i = node_count - 1;
  315.             while(tree->root != NULL) {
  316.                 delnode = tree->root;
  317.                 extavltree_delete(tree,delnode);
  318.                 if (!quiet) {
  319.                     if (!exttree_test_link(i)) {
  320.                         print_exttree_link();
  321.                         printf("\n");
  322.                     }
  323.                     exttree_test_parents(tree->root);
  324.                     exttree_test_height(tree->root,1);
  325.                 }
  326.                 i--;
  327.             }
  328.            
  329.             break;
  330.         case 1:
  331.             if (!quiet) printf("\nDelete nodes according to their time of origin\n");
  332.             for (i = 0; i < node_count; i++) {
  333.                 extavltree_delete(tree,&(extavltree_nodes[i]));
  334.                 if (!quiet) {
  335.                     if (!exttree_test_link(node_count-i-1)) {
  336.                         print_exttree_link();
  337.                         printf("\n");
  338.                     }
  339.                     exttree_test_parents(tree->root);
  340.                     exttree_test_height(tree->root,1);
  341.                 }
  342.             }
  343.  
  344.             break; 
  345.     }
  346.    
  347.     if (!quiet) printf("Deletion was finished\n");
  348. }
  349.  
  350. static void timeout_exttree(extavltree_t *tree, int node_count, bool quiet)
  351. {
  352.     int i = node_count - 1;
  353.    
  354.     if (!quiet) printf("\nTimeout tree ...\n");
  355.    
  356.     while(tree->head.next != &(tree->head)) {
  357.         extavltree_delete_min(tree);
  358.         if (!quiet) {
  359.             if (!exttree_test_link(i)) {
  360.                 print_exttree_link();
  361.                 printf("\n");
  362.             }
  363.             exttree_test_parents(tree->root);
  364.             exttree_test_height(tree->root,1);
  365.         }
  366.         i--;
  367.     }
  368.  
  369.     if (!quiet && (i != -1)) printf("Bad node count. Some nodes have been lost!\n");
  370.  
  371.     if (!quiet) printf("Timeout tree finished\n");
  372. }
  373.  
  374. /*
  375. void timeout_exttree_run(extavltree_t *tree, int operation_count, int verbal)
  376. {
  377.     int i;
  378.     extavltree_node_t *node;
  379.     int r;
  380.     int count;
  381.    
  382.     //inicializace stromu:
  383.     extavltree_create(tree);
  384.    
  385.     for(i = 0, count = 0; i < operation_count; i++) {
  386.         if (tree->count && ((rand() % NODE_COUNT) <= tree->count)) {
  387.             if ((r = rand()) % DELETE_PROB == 1) { //mazu nahodne
  388.                 node = exttree_random_delete_node(tree,(r % tree->count));
  389.                 //printf("DELETE key: %d, number: %d,address: %p\n",node->key,r % (tree->count+1),node);
  390.                 node->next = first_free_node;
  391.                 first_free_node = node;
  392.             } else {
  393.                 node = tree->head.next;
  394.                 extavltree_delete_min(tree);
  395.                 //printf("TIMEOUT key: %d, address: %p\n",node->key,node);
  396.                 node->next = first_free_node;
  397.                 first_free_node = node;
  398.             }
  399.             } else {
  400.                     node = alloc_extavltree_node_random();
  401.             //printf("INSERT key: %d, address: %p\n",node->key + tree->basetime,node);
  402.             extavltree_insert(tree, node);
  403.             }
  404.         //test_exttree_height(tree->root,1);
  405.         //exttree_test_parents(tree->root);    
  406.         //print_exttree_link(tree->count);
  407.         //print_exttree_structure_flat(tree->root,0); putchar('\n'); putchar('\n');
  408.     }
  409. }
  410. */
  411.  
  412. char * test_extavltree1(bool quiet)
  413. {
  414.     alloc_extavltree_node_prepare();
  415.     test_exttree_insert(&exttree, NODE_COUNT, quiet);
  416.     test_exttree_delete(&exttree, NODE_COUNT, 0, quiet);
  417.  
  418.     alloc_extavltree_node_prepare();
  419.     test_exttree_insert(&exttree, NODE_COUNT, quiet);
  420.     test_exttree_delete(&exttree, NODE_COUNT, 1, quiet);
  421.  
  422.     alloc_extavltree_node_prepare();
  423.     test_exttree_insert(&exttree, NODE_COUNT, quiet);
  424.     timeout_exttree(&exttree, NODE_COUNT, quiet);
  425.  
  426.     return NULL;
  427. }
  428.