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/extavlrel.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 extavlreltree_t extreltree;
  43.  
  44. /*
  45.  * extavltree nodes in array for faster allocating
  46.  */
  47. static extavlreltree_node_t extavlreltree_nodes[NODE_COUNT];
  48.  
  49. /*
  50.  * head of free nodes' list:
  51.  */
  52. static extavlreltree_node_t *first_free_node = NULL;
  53.  
  54.  
  55.  
  56. static int extreltree_test_height(extavlreltree_node_t *node,bool timeout);
  57. static extavlreltree_node_t *extreltree_test_parents(extavlreltree_node_t *node);
  58. static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level);
  59. static bool extreltree_test_link(extavlreltree_t *tree, int node_count);
  60. static void print_extreltree_link(extavlreltree_t *tree);
  61. static extavlreltree_node_t *alloc_extavlreltree_node(void);
  62.  
  63.  
  64.  
  65. //vraci hloubku stromu
  66. static int extreltree_test_height(extavlreltree_node_t *node,bool timeout)
  67. {
  68.     int h1, h2;
  69.  
  70.     if (!node) return -1;
  71.  
  72.     h1 = extreltree_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 = extreltree_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 extavlreltree_node_t *extreltree_test_parents(extavlreltree_node_t *node)
  92. {
  93.     extavlreltree_node_t *tmp;
  94.    
  95.     if (!node) return NULL;
  96.  
  97.     if (node->lft) {
  98.         tmp = extreltree_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 = extreltree_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 extreltree_test_link(extavlreltree_t *tree, int node_count)
  116. {
  117.     extavlreltree_node_t *node;
  118.     int i;
  119.     bool test_link = true;
  120.  
  121.     for (i = 0,node = tree->head.next; node != &(tree->head); i++,node = node->next)
  122.         ;
  123.     if (i != node_count) {
  124.         printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
  125.         test_link = false;
  126.     }
  127.     for (i = 0,node = tree->head.prev; node != &(tree->head); i++,node = node->prev)
  128.         ;
  129.     if (i != node_count) {
  130.         printf("\nBad node count!!! Counted: %d, right number: %d", i, node_count);
  131.         test_link = false;
  132.     }
  133.     return test_link;
  134. }
  135.  
  136. static int _sum_extreltree(extavlreltree_node_t *node)
  137. {
  138.     int sum = 0;
  139.  
  140.     if (node->rgt)
  141.         sum += _sum_extreltree(node->rgt);
  142.     if (node->lft)
  143.         sum += _sum_extreltree(node->lft);
  144.    
  145.     return sum + node->key;
  146. }
  147.  
  148. static int extreltree_test_rgtsum(extavlreltree_node_t *node)
  149. {
  150.     int rs, ls;
  151.    
  152.     if (!node) return 0;
  153.    
  154.     rs = extreltree_test_rgtsum(node->rgt);
  155.     ls = extreltree_test_rgtsum(node->lft);
  156.  
  157.     if (rs != node->rgt_sum) {
  158.         printf("\nBad RGT_SUM: %d, should be: %d node: %d, address: %p\n",node->rgt_sum,rs,node->key,node);
  159.     }
  160.     return rs + ls + node->key;
  161. }
  162.  
  163. /** Prints the structure of node, which is level levels from the top of the tree.
  164.  *
  165.  */
  166. static void print_extreltree_structure_flat (extavlreltree_node_t *node, int level)
  167. {
  168.     extavlreltree_node_t *tmp;
  169.     int i;
  170.  
  171.     if (level > 16)
  172.     {
  173.         printf ("[...]");
  174.         return;
  175.     }
  176.  
  177.     if (node == NULL)
  178.         return;
  179.    
  180.     for (tmp = node->next,i = 0; (tmp->key == 0) && (tmp != &(extreltree.head)); tmp = tmp->next,i++)
  181.         ;
  182.  
  183.     printf ("%d[%d,%d]", node->key,node->rgt_sum,i);
  184.     if (node->lft != NULL || node->rgt != NULL)
  185.     {
  186.         printf ("(");
  187.  
  188.         print_extreltree_structure_flat (node->lft, level + 1);
  189.         if (node->rgt != NULL)
  190.         {
  191.             printf(",");
  192.             print_extreltree_structure_flat (node->rgt, level + 1);
  193.         }
  194.  
  195.         printf(")");
  196.     }
  197. }
  198.  
  199. /** Prints list of nodes
  200.  *
  201.  */
  202. static void print_extreltree_link(extavlreltree_t *tree)
  203. {
  204.     extavlreltree_node_t *node;
  205.     printf("\n");
  206.     for (node = tree->head.next; node != &(tree->head); node = node->next) {
  207.         printf(" %d,",node->key);
  208.     }
  209.     for (node = tree->head.prev; node != &(tree->head); node = node->prev) {
  210.         printf(" %d,",node->key);
  211.     }
  212. }
  213.  
  214. //****************************************************************
  215. static void alloc_extavlreltree_node_prepare(void)
  216. {
  217.     int i;
  218.  
  219.     for (i = 0; i < NODE_COUNT - 1; i++) {
  220.         extavlreltree_nodes[i].next = &(extavlreltree_nodes[i+1]);
  221.     }
  222.     /*
  223.      * Node keys which will be used for insertion. Up to NODE_COUNT size of array.
  224.      */
  225.  
  226.     // First tree node and same key
  227.     extavlreltree_nodes[0].key = 60;
  228.     extavlreltree_nodes[1].key = 60;
  229.     extavlreltree_nodes[2].key = 60;
  230.     //LL rotation
  231.     extavlreltree_nodes[3].key = 50;
  232.     extavlreltree_nodes[4].key = 40;
  233.     extavlreltree_nodes[5].key = 30;
  234.     //LR rotation
  235.     extavlreltree_nodes[6].key = 20;
  236.     extavlreltree_nodes[7].key = 20;
  237.     extavlreltree_nodes[8].key = 25;
  238.     extavlreltree_nodes[9].key = 25;
  239.     //LL rotation in lower floor
  240.     extavlreltree_nodes[10].key = 35;
  241.     //RR rotation
  242.     extavlreltree_nodes[11].key = 70;
  243.     extavlreltree_nodes[12].key = 80;
  244.     //RL rotation
  245.     extavlreltree_nodes[13].key = 90;
  246.     extavlreltree_nodes[14].key = 85;
  247.     extavlreltree_nodes[15].key = 100;
  248.     extavlreltree_nodes[16].key = 200;
  249.     extavlreltree_nodes[17].key = 300;
  250.     extavlreltree_nodes[18].key = 400;
  251.     extavlreltree_nodes[19].key = 500;
  252.     extavlreltree_nodes[20].key = 600;
  253.  
  254.     for (i = 21; i < NODE_COUNT; i++)
  255.         extavlreltree_nodes[i].key = i * 3;
  256.    
  257.     extavlreltree_nodes[i].next = NULL;
  258.     first_free_node = &(extavlreltree_nodes[0]);
  259. }
  260.  
  261. static extavlreltree_node_t *alloc_extavlreltree_node(void)
  262. {
  263.     extavlreltree_node_t *node;
  264.  
  265.     node = first_free_node;
  266.     first_free_node = first_free_node->next;
  267.  
  268.     return node;
  269. }
  270. //****************************************************************
  271.  
  272. static void test_extreltree_insert(extavlreltree_t *tree, unsigned int node_count, int quiet)
  273. {
  274.     unsigned int i;
  275.     extavlreltree_node_t *newnode;
  276.  
  277.     /*
  278.      * Initialize tree before using.
  279.      */
  280.     extavlreltree_create(tree);
  281.    
  282.     if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
  283.  
  284.     for (i = 0; i < node_count; i++) {
  285.         newnode = alloc_extavlreltree_node();
  286.         //if (!quiet) printf("[[[%d]]]\n",newnode->key);
  287.        
  288.         extavlreltree_insert(tree, newnode);
  289.         if (!quiet) {
  290.             if (!extreltree_test_link(tree,i+1)) {
  291.                 print_extreltree_link(tree);
  292.                 printf("\n");
  293.             }
  294.             extreltree_test_parents(tree->root);
  295.             extreltree_test_height(tree->root,1);
  296.             extreltree_test_rgtsum(tree->root);
  297.         }
  298.     }
  299.        
  300.     if (!quiet) printf("Inserting was finished\n");
  301. }
  302.  
  303. static void test_extreltree_delete(extavlreltree_t *tree, int node_count, int node_position, bool quiet)
  304. {
  305.     extavlreltree_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.                 extavlreltree_delete(tree,delnode);
  318.                 if (!quiet) {
  319.                     if (!extreltree_test_link(tree,i)) {
  320.                         print_extreltree_link(tree);
  321.                         printf("\n");
  322.                     }
  323.                     extreltree_test_parents(tree->root);
  324.                     extreltree_test_height(tree->root,1);
  325.                     extreltree_test_rgtsum(tree->root);
  326.                 }
  327.                 i--;
  328.             }
  329.            
  330.             break;
  331.         case 1:
  332.             if (!quiet) printf("\nDelete nodes according to their time of origin\n");
  333.             for (i = 0; i < node_count; i++) {
  334.                 extavlreltree_delete(tree,&(extavlreltree_nodes[i]));
  335.                 if (!quiet) {
  336.                     if (!extreltree_test_link(tree,node_count-i-1)) {
  337.                         print_extreltree_link(tree);
  338.                         printf("\n");
  339.                     }
  340.                     extreltree_test_parents(tree->root);
  341.                     extreltree_test_height(tree->root,1);
  342.                     extreltree_test_rgtsum(tree->root);
  343.                 }
  344.             }
  345.  
  346.             break; 
  347.     }
  348.    
  349.     if (!quiet) printf("Deletion was finished\n");
  350. }
  351.  
  352. static void timeout_extreltree(extavlreltree_t *tree, int node_count, bool quiet)
  353. {
  354.     int i = node_count - 1;
  355.    
  356.     if (!quiet) printf("\nTimeout tree ...\n");
  357.    
  358.     while(tree->head.next != &(tree->head)) {
  359.         extavlreltree_delete_min(tree);
  360.         if (!quiet) {
  361.             if (!extreltree_test_link(tree,i)) {
  362.                 print_extreltree_link(tree);
  363.                 printf("\n");
  364.             }
  365.             extreltree_test_parents(tree->root);
  366.             extreltree_test_height(tree->root,1);
  367.             extreltree_test_rgtsum(tree->root);
  368.         }
  369.         i--;
  370.     }
  371.  
  372.     if (!quiet && (i != -1)) printf("Bad node count. Some nodes have been lost!\n");
  373.  
  374.     if (!quiet) printf("Timeout tree finished\n");
  375. }
  376.  
  377. char * test_extavlreltree1(bool quiet)
  378. {
  379.     alloc_extavlreltree_node_prepare();
  380.     test_extreltree_insert(&extreltree, NODE_COUNT, quiet);
  381.     test_extreltree_delete(&extreltree, NODE_COUNT, 0, quiet);
  382.  
  383.     alloc_extavlreltree_node_prepare();
  384.     test_extreltree_insert(&extreltree, NODE_COUNT, quiet);
  385.     test_extreltree_delete(&extreltree, NODE_COUNT, 1, quiet);
  386.  
  387.     alloc_extavlreltree_node_prepare();
  388.     test_extreltree_insert(&extreltree, NODE_COUNT, quiet);
  389.     timeout_extreltree(&extreltree, NODE_COUNT, quiet);
  390.  
  391.     return NULL;
  392. }
  393.