]> git.meshlink.io Git - catta/blob - avahi-core/prioq.c
CVE-2009-0758: Reflector creates packet storm on legacy unicast traffic
[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 <assert.h>
27 #include <stdlib.h>
28
29 #include <avahi-common/malloc.h>
30
31 #include "prioq.h"
32
33 AvahiPrioQueue* 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
47 void 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
57 static 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
80 static 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 */
260 void 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
292 AvahiPrioQueueNode* 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
342 void 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