Adding upstream version 1:10.11.6.upstream/1%10.11.6upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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);
+}