/* 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); }