Mercurial > dovecot > original-hg > dovecot-1.2

annotate src/lib/priorityq.c @ 8590:b9faf4db2a9f HEAD

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Updated copyright notices to include year 2009.
author Timo Sirainen <tss@iki.fi>
date Tue, 06 Jan 2009 09:25:38 -0500
parents 8e65f6755843
children 00cd9aacd03c
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
8590
b9faf4db2a9f Updated copyright notices to include year 2009.
Timo Sirainen <tss@iki.fi>
parents: 7302
diff changeset
1 /* Copyright (c) 2008-2009 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
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
19 ARRAY_DEFINE(items, struct priorityq_item *);
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);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
139 }
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 struct priorityq_item *priorityq_peek(struct priorityq *pq)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
142 {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
143 struct priorityq_item *const *items;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
144
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
145 if (array_count(&pq->items) == 0)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
146 return NULL;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
147
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
148 items = array_idx(&pq->items, 0);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
149 return items[0];
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
150 }
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 struct priorityq_item *priorityq_pop(struct priorityq *pq)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
153 {
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
154 struct priorityq_item *item;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
155
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
156 item = priorityq_peek(pq);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
157 if (item != NULL)
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
158 priorityq_remove_idx(pq, 0);
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
159 return item;
618472c2c3c5 Added a priority queue implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
160 }