diff options
Diffstat (limited to 'mysys/queues.c')
| -rw-r--r-- | mysys/queues.c | 141 |
1 files changed, 141 insertions, 0 deletions
diff --git a/mysys/queues.c b/mysys/queues.c new file mode 100644 index 00000000000..f33856b892d --- /dev/null +++ b/mysys/queues.c @@ -0,0 +1,141 @@ +/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Library General Public + License as published by the Free Software Foundation; either + version 2 of the License, or (at your option) any later version. + + This library 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 + Library General Public License for more details. + + You should have received a copy of the GNU Library General Public + License along with this library; 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 <queues.h> + + + /* The actuall code for handling queues */ + +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); +} + +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; + +#ifndef DBUG_OFF + if (queue->elements < queue->max_elements) +#endif + { + queue->root[0]=element; + idx= ++queue->elements; + + 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; + } +} + + /* 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 *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; +} |