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 <assert.h>
27#include <stdlib.h>
28
29#include <avahi-common/malloc.h>
30
31#include "prioq.h"
32
33AvahiPrioQueue* avahi_prio_queue_new(AvahiPQCompareFunc compare) {
34    AvahiPrioQueue *q;
35    assert(compare);
36
37    if (!(q = avahi_new(AvahiPrioQueue, 1)))
38        return NULL; /* OOM */
39
40    q->root = q->last = NULL;
41    q->n_nodes = 0;
42    q->compare = compare;
43
44    return q;
45}
46
47void avahi_prio_queue_free(AvahiPrioQueue *q) {
48    assert(q);
49
50    while (q->last)
51        avahi_prio_queue_remove(q, q->last);
52
53    assert(!q->n_nodes);
54    avahi_free(q);
55}
56
57static AvahiPrioQueueNode* get_node_at_xy(AvahiPrioQueue *q, unsigned x, unsigned y) {
58    unsigned r;
59    AvahiPrioQueueNode *n;
60    assert(q);
61
62    n = q->root;
63    assert(n);
64
65    for (r = 0; r < y; r++) {
66        assert(n);
67
68        if ((x >> (y-r-1)) & 1)
69            n = n->right;
70        else
71            n = n->left;
72    }
73
74    assert(n->x == x);
75    assert(n->y == y);
76
77    return n;
78}
79
80static void exchange_nodes(AvahiPrioQueue *q, AvahiPrioQueueNode *a, AvahiPrioQueueNode *b) {
81    AvahiPrioQueueNode *l, *r, *p, *ap, *an, *bp, *bn;
82    unsigned t;
83    assert(q);
84    assert(a);
85    assert(b);
86    assert(a != b);
87
88    /* Swap positions */
89    t = a->x; a->x = b->x; b->x = t;
90    t = a->y; a->y = b->y; b->y = t;
91
92    if (a->parent == b) {
93        /* B is parent of A */
94
95        p = b->parent;
96        b->parent = a;
97
98        if ((a->parent = p)) {
99            if (a->parent->left == b)
100                a->parent->left = a;
101            else
102                a->parent->right = a;
103        } else
104            q->root = a;
105
106        if (b->left == a) {
107            if ((b->left = a->left))
108                b->left->parent = b;
109            a->left = b;
110
111            r = a->right;
112            if ((a->right = b->right))
113                a->right->parent = a;
114            if ((b->right = r))
115                b->right->parent = b;
116
117        } else {
118            if ((b->right = a->right))
119                b->right->parent = b;
120            a->right = b;
121
122            l = a->left;
123            if ((a->left = b->left))
124                a->left->parent = a;
125            if ((b->left = l))
126                b->left->parent = b;
127        }
128    } else if (b->parent == a) {
129        /* A ist parent of B */
130
131        p = a->parent;
132        a->parent = b;
133
134        if ((b->parent = p)) {
135            if (b->parent->left == a)
136                b->parent->left = b;
137            else
138                b->parent->right = b;
139        } else
140            q->root = b;
141
142        if (a->left == b) {
143            if ((a->left = b->left))
144                a->left->parent = a;
145            b->left = a;
146
147            r = a->right;
148            if ((a->right = b->right))
149                a->right->parent = a;
150            if ((b->right = r))
151                b->right->parent = b;
152        } else {
153            if ((a->right = b->right))
154                a->right->parent = a;
155            b->right = a;
156
157            l = a->left;
158            if ((a->left = b->left))
159                a->left->parent = a;
160            if ((b->left = l))
161                b->left->parent = b;
162        }
163    } else {
164        AvahiPrioQueueNode *apl = NULL, *bpl = NULL;
165
166        /* Swap parents */
167        ap = a->parent;
168        bp = b->parent;
169
170        if (ap)
171            apl = ap->left;
172        if (bp)
173            bpl = bp->left;
174
175        if ((a->parent = bp)) {
176            if (bpl == b)
177                bp->left = a;
178            else
179                bp->right = a;
180        } else
181            q->root = a;
182
183        if ((b->parent = ap)) {
184            if (apl == a)
185                ap->left = b;
186            else
187                ap->right = b;
188        } else
189            q->root = b;
190
191        /* Swap children */
192        l = a->left;
193        r = a->right;
194
195        if ((a->left = b->left))
196            a->left->parent = a;
197
198        if ((b->left = l))
199            b->left->parent = b;
200
201        if ((a->right = b->right))
202            a->right->parent = a;
203
204        if ((b->right = r))
205            b->right->parent = b;
206    }
207
208    /* Swap siblings */
209    ap = a->prev; an = a->next;
210    bp = b->prev; bn = b->next;
211
212    if (a->next == b) {
213        /* A is predecessor of B */
214        a->prev = b;
215        b->next = a;
216
217        if ((a->next = bn))
218            a->next->prev = a;
219        else
220            q->last = a;
221
222        if ((b->prev = ap))
223            b->prev->next = b;
224
225    } else if (b->next == a) {
226        /* B is predecessor of A */
227        a->next = b;
228        b->prev = a;
229
230        if ((a->prev = bp))
231            a->prev->next = a;
232
233        if ((b->next = an))
234            b->next->prev = b;
235        else
236            q->last = b;
237
238    } else {
239        /* A is no neighbour of B */
240
241        if ((a->prev = bp))
242            a->prev->next = a;
243
244        if ((a->next = bn))
245            a->next->prev = a;
246        else
247            q->last = a;
248
249        if ((b->prev = ap))
250            b->prev->next = b;
251
252        if ((b->next = an))
253            b->next->prev = b;
254        else
255            q->last = b;
256    }
257}
258
259/* Move a node to the correct position */
260void avahi_prio_queue_shuffle(AvahiPrioQueue *q, AvahiPrioQueueNode *n) {
261    assert(q);
262    assert(n);
263    assert(n->queue == q);
264
265    /* Move up until the position is OK */
266    while (n->parent && q->compare(n->parent->data, n->data) > 0)
267        exchange_nodes(q, n, n->parent);
268
269    /* Move down until the position is OK */
270    for (;;) {
271        AvahiPrioQueueNode *min;
272
273        if (!(min = n->left)) {
274            /* No children */
275            assert(!n->right);
276            break;
277        }
278
279        if (n->right && q->compare(n->right->data, min->data) < 0)
280            min = n->right;
281
282        /* min now contains the smaller one of our two children */
283
284        if (q->compare(n->data, min->data) <= 0)
285            /* Order OK */
286            break;
287
288        exchange_nodes(q, n, min);
289    }
290}
291
292AvahiPrioQueueNode* avahi_prio_queue_put(AvahiPrioQueue *q, void* data) {
293    AvahiPrioQueueNode *n;
294    assert(q);
295
296    if (!(n = avahi_new(AvahiPrioQueueNode, 1)))
297        return NULL; /* OOM */
298
299    n->queue = q;
300    n->data = data;
301
302    if (q->last) {
303        assert(q->root);
304        assert(q->n_nodes);
305
306        n->y = q->last->y;
307        n->x = q->last->x+1;
308
309        if (n->x >= ((unsigned) 1 << n->y)) {
310            n->x = 0;
311            n->y++;
312        }
313
314        q->last->next = n;
315        n->prev = q->last;
316
317        assert(n->y > 0);
318        n->parent = get_node_at_xy(q, n->x/2, n->y-1);
319
320        if (n->x & 1)
321            n->parent->right = n;
322        else
323            n->parent->left = n;
324    } else {
325        assert(!q->root);
326        assert(!q->n_nodes);
327
328        n->y = n->x = 0;
329        q->root = n;
330        n->prev = n->parent = NULL;
331    }
332
333    n->next = n->left = n->right = NULL;
334    q->last = n;
335    q->n_nodes++;
336
337    avahi_prio_queue_shuffle(q, n);
338
339    return n;
340}
341
342void avahi_prio_queue_remove(AvahiPrioQueue *q, AvahiPrioQueueNode *n) {
343    assert(q);
344    assert(n);
345    assert(q == n->queue);
346
347    if (n != q->last) {
348        AvahiPrioQueueNode *replacement = q->last;
349        exchange_nodes(q, replacement, n);
350        avahi_prio_queue_remove(q, n);
351        avahi_prio_queue_shuffle(q, replacement);
352        return;
353    }
354
355    assert(n == q->last);
356    assert(!n->next);
357    assert(!n->left);
358    assert(!n->right);
359
360    q->last = n->prev;
361
362    if (n->prev) {
363        n->prev->next = NULL;
364        assert(n->parent);
365    } else
366        assert(!n->parent);
367
368    if (n->parent) {
369        assert(n->prev);
370        if (n->parent->left == n) {
371            assert(n->parent->right == NULL);
372            n->parent->left = NULL;
373        } else {
374            assert(n->parent->right == n);
375            assert(n->parent->left != NULL);
376            n->parent->right = NULL;
377        }
378    } else {
379        assert(q->root == n);
380        assert(!n->prev);
381        assert(q->n_nodes == 1);
382        q->root = NULL;
383    }
384
385    avahi_free(n);
386
387    assert(q->n_nodes > 0);
388    q->n_nodes--;
389}
390
391