summaryrefslogtreecommitdiffstats
path: root/mysys/queues.c
diff options
context:
space:
mode:
Diffstat (limited to 'mysys/queues.c')
-rw-r--r--mysys/queues.c386
1 files changed, 386 insertions, 0 deletions
diff --git a/mysys/queues.c b/mysys/queues.c
new file mode 100644
index 00000000..0a1149bf
--- /dev/null
+++ b/mysys/queues.c
@@ -0,0 +1,386 @@
+/* Copyright (C) 2010 Monty Program Ab
+ All Rights reserved
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
+ * Redistributions of source code must retain the above copyright
+ notice, this list of conditions and the following disclaimer.
+ * Redistributions in binary form must reproduce the following disclaimer
+ in the documentation and/or other materials provided with the
+ distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ <COPYRIGHT HOLDER> BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
+ USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
+ OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ SUCH DAMAGE.
+*/
+
+/*
+ This code originates from the Unireg project.
+
+ Code for generell handling of priority Queues.
+ Implementation of queues from "Algorithms in C" by Robert Sedgewick.
+
+ The queue can optionally store the position in queue in the element
+ that is in the queue. This allows one to remove any element from the queue
+ in O(1) time.
+
+ Optimisation of _downheap() and queue_fix() is inspired by code done
+ by Mikael Ronström, based on an optimisation of _downheap from
+ Exercise 7.51 in "Data Structures & Algorithms in C++" by Mark Allen
+ Weiss, Second Edition.
+*/
+
+#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
+ offset_to_queue_pos If <> 0, then offset+1 in element to store position
+ in queue (for fast delete of element in queue)
+ 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(QUEUE *queue, uint max_elements, uint offset_to_key,
+ my_bool max_at_top, int (*compare) (void *, uchar *, uchar *),
+ void *first_cmp_arg, uint offset_to_queue_pos,
+ uint auto_extent)
+{
+ DBUG_ENTER("init_queue");
+ if ((queue->root= (uchar **) my_malloc(key_memory_QUEUE,
+ (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->offset_to_queue_pos= offset_to_queue_pos;
+ queue->auto_extent= auto_extent;
+ queue_set_max_at_top(queue, max_at_top);
+ DBUG_RETURN(0);
+}
+
+
+/*
+ Reinitialize queue for other usage
+
+ SYNOPSIS
+ reinit_queue()
+ queue Queue to initialise
+ For rest of arguments, see init_queue() above
+
+ NOTES
+ This will delete all elements from the queue. If you don't want this,
+ use resize_queue() instead.
+
+ RETURN
+ 0 ok
+ 1 Wrong max_elements; Queue has old size
+*/
+
+int reinit_queue(QUEUE *queue, uint max_elements, uint offset_to_key,
+ my_bool max_at_top, int (*compare) (void *, uchar *, uchar *),
+ void *first_cmp_arg, uint offset_to_queue_pos,
+ uint auto_extent)
+{
+ 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->offset_to_queue_pos= offset_to_queue_pos;
+ queue->auto_extent= auto_extent;
+ queue_set_max_at_top(queue, max_at_top);
+ DBUG_RETURN(resize_queue(queue, max_elements));
+}
+
+
+/*
+ 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;
+ DBUG_ENTER("resize_queue");
+ if (queue->max_elements == max_elements)
+ DBUG_RETURN(0);
+ if ((new_root= (uchar **) my_realloc(key_memory_QUEUE, (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");
+ my_free(queue->root);
+ queue->root=0; /* Allow multiple calls */
+ DBUG_VOID_RETURN;
+}
+
+
+static void insert_at(QUEUE *queue, uchar *element, uint idx)
+{
+ uint next_index, offset_to_key= queue->offset_to_key;
+ uint offset_to_queue_pos= queue->offset_to_queue_pos;
+ /* max_at_top swaps the comparison if we want to order by desc */
+ while ((next_index= idx >> 1) > 0 &&
+ queue->compare(queue->first_cmp_arg,
+ element + offset_to_key,
+ queue->root[next_index] + offset_to_key) *
+ queue->max_at_top < 0)
+ {
+ queue->root[idx]= queue->root[next_index];
+ if (offset_to_queue_pos)
+ (*(uint*) (queue->root[idx] + offset_to_queue_pos-1))= idx;
+ idx= next_index;
+ }
+ queue->root[idx]= element;
+ if (offset_to_queue_pos)
+ (*(uint*) (element + offset_to_queue_pos-1))= idx;
+}
+
+
+/*
+ Insert element in queue
+
+ SYNOPSIS
+ queue_insert()
+ queue Queue to use
+ element Element to insert
+*/
+
+void queue_insert(QUEUE *queue, uchar *element)
+{
+ DBUG_ASSERT(queue->elements < queue->max_elements);
+ insert_at(queue, element, ++queue->elements);
+}
+
+
+/*
+ Like queue_insert, but resize queue if queue is full
+
+ SYNOPSIS
+ queue_insert_safe()
+ queue Queue to use
+ element Element to insert
+
+ RETURN
+ 0 OK
+ 1 Cannot allocate more memory
+ 2 auto_extend is 0; No insertion done
+*/
+
+int queue_insert_safe(QUEUE *queue, uchar *element)
+{
+
+ if (queue->elements == queue->max_elements)
+ {
+ if (!queue->auto_extent)
+ return 2;
+ if (resize_queue(queue, queue->max_elements + queue->auto_extent))
+ return 1;
+ }
+
+ queue_insert(queue, element);
+ return 0;
+}
+
+
+/*
+ Remove item from queue
+
+ SYNOPSIS
+ queue_remove()
+ queue Queue to use
+ element Index of element to remove.
+ First element in queue is 'queue_first_element(queue)'
+
+ RETURN
+ pointer to removed element
+*/
+
+uchar *queue_remove(QUEUE *queue, uint idx)
+{
+ uchar *element;
+ DBUG_ASSERT(idx >= 1);
+ DBUG_ASSERT(idx <= queue->elements);
+ element= queue->root[idx];
+ queue->root[idx]= queue->root[queue->elements--];
+ queue_replace(queue, idx);
+ return element;
+}
+
+
+/*
+ Restores the heap property from idx down the heap
+
+ SYNOPSIS
+ _downheap()
+ queue Queue to use
+ idx Index of element to change
+*/
+
+void _downheap(QUEUE *queue, uint idx)
+{
+ uchar *element= queue->root[idx];
+ uint next_index,
+ elements= queue->elements,
+ half_queue= elements >> 1,
+ offset_to_key= queue->offset_to_key,
+ offset_to_queue_pos= queue->offset_to_queue_pos;
+
+ 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];
+ if (offset_to_queue_pos)
+ (*(uint*) (queue->root[idx] + offset_to_queue_pos-1))= idx;
+ idx= next_index;
+ }
+ queue->root[idx]=element;
+ if (offset_to_queue_pos)
+ (*(uint*) (element + offset_to_queue_pos-1))= idx;
+}
+
+
+/*
+ Fix heap when every element was changed.
+
+ SYNOPSIS
+ queue_fix()
+ queue Queue to use
+*/
+
+void queue_fix(QUEUE *queue)
+{
+ uint i;
+ for (i= queue->elements >> 1; i > 0; i--)
+ _downheap(queue, i);
+}
+
+
+/*
+ Change element at fixed position
+
+ SYNOPSIS
+ queue_replace()
+ queue Queue to use
+ idx Index of element to change
+
+ NOTE
+ optimized for the case when the new position is close to the end of the
+ heap (typical for queue_remove() replacements).
+*/
+
+void queue_replace(QUEUE *queue, uint idx)
+{
+ uchar *element= queue->root[idx];
+ uint next_index,
+ elements= queue->elements,
+ half_queue= elements>>1,
+ offset_to_key= queue->offset_to_key,
+ offset_to_queue_pos= queue->offset_to_queue_pos;
+ my_bool first= TRUE;
+
+ 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;
+ if (offset_to_queue_pos)
+ (*(uint*) (element + offset_to_queue_pos-1))= idx;
+ break;
+ }
+ first= FALSE;
+ queue->root[idx]= queue->root[next_index];
+ if (offset_to_queue_pos)
+ (*(uint*) (queue->root[idx] + offset_to_queue_pos-1))= idx;
+ idx=next_index;
+ }
+
+ insert_at(queue, element, idx);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-19 09:47:52 +0000