Subversion Repositories HelenOS

Rev

Rev 2461 | 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 <adt/favl.h>
  33. #include <adt/extavl.h>
  34. #include <adt/extavlrel.h>
  35. #include <debug.h>
  36. #include <arch/types.h>
  37. #include <arch/cycle.h>
  38. #include <arch/asm.h>
  39. #include <panic.h>
  40. #include <mm/slab.h>
  41.  
  42. /*
  43.  * Node count must be more then 1000!
  44.  */
  45. #define NODE_COUNT 100000
  46. /*
  47.  * Seed constant.
  48.  */
  49. #define GEN_NUM 275604541
  50. #define OPERATION_COUNT 1000000
  51. #define TEST_COUNT 3
  52.  
  53. static unsigned int node_count[TEST_COUNT] = {100,1000,NODE_COUNT};
  54.  
  55. /*
  56.  * Wrapper tree data structures.
  57.  */
  58. static avltree_t avltree;
  59. static favltree_t favltree;
  60. static extavltree_t extavltree;
  61. static extavlreltree_t extavlreltree;
  62.  
  63. /*
  64.  * Slab cache variables.
  65.  */
  66. static slab_cache_t *avl_slab;
  67. static slab_cache_t *favl_slab;
  68. static slab_cache_t *extavl_slab;
  69. static slab_cache_t *extavlrel_slab;
  70.  
  71. /*
  72.  * Head of free nodes' list:
  73.  */
  74. static avltree_node_t *avl_ffn = NULL;
  75. static favltree_node_t *favl_ffn = NULL;
  76. static extavltree_node_t *extavl_ffn = NULL;
  77. static extavlreltree_node_t *extavlrel_ffn = NULL;
  78.  
  79.  
  80. static void keys_prepare(int node_count, int type)
  81. {
  82.     unsigned int i;
  83.     uint16_t s;
  84.     avltree_node_t *a = avl_ffn;
  85.     favltree_node_t *b = favl_ffn;
  86.     extavltree_node_t *c = extavl_ffn;
  87.     extavlreltree_node_t *d = extavlrel_ffn;
  88.    
  89.     switch (type) {
  90.         case 0:
  91.             s = (uint16_t) get_cycle();
  92.             for (i = 0; i < node_count; i++) {
  93.                 a->key = s;
  94.                 b->key = s;
  95.                 c->key = s;
  96.                 d->key = s;
  97.                 s += GEN_NUM;
  98.                 a = a->par;
  99.                 b = b->par;
  100.                 c = c->par;
  101.                 d = d->par;
  102.             }
  103.             break;
  104.         case 1:
  105.             for (i = 1; i <= node_count; i++) {
  106.                 a->key = i;
  107.                 b->key = i;
  108.                 c->key = i;
  109.                 d->key = i;
  110.                 a = a->par;
  111.                 b = b->par;
  112.                 c = c->par;
  113.                 d = d->par;
  114.             }
  115.             break;
  116.         case 2:
  117.             for (i = node_count; i > 0; i--) {
  118.                 a->key = i;
  119.                 b->key = i;
  120.                 c->key = i;
  121.                 d->key = i;
  122.                 a = a->par;
  123.                 b = b->par;
  124.                 c = c->par;
  125.                 d = d->par;        
  126.             }
  127.             break;
  128.     }
  129. }
  130.  
  131.  
  132. static bool alloc_nodes(int node_count)
  133. {
  134.     int i;
  135.     avltree_node_t *a;
  136.     extavltree_node_t *b;
  137.     extavlreltree_node_t *c;
  138.     favltree_node_t *d;
  139.    
  140.     avl_ffn = NULL;
  141.     favl_ffn = NULL;
  142.     extavl_ffn = NULL;
  143.     extavlrel_ffn = NULL;
  144.  
  145.     for (i = 0; i < node_count; i++) {
  146.         a = (avltree_node_t *) slab_alloc(avl_slab,0);
  147.         if (!a) {
  148.             printf("Not enough memory to allocate test arrays.");
  149.             return false;
  150.         }
  151.         b = (extavltree_node_t *) slab_alloc(extavl_slab,0);
  152.         if (!b) {
  153.             printf("Not enough memory to allocate test arrays.");
  154.             return false;
  155.         }
  156.         c = (extavlreltree_node_t *) slab_alloc(extavlrel_slab,0);
  157.         if (!c) {
  158.             printf("Not enough memory to allocate test arrays.");
  159.             return false;
  160.         }
  161.         d = (favltree_node_t *) slab_alloc(favl_slab,0);
  162.         if (!d) {
  163.             printf("Not enough memory to allocate test arrays.");
  164.             return false;
  165.         }
  166.         a->par = avl_ffn;
  167.         b->par = extavl_ffn;
  168.         c->par = extavlrel_ffn;
  169.         d->par = favl_ffn;
  170.         avl_ffn = a;
  171.         extavl_ffn = b;
  172.         extavlrel_ffn = c;
  173.         favl_ffn = d;
  174.     }
  175.     return true;
  176. }
  177.  
  178. static void free_nodes(int node_count)
  179. {
  180.     int i;
  181.     avltree_node_t *a;
  182.     extavltree_node_t *b;
  183.     extavlreltree_node_t *c;
  184.     favltree_node_t *d;
  185.    
  186.     for (i = 0; i < node_count; i++) {
  187.         a = avl_ffn;
  188.         b = extavl_ffn;
  189.         c = extavlrel_ffn;
  190.         d = favl_ffn;
  191.         if (!a || !b || !c || !d) {
  192.             printf("Deleted nodes: %d, node count: %d, a: %p, b: %p, c: %p, d: %p\n",
  193.                     i,node_count,a,b,c,d);
  194.             panic("Some nodes have been lost!");
  195.         }
  196.         avl_ffn = avl_ffn->par;
  197.         extavl_ffn = extavl_ffn->par;
  198.         extavlrel_ffn = extavlrel_ffn->par;
  199.         favl_ffn = favl_ffn->par;
  200.         slab_free(avl_slab,a);
  201.         slab_free(extavl_slab,b);
  202.         slab_free(extavlrel_slab,c);
  203.         slab_free(favl_slab,d);
  204.     }
  205. }
  206.  
  207. static avltree_node_t *alloc_avltree_node(void)
  208. {
  209.     avltree_node_t *node;
  210.  
  211.     node = avl_ffn;
  212.     avl_ffn = avl_ffn->par;
  213.  
  214.     return node;
  215. }
  216.  
  217. static favltree_node_t *alloc_favltree_node(void)
  218. {
  219.     favltree_node_t *node;
  220.  
  221.     node = favl_ffn;
  222.     favl_ffn = favl_ffn->par;
  223.  
  224.     return node;
  225. }
  226.  
  227. static extavltree_node_t *alloc_extavltree_node(void)
  228. {
  229.     extavltree_node_t *node;
  230.  
  231.     node = extavl_ffn;
  232.  
  233.     extavl_ffn = extavl_ffn->par;
  234.  
  235.     return node;
  236. }
  237.  
  238. static extavlreltree_node_t *alloc_extavlreltree_node(void)
  239. {
  240.     extavlreltree_node_t *node;
  241.  
  242.     node = extavlrel_ffn;
  243.     extavlrel_ffn = extavlrel_ffn->par;
  244.  
  245.     return node;
  246. }
  247.  
  248. static void free_avltree_node(avltree_node_t *node)
  249. {
  250.     node->par = avl_ffn;
  251.     avl_ffn = node;
  252. }
  253.  
  254. static void free_favltree_node(favltree_node_t *node)
  255. {
  256.     node->par = favl_ffn;
  257.     favl_ffn = node;
  258. }
  259.  
  260. static void free_extavltree_node(extavltree_node_t *node)
  261. {
  262.     node->par = extavl_ffn;
  263.     extavl_ffn = node;
  264. }
  265.  
  266. static void free_extavlreltree_node(extavlreltree_node_t *node)
  267. {
  268.     node->par = extavlrel_ffn;
  269.     extavlrel_ffn = node;
  270. }
  271.  
  272. /** Insert keys of ascending sequence and delete tree deleting root nodes.
  273.  */
  274. static void test1(void)
  275. {
  276.     uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
  277.     uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT];
  278.     unsigned int i,ii;
  279.     avltree_node_t *a;
  280.     extavltree_node_t *b;
  281.     extavlreltree_node_t *c;
  282.     favltree_node_t *d;
  283.    
  284.    
  285.     printf("INSERT nodes with keys of ascending sequence.\n");
  286.     printf("Nodes:\t\t");
  287.     for (ii = 0; ii < TEST_COUNT; ii++) {
  288.         printf("%20u",node_count[ii]);
  289.         keys_prepare(node_count[ii],1);
  290.  
  291.         /*
  292.          * AVL INSERT
  293.          */
  294.         s[0][ii] = get_cycle();
  295.        
  296.         avltree_create(&avltree);
  297.         for (i = 0; i < node_count[ii]; i++) {
  298.             avltree_insert(&avltree,alloc_avltree_node());
  299.         }
  300.            
  301.         f[0][ii] = get_cycle();
  302.         /*
  303.          * AVL DELETE
  304.          */
  305.         ds[0][ii] = get_cycle();
  306.        
  307.         while ((a = avltree.root) != NULL) {
  308.             avltree_delete(&avltree,a);
  309.             free_avltree_node(a);
  310.         }
  311.            
  312.         df[0][ii] = get_cycle();
  313.  
  314.         /*
  315.          * ExtAVL INSERT
  316.          */
  317.         s[1][ii] = get_cycle();
  318.        
  319.         extavltree_create(&extavltree);
  320.         for (i = 0; i < node_count[ii]; i++) {
  321.             extavltree_insert(&extavltree,alloc_extavltree_node());
  322.         }
  323.        
  324.         f[1][ii] = get_cycle();
  325.         /*
  326.          * ExtAVL DELETE
  327.          */
  328.         ds[1][ii] = get_cycle();
  329.        
  330.         while ((b = extavltree.root) != NULL) {
  331.             extavltree_delete(&extavltree,b);
  332.             free_extavltree_node(b);
  333.         }
  334.            
  335.         df[1][ii] = get_cycle();
  336.  
  337.         /*
  338.          * ExtAVLrel INSERT
  339.          */
  340.         s[2][ii] = get_cycle();
  341.        
  342.         extavlreltree_create(&extavlreltree);
  343.         for (i = 0; i < node_count[ii]; i++) {
  344.             extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
  345.         }
  346.        
  347.         f[2][ii] = get_cycle();
  348.         /*
  349.          * ExtAVLrel DELETE
  350.          */
  351.         ds[2][ii] = get_cycle();
  352.        
  353.         while ((c = extavlreltree.root) != NULL) {
  354.             extavlreltree_delete(&extavlreltree,c);
  355.             free_extavlreltree_node(c);
  356.         }
  357.            
  358.         df[2][ii] = get_cycle();
  359.  
  360.         /*
  361.          * FAVL INSERT
  362.          */
  363.         s[3][ii] = get_cycle();
  364.        
  365.         favltree_create(&favltree);
  366.         for (i = 0; i < node_count[ii]; i++) {
  367.             favltree_insert(&favltree,alloc_favltree_node());
  368.         }
  369.            
  370.         f[3][ii] = get_cycle();
  371.         /*
  372.          * FAVL DELETE
  373.          */
  374.         ds[3][ii] = get_cycle();
  375.        
  376.         while ((d = favltree.root) != NULL) {
  377.             favltree_delete(&favltree,d);
  378.             free_favltree_node(d);
  379.         }
  380.            
  381.         df[3][ii] = get_cycle();
  382.     }
  383.     printf("\n----------------------------------------------------------------------------");  
  384.     printf("\nAVL\t\t");
  385.     for (ii = 0; ii < TEST_COUNT; ii++)
  386.         printf("%20llu",f[0][ii]-s[0][ii]);
  387.     printf("\nFAVL\t\t");
  388.     for (ii = 0; ii < TEST_COUNT; ii++)
  389.         printf("%20llu",f[3][ii]-s[3][ii]);
  390.     printf("\nExtAVL\t\t");
  391.     for (ii = 0; ii < TEST_COUNT; ii++)
  392.         printf("%20llu",f[1][ii]-s[1][ii]);
  393.     printf("\nExtAVLrel\t");
  394.     for (ii = 0; ii < TEST_COUNT; ii++)
  395.         printf("%20llu",f[2][ii]-s[2][ii]);
  396.     printf("\n\n");
  397.  
  398.     printf("DELETE tree deleting root nodes\n");
  399.     printf("Nodes:\t\t");
  400.     for (ii = 0; ii < TEST_COUNT; ii++)
  401.         printf("%20u",node_count[ii]);
  402.     printf("\n----------------------------------------------------------------------------");  
  403.     printf("\nAVL\t\t");
  404.     for (ii = 0; ii < TEST_COUNT; ii++)
  405.         printf("%20llu",df[0][ii]-ds[0][ii]);
  406.     printf("\nAVL\t\t");
  407.     for (ii = 0; ii < TEST_COUNT; ii++)
  408.         printf("%20llu",df[3][ii]-ds[3][ii]);
  409.     printf("\nExtAVL\t\t");
  410.     for (ii = 0; ii < TEST_COUNT; ii++)
  411.         printf("%20llu",df[1][ii]-ds[1][ii]);
  412.     printf("\nExtAVLrel\t");
  413.     for (ii = 0; ii < TEST_COUNT; ii++)
  414.         printf("%20llu",df[2][ii]-ds[2][ii]);
  415.     printf("\n\n");
  416. }
  417.  
  418.  
  419. /** Insert keys of ascending sequence and delete tree with delete_min functions.
  420.  */
  421. static void test2(void)
  422. {
  423.     uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
  424.     uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT];
  425.     unsigned int i,ii;
  426.     avltree_node_t *a;
  427.     extavltree_node_t *b;
  428.     extavlreltree_node_t *c;
  429.     favltree_node_t *d;
  430.  
  431.  
  432.     printf("INSERT nodes with keys of descending sequence.\n");
  433.     printf("Nodes:\t\t");
  434.     for (ii = 0; ii < TEST_COUNT; ii++) {
  435.         printf("%20u",node_count[ii]);
  436.         keys_prepare(node_count[ii],2);
  437.        
  438.         /*
  439.          * AVL INSERT
  440.          */
  441.         s[0][ii] = get_cycle();
  442.        
  443.         avltree_create(&avltree);
  444.         for (i = 0; i < node_count[ii]; i++) {
  445.             avltree_insert(&avltree,alloc_avltree_node());
  446.         }
  447.            
  448.         f[0][ii] = get_cycle();
  449.         /*
  450.          * AVL DELETE
  451.          */
  452.         ds[0][ii] = get_cycle();
  453.        
  454.         while (avltree.root != NULL) {
  455.             a = avltree_find_min(&avltree);
  456.             avltree_delete_min(&avltree);
  457.             free_avltree_node(a);
  458.         }
  459.            
  460.         df[0][ii] = get_cycle();
  461.  
  462.         /*
  463.          * ExtAVL INSERT
  464.          */
  465.         s[1][ii] = get_cycle();
  466.        
  467.         extavltree_create(&extavltree);
  468.         for (i = 0; i < node_count[ii]; i++) {
  469.             extavltree_insert(&extavltree,alloc_extavltree_node());
  470.         }
  471.        
  472.         f[1][ii] = get_cycle();
  473.         /*
  474.          * ExtAVL DELETE
  475.          */
  476.         ds[1][ii] = get_cycle();
  477.        
  478.         while (extavltree.root != NULL) {
  479.             b = extavltree.head.next;
  480.             extavltree_delete_min(&extavltree);
  481.             free_extavltree_node(b);
  482.         }
  483.            
  484.         df[1][ii] = get_cycle();
  485.         /*
  486.          * ExtAVLrel INSERT
  487.          */
  488.         s[2][ii] = get_cycle();
  489.        
  490.         extavlreltree_create(&extavlreltree);
  491.         for (i = 0; i < node_count[ii]; i++) {
  492.             extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
  493.         }
  494.        
  495.         f[2][ii] = get_cycle();
  496.         /*
  497.          * ExtAVLrel DELETE
  498.          */
  499.         ds[2][ii] = get_cycle();
  500.        
  501.         while (extavlreltree.root != NULL) {
  502.             c = extavlreltree.head.next;
  503.             extavlreltree_delete_min(&extavlreltree);
  504.             free_extavlreltree_node(c);
  505.         }
  506.            
  507.         df[2][ii] = get_cycle();
  508.  
  509.         /*
  510.          * FAVL INSERT
  511.          */
  512.         s[3][ii] = get_cycle();
  513.        
  514.         favltree_create(&favltree);
  515.         for (i = 0; i < node_count[ii]; i++) {
  516.             favltree_insert(&favltree,alloc_favltree_node());
  517.         }
  518.            
  519.         f[3][ii] = get_cycle();
  520.         /*
  521.          * AVL DELETE
  522.          */
  523.         ds[3][ii] = get_cycle();
  524.        
  525.         while (favltree.root != NULL) {
  526.             d = favltree_find_min(&favltree);
  527.             favltree_delete_min(&favltree);
  528.             free_favltree_node(d);
  529.         }
  530.            
  531.         df[3][ii] = get_cycle();
  532.  
  533.     }
  534.     printf("\n----------------------------------------------------------------------------");  
  535.     printf("\nAVL\t\t");
  536.     for (ii = 0; ii < TEST_COUNT; ii++)
  537.         printf("%20llu",f[0][ii]-s[0][ii]);
  538.     printf("\nFAVL\t\t");
  539.     for (ii = 0; ii < TEST_COUNT; ii++)
  540.         printf("%20llu",f[3][ii]-s[3][ii]);
  541.     printf("\nExtAVL\t\t");
  542.     for (ii = 0; ii < TEST_COUNT; ii++)
  543.         printf("%20llu",f[1][ii]-s[1][ii]);
  544.     printf("\nExtAVLrel\t");
  545.     for (ii = 0; ii < TEST_COUNT; ii++)
  546.         printf("%20llu",f[2][ii]-s[2][ii]);
  547.     printf("\n\n");
  548.  
  549.     printf("DELETE tree deleting nodes with minimal key\n");
  550.     printf("Nodes:\t\t");
  551.     for (ii = 0; ii < TEST_COUNT; ii++)
  552.         printf("%20u",node_count[ii]);
  553.     printf("\n----------------------------------------------------------------------------");  
  554.     printf("\nAVL\t\t");
  555.     for (ii = 0; ii < TEST_COUNT; ii++)
  556.         printf("%20llu",df[0][ii]-ds[0][ii]);
  557.     printf("\nFAVL\t\t");
  558.     for (ii = 0; ii < TEST_COUNT; ii++)
  559.         printf("%20llu",df[3][ii]-ds[3][ii]);
  560.     printf("\nExtAVL\t\t");
  561.     for (ii = 0; ii < TEST_COUNT; ii++)
  562.         printf("%20llu",df[1][ii]-ds[1][ii]);
  563.     printf("\nExtAVLrel\t");
  564.     for (ii = 0; ii < TEST_COUNT; ii++)
  565.         printf("%20llu",df[2][ii]-ds[2][ii]);
  566.     printf("\n\n");
  567. }
  568.  
  569.  
  570. /** Insert keys of random sequence and delete tree with delete_min functions.
  571.  */
  572. static void test3(void)
  573. {
  574.     uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
  575.     uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT];
  576.     unsigned int i,ii;
  577.     avltree_node_t *a;
  578.     extavltree_node_t *b;
  579.     extavlreltree_node_t *c;
  580.     favltree_node_t *d;
  581.  
  582.    
  583.     printf("INSERT nodes with keys of random sequence 1-65536.\n");
  584.     printf("Nodes:\t\t");
  585.     for (ii = 0; ii < TEST_COUNT; ii++) {
  586.         printf("%20u",node_count[ii]);
  587.         keys_prepare(node_count[ii],0);
  588.        
  589.         /*
  590.          * AVL INSERT
  591.          */
  592.         s[0][ii] = get_cycle();
  593.        
  594.         avltree_create(&avltree);
  595.         for (i = 0; i < node_count[ii]; i++) {
  596.             avltree_insert(&avltree,alloc_avltree_node());
  597.         }
  598.            
  599.         f[0][ii] = get_cycle();
  600.         /*
  601.          * AVL DELETE
  602.          */
  603.         ds[0][ii] = get_cycle();
  604.        
  605.         while (avltree.root != NULL) {
  606.             a = avltree_find_min(&avltree);
  607.             avltree_delete_min(&avltree);
  608.             free_avltree_node(a);
  609.         }
  610.            
  611.         df[0][ii] = get_cycle();
  612.  
  613.         /*
  614.          * ExtAVL INSERT
  615.          */
  616.         s[1][ii] = get_cycle();
  617.        
  618.         extavltree_create(&extavltree);
  619.         for (i = 0; i < node_count[ii]; i++) {
  620.             extavltree_insert(&extavltree,alloc_extavltree_node());
  621.         }
  622.        
  623.         f[1][ii] = get_cycle();
  624.         /*
  625.          * ExtAVL DELETE
  626.          */
  627.         ds[1][ii] = get_cycle();
  628.        
  629.         while (extavltree.root != NULL) {
  630.             b = extavltree.head.next;
  631.             extavltree_delete_min(&extavltree);
  632.             free_extavltree_node(b);
  633.         }
  634.            
  635.         df[1][ii] = get_cycle();
  636.         /*
  637.          * ExtAVLrel INSERT
  638.          */
  639.         s[2][ii] = get_cycle();
  640.        
  641.         extavlreltree_create(&extavlreltree);
  642.         for (i = 0; i < node_count[ii]; i++) {
  643.             extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
  644.         }
  645.        
  646.         f[2][ii] = get_cycle();
  647.         /*
  648.          * ExtAVLrel DELETE
  649.          */
  650.         ds[2][ii] = get_cycle();
  651.        
  652.         while (extavlreltree.root != NULL) {
  653.             c = extavlreltree.head.next;
  654.             extavlreltree_delete_min(&extavlreltree);
  655.             free_extavlreltree_node(c);
  656.         }
  657.            
  658.         df[2][ii] = get_cycle();
  659.  
  660.         /*
  661.          * FAVL INSERT
  662.          */
  663.         s[3][ii] = get_cycle();
  664.        
  665.         favltree_create(&favltree);
  666.         for (i = 0; i < node_count[ii]; i++) {
  667.             favltree_insert(&favltree,alloc_favltree_node());
  668.         }
  669.            
  670.         f[3][ii] = get_cycle();
  671.         /*
  672.          * AVL DELETE
  673.          */
  674.         ds[3][ii] = get_cycle();
  675.        
  676.         while (favltree.root != NULL) {
  677.             d = favltree_find_min(&favltree);
  678.             favltree_delete_min(&favltree);
  679.             free_favltree_node(d);
  680.         }
  681.            
  682.         df[3][ii] = get_cycle();
  683.     }
  684.     printf("\n----------------------------------------------------------------------------");  
  685.     printf("\nAVL\t\t");
  686.     for (ii = 0; ii < TEST_COUNT; ii++)
  687.         printf("%20llu",f[0][ii]-s[0][ii]);
  688.     printf("\nFAVL\t\t");
  689.     for (ii = 0; ii < TEST_COUNT; ii++)
  690.         printf("%20llu",f[3][ii]-s[3][ii]);
  691.     printf("\nExtAVL\t\t");
  692.     for (ii = 0; ii < TEST_COUNT; ii++)
  693.         printf("%20llu",f[1][ii]-s[1][ii]);
  694.     printf("\nExtAVLrel\t");
  695.     for (ii = 0; ii < TEST_COUNT; ii++)
  696.         printf("%20llu",f[2][ii]-s[2][ii]);
  697.     printf("\n\n");
  698.  
  699.     printf("DELETE tree deleting nodes with minimal key\n");
  700.     printf("Nodes:\t\t");
  701.     for (ii = 0; ii < TEST_COUNT; ii++)
  702.         printf("%20u",node_count[ii]);
  703.     printf("\n----------------------------------------------------------------------------");  
  704.     printf("\nAVL\t\t");
  705.     for (ii = 0; ii < TEST_COUNT; ii++)
  706.         printf("%20llu",df[0][ii]-ds[0][ii]);
  707.     printf("\nFAVL\t\t");
  708.     for (ii = 0; ii < TEST_COUNT; ii++)
  709.         printf("%20llu",df[3][ii]-ds[3][ii]);
  710.     printf("\nExtAVL\t\t");
  711.     for (ii = 0; ii < TEST_COUNT; ii++)
  712.         printf("%20llu",df[1][ii]-ds[1][ii]);
  713.     printf("\nExtAVLrel\t");
  714.     for (ii = 0; ii < TEST_COUNT; ii++)
  715.         printf("%20llu",df[2][ii]-ds[2][ii]);
  716.     printf("\n\n");
  717. }
  718.  
  719.  
  720. /** Simulating timeout mechanismus with insert and delete_min operations.
  721.  */
  722. static void test4(void)
  723. {
  724.     uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
  725.     unsigned int i,ii;
  726.     avltree_node_t *a;
  727.     extavltree_node_t *b;
  728.     extavlreltree_node_t *c;
  729.     favltree_node_t *d;
  730.     uint64_t r;
  731.     uint16_t rr;
  732.     unsigned int mn,nc;
  733.  
  734.    
  735.     printf("Simulating timeout mechanismus with %d insert or delete_min operations\n",OPERATION_COUNT);
  736.     printf("Maximum nodes:\t");
  737.     for (ii = 0; ii < TEST_COUNT; ii++) {
  738.         printf("%20u",node_count[ii]);
  739.        
  740.         r = (uint64_t) get_cycle();
  741.         mn = node_count[ii];
  742.        
  743.         /*
  744.          * AVL
  745.          */
  746.         rr = r;
  747.         nc = 0;
  748.         s[0][ii] = get_cycle();
  749.        
  750.         avltree_create(&avltree);
  751.         for (i = 0; i < OPERATION_COUNT; i++) {
  752.             if (((rr % mn) <= nc) && nc) {
  753.                 /*
  754.                  * Delete min.
  755.                  */
  756.                 a = avltree_find_min(&avltree);
  757.                 avltree_delete_min(&avltree);
  758.                 free_avltree_node(a);
  759.                 nc--;
  760.             } else {
  761.                 /*
  762.                  * Insert.
  763.                  */
  764.                 a = alloc_avltree_node();
  765.                 a->key = rr;
  766.                 avltree_insert(&avltree,a);
  767.                 nc++;
  768.             }
  769.             rr += GEN_NUM;
  770.         }
  771.         /*
  772.          * Delete rest tree.
  773.          */
  774.         while (avltree.root != NULL) {
  775.             a = avltree_find_min(&avltree);
  776.             avltree_delete_min(&avltree);
  777.             free_avltree_node(a);
  778.         }  
  779.        
  780.         f[0][ii] = get_cycle();
  781.  
  782.         /*
  783.          * FAVL
  784.          */
  785.         rr = r;
  786.         nc = 0;
  787.         s[3][ii] = get_cycle();
  788.        
  789.         avltree_create(&avltree);
  790.         for (i = 0; i < OPERATION_COUNT; i++) {
  791.             if (((rr % mn) <= nc) && nc) {
  792.                 /*
  793.                  * Delete min.
  794.                  */
  795.                 d = favltree_find_min(&favltree);
  796.                 favltree_delete_min(&favltree);
  797.                 free_favltree_node(d);
  798.                 nc--;
  799.             } else {
  800.                 /*
  801.                  * Insert.
  802.                  */
  803.                 d = alloc_favltree_node();
  804.                 d->key = rr;
  805.                 favltree_insert(&favltree,d);
  806.                 nc++;
  807.             }
  808.             rr += GEN_NUM;
  809.         }
  810.         /*
  811.          * Delete rest tree.
  812.          */
  813.         while (favltree.root != NULL) {
  814.             d = favltree_find_min(&favltree);
  815.             favltree_delete_min(&favltree);
  816.             free_favltree_node(d);
  817.         }  
  818.        
  819.         f[3][ii] = get_cycle();
  820.  
  821.         /*
  822.          * ExtAVL
  823.          */
  824.         rr = r;
  825.         nc = 0;
  826.         s[1][ii] = get_cycle();
  827.        
  828.         extavltree_create(&extavltree);
  829.         for (i = 0; i < OPERATION_COUNT; i++) {
  830.             if (((rr % mn) <= nc) && nc) {
  831.                 /*
  832.                  * Delete min.
  833.                  */
  834.                 b = extavltree.head.next;
  835.                 extavltree_delete_min(&extavltree);
  836.                 free_extavltree_node(b);
  837.                 nc--;
  838.             } else {
  839.                 /*
  840.                  * Insert.
  841.                  */
  842.                 b = alloc_extavltree_node();
  843.                 b->key = rr;
  844.                 extavltree_insert(&extavltree,b);
  845.                 nc++;
  846.             }
  847.             rr += GEN_NUM;
  848.         }
  849.         /*
  850.          * Delete rest tree.
  851.          */
  852.         while (extavltree.root != NULL) {
  853.             b = extavltree.head.next;
  854.             extavltree_delete_min(&extavltree);
  855.             free_extavltree_node(b);
  856.         }
  857.  
  858.         f[1][ii] = get_cycle();
  859.        
  860.         /*
  861.          * ExtAVLrel
  862.          */
  863.         rr = r;
  864.         nc = 0;
  865.         s[2][ii] = get_cycle();
  866.        
  867.         extavlreltree_create(&extavlreltree);
  868.         for (i = 0; i < OPERATION_COUNT; i++) {
  869.             if (((rr % mn) <= nc) && nc) {
  870.                 /*
  871.                  * Delete min.
  872.                  */
  873.                 c = extavlreltree.head.next;
  874.                 //if (ii == 2 && !(i % 100)) printf("DEL key %llu, nc: %u, op: %u\n",c->key,nc,i);
  875.                 extavlreltree_delete_min(&extavlreltree);
  876.                 free_extavlreltree_node(c);
  877.                 nc--;
  878.             } else {
  879.                 /*
  880.                  * Insert.
  881.                  */
  882.                 c = alloc_extavlreltree_node();
  883.                 c->key = rr;
  884.                 //if (ii == 2 && !(i % 100)) printf("INS key %llu, nc: %u, op: %u\n",c->key,nc,i);
  885.                 extavlreltree_insert(&extavlreltree,c);
  886.                 nc++;
  887.             }
  888.             rr += GEN_NUM;
  889.         }
  890.         /*
  891.          * Delete rest tree.
  892.          */
  893.         while (extavlreltree.root != NULL) {
  894.             c = extavlreltree.head.next;
  895.             extavlreltree_delete_min(&extavlreltree);
  896.             free_extavlreltree_node(c);
  897.         }
  898.  
  899.         f[2][ii] = get_cycle();
  900.     }
  901.     printf("\n----------------------------------------------------------------------------");  
  902.     printf("\nAVL\t\t");
  903.     for (ii = 0; ii < TEST_COUNT; ii++)
  904.         printf("%20llu",f[0][ii]-s[0][ii]);
  905.     printf("\nFAVL\t\t");
  906.     for (ii = 0; ii < TEST_COUNT; ii++)
  907.         printf("%20llu",f[3][ii]-s[3][ii]);
  908.     printf("\nExtAVL\t\t");
  909.     for (ii = 0; ii < TEST_COUNT; ii++)
  910.         printf("%20llu",f[1][ii]-s[1][ii]);
  911.     printf("\nExtAVLrel\t");
  912.     for (ii = 0; ii < TEST_COUNT; ii++)
  913.         printf("%20llu",f[2][ii]-s[2][ii]);
  914.     printf("\n\n");
  915. }
  916.  
  917.  
  918. char * test_timeoutbench1(bool quiet)
  919. {
  920.     printf("\n\tBenchmark test of timeout data structures: AVL, ExtAVL and ExtAVLrel.\n"
  921.         "Run test more than once for eliminating possible distortion due to caching!\n\n");
  922.  
  923.    
  924.     avl_slab = slab_cache_create("avl_slab",sizeof(avltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
  925.     favl_slab = slab_cache_create("favl_slab",sizeof(favltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
  926.     extavl_slab = slab_cache_create("extavl_slab",sizeof(extavltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
  927.     extavlrel_slab = slab_cache_create("extavlrel_slab",sizeof(extavlreltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
  928.  
  929.     if (!alloc_nodes(NODE_COUNT))
  930.         return NULL;
  931.  
  932.     /*
  933.      * store initial cycle count,
  934.      * do test,
  935.      * store finish cycle count,
  936.      * show results
  937.      */
  938.  
  939.     test1();
  940.     test2();
  941.     test3();
  942.     test4();
  943.  
  944.     /*
  945.      * Deallocate arrays.
  946.      */
  947.     free_nodes(NODE_COUNT);
  948.    
  949.     return NULL;
  950. }
  951.