Nagios  4.4.7
Dev docs for Nagios core and neb-module hackers
prqueue.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 prqueue.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 prqueue_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 prqueue_pri_t;
38 
39 /** callback functions to get/set/compare the priority of an element */
40 typedef prqueue_pri_t (*prqueue_get_pri_f)(void *a);
41 typedef void (*prqueue_set_pri_f)(void *a, prqueue_pri_t pri);
42 typedef int (*prqueue_cmp_pri_f)(prqueue_pri_t next, prqueue_pri_t curr);
43 
44 
45 /** callback functions to get/set the position of an element */
46 typedef unsigned int (*prqueue_get_pos_f)(void *a);
47 typedef void (*prqueue_set_pos_f)(void *a, unsigned int pos);
48 
49 
50 /** debug callback function to print a entry */
51 typedef void (*prqueue_print_entry_f)(FILE *out, void *a);
52 
53 
54 /** the priority queue handle */
55 typedef struct prqueue_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  prqueue_cmp_pri_f cmppri; /**< callback to compare nodes */
61  prqueue_get_pri_f getpri; /**< callback to get priority of a node */
62  prqueue_set_pri_f setpri; /**< callback to set priority of a node */
63  prqueue_get_pos_f getpos; /**< callback to get position of a node */
64  prqueue_set_pos_f setpos; /**< callback to set position of a node */
65  void **d; /**< The actual queue in binary heap form */
66 } prqueue_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 prqueue_t *
85 prqueue_init(unsigned int n,
86  prqueue_cmp_pri_f cmppri,
87  prqueue_get_pri_f getpri,
88  prqueue_set_pri_f setpri,
89  prqueue_get_pos_f getpos,
90  prqueue_set_pos_f setpos);
91 
92 
93 /**
94  * free all memory used by the queue
95  * @param q the queue
96  */
97 void prqueue_free(prqueue_t *q);
98 
99 
100 /**
101  * return the size of the queue.
102  * @param q the queue
103  */
104 unsigned int prqueue_size(prqueue_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 prqueue_insert(prqueue_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  prqueue_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 *prqueue_pop(prqueue_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 prqueue_remove(prqueue_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 *prqueue_peek(prqueue_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 prqueue_print(prqueue_t *q, FILE *out, prqueue_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 prqueue_dump(prqueue_t *q, FILE *out, prqueue_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  */
183 
184 #endif
185 /** @} */
prqueue_get_pos_f getpos
callback to get position of a node
Definition: prqueue.h:63
unsigned long long prqueue_pri_t
priority data type (used to be double, but ull is 107 times faster)
Definition: prqueue.h:37
prqueue_set_pos_f setpos
callback to set position of a node
Definition: prqueue.h:64
prqueue_pri_t(* prqueue_get_pri_f)(void *a)
callback functions to get/set/compare the priority of an element
Definition: prqueue.h:40
void * prqueue_pop(prqueue_t *q)
pop the highest-ranking item from the queue.
int prqueue_is_valid(prqueue_t *q)
checks that the pq is in the right order, etc
prqueue_set_pri_f setpri
callback to set priority of a node
Definition: prqueue.h:62
void prqueue_print(prqueue_t *q, FILE *out, prqueue_print_entry_f print)
print the queue
void prqueue_dump(prqueue_t *q, FILE *out, prqueue_print_entry_f print)
dump the queue and it&#39;s internal structure
int prqueue_remove(prqueue_t *q, void *d)
remove an item from the queue.
void(* prqueue_print_entry_f)(FILE *out, void *a)
debug callback function to print a entry
Definition: prqueue.h:51
unsigned int avail
slots available in this queue
Definition: prqueue.h:58
void ** d
The actual queue in binary heap form.
Definition: prqueue.h:65
int prqueue_insert(prqueue_t *q, void *d)
insert an item into the queue.
prqueue_cmp_pri_f cmppri
callback to compare nodes
Definition: prqueue.h:60
void prqueue_change_priority(prqueue_t *q, prqueue_pri_t new_pri, void *d)
move an existing entry to a different priority
prqueue_get_pri_f getpri
callback to get priority of a node
Definition: prqueue.h:61
prqueue_t * prqueue_init(unsigned int n, prqueue_cmp_pri_f cmppri, prqueue_get_pri_f getpri, prqueue_set_pri_f setpri, prqueue_get_pos_f getpos, prqueue_set_pos_f setpos)
initialize the queue
unsigned int size
number of elements in this queue
Definition: prqueue.h:57
the priority queue handle
Definition: prqueue.h:55
struct prqueue_t prqueue_t
the priority queue handle
void prqueue_free(prqueue_t *q)
free all memory used by the queue
void * prqueue_peek(prqueue_t *q)
access highest-ranking item without removing it.
unsigned int prqueue_size(prqueue_t *q)
return the size of the queue.
unsigned int(* prqueue_get_pos_f)(void *a)
callback functions to get/set the position of an element
Definition: prqueue.h:46
unsigned int step
growth stepping setting
Definition: prqueue.h:59