]> git.meshlink.io Git - catta/blob - avahi-core/prioq.c
improve documentation
[catta] / avahi-core / prioq.c
1 /* $Id$ */
2
3 /***
4   This file is part of avahi.
5  
6   avahi is free software; you can redistribute it and/or modify it
7   under the terms of the GNU Lesser General Public License as
8   published by the Free Software Foundation; either version 2.1 of the
9   License, or (at your option) any later version.
10  
11   avahi is distributed in the hope that it will be useful, but WITHOUT
12   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13   or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
14   Public License for more details.
15  
16   You should have received a copy of the GNU Lesser General Public
17   License along with avahi; if not, write to the Free Software
18   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
19   USA.
20 ***/
21
22 #ifdef HAVE_CONFIG_H
23 #include <config.h>
24 #endif
25
26 #include "prioq.h"
27
28 AvahiPrioQueue* avahi_prio_queue_new(gint (*compare) (gconstpointer a, gconstpointer b)) {
29     AvahiPrioQueue *q;
30     g_assert(compare);
31
32     q = g_new(AvahiPrioQueue, 1);
33     q->root = q->last = NULL;
34     q->n_nodes = 0;
35     q->compare = compare;
36     return q;
37 }
38
39 void avahi_prio_queue_free(AvahiPrioQueue *q) {
40     g_assert(q);
41
42     while (q->last)
43         avahi_prio_queue_remove(q, q->last);
44
45     g_assert(!q->n_nodes);
46     g_free(q);
47 }
48
49 static AvahiPrioQueueNode* get_node_at_xy(AvahiPrioQueue *q, guint x, guint y) {
50     guint r;
51     AvahiPrioQueueNode *n;
52     g_assert(q);
53
54     n = q->root;
55     g_assert(n);
56
57     for (r = 0; r < y; r++) {
58         g_assert(n);
59         
60         if ((x >> (y-r-1)) & 1)
61             n = n->right;
62         else
63             n = n->left;
64     }
65
66     g_assert(n->x == x);
67     g_assert(n->y == y);
68
69     return n;
70 }
71
72 static void exchange_nodes(AvahiPrioQueue *q, AvahiPrioQueueNode *a, AvahiPrioQueueNode *b) {
73     AvahiPrioQueueNode *l, *r, *p, *ap, *an, *bp, *bn;
74     gint t;
75     g_assert(q);
76     g_assert(a);
77     g_assert(b);
78     g_assert(a != b);
79
80     /* Swap positions */
81     t = a->x; a->x = b->x; b->x = t;
82     t = a->y; a->y = b->y; b->y = t;
83
84     if (a->parent == b) {
85         /* B is parent of A */
86         
87         p = b->parent;
88         b->parent = a;
89
90         if ((a->parent = p)) {
91             if (a->parent->left == b)
92                 a->parent->left = a;
93             else
94                 a->parent->right = a;
95         } else
96             q->root = a;
97
98         if (b->left == a) {
99             if ((b->left = a->left))
100                 b->left->parent = b;
101             a->left = b;
102
103             r = a->right;
104             if ((a->right = b->right))
105                 a->right->parent = a;
106             if ((b->right = r))
107                 b->right->parent = b;
108             
109         } else {
110             if ((b->right = a->right))
111                 b->right->parent = b;
112             a->right = b;
113
114             l = a->left;
115             if ((a->left = b->left))
116                 a->left->parent = a;
117             if ((b->left = l))
118                 b->left->parent = b;
119         }
120     } else if (b->parent == a) {
121         /* A ist parent of B */
122         
123         p = a->parent;
124         a->parent = b;
125
126         if ((b->parent = p)) {
127             if (b->parent->left == a)
128                 b->parent->left = b;
129             else
130                 b->parent->right = b;
131         } else
132             q->root = b;
133
134         if (a->left == b) {
135             if ((a->left = b->left))
136                 a->left->parent = a;
137             b->left = a;
138
139             r = a->right;
140             if ((a->right = b->right))
141                 a->right->parent = a;
142             if ((b->right = r))
143                 b->right->parent = b;
144         } else {
145             if ((a->right = b->right))
146                 a->right->parent = a;
147             b->right = a;
148
149             l = a->left;
150             if ((a->left = b->left))
151                 a->left->parent = a;
152             if ((b->left = l))
153                 b->left->parent = b;
154         }
155     } else {
156         AvahiPrioQueueNode *apl = NULL, *bpl = NULL;
157         
158         /* Swap parents */
159         ap = a->parent;
160         bp = b->parent;
161
162         if (ap)
163             apl = ap->left;
164         if (bp)
165             bpl = bp->left;
166         
167         if ((a->parent = bp)) {
168             if (bpl == b)
169                 bp->left = a;
170             else 
171                 bp->right = a;
172         } else
173             q->root = a;
174                 
175         if ((b->parent = ap)) {
176             if (apl == a)
177                 ap->left = b;
178             else
179                 ap->right = b;
180         } else
181             q->root = b;
182
183         /* Swap children */
184         l = a->left; 
185         r = a->right; 
186
187         if ((a->left = b->left))
188             a->left->parent = a;
189
190         if ((b->left = l))
191             b->left->parent = b;
192
193         if ((a->right = b->right))
194             a->right->parent = a;
195
196         if ((b->right = r))
197             b->right->parent = b;
198     }
199     
200     /* Swap siblings */
201     ap = a->prev; an = a->next;
202     bp = b->prev; bn = b->next;
203
204     if (a->next == b) {
205         /* A is predecessor of B */
206         a->prev = b;
207         b->next = a;
208
209         if ((a->next = bn))
210             a->next->prev = a;
211         else
212             q->last = a;
213
214         if ((b->prev = ap))
215             b->prev->next = b;
216         
217     } else if (b->next == a) {
218         /* B is predecessor of A */
219         a->next = b;
220         b->prev = a;
221
222         if ((a->prev = bp))
223             a->prev->next = a;
224
225         if ((b->next = an))
226             b->next->prev = b;
227         else
228             q->last = b;
229
230     } else {
231         /* A is no neighbour of B */
232
233         if ((a->prev = bp))
234             a->prev->next = a;
235         
236         if ((a->next = bn))
237             a->next->prev = a;
238         else
239             q->last = a;
240         
241         if ((b->prev = ap))
242             b->prev->next = b;
243         
244         if ((b->next = an))
245             b->next->prev = b;
246         else
247             q->last = b;
248     }
249 }
250
251 /* Move a node to the correct position */
252 void avahi_prio_queue_shuffle(AvahiPrioQueue *q, AvahiPrioQueueNode *n) {
253     g_assert(q);
254     g_assert(n);
255
256     /* Move up until the position is OK */
257     while (n->parent && q->compare(n->parent->data, n->data) > 0)
258         exchange_nodes(q, n, n->parent);
259
260     /* Move down until the position is OK */
261     for (;;) {
262         AvahiPrioQueueNode *min;
263
264         if (!(min = n->left)) {
265             /* No children */
266             g_assert(!n->right);
267             break;
268         }
269
270         if (n->right && q->compare(n->right->data, min->data) < 0)
271             min = n->right;
272
273         /* min now contains the smaller one of our two children */
274
275         if (q->compare(n->data, min->data) <= 0)
276             /* Order OK */
277             break;
278
279         exchange_nodes(q, n, min);
280     }
281 }
282
283 AvahiPrioQueueNode* avahi_prio_queue_put(AvahiPrioQueue *q, gpointer data) {
284     AvahiPrioQueueNode *n;
285     g_assert(q);
286
287     n = g_new(AvahiPrioQueueNode, 1);
288     n->queue = q;
289     n->data = data;
290
291     if (q->last) {
292         g_assert(q->root);
293         g_assert(q->n_nodes);
294          
295         n->y = q->last->y;
296         n->x = q->last->x+1;
297
298         if (n->x >= ((guint) 1 << n->y)) {
299             n->x = 0;
300             n->y++;
301         }
302
303         q->last->next = n;
304         n->prev = q->last;
305         
306         g_assert(n->y > 0);
307         n->parent = get_node_at_xy(q, n->x/2, n->y-1);
308
309         if (n->x & 1)
310             n->parent->right = n;
311         else
312             n->parent->left = n;
313     } else {
314         g_assert(!q->root);
315         g_assert(!q->n_nodes);
316         
317         n->y = n->x = 0;
318         q->root = n;
319         n->prev = n->parent = NULL;
320     }
321
322     n->next = n->left = n->right = NULL;
323     q->last = n;
324     q->n_nodes++;
325
326     avahi_prio_queue_shuffle(q, n);
327
328     return n;
329 }
330
331 void avahi_prio_queue_remove(AvahiPrioQueue *q, AvahiPrioQueueNode *n) {
332     g_assert(q);
333     g_assert(n);
334
335     if (n != q->last) {
336         AvahiPrioQueueNode *replacement = q->last;
337         exchange_nodes(q, replacement, n);
338         avahi_prio_queue_remove(q, n);
339         avahi_prio_queue_shuffle(q, replacement);
340         return;
341     }
342
343     g_assert(n == q->last);
344     g_assert(!n->next);
345     g_assert(!n->left);
346     g_assert(!n->right);
347
348     q->last = n->prev;
349     
350     if (n->prev) {
351         n->prev->next = NULL;
352         g_assert(n->parent);
353     } else
354         g_assert(!n->parent);
355
356     if (n->parent) {
357         g_assert(n->prev);
358         if (n->parent->left == n) {
359             g_assert(n->parent->right == NULL);
360             n->parent->left = NULL;
361         } else {
362             g_assert(n->parent->right == n);
363             g_assert(n->parent->left != NULL);
364             n->parent->right = NULL;
365         }
366     } else {
367         g_assert(q->root == n);
368         g_assert(!n->prev);
369         g_assert(q->n_nodes == 1);
370         q->root = NULL;
371     }
372
373     g_free(n);
374
375     g_assert(q->n_nodes > 0);
376     q->n_nodes--;
377 }
378