Nagios  4.4.6
Dev docs for Nagios core and neb-module hackers
pqueue.h
Go to the documentation of this file.
1 /*
2  * Copyright 2010 Volkan Yazıcı <volkan.yazici@gmail.com>
3  * Copyright 2006-2010 The Apache Software Foundation
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License"); you may not
6  * use this file except in compliance with the License. You may obtain a copy of
7  * the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing, software
12  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
13  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
14  * License for the specific language governing permissions and limitations under
15  * the License.
16  */
17 #ifndef LIBNAGIOS_PQUEUE_H_INCLUDED
18 #define LIBNAGIOS_PQUEUE_H_INCLUDED
19 #include <stdio.h>
20 
21 /**
22  * @file pqueue.h
23  * @brief Priority Queue function declarations
24  *
25  * This priority queue library was originally written by Volkan Yazici
26  * <volkan.yazici@gmail.com>. It was lated adapted for Nagios by
27  * Andreas Ericsson <ae@op5.se>. Changes compared to the original
28  * version are pretty much limited to changing pqueue_pri_t to be
29  * an unsigned long long instead of a double, since ULL comparisons
30  * are 107 times faster on my 64-bit laptop.
31  *
32  * @{
33  */
34 
35 
36 /** priority data type (used to be double, but ull is 107 times faster) */
37 typedef unsigned long long pqueue_pri_t;
38 
39 /** callback functions to get/set/compare the priority of an element */
40 typedef pqueue_pri_t (*pqueue_get_pri_f)(void *a);
41 typedef void (*pqueue_set_pri_f)(void *a, pqueue_pri_t pri);
42 typedef int (*pqueue_cmp_pri_f)(pqueue_pri_t next, pqueue_pri_t curr);
43 
44 
45 /** callback functions to get/set the position of an element */
46 typedef unsigned int (*pqueue_get_pos_f)(void *a);
47 typedef void (*pqueue_set_pos_f)(void *a, unsigned int pos);
48 
49 
50 /** debug callback function to print a entry */
51 typedef void (*pqueue_print_entry_f)(FILE *out, void *a);
52 
53 
54 /** the priority queue handle */
55 typedef struct pqueue_t
56 {
57  unsigned int size; /**< number of elements in this queue */
58  unsigned int avail; /**< slots available in this queue */
59  unsigned int step; /**< growth stepping setting */
60  pqueue_cmp_pri_f cmppri; /**< callback to compare nodes */
61  pqueue_get_pri_f getpri; /**< callback to get priority of a node */
62  pqueue_set_pri_f setpri; /**< callback to set priority of a node */
63  pqueue_get_pos_f getpos; /**< callback to get position of a node */
64  pqueue_set_pos_f setpos; /**< callback to set position of a node */
65  void **d; /**< The actual queue in binary heap form */
66 } pqueue_t;
67 
68 
69 /**
70  * initialize the queue
71  *
72  * @param n the initial estimate of the number of queue items for which memory
73  * should be preallocated
74  * @param cmppri The callback function to run to compare two elements
75  * This callback should return 0 for 'lower' and non-zero
76  * for 'higher', or vice versa if reverse priority is desired
77  * @param setpri the callback function to run to assign a score to an element
78  * @param getpri the callback function to run to set a score to an element
79  * @param getpos the callback function to get the current element's position
80  * @param setpos the callback function to set the current element's position
81  *
82  * @return the handle or NULL for insufficient memory
83  */
84 pqueue_t *
85 pqueue_init(unsigned int n,
86  pqueue_cmp_pri_f cmppri,
87  pqueue_get_pri_f getpri,
88  pqueue_set_pri_f setpri,
89  pqueue_get_pos_f getpos,
90  pqueue_set_pos_f setpos);
91 
92 
93 /**
94  * free all memory used by the queue
95  * @param q the queue
96  */
97 void pqueue_free(pqueue_t *q);
98 
99 
100 /**
101  * return the size of the queue.
102  * @param q the queue
103  */
104 unsigned int pqueue_size(pqueue_t *q);
105 
106 
107 /**
108  * insert an item into the queue.
109  * @param q the queue
110  * @param d the item
111  * @return 0 on success
112  */
113 int pqueue_insert(pqueue_t *q, void *d);
114 
115 
116 /**
117  * move an existing entry to a different priority
118  * @param q the queue
119  * @param new_pri the new priority
120  * @param d the entry
121  */
122 void
124  pqueue_pri_t new_pri,
125  void *d);
126 
127 
128 /**
129  * pop the highest-ranking item from the queue.
130  * @param q the queue
131  * @return NULL on error, otherwise the entry
132  */
133 void *pqueue_pop(pqueue_t *q);
134 
135 
136 /**
137  * remove an item from the queue.
138  * @param q the queue
139  * @param d the entry
140  * @return 0 on success
141  */
142 int pqueue_remove(pqueue_t *q, void *d);
143 
144 
145 /**
146  * access highest-ranking item without removing it.
147  * @param q the queue
148  * @return NULL on error, otherwise the entry
149  */
150 void *pqueue_peek(pqueue_t *q);
151 
152 
153 /**
154  * print the queue
155  * @internal
156  * DEBUG function only
157  * @param q the queue
158  * @param out the output handle
159  * @param the callback function to print the entry
160  */
161 void
162 pqueue_print(pqueue_t *q, FILE *out, pqueue_print_entry_f print);
163 
164 
165 /**
166  * dump the queue and it's internal structure
167  * @internal
168  * debug function only
169  * @param q the queue
170  * @param out the output handle
171  * @param the callback function to print the entry
172  */
173 void pqueue_dump(pqueue_t *q, FILE *out, pqueue_print_entry_f print);
174 
175 
176 /**
177  * checks that the pq is in the right order, etc
178  * @internal
179  * debug function only
180  * @param q the queue
181  */
182 int pqueue_is_valid(pqueue_t *q);
183 
184 #endif
185 /** @} */
pqueue_size
unsigned int pqueue_size(pqueue_t *q)
return the size of the queue.
pqueue_pop
void * pqueue_pop(pqueue_t *q)
pop the highest-ranking item from the queue.
pqueue_free
void pqueue_free(pqueue_t *q)
free all memory used by the queue
pqueue_print
void pqueue_print(pqueue_t *q, FILE *out, pqueue_print_entry_f print)
print the queue
pqueue_change_priority
void pqueue_change_priority(pqueue_t *q, pqueue_pri_t new_pri, void *d)
move an existing entry to a different priority
pqueue_remove
int pqueue_remove(pqueue_t *q, void *d)
remove an item from the queue.
pqueue_get_pos_f
unsigned int(* pqueue_get_pos_f)(void *a)
callback functions to get/set the position of an element
Definition: pqueue.h:46
pqueue_dump
void pqueue_dump(pqueue_t *q, FILE *out, pqueue_print_entry_f print)
dump the queue and it's internal structure
pqueue_pri_t
unsigned long long pqueue_pri_t
priority data type (used to be double, but ull is 107 times faster)
Definition: pqueue.h:37
pqueue_t::step
unsigned int step
growth stepping setting
Definition: pqueue.h:59
pqueue_t::getpos
pqueue_get_pos_f getpos
callback to get position of a node
Definition: pqueue.h:63
pqueue_t::cmppri
pqueue_cmp_pri_f cmppri
callback to compare nodes
Definition: pqueue.h:60
pqueue_insert
int pqueue_insert(pqueue_t *q, void *d)
insert an item into the queue.
pqueue_t
struct pqueue_t pqueue_t
the priority queue handle
pqueue_t
the priority queue handle
Definition: pqueue.h:55
pqueue_t::d
void ** d
The actual queue in binary heap form.
Definition: pqueue.h:65
pqueue_get_pri_f
pqueue_pri_t(* pqueue_get_pri_f)(void *a)
callback functions to get/set/compare the priority of an element
Definition: pqueue.h:40
pqueue_peek
void * pqueue_peek(pqueue_t *q)
access highest-ranking item without removing it.
pqueue_is_valid
int pqueue_is_valid(pqueue_t *q)
checks that the pq is in the right order, etc
pqueue_t::avail
unsigned int avail
slots available in this queue
Definition: pqueue.h:58
pqueue_t::setpri
pqueue_set_pri_f setpri
callback to set priority of a node
Definition: pqueue.h:62
pqueue_init
pqueue_t * pqueue_init(unsigned int n, pqueue_cmp_pri_f cmppri, pqueue_get_pri_f getpri, pqueue_set_pri_f setpri, pqueue_get_pos_f getpos, pqueue_set_pos_f setpos)
initialize the queue
pqueue_t::setpos
pqueue_set_pos_f setpos
callback to set position of a node
Definition: pqueue.h:64
pqueue_t::getpri
pqueue_get_pri_f getpri
callback to get priority of a node
Definition: pqueue.h:61
pqueue_t::size
unsigned int size
number of elements in this queue
Definition: pqueue.h:57
pqueue_print_entry_f
void(* pqueue_print_entry_f)(FILE *out, void *a)
debug callback function to print a entry
Definition: pqueue.h:51