1 // 2 // priority queue header file "prioque.h" */ 3 // (c) 198x/1998/2001/2004 (minor updates) by Golden G. Richard III, Ph.D. */ 4 // 5 // 6 // Major update October 2004: The package is now thread-safe. The 7 // package now depends on the pthreads library (for access to 8 // semaphores). All functions now take one or more pointers to a 9 // queue or context, so existing applications will need to be 10 // modified slightly. 11 12 // Additionally, new functions are now provided for walking the queue 13 // "locally"--that is, more than one thread can maintain a position in 14 // the queue using a local Context. The old 'rewind_queue()', 15 // 'pointer_to_current()', etc. are maintained for a single position 16 // during a global walk. 17 // 18 // Finally, a long-standing memory leak was corrected. 19 // 20 // April 2007: added an option to init_queue to allow priority field to 21 // serve only as a tag--the queue is not sorted by the priority field when 22 // 'priority_is_tag_only' is set. 23 // 24 25 #include <pthread.h> 26 27 #define TRUE 1 28 #define FALSE 0 29 #define CONSISTENCY_CHECKING 30 31 #if ! defined(QUEUE_TYPE_DEFINED) 32 #define QUEUE_TYPE_DEFINED 33 34 /* type of one element in a queue */ 35 36 typedef struct _Queue_element 37 { 38 void *info; 39 int priority; 40 struct _Queue_element *next; 41 } *Queue_element; 42 43 /* basic queue type */ 44 45 typedef struct Queue 46 { 47 Queue_element queue; /* linked list of elements */ 48 Queue_element current; /* current position for sequential access functions */ 49 Queue_element previous; /* one step back from current */ 50 int queuelength; /* # of elements in queue */ 51 int elementsize; /* 'sizeof()' one element */ 52 int duplicates; /* are duplicates allowed? */ 53 int (*compare) (void *e1, void *e2); /* element comparision function */ 54 pthread_mutex_t lock; 55 int priority_is_tag_only; 56 } Queue; 57 58 typedef struct Context 59 { 60 Queue_element current; /* current position for local seq access functions */ 61 Queue_element previous; /* one step back from current */ 62 Queue *queue; /* queue associated with this context */ 63 } Context; 64 65 66 67 /********/ 68 /* 69 NOTE: init_queue() must be called for a new queue before any other "prioque.c" 70 functions are called. 71 */ 72 /********/ 73 74 75 /* function prototypes and descriptions for visible "prioque.c" functions 76 */ 77 78 //////////////////////////// 79 // SECTION 1 80 //////////////////////////// 81 82 /* initializes a new queue 'q' to have elements of size 'elementsize'. 83 If 'duplicates' is true, then duplicate elements in the queue are 84 allowed, otherwise duplicates are silently deleted. The 85 element-comparing function 'compare' is required only if 86 duplicates==FALSE or either equal_queues() or element_in_queue() 87 are used (otherwise, a null function is acceptable). 'compare' 88 should be a standard qsort()-style element comparison function: 89 returns 0 if elements match, otherwise a non-0 result (<, > cases 90 are not used). 91 92 NOTE:Only the 'compare' function is used for duplicate 93 detection--priority is not considered (i.e., attempting to add a 94 "duplicate" element that has a different priority than the existing 95 element will have no effect!) 96 */ 97 void init_queue (Queue * q, int elementsize, int duplicates, 98 int (*compare) (void *e1, void *e2), 99 int priority_is_tag_only); 100 101 102 /* destroys all elements in 'q' 103 */ 104 void destroy_queue (Queue * q); 105 106 107 /* adds 'element' to the 'q' with position based on 'priority'. 108 Elements with lower-numbered priorities are placed closer to the 109 front of the queue, with strict 'to the rear' placement for items 110 with equal priority [that is, given two items with equal priority, 111 the one most recently added will appear closer to the rear of the 112 queue]. 113 */ 114 void add_to_queue (Queue * q, void *element, int priority); 115 116 117 118 119 /* removes the element at the front of the 'q' and places it in 'element'. 120 */ 121 void remove_from_front (Queue * q, void *element); 122 123 124 /* returns TRUE if the 'element' exists in the 'q', otherwise false. 125 The 'compare' function is used for matching. As a side-effect, the 126 current position in the queue is set to matching element, so 127 'update_current()' can be used to update the value of the 128 'element'. If the element is not found, the current position is 129 set to the first element in the queue. 130 */ 131 int element_in_queue (Queue * q, void *element); 132 133 134 /* returns TRUE if 'q' is empty, FALSE otherwise 135 */ 136 int empty_queue (Queue * q); 137 138 139 /* returns the number of elements in the 'q'. 140 */ 141 int queue_length (Queue * q); 142 143 144 /* makes a copy of 'q2' into 'q1'. 'q2' is not modified. 145 */ 146 void copy_queue (Queue * q1, Queue * q2); 147 148 149 /* determines if 'q1' and 'q2' are equivalent. Uses the 'compare' 150 function of the first queue, which should match the 'compare' for 151 the second! Returns TRUE if the queues are equal, otherwise 152 returns FALSE. 153 */ 154 int equal_queues (Queue * q1, Queue * q2); 155 156 157 /* merge 'q2' into 'q1'. 'q2' is not modified. 158 */ 159 void merge_queues (Queue * q1, Queue * q2); 160 161 162 //////////////////////////// 163 // SECTION 2 164 //////////////////////////// 165 166 /* the following are functions used to "walk" the queue (globally) 167 like a linked list, examining or deleting elements along the way. 168 Current position is rewound to the beginning by functions above (in 169 SECTION 1), except for 'empty_queue()' and 'queue_length()', which 170 do not modify the global current position. 171 */ 172 173 /********************/ 174 /********************/ 175 176 177 /* move to the first element in the 'q' */ 178 void rewind_queue (Queue * q); 179 180 181 /* move to the next element in the 'q' */ 182 void next_element (Queue * q); 183 184 185 /* allows update of current element. The priority should not 186 be changed by this function! 187 */ 188 189 void update_current (Queue * q, void *element); 190 191 192 /* retrieve the element stored at the current position in the 'q' */ 193 void peek_at_current (Queue * q, void *element); 194 195 196 /* return a pointer to the data portion of the current element */ 197 void *pointer_to_current (Queue * q); 198 199 200 /* return priority of current element in the 'q' */ 201 int current_priority (Queue * q); 202 203 204 /* delete the element stored at the current position */ 205 void delete_current (Queue * q); 206 207 208 209 /* has the current position in 'q' moved beyond the last valid element? 210 Returns TRUE if so, FALSE otherwise. 211 */ 212 int end_of_queue (Queue * q); 213 214 //////////////////////////// 215 // SECTION 3 216 //////////////////////////// 217 218 // Functions in this section provide the ability to walk the queue 219 // with a locally maintained position. They do not affect the global 220 // queue position for functions in SECTION 2. 221 // 222 223 /* create a new local context for queue 'q'. The first element in 224 'q' becomes the current element in the newly created context. 225 */ 226 void local_init_context (Queue * q, Context * ctx); 227 228 229 /* move to the first element in the 'q', maintaining a local position */ 230 void local_rewind_queue (Context * ctx); 231 232 233 /* move to the next element in the 'q', maintaining a local position */ 234 void local_next_element (Context * ctx); 235 236 237 /* allows update of current element, relative to current local position. 238 The priority should not be changed by this function! 239 */ 240 241 void local_update_current (Context * ctx, void *element); 242 243 244 /* retrieve the element stored at the current local position in the 'q' */ 245 void local_peek_at_current (Context * ctx, void *element); 246 247 248 /* return a pointer to the data portion of the element at the current 249 local position */ 250 void *local_pointer_to_current (Context * ctx); 251 252 253 /* return priority of element at current local position in the 'q' */ 254 int local_current_priority (Context * ctx); 255 256 257 /* delete the element stored at the current local position */ 258 void local_delete_current (Context * ctx); 259 260 261 /* has the current local position in 'q' moved beyond the last valid 262 element? Returns TRUE if so, FALSE otherwise. 263 */ 264 int local_end_of_queue (Context * ctx); 265 266 267 #endif 268 269 270 /*** QUICK REFERENCE *** 271 272 // SECTION 1 273 void init_queue(Queue *q, int elementsize, int duplicates, 274 int (*compare)(void *e1, void *e2), int priority_is_tag_only); 275 void destroy_queue(Queue *q); 276 void add_to_queue(Queue *q, void *element, int priority); 277 void remove_from_front(Queue *q, void *element); 278 int element_in_queue(Queue *q, void *element); 279 int empty_queue(Queue *q); 280 int queue_length(Queue *q); 281 void copy_queue(Queue *q1, Queue *q2); 282 int equal_queues(Queue q1, Queue *q2); 283 void merge_queues(Queue *q1, Queue *q2); 284 285 // SECTION 2 286 287 void rewind_queue(Queue *q); 288 void next_element(Queue *q); 289 void update_current(Queue *q, void *element); 290 void peek_at_current(Queue *q, void *element); 291 void *pointer_to_current(Queue *q); 292 int current_priority(Queue *q); 293 void delete_current(Queue *q); 294 int end_of_queue(Queue *q); 295 296 // SECTION 3 297 void local_init_context(Queue, *q, Context *ctx); 298 void local_rewind_queue(Context *ctx); 299 void local_next_element(Context *ctx); 300 void local_update_current(Context *ctx, void *element); 301 void local_peek_at_current(Context *ctx, void *element); 302 void local_*pointer_to_current(Context *ctx); 303 int local_current_priority(Context *ctx); 304 void local_delete_current(Context *ctx); 305 int local_end_of_queue(Context *ctx); 306 *** QUICK REFERENCE ***/ 307