Subversion Repositories HelenOS

Rev

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