From a175314c3e5827eb193872241446f2f8f5c9d33c Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 4 May 2024 20:07:14 +0200 Subject: Adding upstream version 1:10.5.12. Signed-off-by: Daniel Baumann --- mysys/queues.c | 386 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 386 insertions(+) create mode 100644 mysys/queues.c (limited to 'mysys/queues.c') 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 + 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 + + +/* + 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); +} -- cgit v1.2.3