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