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 "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