Nagios 4.4.14
Dev docs for Nagios core and neb-module hackers
Loading...
Searching...
No Matches
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) */
37typedef unsigned long long prqueue_pri_t;
38
39/** callback functions to get/set/compare the priority of an element */
40typedef prqueue_pri_t (*prqueue_get_pri_f)(void *a);
41typedef void (*prqueue_set_pri_f)(void *a, prqueue_pri_t pri);
42typedef 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 */
46typedef unsigned int (*prqueue_get_pos_f)(void *a);
47typedef void (*prqueue_set_pos_f)(void *a, unsigned int pos);
48
49
50/** debug callback function to print a entry */
51typedef void (*prqueue_print_entry_f)(FILE *out, void *a);
52
53
54/** the priority queue handle */
55typedef 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 */
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 */
85prqueue_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 */
98
99
100/**
101 * return the size of the queue.
102 * @param q the queue
103 */
104unsigned 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 */
113int 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 */
122void
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 */
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 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 */
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 */
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/** @} */
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
void prqueue_print(prqueue_t *q, FILE *out, prqueue_print_entry_f print)
print the queue
unsigned long long prqueue_pri_t
priority data type (used to be double, but ull is 107 times faster)
Definition prqueue.h:37
prqueue_pri_t(* prqueue_get_pri_f)(void *a)
callback functions to get/set/compare the priority of an element
Definition prqueue.h:40
unsigned int(* prqueue_get_pos_f)(void *a)
callback functions to get/set the position of an element
Definition prqueue.h:46
void prqueue_dump(prqueue_t *q, FILE *out, prqueue_print_entry_f print)
dump the queue and it's internal structure
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
void prqueue_change_priority(prqueue_t *q, prqueue_pri_t new_pri, void *d)
move an existing entry to a different priority
int prqueue_remove(prqueue_t *q, void *d)
remove an item from the queue.
void * prqueue_peek(prqueue_t *q)
access highest-ranking item without removing it.
void(* prqueue_print_entry_f)(FILE *out, void *a)
debug callback function to print a entry
Definition prqueue.h:51
void prqueue_free(prqueue_t *q)
free all memory used by the queue
int prqueue_insert(prqueue_t *q, void *d)
insert an item into the queue.
unsigned int prqueue_size(prqueue_t *q)
return the size of the queue.
the priority queue handle
Definition prqueue.h:56
unsigned int step
growth stepping setting
Definition prqueue.h:59
prqueue_set_pri_f setpri
callback to set priority of a node
Definition prqueue.h:62
prqueue_get_pri_f getpri
callback to get priority of a node
Definition prqueue.h:61
unsigned int size
number of elements in this queue
Definition prqueue.h:57
prqueue_set_pos_f setpos
callback to set position of a node
Definition prqueue.h:64
void ** d
The actual queue in binary heap form.
Definition prqueue.h:65
prqueue_get_pos_f getpos
callback to get position of a node
Definition prqueue.h:63
prqueue_cmp_pri_f cmppri
callback to compare nodes
Definition prqueue.h:60
unsigned int avail
slots available in this queue
Definition prqueue.h:58