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