Mercurial > dovecot > core-2.2

annotate src/lib/priorityq.h @ 23007:36e01285b5b8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
lib: buffer - Improve header comment for buffer_insert() and buffer_delete().
author Stephan Bosch <stephan.bosch@dovecot.fi>
date Mon, 18 Mar 2019 00:52:37 +0100
parents ee4201fdad4f
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
7097
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
1 #ifndef PRIORITYQ_H
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
2 #define PRIORITYQ_H
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
3
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
4 /* Priority queue implementation using heap. The items you add to the queue
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
5 must begin with a struct priorityq_item. This is necessary for
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
6 priorityq_remove() to work fast. */
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
7
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
8 struct priorityq_item {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
9 /* Current index in the queue array, updated automatically. */
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
10 unsigned int idx;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
11 /* [your own data] */
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
12 };
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
13
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
14 /* Returns <0, 0 or >0 */
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
15 typedef int priorityq_cmp_callback_t(const void *p1, const void *p2);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
16
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
17 /* Create a new priority queue. Callback is used to compare added items. */
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
18 struct priorityq *
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
19 priorityq_init(priorityq_cmp_callback_t *cmp_callback, unsigned int init_size);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
20 void priorityq_deinit(struct priorityq **pq);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
21
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
22 /* Return number of items in the queue. */
7912
81806d402514 Added more consts, ATTR_CONSTs and ATTR_PUREs.
Timo Sirainen <tss@iki.fi>
parents: 7097
diff changeset
23 unsigned int priorityq_count(const struct priorityq *pq) ATTR_PURE;
7097
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
24
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
25 /* Add a new item to the queue. */
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
26 void priorityq_add(struct priorityq *pq, struct priorityq_item *item);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
27 /* Remove the specified item from the queue. */
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
28 void priorityq_remove(struct priorityq *pq, struct priorityq_item *item);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
29
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
30 /* Return the item with the highest priority. Returns NULL if queue is empty. */
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
31 struct priorityq_item *priorityq_peek(struct priorityq *pq);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
32 /* Like priorityq_peek(), but also remove the returned item from the queue. */
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
33 struct priorityq_item *priorityq_pop(struct priorityq *pq);
9493
ee4201fdad4f Added priorityq_items() for getting all items from a priority queue.
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
34 /* Returns array containing all the priorityq_items. Only the first item is
ee4201fdad4f Added priorityq_items() for getting all items from a priority queue.
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
35 guaranteed to be the highest priority item, the rest can't be assumed to
ee4201fdad4f Added priorityq_items() for getting all items from a priority queue.
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
36 be in any order. */
ee4201fdad4f Added priorityq_items() for getting all items from a priority queue.
Timo Sirainen <tss@iki.fi>
parents: 7912
diff changeset
37 struct priorityq_item *const *priorityq_items(struct priorityq *pq);
7097
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
38
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
39 #endif