summaryrefslogtreecommitdiff
path: root/mysys/queues.c
diff options
context:
space:
mode:
Diffstat (limited to 'mysys/queues.c')
-rw-r--r--mysys/queues.c141
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;
+}