~drizzle-trunk/drizzle/development

/* 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 */

/*

  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.

*/

#include "mysys_priv.h"

#include "mysys_err.h"

#include <queues.h>

/*

  Init queue

  SYNOPSIS

    init_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

  NOTES

    Will allocate max_element pointers for queue array

  RETURN

    0	ok

    1	Could not allocate memory

*/

int init_queue(QUEUE *queue, uint max_elements, uint offset_to_key,

	       bool max_at_top, int (*compare) (void *, uchar *, uchar *),

	       void *first_cmp_arg)

{

  if ((queue->root= (uchar **) my_malloc((max_elements+1)*sizeof(void*),

					 MYF(MY_WME))) == 0)

    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_set_max_at_top(queue, max_at_top);

  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,

	       bool max_at_top, int (*compare) (void *, uchar *, uchar *),

	       void *first_cmp_arg, uint auto_extent)

{

  int ret;

  if ((ret= init_queue(queue, max_elements, offset_to_key, max_at_top, compare,

                       first_cmp_arg)))

    return(ret);

  queue->auto_extent= auto_extent;

  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

  NOTES

    This will delete all elements from the queue.  If you don't want this,

    use resize_queue() instead.

  RETURN

    0			ok

    EE_OUTOFMEMORY	Wrong max_elements

*/

int reinit_queue(QUEUE *queue, uint max_elements, uint offset_to_key,

		 bool max_at_top, int (*compare) (void *, uchar *, uchar *),

		 void *first_cmp_arg)

{

  queue->elements=0;

  queue->compare=compare;

  queue->first_cmp_arg=first_cmp_arg;

  queue->offset_to_key=offset_to_key;

  queue_set_max_at_top(queue, max_at_top);

  resize_queue(queue, max_elements);

  return(0);

}

/*

  Resize queue

  SYNOPSIS

    resize_queue()

    queue			Queue

    max_elements		New max size for queue

  NOTES

    If you resize queue to be less than the elements you have in it,

    the extra elements will be deleted

  RETURN

    0	ok

    1	Error.  In this case the queue is unchanged

*/

int resize_queue(QUEUE *queue, uint max_elements)

{

  uchar **new_root;

  if (queue->max_elements == max_elements)

    return(0);

  if ((new_root= (uchar **) my_realloc((void *)queue->root,

				      (max_elements+1)*sizeof(void*),

				      MYF(MY_WME))) == 0)

    return(1);

  set_if_smaller(queue->elements, max_elements);

  queue->max_elements= max_elements;

  queue->root= new_root;

  return(0);

}

/*

  Delete queue

  SYNOPSIS

   delete_queue()

   queue		Queue to delete

  IMPLEMENTATION

    Just free allocated memory.

  NOTES

    Can be called safely multiple times

*/

void delete_queue(QUEUE *queue)

{

  if (queue->root)

  {

    my_free((uchar*) queue->root,MYF(0));

    queue->root=0;

  }

  return;

}

	/* Code for insert, search and delete of elements */

void queue_insert(register QUEUE *queue, uchar *element)

{

  register uint idx, next;

  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,

                         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];

    idx= next;

  }

  queue->root[idx]= element;

}

/*

  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

*/

int queue_insert_safe(register QUEUE *queue, uchar *element)

{

  if (queue->elements == queue->max_elements)

  {

    if (!queue->auto_extent)

      return 2;

    else if (resize_queue(queue, queue->max_elements + queue->auto_extent))

      return 1;

  }

  queue_insert(queue, element);

  return 0;

}

	/* Remove item from queue */

	/* Returns pointer to removed element */

uchar *queue_remove(register QUEUE *queue, uint idx)

{

  uchar *element;

  assert(idx < queue->max_elements);

  element= queue->root[++idx];  /* Intern index starts from 1 */

  queue->root[idx]= queue->root[queue->elements--];

  _downheap(queue, idx);

  return element;

}

	/* Fix when element on top has been replaced */

#ifndef queue_replaced

void queue_replaced(QUEUE *queue)

{

  _downheap(queue,1);

}

#endif

#ifndef OLD_VERSION

void _downheap(register QUEUE *queue, uint idx)

{

  uchar *element;

  uint elements,half_queue,offset_to_key, next_index;

  bool first= true;

  uint start_idx= idx;

  offset_to_key=queue->offset_to_key;

  element=queue->root[idx];

  half_queue=(elements=queue->elements) >> 1;

  while (idx <= half_queue)

  {

    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 (first && 

        (((queue->compare(queue->first_cmp_arg,

                          queue->root[next_index]+offset_to_key,

                          element+offset_to_key) * queue->max_at_top) >= 0)))

    {

      queue->root[idx]= element;

      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];

    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.

  */

	/* 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)

  {

    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]=element;

}

#endif

/*

  Fix heap when every element was changed.

*/

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 uint64_t 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()

{

  uint64_t 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;

}

#endif