priorityq.h revision 68a4946b12583b88fa802e52ebee45cd96056772
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#ifndef PRIORITYQ_H
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen#define PRIORITYQ_H
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen/* Priority queue implementation using heap. The items you add to the queue
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen must begin with a struct priorityq_item. This is necessary for
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen priorityq_remove() to work fast. */
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainenstruct priorityq_item {
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen /* Current index in the queue array, updated automatically. */
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen unsigned int idx;
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen /* [your own data] */
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen};
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen/* Returns <0, 0 or >0 */
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainentypedef int priorityq_cmp_callback_t(const void *p1, const void *p2);
1c633f71ec2060e5bfa500a97f34cd881a958ecdTimo Sirainen
/* Create a new priority queue. Callback is used to compare added items. */
struct priorityq *
priorityq_init(priorityq_cmp_callback_t *cmp_callback, unsigned int init_size);
void priorityq_deinit(struct priorityq **pq);
/* Return number of items in the queue. */
unsigned int priorityq_count(const struct priorityq *pq) ATTR_PURE;
/* Add a new item to the queue. */
void priorityq_add(struct priorityq *pq, struct priorityq_item *item);
/* Remove the specified item from the queue. */
void priorityq_remove(struct priorityq *pq, struct priorityq_item *item);
/* Return the item with the highest priority. Returns NULL if queue is empty. */
struct priorityq_item *priorityq_peek(struct priorityq *pq);
/* Like priorityq_peek(), but also remove the returned item from the queue. */
struct priorityq_item *priorityq_pop(struct priorityq *pq);
#endif