Subversion Repositories HelenOS

Rev

Rev 2431 | 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/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 100000
  45. #define GEN_NUM 275604541
  46. #define OPERATION_COUNT 1000000
  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.     uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
  233.     uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
  234.     unsigned int i,ii;
  235.     avltree_node_t *a;
  236.     extavltree_node_t *b;
  237.     extavlreltree_node_t *c;
  238.    
  239.    
  240.     printf("INSERT nodes with keys of ascending sequence.\n");
  241.     printf("Nodes:\t\t");
  242.     for (ii = 0; ii < TEST_COUNT; ii++) {
  243.         printf("%20u",node_count[ii]);
  244.         keys_prepare(node_count[ii],1);
  245.  
  246.         /*
  247.          * AVL INSERT
  248.          */
  249.         s[0][ii] = get_cycle();
  250.        
  251.         avltree_create(&avltree);
  252.         for (i = 0; i < node_count[ii]; i++) {
  253.             avltree_insert(&avltree,alloc_avltree_node());
  254.         }
  255.            
  256.         f[0][ii] = get_cycle();
  257.         /*
  258.          * AVL DELETE
  259.          */
  260.         ds[0][ii] = get_cycle();
  261.        
  262.         while ((a = avltree.root) != NULL) {
  263.             avltree_delete(&avltree,a);
  264.             free_avltree_node(a);
  265.         }
  266.            
  267.         df[0][ii] = get_cycle();
  268.  
  269.         /*
  270.          * ExtAVL INSERT
  271.          */
  272.         s[1][ii] = get_cycle();
  273.        
  274.         extavltree_create(&extavltree);
  275.         for (i = 0; i < node_count[ii]; i++) {
  276.             extavltree_insert(&extavltree,alloc_extavltree_node());
  277.         }
  278.        
  279.         f[1][ii] = get_cycle();
  280.         /*
  281.          * ExtAVL DELETE
  282.          */
  283.         ds[1][ii] = get_cycle();
  284.        
  285.         while ((b = extavltree.root) != NULL) {
  286.             extavltree_delete(&extavltree,b);
  287.             free_extavltree_node(b);
  288.         }
  289.            
  290.         df[1][ii] = get_cycle();
  291.  
  292.         /*
  293.          * ExtAVLrel INSERT
  294.          */
  295.         s[2][ii] = get_cycle();
  296.        
  297.         extavlreltree_create(&extavlreltree);
  298.         for (i = 0; i < node_count[ii]; i++) {
  299.             extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
  300.         }
  301.        
  302.         f[2][ii] = get_cycle();
  303.         /*
  304.          * ExtAVLrel DELETE
  305.          */
  306.         ds[2][ii] = get_cycle();
  307.        
  308.         while ((c = extavlreltree.root) != NULL) {
  309.             extavlreltree_delete(&extavlreltree,c);
  310.             free_extavlreltree_node(c);
  311.         }
  312.            
  313.         df[2][ii] = get_cycle();
  314.     }
  315.     printf("\n----------------------------------------------------------------------------");  
  316.     printf("\nAVL\t\t");
  317.     for (ii = 0; ii < TEST_COUNT; ii++)
  318.         printf("%20llu",f[0][ii]-s[0][ii]);
  319.     printf("\nExtAVL\t\t");
  320.     for (ii = 0; ii < TEST_COUNT; ii++)
  321.         printf("%20llu",f[1][ii]-s[1][ii]);
  322.     printf("\nExtAVLrel\t");
  323.     for (ii = 0; ii < TEST_COUNT; ii++)
  324.         printf("%20llu",f[2][ii]-s[2][ii]);
  325.     printf("\n\n");
  326.  
  327.     printf("DELETE tree deleting root nodes\n");
  328.     printf("Nodes:\t\t");
  329.     for (ii = 0; ii < TEST_COUNT; ii++)
  330.         printf("%20u",node_count[ii]);
  331.     printf("\n----------------------------------------------------------------------------");  
  332.     printf("\nAVL\t\t");
  333.     for (ii = 0; ii < TEST_COUNT; ii++)
  334.         printf("%20llu",df[0][ii]-ds[0][ii]);
  335.     printf("\nExtAVL\t\t");
  336.     for (ii = 0; ii < TEST_COUNT; ii++)
  337.         printf("%20llu",df[1][ii]-ds[1][ii]);
  338.     printf("\nExtAVLrel\t");
  339.     for (ii = 0; ii < TEST_COUNT; ii++)
  340.         printf("%20llu",df[2][ii]-ds[2][ii]);
  341.     printf("\n\n");
  342. }
  343.  
  344.  
  345. /** Insert keys of ascending sequence and delete tree with delete_min functions.
  346.  */
  347. static void test2(void)
  348. {
  349.     uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
  350.     uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
  351.     unsigned int i,ii;
  352.     avltree_node_t *a;
  353.     extavltree_node_t *b;
  354.     extavlreltree_node_t *c;
  355.  
  356.  
  357.     printf("INSERT nodes with keys of descending sequence.\n");
  358.     printf("Nodes:\t\t");
  359.     for (ii = 0; ii < TEST_COUNT; ii++) {
  360.         printf("%20u",node_count[ii]);
  361.         keys_prepare(node_count[ii],2);
  362.        
  363.         /*
  364.          * AVL INSERT
  365.          */
  366.         s[0][ii] = get_cycle();
  367.        
  368.         avltree_create(&avltree);
  369.         for (i = 0; i < node_count[ii]; i++) {
  370.             avltree_insert(&avltree,alloc_avltree_node());
  371.         }
  372.            
  373.         f[0][ii] = get_cycle();
  374.         /*
  375.          * AVL DELETE
  376.          */
  377.         ds[0][ii] = get_cycle();
  378.        
  379.         while (avltree.root != NULL) {
  380.             a = avltree_find_min(&avltree);
  381.             avltree_delete_min(&avltree);
  382.             free_avltree_node(a);
  383.         }
  384.            
  385.         df[0][ii] = get_cycle();
  386.  
  387.         /*
  388.          * ExtAVL INSERT
  389.          */
  390.         s[1][ii] = get_cycle();
  391.        
  392.         extavltree_create(&extavltree);
  393.         for (i = 0; i < node_count[ii]; i++) {
  394.             extavltree_insert(&extavltree,alloc_extavltree_node());
  395.         }
  396.        
  397.         f[1][ii] = get_cycle();
  398.         /*
  399.          * ExtAVL DELETE
  400.          */
  401.         ds[1][ii] = get_cycle();
  402.        
  403.         while (extavltree.root != NULL) {
  404.             b = extavltree.head.next;
  405.             extavltree_delete_min(&extavltree);
  406.             free_extavltree_node(b);
  407.         }
  408.            
  409.         df[1][ii] = get_cycle();
  410.         /*
  411.          * ExtAVLrel INSERT
  412.          */
  413.         s[2][ii] = get_cycle();
  414.        
  415.         extavlreltree_create(&extavlreltree);
  416.         for (i = 0; i < node_count[ii]; i++) {
  417.             extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
  418.         }
  419.        
  420.         f[2][ii] = get_cycle();
  421.         /*
  422.          * ExtAVLrel DELETE
  423.          */
  424.         ds[2][ii] = get_cycle();
  425.        
  426.         while (extavlreltree.root != NULL) {
  427.             c = extavlreltree.head.next;
  428.             extavlreltree_delete_min(&extavlreltree);
  429.             free_extavlreltree_node(c);
  430.         }
  431.            
  432.         df[2][ii] = get_cycle();
  433.     }
  434.     printf("\n----------------------------------------------------------------------------");  
  435.     printf("\nAVL\t\t");
  436.     for (ii = 0; ii < TEST_COUNT; ii++)
  437.         printf("%20llu",f[0][ii]-s[0][ii]);
  438.     printf("\nExtAVL\t\t");
  439.     for (ii = 0; ii < TEST_COUNT; ii++)
  440.         printf("%20llu",f[1][ii]-s[1][ii]);
  441.     printf("\nExtAVLrel\t");
  442.     for (ii = 0; ii < TEST_COUNT; ii++)
  443.         printf("%20llu",f[2][ii]-s[2][ii]);
  444.     printf("\n\n");
  445.  
  446.     printf("DELETE tree deleting nodes with minimal key\n");
  447.     printf("Nodes:\t\t");
  448.     for (ii = 0; ii < TEST_COUNT; ii++)
  449.         printf("%20u",node_count[ii]);
  450.     printf("\n----------------------------------------------------------------------------");  
  451.     printf("\nAVL\t\t");
  452.     for (ii = 0; ii < TEST_COUNT; ii++)
  453.         printf("%20llu",df[0][ii]-ds[0][ii]);
  454.     printf("\nExtAVL\t\t");
  455.     for (ii = 0; ii < TEST_COUNT; ii++)
  456.         printf("%20llu",df[1][ii]-ds[1][ii]);
  457.     printf("\nExtAVLrel\t");
  458.     for (ii = 0; ii < TEST_COUNT; ii++)
  459.         printf("%20llu",df[2][ii]-ds[2][ii]);
  460.     printf("\n\n");
  461. }
  462.  
  463.  
  464. /** Insert keys of random sequence and delete tree with delete_min functions.
  465.  */
  466. static void test3(void)
  467. {
  468.     uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
  469.     uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
  470.     unsigned int i,ii;
  471.     avltree_node_t *a;
  472.     extavltree_node_t *b;
  473.     extavlreltree_node_t *c;
  474.  
  475.    
  476.     printf("INSERT nodes with keys of random sequence 1-65536.\n");
  477.     printf("Nodes:\t\t");
  478.     for (ii = 0; ii < TEST_COUNT; ii++) {
  479.         printf("%20u",node_count[ii]);
  480.         keys_prepare(node_count[ii],0);
  481.        
  482.         /*
  483.          * AVL INSERT
  484.          */
  485.         s[0][ii] = get_cycle();
  486.        
  487.         avltree_create(&avltree);
  488.         for (i = 0; i < node_count[ii]; i++) {
  489.             avltree_insert(&avltree,alloc_avltree_node());
  490.         }
  491.            
  492.         f[0][ii] = get_cycle();
  493.         /*
  494.          * AVL DELETE
  495.          */
  496.         ds[0][ii] = get_cycle();
  497.        
  498.         while (avltree.root != NULL) {
  499.             a = avltree_find_min(&avltree);
  500.             avltree_delete_min(&avltree);
  501.             free_avltree_node(a);
  502.         }
  503.            
  504.         df[0][ii] = get_cycle();
  505.  
  506.         /*
  507.          * ExtAVL INSERT
  508.          */
  509.         s[1][ii] = get_cycle();
  510.        
  511.         extavltree_create(&extavltree);
  512.         for (i = 0; i < node_count[ii]; i++) {
  513.             extavltree_insert(&extavltree,alloc_extavltree_node());
  514.         }
  515.        
  516.         f[1][ii] = get_cycle();
  517.         /*
  518.          * ExtAVL DELETE
  519.          */
  520.         ds[1][ii] = get_cycle();
  521.        
  522.         while (extavltree.root != NULL) {
  523.             b = extavltree.head.next;
  524.             extavltree_delete_min(&extavltree);
  525.             free_extavltree_node(b);
  526.         }
  527.            
  528.         df[1][ii] = get_cycle();
  529.         /*
  530.          * ExtAVLrel INSERT
  531.          */
  532.         s[2][ii] = get_cycle();
  533.        
  534.         extavlreltree_create(&extavlreltree);
  535.         for (i = 0; i < node_count[ii]; i++) {
  536.             extavlreltree_insert(&extavlreltree,alloc_extavlreltree_node());
  537.         }
  538.        
  539.         f[2][ii] = get_cycle();
  540.         /*
  541.          * ExtAVLrel DELETE
  542.          */
  543.         ds[2][ii] = get_cycle();
  544.        
  545.         while (extavlreltree.root != NULL) {
  546.             c = extavlreltree.head.next;
  547.             extavlreltree_delete_min(&extavlreltree);
  548.             free_extavlreltree_node(c);
  549.         }
  550.            
  551.         df[2][ii] = get_cycle();
  552.     }
  553.     printf("\n----------------------------------------------------------------------------");  
  554.     printf("\nAVL\t\t");
  555.     for (ii = 0; ii < TEST_COUNT; ii++)
  556.         printf("%20llu",f[0][ii]-s[0][ii]);
  557.     printf("\nExtAVL\t\t");
  558.     for (ii = 0; ii < TEST_COUNT; ii++)
  559.         printf("%20llu",f[1][ii]-s[1][ii]);
  560.     printf("\nExtAVLrel\t");
  561.     for (ii = 0; ii < TEST_COUNT; ii++)
  562.         printf("%20llu",f[2][ii]-s[2][ii]);
  563.     printf("\n\n");
  564.  
  565.     printf("DELETE tree deleting nodes with minimal key\n");
  566.     printf("Nodes:\t\t");
  567.     for (ii = 0; ii < TEST_COUNT; ii++)
  568.         printf("%20u",node_count[ii]);
  569.     printf("\n----------------------------------------------------------------------------");  
  570.     printf("\nAVL\t\t");
  571.     for (ii = 0; ii < TEST_COUNT; ii++)
  572.         printf("%20llu",df[0][ii]-ds[0][ii]);
  573.     printf("\nExtAVL\t\t");
  574.     for (ii = 0; ii < TEST_COUNT; ii++)
  575.         printf("%20llu",df[1][ii]-ds[1][ii]);
  576.     printf("\nExtAVLrel\t");
  577.     for (ii = 0; ii < TEST_COUNT; ii++)
  578.         printf("%20llu",df[2][ii]-ds[2][ii]);
  579.     printf("\n\n");
  580. }
  581.  
  582.  
  583. /** Simulating timeout mechanismus with insert and delete_min operations.
  584.  */
  585. static void test4(void)
  586. {
  587.     uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
  588.     unsigned int i,ii;
  589.     avltree_node_t *a;
  590.     extavltree_node_t *b;
  591.     extavlreltree_node_t *c;
  592.     uint64_t r;
  593.     uint16_t rr;
  594.     unsigned int mn,nc;
  595.  
  596.    
  597.     printf("Simulating timeout mechanismus with %d insert or delete_min operations\n",OPERATION_COUNT);
  598.     printf("Maximum nodes:\t");
  599.     for (ii = 0; ii < TEST_COUNT; ii++) {
  600.         printf("%20u",node_count[ii]);
  601.        
  602.         r = (uint64_t) get_cycle();
  603.         mn = node_count[ii];
  604.        
  605.         /*
  606.          * AVL
  607.          */
  608.         rr = r;
  609.         nc = 0;
  610.         s[0][ii] = get_cycle();
  611.        
  612.         avltree_create(&avltree);
  613.         for (i = 0; i < OPERATION_COUNT; i++) {
  614.             if (((rr % mn) <= nc) && nc) {
  615.                 /*
  616.                  * Delete min.
  617.                  */
  618.                 a = avltree_find_min(&avltree);
  619.                 avltree_delete_min(&avltree);
  620.                 free_avltree_node(a);
  621.                 nc--;
  622.             } else {
  623.                 /*
  624.                  * Insert.
  625.                  */
  626.                 a = alloc_avltree_node();
  627.                 a->key = rr;
  628.                 avltree_insert(&avltree,a);
  629.                 nc++;
  630.             }
  631.             rr += GEN_NUM;
  632.         }
  633.         /*
  634.          * Delete rest tree.
  635.          */
  636.         while (avltree.root != NULL) {
  637.             a = avltree_find_min(&avltree);
  638.             avltree_delete_min(&avltree);
  639.             free_avltree_node(a);
  640.         }  
  641.        
  642.         f[0][ii] = get_cycle();
  643.  
  644.         /*
  645.          * ExtAVL
  646.          */
  647.         rr = r;
  648.         nc = 0;
  649.         s[1][ii] = get_cycle();
  650.        
  651.         extavltree_create(&extavltree);
  652.         for (i = 0; i < OPERATION_COUNT; i++) {
  653.             if (((rr % mn) <= nc) && nc) {
  654.                 /*
  655.                  * Delete min.
  656.                  */
  657.                 b = extavltree.head.next;
  658.                 extavltree_delete_min(&extavltree);
  659.                 free_extavltree_node(b);
  660.                 nc--;
  661.             } else {
  662.                 /*
  663.                  * Insert.
  664.                  */
  665.                 b = alloc_extavltree_node();
  666.                 b->key = rr;
  667.                 extavltree_insert(&extavltree,b);
  668.                 nc++;
  669.             }
  670.             rr += GEN_NUM;
  671.         }
  672.         /*
  673.          * Delete rest tree.
  674.          */
  675.         while (extavltree.root != NULL) {
  676.             b = extavltree.head.next;
  677.             extavltree_delete_min(&extavltree);
  678.             free_extavltree_node(b);
  679.         }
  680.  
  681.         f[1][ii] = get_cycle();
  682.        
  683.         /*
  684.          * ExtAVLrel
  685.          */
  686.         rr = r;
  687.         nc = 0;
  688.         s[2][ii] = get_cycle();
  689.        
  690.         extavlreltree_create(&extavlreltree);
  691.         for (i = 0; i < OPERATION_COUNT; i++) {
  692.             if (((rr % mn) <= nc) && nc) {
  693.                 /*
  694.                  * Delete min.
  695.                  */
  696.                 c = extavlreltree.head.next;
  697.                 //if (ii == 2 && !(i % 100)) printf("DEL key %llu, nc: %u, op: %u\n",c->key,nc,i);
  698.                 extavlreltree_delete_min(&extavlreltree);
  699.                 free_extavlreltree_node(c);
  700.                 nc--;
  701.             } else {
  702.                 /*
  703.                  * Insert.
  704.                  */
  705.                 c = alloc_extavlreltree_node();
  706.                 c->key = rr;
  707.                 //if (ii == 2 && !(i % 100)) printf("INS key %llu, nc: %u, op: %u\n",c->key,nc,i);
  708.                 extavlreltree_insert(&extavlreltree,c);
  709.                 nc++;
  710.             }
  711.             rr += GEN_NUM;
  712.         }
  713.         /*
  714.          * Delete rest tree.
  715.          */
  716.         while (extavlreltree.root != NULL) {
  717.             c = extavlreltree.head.next;
  718.             extavlreltree_delete_min(&extavlreltree);
  719.             free_extavlreltree_node(c);
  720.         }
  721.  
  722.         f[2][ii] = get_cycle();
  723.     }
  724.     printf("\n----------------------------------------------------------------------------");  
  725.     printf("\nAVL\t\t");
  726.     for (ii = 0; ii < TEST_COUNT; ii++)
  727.         printf("%20llu",f[0][ii]-s[0][ii]);
  728.     printf("\nExtAVL\t\t");
  729.     for (ii = 0; ii < TEST_COUNT; ii++)
  730.         printf("%20llu",f[1][ii]-s[1][ii]);
  731.     printf("\nExtAVLrel\t");
  732.     for (ii = 0; ii < TEST_COUNT; ii++)
  733.         printf("%20llu",f[2][ii]-s[2][ii]);
  734.     printf("\n\n");
  735. }
  736.  
  737.  
  738. char * test_timeoutbench1(bool quiet)
  739. {
  740.     printf("\n\tBenchmark test of timeout data structures: AVL, ExtAVL and ExtAVLrel.\n"
  741.         "Run test more than once for eliminating possible distortion due to caching!\n\n");
  742.  
  743.    
  744.     avl_slab = slab_cache_create("avl_slab",sizeof(avltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
  745.     extavl_slab = slab_cache_create("extavl_slab",sizeof(extavltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
  746.     extavlrel_slab = slab_cache_create("extavlrel_slab",sizeof(extavlreltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
  747.  
  748.     if (!alloc_nodes(NODE_COUNT))
  749.         return NULL;
  750.  
  751.     /*
  752.      * store initial cycle count,
  753.      * do test,
  754.      * store finish cycle count,
  755.      * show results
  756.      */
  757.  
  758.     test1();
  759.     test2();
  760.     test3();
  761.     test4();
  762.  
  763.     /*
  764.      * Deallocate arrays.
  765.      */
  766.     free_nodes(NODE_COUNT);
  767.    
  768.     return NULL;
  769. }
  770.