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) */
37typedef unsigned long long pqueue_pri_t;
38
39/** callback functions to get/set/compare the priority of an element */
40typedef pqueue_pri_t (*pqueue_get_pri_f)(void *a);
41typedef void (*pqueue_set_pri_f)(void *a, pqueue_pri_t pri);
42typedef 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 */
46typedef unsigned int (*pqueue_get_pos_f)(void *a);
47typedef void (*pqueue_set_pos_f)(void *a, unsigned int pos);
48
49
50/** debug callback function to print a entry */
51typedef void (*pqueue_print_entry_f)(FILE *out, void *a);
52
53
54/** the priority queue handle */
55typedef 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 */
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 */
85pqueue_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 */
98
99
100/**
101 * return the size of the queue.
102 * @param q the queue
103 */
104unsigned 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 */
113int 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 */
122void
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 */
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 */
142int 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 */
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 */
161void
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 */
173void 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 */
183
184#endif
185/** @} */
struct pqueue_t pqueue_t
the priority queue handle
void(* pqueue_print_entry_f)(FILE *out, void *a)
debug callback function to print a entry
Definition: pqueue.h:51
void * pqueue_pop(pqueue_t *q)
pop the highest-ranking item from the queue.
unsigned int pqueue_size(pqueue_t *q)
return the size of the queue.
void pqueue_change_priority(pqueue_t *q, pqueue_pri_t new_pri, void *d)
move an existing entry to a different priority
void pqueue_print(pqueue_t *q, FILE *out, pqueue_print_entry_f print)
print the queue
int pqueue_remove(pqueue_t *q, void *d)
remove an item from the queue.
void * pqueue_peek(pqueue_t *q)
access highest-ranking item without removing it.
pqueue_pri_t(* pqueue_get_pri_f)(void *a)
callback functions to get/set/compare the priority of an element
Definition: pqueue.h:40
unsigned int(* pqueue_get_pos_f)(void *a)
callback functions to get/set the position of an element
Definition: pqueue.h:46
void pqueue_free(pqueue_t *q)
free all memory used by the queue
unsigned long long pqueue_pri_t
priority data type (used to be double, but ull is 107 times faster)
Definition: pqueue.h:37
int pqueue_insert(pqueue_t *q, void *d)
insert an item into the queue.
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
void pqueue_dump(pqueue_t *q, FILE *out, pqueue_print_entry_f print)
dump the queue and it's internal structure
int pqueue_is_valid(pqueue_t *q)
checks that the pq is in the right order, etc
the priority queue handle
Definition: pqueue.h:56
pqueue_set_pos_f setpos
callback to set position of a node
Definition: pqueue.h:64
pqueue_get_pos_f getpos
callback to get position of a node
Definition: pqueue.h:63
unsigned int step
growth stepping setting
Definition: pqueue.h:59
unsigned int size
number of elements in this queue
Definition: pqueue.h:57
unsigned int avail
slots available in this queue
Definition: pqueue.h:58
void ** d
The actual queue in binary heap form.
Definition: pqueue.h:65
pqueue_set_pri_f setpri
callback to set priority of a node
Definition: pqueue.h:62
pqueue_get_pri_f getpri
callback to get priority of a node
Definition: pqueue.h:61
pqueue_cmp_pri_f cmppri
callback to compare nodes
Definition: pqueue.h:60