00001 /* 00002 * Copyright 2010 Volkan Yazıcı <volkan.yazici@gmail.com> 00003 * Copyright 2006-2010 The Apache Software Foundation 00004 * 00005 * Licensed under the Apache License, Version 2.0 (the "License"); you may not 00006 * use this file except in compliance with the License. You may obtain a copy of 00007 * the License at 00008 * 00009 * http://www.apache.org/licenses/LICENSE-2.0 00010 * 00011 * Unless required by applicable law or agreed to in writing, software 00012 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 00013 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the 00014 * License for the specific language governing permissions and limitations under 00015 * the License. 00016 */ 00017 #ifndef LIBNAGIOS_pqueue_h__ 00018 #define LIBNAGIOS_pqueue_h__ 00019 #include <stdio.h> 00020 00021 /** 00022 * @file pqueue.h 00023 * @brief Priority Queue function declarations 00024 * 00025 * This priority queue library was originally written by Volkan Yazici 00026 * <volkan.yazici@gmail.com>. It was lated adapted for Nagios by 00027 * Andreas Ericsson <ae@op5.se>. Changes compared to the original 00028 * version are pretty much limited to changing pqueue_pri_t to be 00029 * an unsigned long long instead of a double, since ULL comparisons 00030 * are 107 times faster on my 64-bit laptop. 00031 * 00032 * @{ 00033 */ 00034 00035 00036 /** priority data type (used to be double, but ull is 107 times faster) */ 00037 typedef unsigned long long pqueue_pri_t; 00038 00039 /** callback functions to get/set/compare the priority of an element */ 00040 typedef pqueue_pri_t (*pqueue_get_pri_f)(void *a); 00041 typedef void (*pqueue_set_pri_f)(void *a, pqueue_pri_t pri); 00042 typedef int (*pqueue_cmp_pri_f)(pqueue_pri_t next, pqueue_pri_t curr); 00043 00044 00045 /** callback functions to get/set the position of an element */ 00046 typedef unsigned int (*pqueue_get_pos_f)(void *a); 00047 typedef void (*pqueue_set_pos_f)(void *a, unsigned int pos); 00048 00049 00050 /** debug callback function to print a entry */ 00051 typedef void (*pqueue_print_entry_f)(FILE *out, void *a); 00052 00053 00054 /** the priority queue handle */ 00055 typedef struct pqueue_t 00056 { 00057 unsigned int size; /**< number of elements in this queue */ 00058 unsigned int avail; /**< slots available in this queue */ 00059 unsigned int step; /**< growth stepping setting */ 00060 pqueue_cmp_pri_f cmppri; /**< callback to compare nodes */ 00061 pqueue_get_pri_f getpri; /**< callback to get priority of a node */ 00062 pqueue_set_pri_f setpri; /**< callback to set priority of a node */ 00063 pqueue_get_pos_f getpos; /**< callback to get position of a node */ 00064 pqueue_set_pos_f setpos; /**< callback to set position of a node */ 00065 void **d; /**< The actualy queue in binary heap form */ 00066 } pqueue_t; 00067 00068 00069 /** 00070 * initialize the queue 00071 * 00072 * @param n the initial estimate of the number of queue items for which memory 00073 * should be preallocated 00074 * @param cmppri The callback function to run to compare two elements 00075 * This callback should return 0 for 'lower' and non-zero 00076 * for 'higher', or vice versa if reverse priority is desired 00077 * @param setpri the callback function to run to assign a score to an element 00078 * @param getpri the callback function to run to set a score to an element 00079 * @param getpos the callback function to get the current element's position 00080 * @param setpos the callback function to set the current element's position 00081 * 00082 * @return the handle or NULL for insufficent memory 00083 */ 00084 pqueue_t * 00085 pqueue_init(unsigned int n, 00086 pqueue_cmp_pri_f cmppri, 00087 pqueue_get_pri_f getpri, 00088 pqueue_set_pri_f setpri, 00089 pqueue_get_pos_f getpos, 00090 pqueue_set_pos_f setpos); 00091 00092 00093 /** 00094 * free all memory used by the queue 00095 * @param q the queue 00096 */ 00097 void pqueue_free(pqueue_t *q); 00098 00099 00100 /** 00101 * return the size of the queue. 00102 * @param q the queue 00103 */ 00104 unsigned int pqueue_size(pqueue_t *q); 00105 00106 00107 /** 00108 * insert an item into the queue. 00109 * @param q the queue 00110 * @param d the item 00111 * @return 0 on success 00112 */ 00113 int pqueue_insert(pqueue_t *q, void *d); 00114 00115 00116 /** 00117 * move an existing entry to a different priority 00118 * @param q the queue 00119 * @param new_pri the new priority 00120 * @param d the entry 00121 */ 00122 void 00123 pqueue_change_priority(pqueue_t *q, 00124 pqueue_pri_t new_pri, 00125 void *d); 00126 00127 00128 /** 00129 * pop the highest-ranking item from the queue. 00130 * @param q the queue 00131 * @return NULL on error, otherwise the entry 00132 */ 00133 void *pqueue_pop(pqueue_t *q); 00134 00135 00136 /** 00137 * remove an item from the queue. 00138 * @param q the queue 00139 * @param d the entry 00140 * @return 0 on success 00141 */ 00142 int pqueue_remove(pqueue_t *q, void *d); 00143 00144 00145 /** 00146 * access highest-ranking item without removing it. 00147 * @param q the queue 00148 * @return NULL on error, otherwise the entry 00149 */ 00150 void *pqueue_peek(pqueue_t *q); 00151 00152 00153 /** 00154 * print the queue 00155 * @internal 00156 * DEBUG function only 00157 * @param q the queue 00158 * @param out the output handle 00159 * @param the callback function to print the entry 00160 */ 00161 void 00162 pqueue_print(pqueue_t *q, FILE *out, pqueue_print_entry_f print); 00163 00164 00165 /** 00166 * dump the queue and it's internal structure 00167 * @internal 00168 * debug function only 00169 * @param q the queue 00170 * @param out the output handle 00171 * @param the callback function to print the entry 00172 */ 00173 void pqueue_dump(pqueue_t *q, FILE *out, pqueue_print_entry_f print); 00174 00175 00176 /** 00177 * checks that the pq is in the right order, etc 00178 * @internal 00179 * debug function only 00180 * @param q the queue 00181 */ 00182 int pqueue_is_valid(pqueue_t *q); 00183 00184 #endif 00185 /** @} */