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