1/* Copyright (C) 2010 Monty Program Ab
2 All Rights reserved
3
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions are met:
6 * Redistributions of source code must retain the above copyright
7 notice, this list of conditions and the following disclaimer.
8 * Redistributions in binary form must reproduce the following disclaimer
9 in the documentation and/or other materials provided with the
10 distribution.
11
12 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
13 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
14 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
15 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
16 <COPYRIGHT HOLDER> BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
17 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
18 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
19 USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
20 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
21 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
22 OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
23 SUCH DAMAGE.
24*/
25
26/*
27 Code for generell handling of priority Queues.
28 Implementation of queues from "Algorithms in C" by Robert Sedgewick.
29*/
30
31#ifndef _queues_h
32#define _queues_h
33
34#ifdef __cplusplus
35extern "C" {
36#endif
37
38typedef struct st_queue {
39 uchar **root;
40 void *first_cmp_arg;
41 uint elements;
42 uint max_elements;
43 uint offset_to_key; /* compare is done on element+offset */
44 uint offset_to_queue_pos; /* If we want to store position in element */
45 uint auto_extent;
46 int max_at_top; /* Normally 1, set to -1 if queue_top gives max */
47 int (*compare)(void *, uchar *,uchar *);
48} QUEUE;
49
50#define queue_first_element(queue) 1
51#define queue_last_element(queue) (queue)->elements
52#define queue_empty(queue) ((queue)->elements == 0)
53#define queue_top(queue) ((queue)->root[1])
54#define queue_element(queue,index) ((queue)->root[index])
55#define queue_end(queue) ((queue)->root[(queue)->elements])
56#define queue_replace_top(queue) _downheap(queue, 1, (queue)->root[1])
57#define queue_set_cmp_arg(queue, set_arg) (queue)->first_cmp_arg= set_arg
58#define queue_set_max_at_top(queue, set_arg) \
59 (queue)->max_at_top= set_arg ? -1 : 1
60#define queue_remove_top(queue_arg) queue_remove((queue_arg), queue_first_element(queue_arg))
61typedef int (*queue_compare)(void *,uchar *, uchar *);
62
63int init_queue(QUEUE *queue,uint max_elements,uint offset_to_key,
64 pbool max_at_top, queue_compare compare,
65 void *first_cmp_arg, uint offset_to_queue_pos,
66 uint auto_extent);
67int reinit_queue(QUEUE *queue,uint max_elements,uint offset_to_key,
68 pbool max_at_top, queue_compare compare,
69 void *first_cmp_arg, uint offset_to_queue_pos,
70 uint auto_extent);
71int resize_queue(QUEUE *queue, uint max_elements);
72void delete_queue(QUEUE *queue);
73void queue_insert(QUEUE *queue,uchar *element);
74int queue_insert_safe(QUEUE *queue, uchar *element);
75uchar *queue_remove(QUEUE *queue,uint idx);
76void queue_replace(QUEUE *queue,uint idx);
77
78#define queue_remove_all(queue) { (queue)->elements= 0; }
79#define queue_is_full(queue) (queue->elements == queue->max_elements)
80void _downheap(QUEUE *queue, uint idx, uchar *element);
81void queue_fix(QUEUE *queue);
82#define is_queue_inited(queue) ((queue)->root != 0)
83
84#ifdef __cplusplus
85}
86#endif
87#endif
88