diff options
Diffstat (limited to 'include/queues.h')
| -rw-r--r-- | include/queues.h | 60 |
1 files changed, 36 insertions, 24 deletions
diff --git a/include/queues.h b/include/queues.h index d01b73ba999..f5f09359cbc 100644 --- a/include/queues.h +++ b/include/queues.h @@ -1,23 +1,31 @@ -/* Copyright (C) 2000 MySQL AB +/* Copyright (C) 2010 Monty Program Ab + All Rights reserved - This program is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; version 2 of the License. + 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 program 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 General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ + 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. +*/ /* Code for generell handling of priority Queues. Implemention of queues from "Algoritms in C" by Robert Sedgewick. - Copyright Monty Program KB. - By monty. */ #ifndef _queues_h @@ -31,30 +39,34 @@ typedef struct st_queue { void *first_cmp_arg; uint elements; uint max_elements; - uint offset_to_key; /* compare is done on element+offset */ + uint offset_to_key; /* compare is done on element+offset */ + uint offset_to_queue_pos; /* If we want to store position in element */ + uint auto_extent; int max_at_top; /* Normally 1, set to -1 if queue_top gives max */ int (*compare)(void *, uchar *,uchar *); - uint auto_extent; } QUEUE; +#define queue_first_element(queue) 1 +#define queue_last_element(queue) (queue)->elements #define queue_top(queue) ((queue)->root[1]) -#define queue_element(queue,index) ((queue)->root[index+1]) +#define queue_element(queue,index) ((queue)->root[index]) #define queue_end(queue) ((queue)->root[(queue)->elements]) -#define queue_replaced(queue) _downheap(queue,1) +#define queue_replace(queue, idx) _downheap(queue, idx, (queue)->root[idx]) +#define queue_replace_top(queue) _downheap(queue, 1, (queue)->root[1]) #define queue_set_cmp_arg(queue, set_arg) (queue)->first_cmp_arg= set_arg #define queue_set_max_at_top(queue, set_arg) \ (queue)->max_at_top= set_arg ? -1 : 1 +#define queue_remove_top(queue_arg) queue_remove((queue_arg), queue_first_element(queue_arg)) typedef int (*queue_compare)(void *,uchar *, uchar *); int init_queue(QUEUE *queue,uint max_elements,uint offset_to_key, pbool max_at_top, queue_compare compare, - void *first_cmp_arg); -int init_queue_ex(QUEUE *queue,uint max_elements,uint offset_to_key, - pbool max_at_top, queue_compare compare, - void *first_cmp_arg, uint auto_extent); + void *first_cmp_arg, uint offset_to_queue_pos, + uint auto_extent); int reinit_queue(QUEUE *queue,uint max_elements,uint offset_to_key, pbool max_at_top, queue_compare compare, - void *first_cmp_arg); + void *first_cmp_arg, uint offset_to_queue_pos, + uint auto_extent); int resize_queue(QUEUE *queue, uint max_elements); void delete_queue(QUEUE *queue); void queue_insert(QUEUE *queue,uchar *element); @@ -62,7 +74,7 @@ int queue_insert_safe(QUEUE *queue, uchar *element); uchar *queue_remove(QUEUE *queue,uint idx); #define queue_remove_all(queue) { (queue)->elements= 0; } #define queue_is_full(queue) (queue->elements == queue->max_elements) -void _downheap(QUEUE *queue,uint idx); +void _downheap(QUEUE *queue, uint idx, uchar *element); void queue_fix(QUEUE *queue); #define is_queue_inited(queue) ((queue)->root != 0) |