1 /****************************************************************\
2 * *
3 * Priority queue library using pairing heaps. *
4 * *
5 * Guy St.C. Slater.. mailto:guy@ebi.ac.uk *
6 * Copyright (C) 2000-2009. All Rights Reserved. *
7 * *
8 * This source code is distributed under the terms of the *
9 * GNU General Public License, version 3. See the file COPYING *
10 * or http://www.gnu.org/licenses/gpl.txt for details *
11 * *
12 * If you use this code, please keep this notice intact. *
13 * *
14 \****************************************************************/
15
16 #include "pqueue.h"
17
PQueueSet_create(void)18 PQueueSet *PQueueSet_create(void){
19 register PQueueSet *pq_set = g_new(PQueueSet, 1);
20 pq_set->pq_recycle = RecycleBin_create("PQueue",
21 sizeof(PQueue), 64);
22 pq_set->node_recycle = RecycleBin_create("PQueue_Node",
23 sizeof(PQueue), 64);
24 return pq_set;
25 }
26
PQueueSet_destroy(PQueueSet * pq_set)27 void PQueueSet_destroy(PQueueSet *pq_set){
28 g_assert(pq_set);
29 RecycleBin_destroy(pq_set->pq_recycle);
30 RecycleBin_destroy(pq_set->node_recycle);
31 g_free(pq_set);
32 return;
33 }
34
PQueue_create(PQueueSet * pq_set,PQueue_Compare_Func comp_func,gpointer user_data)35 PQueue *PQueue_create(PQueueSet *pq_set,
36 PQueue_Compare_Func comp_func,
37 gpointer user_data){
38 register PQueue *pq;
39 g_assert(pq_set);
40 g_assert(comp_func);
41 pq = RecycleBin_alloc(pq_set->pq_recycle);
42 pq->root = NULL;
43 pq->total = 0;
44 pq->comp_func = comp_func;
45 pq->set = pq_set;
46 pq->user_data = user_data;
47 return pq;
48 }
49
PQueue_Node_destroy(PQueueSet * pq_set,PQueue_Node * pqn)50 static void PQueue_Node_destroy(PQueueSet *pq_set, PQueue_Node *pqn){
51 if(pqn){
52 PQueue_Node_destroy(pq_set, pqn->left);
53 PQueue_Node_destroy(pq_set, pqn->next);
54 RecycleBin_recycle(pq_set->node_recycle, pqn);
55 }
56 return;
57 }
58
PQueue_Node_destroy_with_func(PQueueSet * pq_set,PQueue_Node * pqn,PQueue_Free_Func free_func,gpointer * user_data)59 static void PQueue_Node_destroy_with_func(PQueueSet *pq_set,
60 PQueue_Node *pqn,
61 PQueue_Free_Func free_func, gpointer *user_data){
62 if(pqn){
63 PQueue_Node_destroy_with_func(pq_set, pqn->left,
64 free_func, user_data);
65 PQueue_Node_destroy_with_func(pq_set, pqn->next,
66 free_func, user_data);
67 free_func(pqn->data, user_data);
68 RecycleBin_recycle(pq_set->node_recycle, pqn);
69 }
70 return;
71 }
72
PQueue_destroy(PQueue * pq,PQueue_Free_Func free_func,gpointer user_data)73 void PQueue_destroy(PQueue *pq, PQueue_Free_Func free_func,
74 gpointer user_data){
75 if(free_func)
76 PQueue_Node_destroy_with_func(pq->set, pq->root,
77 free_func, user_data);
78 else
79 PQueue_Node_destroy(pq->set, pq->root);
80 RecycleBin_recycle(pq->set->pq_recycle, pq);
81 return;
82 }
83
84 #ifndef Swap
85 #define Swap(x,y,temp) ((temp)=(x),(x)=(y),(y)=(temp))
86 #endif /* Swap */
87
PQueue_Node_order(PQueue * pq,PQueue_Node * a,PQueue_Node * b)88 static PQueue_Node *PQueue_Node_order(PQueue *pq,
89 PQueue_Node *a, PQueue_Node *b){
90 register PQueue_Node *tmp;
91 g_assert(a);
92 g_assert(b);
93 if(pq->comp_func(a->data, b->data, pq->user_data)){
94 /* Add b before a */
95 a->next = b->next;
96 if(a->next)
97 a->next->prev = a;
98 Swap(a, b, tmp);
99 } else { /* Add a before b */
100 b->prev = a->prev;
101 }
102 a->prev = b;
103 a->next = b->left;
104 if(a->next)
105 a->next->prev = a;
106 b->left = a;
107 return b;
108 }
109
PQueue_push(PQueue * pq,gpointer data)110 PQueue_Node *PQueue_push(PQueue *pq, gpointer data){
111 register PQueue_Node *pqn = RecycleBin_alloc(pq->set->node_recycle);
112 /* Create empty heap and meld with existing heap */
113 pqn->data = data;
114 pqn->left = pqn->next = pqn->prev = NULL;
115 if(pq->root)
116 pq->root = PQueue_Node_order(pq, pq->root, pqn);
117 else
118 pq->root = pqn; /* Is the first node */
119 pq->total++;
120 return pqn;
121 }
122
PQueue_Node_extract(PQueue_Node * pqn)123 static void PQueue_Node_extract(PQueue_Node *pqn){
124 if(pqn->next)
125 pqn->next->prev = pqn->prev;
126 if(pqn->prev->left == pqn)
127 pqn->prev->left = pqn->next;
128 else
129 pqn->prev->next = pqn->next;
130 pqn->next = NULL;
131 return;
132 }
133
PQueue_raise(PQueue * pq,PQueue_Node * pqn)134 void PQueue_raise(PQueue *pq, PQueue_Node *pqn){
135 if(pq->root == pqn) /* If the root node */
136 return;
137 PQueue_Node_extract(pqn);
138 pq->root = PQueue_Node_order(pq, pq->root, pqn);
139 return;
140 }
141
PQueue_change(PQueue * pq,PQueue_Node * pqn)142 void PQueue_change(PQueue *pq, PQueue_Node *pqn){
143 register PQueue_Node *npqn;
144 npqn = PQueue_push(pq, PQueue_remove(pq, pqn));
145 g_assert(npqn == pqn);
146 return;
147 }
148
PQueue_Node_combine(PQueue * pq,PQueue_Node * pqn)149 static PQueue_Node *PQueue_Node_combine(PQueue *pq,
150 PQueue_Node *pqn){
151 register gint i, count;
152 register GPtrArray *combine;
153 register PQueue_Node *npqn;
154 if(!pqn->next){ /* Single member */
155 return pqn;
156 }
157 combine = g_ptr_array_new();
158 for(count = 0; pqn; count++){
159 g_ptr_array_add(combine, pqn);
160 pqn->prev->next = NULL; /* Break links */
161 pqn = pqn->next;
162 }
163 count--;
164 for(i = 0; i < count; i+=2)
165 combine->pdata[i] = PQueue_Node_order(pq, combine->pdata[i],
166 combine->pdata[i+1]);
167 if(!(count&1)) /* Pick up spare if odd count */
168 combine->pdata[i-2] = PQueue_Node_order(pq, combine->pdata[i-2],
169 combine->pdata[i]);
170 for(i-=2; i>=2; i-=2)
171 combine->pdata[i-2] = PQueue_Node_order(pq, combine->pdata[i-2],
172 combine->pdata[i]);
173 npqn = combine->pdata[0];
174 g_ptr_array_free(combine, TRUE);
175 return npqn;
176 }
177
PQueue_pop(PQueue * pq)178 gpointer PQueue_pop(PQueue *pq){
179 register PQueue_Node *pqn = pq->root;
180 register gpointer data;
181 if(!pq->root)
182 return NULL; /* Queue is empty */
183 data = pq->root->data;
184 g_assert((pq->total <= 1) || pq->root->left);
185 pq->root = pq->root->left
186 ? PQueue_Node_combine(pq, pq->root->left)
187 : NULL;
188 g_assert(pqn);
189 RecycleBin_recycle(pq->set->node_recycle, pqn);
190 if(!--pq->total) /* Set root as NULL if PQueue is now empty */
191 pq->root = NULL;
192 return data;
193 }
194
PQueue_join(PQueue * a,PQueue * b)195 PQueue *PQueue_join(PQueue *a, PQueue *b){
196 g_assert(a->set == b->set);
197 g_assert(a->comp_func == b->comp_func);
198 g_assert(a->user_data == b->user_data);
199 a->root = PQueue_Node_combine(a, b->root);
200 a->total += b->total;
201 RecycleBin_recycle(a->set->pq_recycle, b);
202 return a;
203 }
204
PQueue_remove(PQueue * pq,PQueue_Node * pqn)205 gpointer PQueue_remove(PQueue *pq, PQueue_Node *pqn){
206 register gpointer data = pqn->data;
207 register PQueue_Node *nb;
208 g_assert(pqn);
209 g_assert(pq->root);
210 if(pqn == pq->root)
211 return PQueue_pop(pq);
212 g_assert(pq->total > 1);
213 PQueue_Node_extract(pqn);
214 if(--pq->total){
215 if(pqn->left){
216 nb = PQueue_Node_combine(pq, pqn->left);
217 pq->root = PQueue_Node_order(pq, pq->root, nb);
218 }
219 } else {
220 pq->root = NULL;
221 }
222 RecycleBin_recycle(pq->set->node_recycle, pqn);
223 return data;
224 }
225
PQueue_traverse_recur(PQueue * pq,PQueue_Node * pqn,PQueue_Traverse_Func tf,gpointer user_data,gboolean * stop)226 static void PQueue_traverse_recur(PQueue *pq, PQueue_Node *pqn,
227 PQueue_Traverse_Func tf, gpointer user_data,
228 gboolean *stop){
229 if((!pqn || (*stop)))
230 return;
231 (*stop) = tf(pqn->data, user_data);
232 PQueue_traverse_recur(pq, pqn->left, tf, user_data, stop);
233 PQueue_traverse_recur(pq, pqn->next, tf, user_data, stop);
234 return;
235 }
236
PQueue_traverse(PQueue * pq,PQueue_Traverse_Func tf,gpointer user_data)237 void PQueue_traverse(PQueue *pq, PQueue_Traverse_Func tf,
238 gpointer user_data){
239 gboolean stop = FALSE;
240 PQueue_traverse_recur(pq, pq->root, tf, user_data, &stop);
241 return;
242 }
243
244