Improved speed of thr_alarm from O(N) to O(1). thr_alarm is used to handle timeouts and kill of connections.

Fixed compiler warnings.
queues.h and queues.c are now based on the UNIREG code and thus made BSD.
Fix code to use new queue() interface. This mostly affects how you access elements in the queue.
If USE_NET_CLEAR is not set, don't clear connection from unexpected characters. This should give a speed up when doing a lot of fast queries.
Fixed some code in ma_ft_boolean_search.c that had not made it from myisam/ft_boolean_search.c


include/queues.h:
  Use UNIREG code base (BSD)
  Changed init_queue() to take all initialization arguments.
  New interface to access elements in queue
include/thr_alarm.h:
  Changed to use time_t instead of ulong (portability)
  Added index_in_queue, to be able to remove random element from queue in O(1)
mysys/queues.c:
  Use UNIREG code base (BSD)
  init_queue() and reinit_queue() now takes more initialization arguments. (No need for init_queue_ex() anymore)
  Now one can tell queue_insert() to store in the element a pointer to where element is in queue. This allows one to remove elements from queue in O(1) instead of O(N)
mysys/thr_alarm.c:
  Use new option in queue() to allow fast removal of elements.
  Do less inside LOCK_alarm mutex.
  This should give a major speed up of thr_alarm usage when there is many threads
sql/create_options.cc:
  Fixed wrong printf
sql/event_queue.cc:
  Use new queue interface()
sql/filesort.cc:
  Use new queue interface()
sql/ha_partition.cc:
  Use new queue interface()
sql/ha_partition.h:
  Fixed compiler warning
sql/item_cmpfunc.cc:
  Fixed compiler warning
sql/item_subselect.cc:
  Use new queue interface()
  Removed not used variable
sql/net_serv.cc:
  If USE_NET_CLEAR is not set, don't clear connection from unexpected characters.
  This should give a speed up when doing a lot of fast queries at the disadvantage that if there is a bug in the client protocol the connection will be dropped instead of being unnoticed.
sql/opt_range.cc:
  Use new queue interface()
  Fixed compiler warnings
sql/uniques.cc:
  Use new queue interface()
storage/maria/ma_ft_boolean_search.c:
  Copy code from myisam/ft_boolean_search.c
  Use new queue interface()
storage/maria/ma_ft_nlq_search.c:
  Use new queue interface()
storage/maria/ma_sort.c:
  Use new queue interface()
storage/maria/maria_pack.c:
  Use new queue interface()
  Use queue_fix() instead of own loop to fix queue.
storage/myisam/ft_boolean_search.c:
  Use new queue interface()
storage/myisam/ft_nlq_search.c:
  Use new queue interface()
storage/myisam/mi_test_all.sh:
  Remove temporary file from last run
storage/myisam/myisampack.c:
  Use new queue interface()
  Use queue_fix() instead of own loop to fix queue.
storage/myisam/sort.c:
  Use new queue interface()
storage/myisammrg/myrg_queue.c:
  Use new queue interface()
storage/myisammrg/myrg_rnext.c:
  Use new queue interface()
storage/myisammrg/myrg_rnext_same.c:
  Use new queue interface()
storage/myisammrg/myrg_rprev.c:
  Use new queue interface()

1 files changed, 145 insertions, 480 deletions

diff --git a/mysys/queues.c b/mysys/queues.c
index 9c85e493141..a65a7f8914c 100644
--- a/mysys/queues.c
+++ b/mysys/queues.c
@@ -1,25 +1,42 @@
-/* Copyright (C) 2000, 2005 MySQL AB
-
-   This program is free software; you can redistribute it and/or modify
-   it under the terms of the GNU General Public License as published by
-   the Free Software Foundation; version 2 of the License.
-
-   This program is distributed in the hope that it will be useful,
-   but WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-   GNU General Public License for more details.
-
-   You should have received a copy of the GNU General Public License
-   along with this program; if not, write to the Free Software
-   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+/* Copyright (C) 2010 Monty Program Ab
+   All Rights reserved
+
+   Redistribution and use in source and binary forms, with or without
+   modification, are permitted provided that the following conditions are met:
+    * Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+    * Redistributions in binary form must reproduce the following disclaimer
+      in the documentation and/or other materials provided with the
+      distribution.
+
+  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+  <COPYRIGHT HOLDER> BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+  USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+  ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+  OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+  SUCH DAMAGE.
+*/
 
 /*
+  This code originates from the Unireg project.
+
   Code for generell handling of priority Queues.
   Implemention of queues from "Algoritms in C" by Robert Sedgewick.
-  An optimisation of _downheap suggested in Exercise 7.51 in "Data
-  Structures & Algorithms in C++" by Mark Allen Weiss, Second Edition
-  was implemented by Mikael Ronstrom 2005. Also the O(N) algorithm
-  of queue_fix was implemented.
+
+  The queue can optionally store the position in queue in the element
+  that is in the queue. This allows one to remove any element from the queue
+  in O(1) time.
+
+  Optimisation of _downheap() and queue_fix() is inspired by code done
+  by Mikael Ronström, based on an optimisation of _downheap from
+  Exercise 7.51 in "Data Structures & Algorithms in C++" by Mark Allen
+  Weiss, Second Edition.
 */
 
 #include "mysys_priv.h"
@@ -39,6 +56,10 @@
     max_at_top		Set to 1 if you want biggest element on top.
     compare		Compare function for elements, takes 3 arguments.
     first_cmp_arg	First argument to compare function
+    offset_to_queue_pos If <> 0, then offset+1 in element to store position
+                        in queue (for fast delete of element in queue)
+    auto_extent         When the queue is full and there is insert operation
+                        extend the queue.
 
   NOTES
     Will allocate max_element pointers for queue array
@@ -50,74 +71,33 @@
 
 int init_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
 	       pbool max_at_top, int (*compare) (void *, uchar *, uchar *),
-	       void *first_cmp_arg)
+	       void *first_cmp_arg, uint offset_to_queue_pos,
+               uint auto_extent)
+               
 {
   DBUG_ENTER("init_queue");
-  if ((queue->root= (uchar **) my_malloc((max_elements+1)*sizeof(void*),
+  if ((queue->root= (uchar **) my_malloc((max_elements + 1) * sizeof(void*),
 					 MYF(MY_WME))) == 0)
     DBUG_RETURN(1);
-  queue->elements=0;
-  queue->compare=compare;
-  queue->first_cmp_arg=first_cmp_arg;
-  queue->max_elements=max_elements;
-  queue->offset_to_key=offset_to_key;
+  queue->elements=      	0;
+  queue->compare=       	compare;
+  queue->first_cmp_arg= 	first_cmp_arg;
+  queue->max_elements=  	max_elements;
+  queue->offset_to_key= 	offset_to_key;
+  queue->offset_to_queue_pos=   offset_to_queue_pos;
+  queue->auto_extent=   	auto_extent;
   queue_set_max_at_top(queue, max_at_top);
   DBUG_RETURN(0);
 }
 
 
-
-/*
-  Init queue, uses init_queue internally for init work but also accepts
-  auto_extent as parameter
-
-  SYNOPSIS
-    init_queue_ex()
-    queue		Queue to initialise
-    max_elements	Max elements that will be put in queue
-    offset_to_key	Offset to key in element stored in queue
-			Used when sending pointers to compare function
-    max_at_top		Set to 1 if you want biggest element on top.
-    compare		Compare function for elements, takes 3 arguments.
-    first_cmp_arg	First argument to compare function
-    auto_extent         When the queue is full and there is insert operation
-                        extend the queue.
-
-  NOTES
-    Will allocate max_element pointers for queue array
-
-  RETURN
-    0	ok
-    1	Could not allocate memory
-*/
-
-int init_queue_ex(QUEUE *queue, uint max_elements, uint offset_to_key,
-	       pbool max_at_top, int (*compare) (void *, uchar *, uchar *),
-	       void *first_cmp_arg, uint auto_extent)
-{
-  int ret;
-  DBUG_ENTER("init_queue_ex");
-
-  if ((ret= init_queue(queue, max_elements, offset_to_key, max_at_top, compare,
-                       first_cmp_arg)))
-    DBUG_RETURN(ret);
-  
-  queue->auto_extent= auto_extent;
-  DBUG_RETURN(0);
-}
-
 /*
   Reinitialize queue for other usage
 
   SYNOPSIS
     reinit_queue()
     queue		Queue to initialise
-    max_elements	Max elements that will be put in queue
-    offset_to_key	Offset to key in element stored in queue
-			Used when sending pointers to compare function
-    max_at_top		Set to 1 if you want biggest element on top.
-    compare		Compare function for elements, takes 3 arguments.
-    first_cmp_arg	First argument to compare function
+    For rest of arguments, see init_queue() above
 
   NOTES
     This will delete all elements from the queue.  If you don't want this,
@@ -125,21 +105,23 @@ int init_queue_ex(QUEUE *queue, uint max_elements, uint offset_to_key,
 
   RETURN
     0			ok
-    EE_OUTOFMEMORY	Wrong max_elements
+    1			Wrong max_elements; Queue has old size
 */
 
 int reinit_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
 		 pbool max_at_top, int (*compare) (void *, uchar *, uchar *),
-		 void *first_cmp_arg)
+		 void *first_cmp_arg, uint offset_to_queue_pos,
+                 uint auto_extent)
 {
   DBUG_ENTER("reinit_queue");
-  queue->elements=0;
-  queue->compare=compare;
-  queue->first_cmp_arg=first_cmp_arg;
-  queue->offset_to_key=offset_to_key;
+  queue->elements=		0;
+  queue->compare=		compare;
+  queue->first_cmp_arg=		first_cmp_arg;
+  queue->offset_to_key=		offset_to_key;
+  queue->offset_to_queue_pos=   offset_to_queue_pos;
+  queue->auto_extent= 		auto_extent;
   queue_set_max_at_top(queue, max_at_top);
-  resize_queue(queue, max_elements);
-  DBUG_RETURN(0);
+  DBUG_RETURN(resize_queue(queue, max_elements));
 }
 
 
@@ -167,8 +149,8 @@ int resize_queue(QUEUE *queue, uint max_elements)
   if (queue->max_elements == max_elements)
     DBUG_RETURN(0);
   if ((new_root= (uchar **) my_realloc((void *)queue->root,
-				      (max_elements+1)*sizeof(void*),
-				      MYF(MY_WME))) == 0)
+                                       (max_elements + 1)* sizeof(void*),
+                                       MYF(MY_WME))) == 0)
     DBUG_RETURN(1);
   set_if_smaller(queue->elements, max_elements);
   queue->max_elements= max_elements;
@@ -197,39 +179,58 @@ void delete_queue(QUEUE *queue)
   if (queue->root)
   {
     my_free((uchar*) queue->root,MYF(0));
-    queue->root=0;
+    queue->root=0;                              /* Allow multiple calls */
   }
   DBUG_VOID_RETURN;
 }
 
 
-	/* Code for insert, search and delete of elements */
+/*
+  Insert element in queue
+
+  SYNOPSIS
+    queue_insert()
+    queue		Queue to use
+    element		Element to insert
+*/
 
 void queue_insert(register QUEUE *queue, uchar *element)
 {
   reg2 uint idx, next;
+  uint offset_to_queue_pos= queue->offset_to_queue_pos;
   DBUG_ASSERT(queue->elements < queue->max_elements);
-  queue->root[0]= element;
+
   idx= ++queue->elements;
   /* max_at_top swaps the comparison if we want to order by desc */
-  while ((queue->compare(queue->first_cmp_arg,
+  while (idx > 1 &&
+         (queue->compare(queue->first_cmp_arg,
                          element + queue->offset_to_key,
                          queue->root[(next= idx >> 1)] +
                          queue->offset_to_key) * queue->max_at_top) < 0)
   {
     queue->root[idx]= queue->root[next];
+    if (offset_to_queue_pos)
+      (*(uint*) (queue->root[idx] + offset_to_queue_pos-1))= idx;
     idx= next;
   }
   queue->root[idx]= element;
+  if (offset_to_queue_pos)
+    (*(uint*) (element+ offset_to_queue_pos-1))= idx;
 }
 
+
 /*
-  Does safe insert. If no more space left on the queue resize it.
-  Return codes:
-    0 - OK
-    1 - Cannot allocate more memory
-    2 - auto_extend is 0, the operation would
-  
+  Like queue_insert, but resize queue if queue is full
+
+  SYNOPSIS
+    queue_insert_safe()
+    queue		Queue to use
+    element		Element to insert
+
+  RETURN
+    0	OK
+    1	Cannot allocate more memory
+    2   auto_extend is 0; No insertion done
 */
 
 int queue_insert_safe(register QUEUE *queue, uchar *element)
@@ -239,7 +240,7 @@ int queue_insert_safe(register QUEUE *queue, uchar *element)
   {
     if (!queue->auto_extent)
       return 2;
-    else if (resize_queue(queue, queue->max_elements + queue->auto_extent))
+    if (resize_queue(queue, queue->max_elements + queue->auto_extent))
       return 1;
   }
   
@@ -248,40 +249,48 @@ int queue_insert_safe(register QUEUE *queue, uchar *element)
 }
 
 
-	/* Remove item from queue */
-	/* Returns pointer to removed element */
+/*
+  Remove item from queue
+
+  SYNOPSIS
+    queue_remove()
+    queue		Queue to use
+    element		Index of element to remove.
+			First element in queue is 'queue_first_element(queue)'
+
+  RETURN
+   pointer to removed element
+*/
 
 uchar *queue_remove(register QUEUE *queue, uint idx)
 {
   uchar *element;
-  DBUG_ASSERT(idx < queue->max_elements);
-  element= queue->root[++idx];  /* Intern index starts from 1 */
-  queue->root[idx]= queue->root[queue->elements--];
-  _downheap(queue, idx);
+  DBUG_ASSERT(idx >= 1 && idx <= queue->elements);
+  element= queue->root[idx];
+  _downheap(queue, idx, queue->root[queue->elements--]);
   return element;
 }
 
-	/* Fix when element on top has been replaced */
 
-#ifndef queue_replaced
-void queue_replaced(QUEUE *queue)
-{
-  _downheap(queue,1);
-}
-#endif
+/*
+  Add element to fixed position and update heap
 
-#ifndef OLD_VERSION
+  SYNOPSIS
+    _downheap()
+    queue	Queue to use
+    idx         Index of element to change
+    element     Element to store at 'idx'
+*/
 
-void _downheap(register QUEUE *queue, uint idx)
+void _downheap(register QUEUE *queue, uint start_idx, uchar *element)
 {
-  uchar *element;
-  uint elements,half_queue,offset_to_key, next_index;
+  uint elements,half_queue,offset_to_key, next_index, offset_to_queue_pos;
+  register uint idx= start_idx;
   my_bool first= TRUE;
-  uint start_idx= idx;
 
   offset_to_key=queue->offset_to_key;
-  element=queue->root[idx];
-  half_queue=(elements=queue->elements) >> 1;
+  offset_to_queue_pos= queue->offset_to_queue_pos;
+  half_queue= (elements= queue->elements) >> 1;
 
   while (idx <= half_queue)
   {
@@ -298,393 +307,49 @@ void _downheap(register QUEUE *queue, uint idx)
                           element+offset_to_key) * queue->max_at_top) >= 0)))
     {
       queue->root[idx]= element;
+      if (offset_to_queue_pos)
+        (*(uint*) (element + offset_to_queue_pos-1))= idx;
       return;
     }
-    queue->root[idx]=queue->root[next_index];
-    idx=next_index;
     first= FALSE;
-  }
-
-  next_index= idx >> 1;
-  while (next_index > start_idx)
-  {
-    if ((queue->compare(queue->first_cmp_arg,
-                       queue->root[next_index]+offset_to_key,
-                       element+offset_to_key) *
-         queue->max_at_top) < 0)
-      break;
-    queue->root[idx]=queue->root[next_index];
+    queue->root[idx]= queue->root[next_index];
+    if (offset_to_queue_pos)
+      (*(uint*) (queue->root[idx] + offset_to_queue_pos-1))= idx;
     idx=next_index;
-    next_index= idx >> 1;
   }
-  queue->root[idx]=element;
-}
 
-#else
   /*
-    The old _downheap version is kept for comparisons with the benchmark
-    suit or new benchmarks anyone wants to run for comparisons.
+    Insert the element into the right position. This is the same code
+    as we have in queue_insert()
   */
-	/* Fix heap when index have changed */
-void _downheap(register QUEUE *queue, uint idx)
-{
-  uchar *element;
-  uint elements,half_queue,next_index,offset_to_key;
-
-  offset_to_key=queue->offset_to_key;
-  element=queue->root[idx];
-  half_queue=(elements=queue->elements) >> 1;
-
-  while (idx <= half_queue)
+  while ((next_index= (idx >> 1)) > start_idx &&
+         queue->compare(queue->first_cmp_arg,
+                        element+offset_to_key,
+                        queue->root[next_index]+offset_to_key)*
+         queue->max_at_top < 0)
   {
-    next_index=idx+idx;
-    if (next_index < elements &&
-	(queue->compare(queue->first_cmp_arg,
-			queue->root[next_index]+offset_to_key,
-			queue->root[next_index+1]+offset_to_key) *
-	 queue->max_at_top) > 0)
-      next_index++;
-    if ((queue->compare(queue->first_cmp_arg,
-                        queue->root[next_index]+offset_to_key,
-                        element+offset_to_key) * queue->max_at_top) >= 0)
-      break;
-    queue->root[idx]=queue->root[next_index];
-    idx=next_index;
+    queue->root[idx]= queue->root[next_index];
+    if (offset_to_queue_pos)
+      (*(uint*) (queue->root[idx] + offset_to_queue_pos-1))= idx;
+    idx= next_index;
   }
-  queue->root[idx]=element;
+  queue->root[idx]= element;
+  if (offset_to_queue_pos)
+    (*(uint*) (element + offset_to_queue_pos-1))= idx;
 }
 
 
-#endif
-
 /*
   Fix heap when every element was changed.
+
+  SYNOPSIS
+    queue_fix()
+    queue	Queue to use
 */
 
 void queue_fix(QUEUE *queue)
 {
   uint i;
   for (i= queue->elements >> 1; i > 0; i--)
-    _downheap(queue, i);
-}
-
-#ifdef MAIN
- /*
-   A test program for the priority queue implementation.
-   It can also be used to benchmark changes of the implementation
-   Build by doing the following in the directory mysys
-   make test_priority_queue
-   ./test_priority_queue
-
-   Written by Mikael Ronström, 2005
- */
-
-static uint num_array[1025];
-static uint tot_no_parts= 0;
-static uint tot_no_loops= 0;
-static uint expected_part= 0;
-static uint expected_num= 0;
-static bool max_ind= 0;
-static bool fix_used= 0;
-static ulonglong start_time= 0;
-
-static bool is_divisible_by(uint num, uint divisor)
-{
-  uint quotient= num / divisor;
-  if (quotient * divisor == num)
-    return TRUE;
-  return FALSE;
-}
-
-void calculate_next()
-{
-  uint part= expected_part, num= expected_num;
-  uint no_parts= tot_no_parts;
-  if (max_ind)
-  {
-    do
-    {
-      while (++part <= no_parts)
-      {
-        if (is_divisible_by(num, part) &&
-            (num <= ((1 << 21) + part)))
-        {
-          expected_part= part;
-          expected_num= num;
-          return;
-        }
-      }
-      part= 0;
-    } while (--num);
-  }
-  else
-  {
-    do
-    {
-      while (--part > 0)
-      {
-        if (is_divisible_by(num, part))
-        {
-          expected_part= part;
-          expected_num= num;
-          return;
-        }
-      }
-      part= no_parts + 1;
-    } while (++num);
-  }
-}
-
-void calculate_end_next(uint part)
-{
-  uint no_parts= tot_no_parts, num;
-  num_array[part]= 0;
-  if (max_ind)
-  {
-    expected_num= 0;
-    for (part= no_parts; part > 0 ; part--)
-    {
-      if (num_array[part])
-      {
-        num= num_array[part] & 0x3FFFFF;
-        if (num >= expected_num)
-        {
-          expected_num= num;
-          expected_part= part;
-        }
-      }
-    }
-    if (expected_num == 0)
-      expected_part= 0;
-  }
-  else
-  {
-    expected_num= 0xFFFFFFFF;
-    for (part= 1; part <= no_parts; part++)
-    {
-      if (num_array[part])
-      {
-        num= num_array[part] & 0x3FFFFF;
-        if (num <= expected_num)
-        {
-          expected_num= num;
-          expected_part= part;
-        }
-      }
-    }
-    if (expected_num == 0xFFFFFFFF)
-      expected_part= 0;
-  }
-  return;
-}
-static int test_compare(void *null_arg, uchar *a, uchar *b)
-{
-  uint a_num= (*(uint*)a) & 0x3FFFFF;
-  uint b_num= (*(uint*)b) & 0x3FFFFF;
-  uint a_part, b_part;
-  if (a_num > b_num)
-    return +1;
-  if (a_num < b_num)
-    return -1;
-  a_part= (*(uint*)a) >> 22;
-  b_part= (*(uint*)b) >> 22;
-  if (a_part < b_part)
-    return +1;
-  if (a_part > b_part)
-    return -1;
-  return 0;
-}
-
-bool check_num(uint num_part)
-{
-  uint part= num_part >> 22;
-  uint num= num_part & 0x3FFFFF;
-  if (part == expected_part)
-    if (num == expected_num)
-      return FALSE;
-  printf("Expect part %u Expect num 0x%x got part %u num 0x%x max_ind %u fix_used %u \n",
-          expected_part, expected_num, part, num, max_ind, fix_used);
-  return TRUE;
-}
-
-
-void perform_insert(QUEUE *queue)
-{
-  uint i= 1, no_parts= tot_no_parts;
-  uint backward_start= 0;
-
-  expected_part= 1;
-  expected_num= 1;
- 
-  if (max_ind)
-    backward_start= 1 << 21;
-
-  do
-  {
-    uint num= (i + backward_start);
-    if (max_ind)
-    {
-      while (!is_divisible_by(num, i))
-        num--;
-      if (max_ind && (num > expected_num ||
-                      (num == expected_num && i < expected_part)))
-      {
-        expected_num= num;
-        expected_part= i;
-      }
-    }
-    num_array[i]= num + (i << 22);
-    if (fix_used)
-      queue_element(queue, i-1)= (uchar*)&num_array[i];
-    else
-      queue_insert(queue, (uchar*)&num_array[i]);
-  } while (++i <= no_parts);
-  if (fix_used)
-  {
-    queue->elements= no_parts;
-    queue_fix(queue);
-  }
-}
-
-bool perform_ins_del(QUEUE *queue, bool max_ind)
-{
-  uint i= 0, no_loops= tot_no_loops, j= tot_no_parts;
-  do
-  {
-    uint num_part= *(uint*)queue_top(queue);
-    uint part= num_part >> 22;
-    if (check_num(num_part))
-      return TRUE;
-    if (j++ >= no_loops)
-    {
-      calculate_end_next(part);
-      queue_remove(queue, (uint) 0);
-    }
-    else
-    {
-      calculate_next();
-      if (max_ind)
-        num_array[part]-= part;
-      else
-        num_array[part]+= part;
-      queue_top(queue)= (uchar*)&num_array[part];
-      queue_replaced(queue);
-    }
-  } while (++i < no_loops);
-  return FALSE;
-}
-
-bool do_test(uint no_parts, uint l_max_ind, bool l_fix_used)
-{
-  QUEUE queue;
-  bool result;
-  max_ind= l_max_ind;
-  fix_used= l_fix_used;
-  init_queue(&queue, no_parts, 0, max_ind, test_compare, NULL);
-  tot_no_parts= no_parts;
-  tot_no_loops= 1024;
-  perform_insert(&queue);
-  if ((result= perform_ins_del(&queue, max_ind)))
-  delete_queue(&queue);
-  if (result)
-  {
-    printf("Error\n");
-    return TRUE;
-  }
-  return FALSE;
-}
-
-static void start_measurement()
-{
-  start_time= my_getsystime();
-}
-
-static void stop_measurement()
-{
-  ulonglong stop_time= my_getsystime();
-  uint time_in_micros;
-  stop_time-= start_time;
-  stop_time/= 10; /* Convert to microseconds */
-  time_in_micros= (uint)stop_time;
-  printf("Time expired is %u microseconds \n", time_in_micros);
-}
-
-static void benchmark_test()
-{
-  QUEUE queue_real;
-  QUEUE *queue= &queue_real;
-  uint i, add;
-  fix_used= TRUE;
-  max_ind= FALSE;
-  tot_no_parts= 1024;
-  init_queue(queue, tot_no_parts, 0, max_ind, test_compare, NULL);
-  /*
-    First benchmark whether queue_fix is faster than using queue_insert
-    for sizes of 16 partitions.
-  */
-  for (tot_no_parts= 2, add=2; tot_no_parts < 128;
-       tot_no_parts+= add, add++)
-  {
-    printf("Start benchmark queue_fix, tot_no_parts= %u \n", tot_no_parts);
-    start_measurement();
-    for (i= 0; i < 128; i++)
-    {
-      perform_insert(queue);
-      queue_remove_all(queue);
-    }
-    stop_measurement();
-
-    fix_used= FALSE;
-    printf("Start benchmark queue_insert\n");
-    start_measurement();
-    for (i= 0; i < 128; i++)
-    {
-      perform_insert(queue);
-      queue_remove_all(queue);
-    }
-    stop_measurement();
-  }
-  /*
-    Now benchmark insertion and deletion of 16400 elements.
-    Used in consecutive runs this shows whether the optimised _downheap
-    is faster than the standard implementation.
-  */
-  printf("Start benchmarking _downheap \n");
-  start_measurement();
-  perform_insert(queue);
-  for (i= 0; i < 65536; i++)
-  {
-    uint num, part;
-    num= *(uint*)queue_top(queue);
-    num+= 16;
-    part= num >> 22;
-    num_array[part]= num;
-    queue_top(queue)= (uchar*)&num_array[part];
-    queue_replaced(queue);
-  }
-  for (i= 0; i < 16; i++)
-    queue_remove(queue, (uint) 0);
-  queue_remove_all(queue);
-  stop_measurement();
-}
-
-int main()
-{
-  int i, add= 1;
-  for (i= 1; i < 1024; i+=add, add++)
-  {
-    printf("Start test for priority queue of size %u\n", i);
-    if (do_test(i, 0, 1))
-      return -1;
-    if (do_test(i, 1, 1))
-      return -1;
-    if (do_test(i, 0, 0))
-      return -1;
-    if (do_test(i, 1, 0))
-      return -1;
-  }
-  benchmark_test();
-  printf("OK\n");
-  return 0;
+    _downheap(queue, i, queue_element(queue, i));
 }
-#endif