Mercurial > dovecot > core-2.2

annotate src/lib/priorityq.c @ 22664:fea53c2725c0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
director: Fix director_max_parallel_moves/kicks type Should be uint, not time.
author Timo Sirainen <timo.sirainen@dovecot.fi>
date Thu, 09 Nov 2017 12:24:16 +0200
parents 2e2563132d5f
children cb108f786fb4
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
21390
2e2563132d5f Updated copyright notices to include the year 2017.
Stephan Bosch <stephan.bosch@dovecot.fi>
parents: 19552
diff changeset
1 /* Copyright (c) 2008-2017 Dovecot authors, see the included COPYING file */
7097
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
2
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
3 #include "lib.h"
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
4 #include "array.h"
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
5 #include "priorityq.h"
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
6
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
7 /* Macros for moving inside an array implementation of binary tree where
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
8 [0] is the root. */
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
9 #define PARENT_IDX(idx) \
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
10 (((idx) - 1) / 2)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
11 #define LEFT_CHILD_IDX(idx) \
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
12 ((idx) * 2 + 1)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
13 #define RIGHT_CHILD_IDX(idx) \
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
14 ((idx) * 2 + 2)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
15
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
16 struct priorityq {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
17 priorityq_cmp_callback_t *cmp_callback;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
18
14920
a097ef0a9d6d Array API changed: ARRAY_DEFINE(name, type) -> ARRAY(type) name
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
19 ARRAY(struct priorityq_item *) items;
7097
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
20 };
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 struct priorityq *
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
23 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
24 {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
25 struct priorityq *pq;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
26
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
27 pq = i_new(struct priorityq, 1);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
28 pq->cmp_callback = cmp_callback;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
29 i_array_init(&pq->items, init_size);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
30 return pq;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
31 }
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
32
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
33 void priorityq_deinit(struct priorityq **_pq)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
34 {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
35 struct priorityq *pq = *_pq;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
36
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
37 *_pq = NULL;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
38 array_free(&pq->items);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
39 i_free(pq);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
40 }
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
41
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
42 unsigned int priorityq_count(const struct priorityq *pq)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
43 {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
44 return array_count(&pq->items);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
45 }
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
46
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
47 static void heap_items_swap(struct priorityq_item **items,
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
48 unsigned int idx1, unsigned int idx2)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
49 {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
50 struct priorityq_item *tmp;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
51
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
52 /* swap the item indexes */
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
53 i_assert(items[idx1]->idx == idx1);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
54 i_assert(items[idx2]->idx == idx2);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
55
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
56 items[idx1]->idx = idx2;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
57 items[idx2]->idx = idx1;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
58
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
59 /* swap the item pointers */
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
60 tmp = items[idx1];
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
61 items[idx1] = items[idx2];
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
62 items[idx2] = tmp;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
63 }
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
64
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
65 static unsigned int
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
66 heap_item_bubble_up(struct priorityq *pq, unsigned int idx)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
67 {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
68 struct priorityq_item **items;
7302
8e65f6755843 Fixed removing last item from priority queue.
Timo Sirainen <tss@iki.fi>
parents: 7097
diff changeset
69 unsigned int parent_idx, count;
7097
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
70
7302
8e65f6755843 Fixed removing last item from priority queue.
Timo Sirainen <tss@iki.fi>
parents: 7097
diff changeset
71 items = array_get_modifiable(&pq->items, &count);
7097
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
72 while (idx > 0) {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
73 parent_idx = PARENT_IDX(idx);
7302
8e65f6755843 Fixed removing last item from priority queue.
Timo Sirainen <tss@iki.fi>
parents: 7097
diff changeset
74
8e65f6755843 Fixed removing last item from priority queue.
Timo Sirainen <tss@iki.fi>
parents: 7097
diff changeset
75 i_assert(idx < count);
7097
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
76 if (pq->cmp_callback(items[idx], items[parent_idx]) >= 0)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
77 break;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
78
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
79 /* wrong order - swap */
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
80 heap_items_swap(items, idx, parent_idx);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
81 idx = parent_idx;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
82 }
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
83 return idx;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
84 }
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
85
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
86 static void heap_item_bubble_down(struct priorityq *pq, unsigned int idx)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
87 {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
88 struct priorityq_item **items;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
89 unsigned int left_idx, right_idx, min_child_idx, count;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
90
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
91 items = array_get_modifiable(&pq->items, &count);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
92 while ((left_idx = LEFT_CHILD_IDX(idx)) < count) {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
93 right_idx = RIGHT_CHILD_IDX(idx);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
94 if (right_idx >= count ||
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
95 pq->cmp_callback(items[left_idx], items[right_idx]) < 0)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
96 min_child_idx = left_idx;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
97 else
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
98 min_child_idx = right_idx;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
99
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
100 if (pq->cmp_callback(items[min_child_idx], items[idx]) >= 0)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
101 break;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
102
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
103 /* wrong order - swap */
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
104 heap_items_swap(items, idx, min_child_idx);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
105 idx = min_child_idx;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
106 }
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
107 }
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
108
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
109 void priorityq_add(struct priorityq *pq, struct priorityq_item *item)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
110 {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
111 item->idx = array_count(&pq->items);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
112 array_append(&pq->items, &item, 1);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
113 (void)heap_item_bubble_up(pq, item->idx);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
114 }
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
115
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
116 static void priorityq_remove_idx(struct priorityq *pq, unsigned int idx)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
117 {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
118 struct priorityq_item **items;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
119 unsigned int count;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
120
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
121 items = array_get_modifiable(&pq->items, &count);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
122 i_assert(idx < count);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
123
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
124 /* move last item over the removed one and fix the heap */
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
125 count--;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
126 heap_items_swap(items, idx, count);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
127 array_delete(&pq->items, count, 1);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
128
7302
8e65f6755843 Fixed removing last item from priority queue.
Timo Sirainen <tss@iki.fi>
parents: 7097
diff changeset
129 if (count > 0 && idx != count) {
7097
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
130 if (idx > 0)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
131 idx = heap_item_bubble_up(pq, idx);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
132 heap_item_bubble_down(pq, idx);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
133 }
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
134 }
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
135
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
136 void priorityq_remove(struct priorityq *pq, struct priorityq_item *item)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
137 {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
138 priorityq_remove_idx(pq, item->idx);
15904
d3cf06639864 Replaced all -1U and (unsigned int)-1 with UINT_MAX.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
139 item->idx = UINT_MAX;
7097
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
140 }
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
141
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
142 struct priorityq_item *priorityq_peek(struct priorityq *pq)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
143 {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
144 struct priorityq_item *const *items;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
145
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
146 if (array_count(&pq->items) == 0)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
147 return NULL;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
148
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
149 items = array_idx(&pq->items, 0);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
150 return items[0];
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
151 }
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
152
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
153 struct priorityq_item *priorityq_pop(struct priorityq *pq)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
154 {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
155 struct priorityq_item *item;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
156
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
157 item = priorityq_peek(pq);
12241
4db5123f91e4 priority queue: Set item's idx value to invalid when it's removed from queue.
Timo Sirainen <tss@iki.fi>
parents: 10582
diff changeset
158 if (item != NULL) {
7097
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
159 priorityq_remove_idx(pq, 0);
15904
d3cf06639864 Replaced all -1U and (unsigned int)-1 with UINT_MAX.
Timo Sirainen <tss@iki.fi>
parents: 15715
diff changeset
160 item->idx = UINT_MAX;
12241
4db5123f91e4 priority queue: Set item's idx value to invalid when it's removed from queue.
Timo Sirainen <tss@iki.fi>
parents: 10582
diff changeset
161 }
7097
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
162 return item;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
163 }
9493
ee4201fdad4f Added priorityq_items() for getting all items from a priority queue.
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
164
ee4201fdad4f Added priorityq_items() for getting all items from a priority queue.
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
165 struct priorityq_item *const *priorityq_items(struct priorityq *pq)
ee4201fdad4f Added priorityq_items() for getting all items from a priority queue.
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
166 {
ee4201fdad4f Added priorityq_items() for getting all items from a priority queue.
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
167 if (array_count(&pq->items) == 0)
ee4201fdad4f Added priorityq_items() for getting all items from a priority queue.
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
168 return NULL;
ee4201fdad4f Added priorityq_items() for getting all items from a priority queue.
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
169
ee4201fdad4f Added priorityq_items() for getting all items from a priority queue.
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
170 return array_idx(&pq->items, 0);
ee4201fdad4f Added priorityq_items() for getting all items from a priority queue.
Timo Sirainen <tss@iki.fi>
parents: 8590
diff changeset
171 }