Nagios
4.4.5
Dev docs for Nagios core and neb-module hackers
Main Page
Related Pages
Data Structures
Files
File List
Globals
All
Data Structures
Files
Functions
Variables
Typedefs
Macros
Pages
lib
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
123
pqueue_change_priority
(
pqueue_t
*q,
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
/** @} */
Generated on Tue Oct 8 2019 00:17:26 for Nagios by
1.8.3.1