git.meshlink.io Git - catta/blob - 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