merge.

checkpoint.
does not compile.

1 files changed, 161 insertions, 474 deletions

diff --git a/mysys/queues.c b/mysys/queues.c
index 25a310c0752..418163d7c58 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;
@@ -195,38 +177,57 @@ void delete_queue(QUEUE *queue)
 {
   DBUG_ENTER("delete_queue");
   my_free(queue->root);
-  queue->root= NULL;
+  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)
@@ -236,7 +237,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;
   }
   
@@ -245,40 +246,51 @@ 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'
+
+  NOTE
+    This only works if element is >= all elements <= start_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)
   {
@@ -295,393 +307,68 @@ 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);
+    _downheap(queue, i, queue_element(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();
+/*
+  Change element at fixed position
 
-    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();
-}
+  SYNOPSIS
+    queue_replace()
+    queue	Queue to use
+    idx         Index of element to change
+    element     Element to store at 'idx'
+*/
 
-int main()
+void queue_replace(QUEUE *queue, uint idx)
 {
-  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;
+  uchar *element= queue->root[idx];
+  DBUG_ASSERT(idx >= 1 && idx <= queue->elements);
+  queue_remove(queue, idx);
+  queue_insert(queue, element);
 }
-#endif