WebSVN – HelenOS – Diff – /branches/rcu/kernel/test/avltree/avltree1.c

 static avltree_node_t *first_free_node = NULL;
 static int test_tree_balance(avltree_node_t *node);
-static avltree_node_t *tree_test_parents(avltree_node_t *node);
+static avltree_node_t *test_tree_parents(avltree_node_t *node);
 static void print_tree_structure_flat (avltree_node_t *node, int level);
 static avltree_node_t *alloc_avltree_node(void);
+}
 /**
  * Prints the structure of node, which is level levels from the top of the tree.
  */
-static void print_tree_structure_flat (const avltree_node_t *node, int level)
+static void print_tree_structure_flat (avltree_node_t *node, int level)
+{
     /* You can set the maximum level as high as you like.
          Most of the time, you'll want to debug code using small trees,
          so that a large level indicates a loop, which is a bug. */
     if (level > 16)
         return;
     printf ("%d[%d]", node->key,node->balance);
     if (node->lft != NULL || node->rgt != NULL)
+    {
-        putchar ('(');
+        printf("(");
         print_tree_structure_flat (node->lft, level + 1);
         if (node->rgt != NULL)
+        {
-            putchar (',');
+            printf(",");
             print_tree_structure_flat (node->rgt, level + 1);
+        }
-        putchar (')');
+        printf(")");
+    }
+}
 //****************************************************************
 static void alloc_avltree_node_prepare(void)
+{
     int i;
     for (i = 0; i < NODE_COUNT - 1; i++) {
-        avltree_nodes[i].n = &(avltree_nodes[i+1]);
+        avltree_nodes[i].par = &(avltree_nodes[i+1]);
+    }
     /*
      * Node keys which will be used for insertion. Up to NODE_COUNT size of array.
      */
     avltree_nodes[20].key = 600;
     for (i = 21; i < NODE_COUNT; i++)
         avltree_nodes[i].key = i * 3;
-    avltree_nodes[i].n = NULL;
+    avltree_nodes[i].par = NULL;
     first_free_node = &(avltree_nodes[0]);
+}
 static avltree_node_t *alloc_avltree_node(void)
+{
     avltree_node_t *node;
     node = first_free_node;
-    first_free_node = first_free_node->n;
+    first_free_node = first_free_node->par;
     return node;
+}
 //****************************************************************
     /*
      * Initialize tree before using.
      */
     avltree_create(tree);
-    if (!quiet) printf("\n\nInserting %d nodes ...\n", node_count);
+    if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
     for (i = 0; i < node_count; i++) {
         newnode = alloc_avltree_node();
         //if (!quiet) printf("[[[%d]]]\n",newnode->key);
+    }
     if (!quiet) printf("Inserting was finished\n");
+}
-/*
-static avltree_node_t *tree_random_delete_node(avltree_t *tree, int node_count, int r, bool quiet)
-{
-    avltree_node_t *delnode;
-    int i;
-    for (i = 0,delnode = tree->head.n; i < (r-1); i++)
-        delnode = delnode->n;
-    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;
-    }
-    avltree_delete(tree, delnode);
-    return delnode;
-}
-*/
 static void test_tree_delete(avltree_t *tree, int node_count, int node_position, bool quiet)
+{
     avltree_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");
+            if (!quiet) printf("\nDelete root nodes\n");
             while(tree->root != NULL) {
                 delnode = tree->root;
                 avltree_delete(tree,delnode);
                 if (!quiet) {
                     test_tree_parents(tree->root);
+                }
+            }
             break;
         case 1:
-            if (!quiet) printf("\n\nDelete nodes according to their time of origin\n");
+            if (!quiet) printf("\nDelete nodes according to their time of origin\n");
             for (i = 0; i < node_count; i++) {
                 avltree_delete(tree,&(avltree_nodes[i]));
                 if (!quiet) {
                     test_tree_parents(tree->root);
                     test_tree_balance(tree->root);
 static void timeout_tree(avltree_t *tree, int node_count, bool quiet)
+{
     int i = 0;
-    if (!quiet) printf("Timeout tree ...\n");
+    if (!quiet) printf("\nTimeout tree ...\n");
-    while(tree->head.n != &(tree->head)) {
+    while(tree->root != NULL) {
         i++;
         avltree_delete_min(tree);
         if (!quiet) {
             test_tree_parents(tree->root);
             test_tree_balance(tree->root);
+        }
+    }
-    if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!");
+    if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!\n");
     if (!quiet) printf("Timeout tree finished\n");
+}
-/*
-void timeout_tree_run(avltree_t *tree, int operation_count, int verbal)
-{
-    int i;
-    avltree_node_t *node;
-    int r;
-    int count;
-    //inicializace stromu:
-    avltree_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 = tree_random_delete_node(tree,(r % tree->count));
-                //printf("DELETE key: %d, number: %d,address: %p\n",node->key,r % (tree->count+1),node);
-                node->n = first_free_node;
-                first_free_node = node;
-            } else {
-                node = tree->head.n;
-                avltree_delete_min(tree);
-                //printf("TIMEOUT key: %d, address: %p\n",node->key,node);
-                node->n = first_free_node;
-                first_free_node = node;
-            }
-            } else {
-                    node = alloc_avltree_node_random();
-            //printf("INSERT key: %d, address: %p\n",node->key + tree->basetime,node);
-            avltree_insert(tree, node);
-            }
-        //test_tree_height(tree->root,1);
-        //tree_test_parents(tree->root);
-        //print_tree_link(tree->count);
-        //print_tree_structure_flat(tree->root,0); putchar('\n'); putchar('\n');
-    }
-}
-*/
 char * test_avltree1(bool quiet)
+{
     alloc_avltree_node_prepare();
-    test_tree_insert(&tree, NODE_COUNT, quiet);
+    test_tree_insert(&avltree, NODE_COUNT, quiet);
-    test_tree_delete(&tree, NODE_COUNT, 0, quiet);
+    test_tree_delete(&avltree, NODE_COUNT, 0, quiet);
     alloc_avltree_node_prepare();
-    test_tree_insert(&tree, NODE_COUNT, quiet);
+    test_tree_insert(&avltree, NODE_COUNT, quiet);
-    test_tree_delete(&tree, NODE_COUNT, 1, quiet);
+    test_tree_delete(&avltree, NODE_COUNT, 1, quiet);
     alloc_avltree_node_prepare();
-    test_tree_insert(&tree, NODE_COUNT, quiet);
+    test_tree_insert(&avltree, NODE_COUNT, quiet);
-    timeout_tree(&tree, NODE_COUNT, quiet);
+    timeout_tree(&avltree, NODE_COUNT, quiet);
     return NULL;
+}

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/test/avltree/avltree1.c – Rev 2416 → 2421