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