Subversion Repositories HelenOS

Rev

Rev 3165 | Rev 4263 | 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. #include <arch/types.h>
  34.  
  35. #define NODE_COUNT 100
  36.  
  37. static avltree_t avltree;
  38.  
  39. /*
  40.  * avl tree nodes in array for faster allocation
  41.  */
  42. static avltree_node_t avltree_nodes[NODE_COUNT];
  43.  
  44. /*
  45.  * head of free nodes' list:
  46.  */
  47. static avltree_node_t *first_free_node = NULL;
  48.  
  49. static int test_tree_balance(avltree_node_t *node);
  50. static avltree_node_t *test_tree_parents(avltree_node_t *node);
  51. static void print_tree_structure_flat (avltree_node_t *node, int level)
  52.     __attribute__ ((used));
  53. static avltree_node_t *alloc_avltree_node(void);
  54.  
  55. static avltree_node_t *test_tree_parents(avltree_node_t *node)
  56. {
  57.     avltree_node_t *tmp;
  58.    
  59.     if (!node)
  60.         return NULL;
  61.  
  62.     if (node->lft) {
  63.         tmp = test_tree_parents(node->lft);
  64.         if (tmp != node) {
  65.             printf("Bad parent pointer key: %" PRIu64
  66.                 ", address: %p\n", tmp->key, node->lft);
  67.         }
  68.     }
  69.     if (node->rgt) {
  70.         tmp = test_tree_parents(node->rgt);
  71.         if (tmp != node) {
  72.             printf("Bad parent pointer key: %" PRIu64
  73.                 ", address: %p\n",
  74.                 tmp->key,node->rgt);
  75.         }
  76.     }
  77.     return node->par;
  78. }
  79.  
  80. int test_tree_balance(avltree_node_t *node)
  81. {
  82.     int h1, h2, diff;
  83.  
  84.     if (!node)
  85.         return 0;
  86.     h1 = test_tree_balance(node->lft);
  87.     h2 = test_tree_balance(node->rgt);
  88.     diff = h2 - h1;
  89.     if (diff != node->balance || (diff != -1 && diff != 0 && diff != 1)) {
  90.         printf("Bad balance\n");
  91.     }
  92.     return h1 > h2 ? h1 + 1 : h2 + 1;
  93. }
  94.  
  95. /**
  96.  * Prints the structure of the node, which is level levels from the top of the
  97.  * tree.
  98.  */
  99. static void
  100. print_tree_structure_flat(avltree_node_t *node, int level)
  101. {
  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.      */
  107.     if (level > 16) {
  108.         printf("[...]");
  109.         return;
  110.     }
  111.  
  112.     if (node == NULL)
  113.         return;
  114.  
  115.     printf("%" PRIu64 "[%" PRIu8 "]", node->key, node->balance);
  116.     if (node->lft != NULL || node->rgt != NULL) {
  117.         printf("(");
  118.  
  119.         print_tree_structure_flat(node->lft, level + 1);
  120.         if (node->rgt != NULL) {
  121.             printf(",");
  122.             print_tree_structure_flat(node->rgt, level + 1);
  123.         }
  124.  
  125.         printf(")");
  126.     }
  127. }
  128.  
  129. static void alloc_avltree_node_prepare(void)
  130. {
  131.     int i;
  132.  
  133.     for (i = 0; i < NODE_COUNT - 1; i++) {
  134.         avltree_nodes[i].par = &avltree_nodes[i + 1];
  135.     }
  136.     avltree_nodes[i].par = NULL;
  137.    
  138.     /*
  139.      * Node keys which will be used for insertion. Up to NODE_COUNT size of
  140.      * array.
  141.      */
  142.  
  143.     /* First tree node and same key */
  144.     avltree_nodes[0].key = 60;
  145.     avltree_nodes[1].key = 60;
  146.     avltree_nodes[2].key = 60;
  147.     /* LL rotation */
  148.     avltree_nodes[3].key = 50;
  149.     avltree_nodes[4].key = 40;
  150.     avltree_nodes[5].key = 30;
  151.     /* LR rotation */
  152.     avltree_nodes[6].key = 20;
  153.     avltree_nodes[7].key = 20;
  154.     avltree_nodes[8].key = 25;
  155.     avltree_nodes[9].key = 25;
  156.     /* LL rotation in lower floor */
  157.     avltree_nodes[10].key = 35;
  158.     /* RR rotation */
  159.     avltree_nodes[11].key = 70;
  160.     avltree_nodes[12].key = 80;
  161.     /* RL rotation */
  162.     avltree_nodes[13].key = 90;
  163.     avltree_nodes[14].key = 85;
  164.     /* Insert 0 key */
  165.     avltree_nodes[15].key = 0;
  166.     avltree_nodes[16].key = 0;
  167.     /* Insert reverse */
  168.     avltree_nodes[17].key = 600;
  169.     avltree_nodes[18].key = 500;
  170.     avltree_nodes[19].key = 400;
  171.     avltree_nodes[20].key = 300;
  172.  
  173.     for (i = 21; i < NODE_COUNT; i++)
  174.         avltree_nodes[i].key = i * 3;
  175.    
  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->par;
  185.  
  186.     return node;
  187. }
  188.  
  189. static void test_tree_insert(avltree_t *tree, count_t node_count, bool quiet)
  190. {
  191.     unsigned int i;
  192.     avltree_node_t *newnode;
  193.  
  194.     avltree_create(tree);
  195.    
  196.     if (!quiet)
  197.         printf("Inserting %" PRIc " nodes...", node_count);
  198.  
  199.     for (i = 0; i < node_count; i++) {
  200.         newnode = alloc_avltree_node();
  201.        
  202.         avltree_insert(tree, newnode);
  203.         if (!quiet) {
  204.             test_tree_parents(tree->root);
  205.             test_tree_balance(tree->root);
  206.         }
  207.     }
  208.        
  209.     if (!quiet)
  210.         printf("done.\n");
  211. }
  212.  
  213.  
  214. static void test_tree_delete(avltree_t *tree, count_t node_count,
  215.     int node_position, bool quiet)
  216. {
  217.     avltree_node_t *delnode;
  218.     unsigned int i;
  219.    
  220.     switch (node_position) {
  221.     case 0:
  222.         if (!quiet)
  223.             printf("Deleting root nodes...");
  224.         while (tree->root != NULL) {
  225.             delnode = tree->root;
  226.             avltree_delete(tree, delnode);
  227.             if (!quiet) {
  228.                 test_tree_parents(tree->root);
  229.                 test_tree_balance(tree->root);
  230.             }
  231.         }
  232.         break;
  233.     case 1:
  234.         if (!quiet)
  235.             printf("Deleting nodes according to creation time...");
  236.         for (i = 0; i < node_count; i++) {
  237.             avltree_delete(tree, &avltree_nodes[i]);
  238.             if (!quiet) {
  239.                 test_tree_parents(tree->root);
  240.                 test_tree_balance(tree->root);
  241.             }
  242.         }
  243.         break; 
  244.     }
  245.    
  246.     if (!quiet)
  247.         printf("done.\n");
  248. }
  249.  
  250. static void test_tree_delmin(avltree_t *tree, count_t node_count, bool quiet)
  251. {
  252.     unsigned int i = 0;
  253.    
  254.     if (!quiet)
  255.         printf("Deleting minimum nodes...");
  256.    
  257.     while (tree->root != NULL) {
  258.         i++;
  259.         avltree_delete_min(tree);
  260.         if (!quiet) {
  261.             test_tree_parents(tree->root);
  262.             test_tree_balance(tree->root);
  263.         }
  264.     }
  265.  
  266.     if (!quiet && (i != node_count))
  267.         printf("Bad node count. Some nodes have been lost!\n");
  268.  
  269.     if (!quiet)
  270.         printf("done.\n");
  271. }
  272.  
  273. char *test_avltree1(bool quiet)
  274. {
  275.     alloc_avltree_node_prepare();
  276.     test_tree_insert(&avltree, NODE_COUNT, quiet);
  277.     test_tree_delete(&avltree, NODE_COUNT, 0, quiet);
  278.  
  279.     alloc_avltree_node_prepare();
  280.     test_tree_insert(&avltree, NODE_COUNT, quiet);
  281.     test_tree_delete(&avltree, NODE_COUNT, 1, quiet);
  282.  
  283.     alloc_avltree_node_prepare();
  284.     test_tree_insert(&avltree, NODE_COUNT, quiet);
  285.     test_tree_delmin(&avltree, NODE_COUNT, quiet);
  286.  
  287.     return NULL;
  288. }
  289.  
  290.