Subversion Repositories HelenOS

Rev

Rev 2421 | Go to most recent revision | 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/avl.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 avl tree root
  41.  */
  42. static avltree_t avltree;
  43.  
  44. /*
  45.  * avl tree nodes in array for faster allocating
  46.  */
  47. static avltree_node_t avltree_nodes[NODE_COUNT];
  48.  
  49. /*
  50.  * head of free nodes' list:
  51.  */
  52. static avltree_node_t *first_free_node = NULL;
  53.  
  54.  
  55.  
  56. static int test_tree_balance(avltree_node_t *node);
  57. static avltree_node_t *tree_test_parents(avltree_node_t *node);
  58. static void print_tree_structure_flat (avltree_node_t *node, int level);
  59. static avltree_node_t *alloc_avltree_node(void);
  60.  
  61.  
  62.  
  63. static avltree_node_t *test_tree_parents(avltree_node_t *node)
  64. {
  65.     avltree_node_t *tmp;
  66.    
  67.     if (!node) return NULL;
  68.  
  69.     if (node->lft) {
  70.         tmp = test_tree_parents(node->lft);
  71.         if (tmp != node) {
  72.             printf("Bad parent pointer key: %d, address: %p\n",tmp->key,node->lft);
  73.         }
  74.     }
  75.     if (node->rgt) {
  76.         tmp = test_tree_parents(node->rgt);
  77.         if (tmp != node) {
  78.             printf("Bad parent pointer key: %d, address: %p\n",tmp->key,node->rgt);
  79.         }
  80.     }
  81.     return node->par;
  82. }
  83.  
  84. int test_tree_balance(avltree_node_t *node)
  85. {
  86.     int h1, h2, diff;
  87.  
  88.     if (!node) return 0;
  89.     h1 = test_tree_balance(node->lft);
  90.     h2 = test_tree_balance(node->rgt);
  91.     diff = h2 - h1;
  92.     if (diff != node->balance || (diff != -1 && diff != 0 && diff != 1)) {
  93.         printf("Bad balance\n");
  94.     }
  95.     return h1 > h2 ? h1 + 1 : h2 + 1;
  96. }
  97.  
  98. /**
  99.  * Prints the structure of node, which is level levels from the top of the tree.
  100.  */
  101. static void print_tree_structure_flat (const avltree_node_t *node, int level)
  102. {
  103.     /* You can set the maximum level as high as you like.
  104.          Most of the time, you'll want to debug code using small trees,
  105.          so that a large level indicates a loop, which is a bug. */
  106.     if (level > 16)
  107.     {
  108.         printf ("[...]");
  109.         return;
  110.     }
  111.  
  112.     if (node == NULL)
  113.         return;
  114.  
  115.     printf ("%d[%d]", node->key,node->balance);
  116.     if (node->lft != NULL || node->rgt != NULL)
  117.     {
  118.         putchar ('(');
  119.  
  120.         print_tree_structure_flat (node->lft, level + 1);
  121.         if (node->rgt != NULL)
  122.         {
  123.             putchar (',');
  124.             print_tree_structure_flat (node->rgt, level + 1);
  125.         }
  126.  
  127.         putchar (')');
  128.     }
  129. }
  130.  
  131.  
  132. //****************************************************************
  133. static void alloc_avltree_node_prepare(void)
  134. {
  135.     int i;
  136.  
  137.     for (i = 0; i < NODE_COUNT - 1; i++) {
  138.         avltree_nodes[i].n = &(avltree_nodes[i+1]);
  139.     }
  140.     /*
  141.      * Node keys which will be used for insertion. Up to NODE_COUNT size of array.
  142.      */
  143.  
  144.     // First tree node and same key
  145.     avltree_nodes[0].key = 60;
  146.     avltree_nodes[1].key = 60;
  147.     avltree_nodes[2].key = 60;
  148.     //LL rotation
  149.     avltree_nodes[3].key = 50;
  150.     avltree_nodes[4].key = 40;
  151.     avltree_nodes[5].key = 30;
  152.     //LR rotation
  153.     avltree_nodes[6].key = 20;
  154.     avltree_nodes[7].key = 20;
  155.     avltree_nodes[8].key = 25;
  156.     avltree_nodes[9].key = 25;
  157.     //LL rotation in lower floor
  158.     avltree_nodes[10].key = 35;
  159.     //RR rotation
  160.     avltree_nodes[11].key = 70;
  161.     avltree_nodes[12].key = 80;
  162.     //RL rotation
  163.     avltree_nodes[13].key = 90;
  164.     avltree_nodes[14].key = 85;
  165.     avltree_nodes[15].key = 100;
  166.     avltree_nodes[16].key = 200;
  167.     avltree_nodes[17].key = 300;
  168.     avltree_nodes[18].key = 400;
  169.     avltree_nodes[19].key = 500;
  170.     avltree_nodes[20].key = 600;
  171.  
  172.     for (i = 21; i < NODE_COUNT; i++)
  173.         avltree_nodes[i].key = i * 3;
  174.    
  175.     avltree_nodes[i].n = NULL;
  176.     first_free_node = &(avltree_nodes[0]);
  177. }
  178.  
  179. static avltree_node_t *alloc_avltree_node(void)
  180. {
  181.     avltree_node_t *node;
  182.  
  183.     node = first_free_node;
  184.     first_free_node = first_free_node->n;
  185.  
  186.     return node;
  187. }
  188. //****************************************************************
  189.  
  190. static void test_tree_insert(avltree_t *tree, unsigned int node_count, int quiet)
  191. {
  192.     unsigned int i;
  193.     avltree_node_t *newnode;
  194.  
  195.     /*
  196.      * Initialize tree before using.
  197.      */
  198.     avltree_create(tree);
  199.    
  200.     if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count);
  201.  
  202.     for (i = 0; i < node_count; i++) {
  203.         newnode = alloc_avltree_node();
  204.         //if (!quiet) printf("[[[%d]]]\n",newnode->key);
  205.        
  206.         avltree_insert(tree, newnode);
  207.         if (!quiet) {
  208.             test_tree_parents(tree->root);
  209.             test_tree_balance(tree->root);
  210.         }
  211.     }
  212.        
  213.     if (!quiet) printf("Inserting was finished\n");
  214. }
  215.  
  216. /*
  217. static avltree_node_t *tree_random_delete_node(avltree_t *tree, int node_count, int r, bool quiet)
  218. {
  219.     avltree_node_t *delnode;
  220.     int i;
  221.  
  222.     for (i = 0,delnode = tree->head.n; i < (r-1); i++)
  223.         delnode = delnode->n;
  224.    
  225.     if (delnode == &tree->head) {
  226.         if (!quiet) printf("Try to delete head! Node count: %d, number of deleted node: %d\n",node_count,r);
  227.         return NULL;
  228.     }
  229.  
  230.     avltree_delete(tree, delnode);
  231.  
  232.     return delnode;
  233. }
  234. */
  235.  
  236. static void test_tree_delete(avltree_t *tree, int node_count, int node_position, bool quiet)
  237. {
  238.     avltree_node_t *delnode;
  239.     unsigned int i;
  240.    
  241.     //aktualni pocet tiku:
  242.     if (!quiet) printf("Deleting tree...\n");
  243.  
  244.     switch(node_position) {
  245.         case 0: //mazani vzdy korene
  246.             if (!quiet) printf("\n\nDelete root nodes\n");
  247.             while(tree->root != NULL) {
  248.                 delnode = tree->root;
  249.                 avltree_delete(tree,delnode);
  250.                 if (!quiet) {
  251.                     test_tree_parents(tree->root);
  252.                     test_tree_balance(tree->root);
  253.                 }
  254.             }
  255.            
  256.             break;
  257.         case 1:
  258.             if (!quiet) printf("\n\nDelete nodes according to their time of origin\n");
  259.             for (i = 0; i < node_count; i++) {
  260.                 avltree_delete(tree,&(avltree_nodes[i]));
  261.                 if (!quiet) {
  262.                     test_tree_parents(tree->root);
  263.                     test_tree_balance(tree->root);
  264.                 }
  265.             }
  266.  
  267.             break; 
  268.     }
  269.    
  270.     if (!quiet) printf("Deletion was finished\n");
  271. }
  272.  
  273. static void timeout_tree(avltree_t *tree, int node_count, bool quiet)
  274. {
  275.     int i = 0;
  276.    
  277.     if (!quiet) printf("Timeout tree ...\n");
  278.    
  279.     while(tree->head.n != &(tree->head)) {
  280.         i++;
  281.         avltree_delete_min(tree);
  282.         if (!quiet) {
  283.             test_tree_parents(tree->root);
  284.             test_tree_balance(tree->root);
  285.         }
  286.     }
  287.  
  288.     if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!");
  289.  
  290.     if (!quiet) printf("Timeout tree finished\n");
  291. }
  292.  
  293. /*
  294. void timeout_tree_run(avltree_t *tree, int operation_count, int verbal)
  295. {
  296.     int i;
  297.     avltree_node_t *node;
  298.     int r;
  299.     int count;
  300.    
  301.     //inicializace stromu:
  302.     avltree_create(tree);
  303.    
  304.     for(i = 0, count = 0; i < operation_count; i++) {
  305.         if (tree->count && ((rand() % NODE_COUNT) <= tree->count)) {
  306.             if ((r = rand()) % DELETE_PROB == 1) { //mazu nahodne
  307.                 node = tree_random_delete_node(tree,(r % tree->count));
  308.                 //printf("DELETE key: %d, number: %d,address: %p\n",node->key,r % (tree->count+1),node);
  309.                 node->n = first_free_node;
  310.                 first_free_node = node;
  311.             } else {
  312.                 node = tree->head.n;
  313.                 avltree_delete_min(tree);
  314.                 //printf("TIMEOUT key: %d, address: %p\n",node->key,node);
  315.                 node->n = first_free_node;
  316.                 first_free_node = node;
  317.             }
  318.             } else {
  319.                     node = alloc_avltree_node_random();
  320.             //printf("INSERT key: %d, address: %p\n",node->key + tree->basetime,node);
  321.             avltree_insert(tree, node);
  322.             }
  323.         //test_tree_height(tree->root,1);
  324.         //tree_test_parents(tree->root);       
  325.         //print_tree_link(tree->count);
  326.         //print_tree_structure_flat(tree->root,0); putchar('\n'); putchar('\n');
  327.     }
  328. }
  329. */
  330.  
  331. char * test_avltree1(bool quiet)
  332. {
  333.     alloc_avltree_node_prepare();
  334.     test_tree_insert(&tree, NODE_COUNT, quiet);
  335.     test_tree_delete(&tree, NODE_COUNT, 0, quiet);
  336.  
  337.     alloc_avltree_node_prepare();
  338.     test_tree_insert(&tree, NODE_COUNT, quiet);
  339.     test_tree_delete(&tree, NODE_COUNT, 1, quiet);
  340.  
  341.     alloc_avltree_node_prepare();
  342.     test_tree_insert(&tree, NODE_COUNT, quiet);
  343.     timeout_tree(&tree, NODE_COUNT, quiet);
  344.  
  345.     return NULL;
  346. }
  347.