path: root/mysys/queues.c

/* Copyright (C) 2000 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; either version 2 of the License, or
   (at your option) any later version.

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

#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,
	       pbool max_at_top, int (*compare) (void *, byte *, byte *),
	       void *first_cmp_arg)
{
  DBUG_ENTER("init_queue");
  if ((queue->root= (byte **) 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->max_at_top= max_at_top ? (-1 ^ 1) : 0;
  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

  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,
		 pbool max_at_top, int (*compare) (void *, byte *, byte *),
		 void *first_cmp_arg)
{
  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->max_at_top= max_at_top ? (-1 ^ 1) : 0;
  resize_queue(queue, max_elements);
  DBUG_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)
{
  byte **new_root;
  DBUG_ENTER("resize_queue");
  if (queue->max_elements == max_elements)
    DBUG_RETURN(0);
  if ((new_root= (byte **) my_realloc((void *)queue->root,
				      (max_elements+1)*sizeof(void*),
				      MYF(MY_WME))) == 0)
    DBUG_RETURN(1);
  set_if_smaller(queue->elements, max_elements);
  queue->max_elements= max_elements;
  queue->root= new_root;
  DBUG_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)
{
  DBUG_ENTER("delete_queue");
  if (queue->root)
  {
    my_free((gptr) queue->root,MYF(0));
    queue->root=0;
  }
  DBUG_VOID_RETURN;
}


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

void queue_insert(register QUEUE *queue, byte *element)
{
  reg2 uint idx,next;
  int cmp;

#ifndef DBUG_OFF
  if (queue->elements < queue->max_elements)
#endif
  {
    queue->root[0]=element;
    idx= ++queue->elements;

    /* max_at_top swaps the comparison if we want to order by desc */
    while ((cmp=queue->compare(queue->first_cmp_arg,
			       element+queue->offset_to_key,
			       queue->root[(next=idx >> 1)] +
			       queue->offset_to_key)) &&
	   (cmp ^ queue->max_at_top) < 0)
    {
      queue->root[idx]=queue->root[next];
      idx=next;
    }
    queue->root[idx]=element;
  }
}

	/* Remove item from queue */
	/* Returns pointer to removed element */

byte *queue_remove(register QUEUE *queue, uint idx)
{
#ifndef DBUG_OFF
  if (idx >= queue->max_elements)
    return 0;
#endif
  {
    byte *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

	/* Fix heap when index have changed */

void _downheap(register QUEUE *queue, uint idx)
{
  byte *element;
  uint elements,half_queue,next_index,offset_to_key;
  int cmp;

  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 ((cmp=queue->compare(queue->first_cmp_arg,
			    queue->root[next_index]+offset_to_key,
			    element+offset_to_key)) == 0 ||
	(cmp ^ queue->max_at_top) > 0)
      break;
    queue->root[idx]=queue->root[next_index];
    idx=next_index;
  }
  queue->root[idx]=element;
}


static int queue_fix_cmp(QUEUE *queue, void **a, void **b)
{
  return queue->compare(queue->first_cmp_arg,
			(byte*) (*a)+queue->offset_to_key,
			(byte*) (*b)+queue->offset_to_key);
}

/*
  Fix heap when every element was changed,
  actually, it can be done better, in linear time, not in n*log(n)
*/

void queue_fix(QUEUE *queue)
{
  qsort2(queue->root+1,queue->elements, sizeof(void *),
	 (qsort2_cmp)queue_fix_cmp, queue);
}