git.meshlink.io Git - catta/blob - avahi/prioq.c

   1 /***
   2   This file is part of avahi.
   3
   4   avahi is free software; you can redistribute it and/or modify it
   5   under the terms of the GNU Lesser General Public License as
   6   published by the Free Software Foundation; either version 2.1 of the
   7   License, or (at your option) any later version.
   8
   9   avahi is distributed in the hope that it will be useful, but WITHOUT
  10   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  11   or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
  12   Public License for more details.
  13
  14   You should have received a copy of the GNU Lesser General Public
  15   License along with avahi; if not, write to the Free Software
  16   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
  17   USA.
  18 ***/
  19
  20 #ifdef HAVE_CONFIG_H
  21 #include <config.h>
  22 #endif
  23
  24 #include <assert.h>
  25 #include <stdlib.h>
  26
  27 #include <avahi/malloc.h>
  28
  29 #include "prioq.h"
  30
  31 AvahiPrioQueue* avahi_prio_queue_new(AvahiPQCompareFunc compare) {
  32     AvahiPrioQueue *q;
  33     assert(compare);
  34
  35     if (!(q = avahi_new(AvahiPrioQueue, 1)))
  36         return NULL; /* OOM */
  37
  38     q->root = q->last = NULL;
  39     q->n_nodes = 0;
  40     q->compare = compare;
  41
  42     return q;
  43 }
  44
  45 void avahi_prio_queue_free(AvahiPrioQueue *q) {
  46     assert(q);
  47
  48     while (q->last)
  49         avahi_prio_queue_remove(q, q->last);
  50
  51     assert(!q->n_nodes);
  52     avahi_free(q);
  53 }
  54
  55 static AvahiPrioQueueNode* get_node_at_xy(AvahiPrioQueue *q, unsigned x, unsigned y) {
  56     unsigned r;
  57     AvahiPrioQueueNode *n;
  58     assert(q);
  59
  60     n = q->root;
  61     assert(n);
  62
  63     for (r = 0; r < y; r++) {
  64         assert(n);
  65
  66         if ((x >> (y-r-1)) & 1)
  67             n = n->right;
  68         else
  69             n = n->left;
  70     }
  71
  72     assert(n->x == x);
  73     assert(n->y == y);
  74
  75     return n;
  76 }
  77
  78 static void exchange_nodes(AvahiPrioQueue *q, AvahiPrioQueueNode *a, AvahiPrioQueueNode *b) {
  79     AvahiPrioQueueNode *l, *r, *p, *ap, *an, *bp, *bn;
  80     unsigned t;
  81     assert(q);
  82     assert(a);
  83     assert(b);
  84     assert(a != b);
  85
  86     /* Swap positions */
  87     t = a->x; a->x = b->x; b->x = t;
  88     t = a->y; a->y = b->y; b->y = t;
  89
  90     if (a->parent == b) {
  91         /* B is parent of A */
  92
  93         p = b->parent;
  94         b->parent = a;
  95
  96         if ((a->parent = p)) {
  97             if (a->parent->left == b)
  98                 a->parent->left = a;
  99             else
 100                 a->parent->right = a;
 101         } else
 102             q->root = a;
 103
 104         if (b->left == a) {
 105             if ((b->left = a->left))
 106                 b->left->parent = b;
 107             a->left = b;
 108
 109             r = a->right;
 110             if ((a->right = b->right))
 111                 a->right->parent = a;
 112             if ((b->right = r))
 113                 b->right->parent = b;
 114
 115         } else {
 116             if ((b->right = a->right))
 117                 b->right->parent = b;
 118             a->right = b;
 119
 120             l = a->left;
 121             if ((a->left = b->left))
 122                 a->left->parent = a;
 123             if ((b->left = l))
 124                 b->left->parent = b;
 125         }
 126     } else if (b->parent == a) {
 127         /* A ist parent of B */
 128
 129         p = a->parent;
 130         a->parent = b;
 131
 132         if ((b->parent = p)) {
 133             if (b->parent->left == a)
 134                 b->parent->left = b;
 135             else
 136                 b->parent->right = b;
 137         } else
 138             q->root = b;
 139
 140         if (a->left == b) {
 141             if ((a->left = b->left))
 142                 a->left->parent = a;
 143             b->left = a;
 144
 145             r = a->right;
 146             if ((a->right = b->right))
 147                 a->right->parent = a;
 148             if ((b->right = r))
 149                 b->right->parent = b;
 150         } else {
 151             if ((a->right = b->right))
 152                 a->right->parent = a;
 153             b->right = a;
 154
 155             l = a->left;
 156             if ((a->left = b->left))
 157                 a->left->parent = a;
 158             if ((b->left = l))
 159                 b->left->parent = b;
 160         }
 161     } else {
 162         AvahiPrioQueueNode *apl = NULL, *bpl = NULL;
 163
 164         /* Swap parents */
 165         ap = a->parent;
 166         bp = b->parent;
 167
 168         if (ap)
 169             apl = ap->left;
 170         if (bp)
 171             bpl = bp->left;
 172
 173         if ((a->parent = bp)) {
 174             if (bpl == b)
 175                 bp->left = a;
 176             else
 177                 bp->right = a;
 178         } else
 179             q->root = a;
 180
 181         if ((b->parent = ap)) {
 182             if (apl == a)
 183                 ap->left = b;
 184             else
 185                 ap->right = b;
 186         } else
 187             q->root = b;
 188
 189         /* Swap children */
 190         l = a->left;
 191         r = a->right;
 192
 193         if ((a->left = b->left))
 194             a->left->parent = a;
 195
 196         if ((b->left = l))
 197             b->left->parent = b;
 198
 199         if ((a->right = b->right))
 200             a->right->parent = a;
 201
 202         if ((b->right = r))
 203             b->right->parent = b;
 204     }
 205
 206     /* Swap siblings */
 207     ap = a->prev; an = a->next;
 208     bp = b->prev; bn = b->next;
 209
 210     if (a->next == b) {
 211         /* A is predecessor of B */
 212         a->prev = b;
 213         b->next = a;
 214
 215         if ((a->next = bn))
 216             a->next->prev = a;
 217         else
 218             q->last = a;
 219
 220         if ((b->prev = ap))
 221             b->prev->next = b;
 222
 223     } else if (b->next == a) {
 224         /* B is predecessor of A */
 225         a->next = b;
 226         b->prev = a;
 227
 228         if ((a->prev = bp))
 229             a->prev->next = a;
 230
 231         if ((b->next = an))
 232             b->next->prev = b;
 233         else
 234             q->last = b;
 235
 236     } else {
 237         /* A is no neighbour of B */
 238
 239         if ((a->prev = bp))
 240             a->prev->next = a;
 241
 242         if ((a->next = bn))
 243             a->next->prev = a;
 244         else
 245             q->last = a;
 246
 247         if ((b->prev = ap))
 248             b->prev->next = b;
 249
 250         if ((b->next = an))
 251             b->next->prev = b;
 252         else
 253             q->last = b;
 254     }
 255 }
 256
 257 /* Move a node to the correct position */
 258 void avahi_prio_queue_shuffle(AvahiPrioQueue *q, AvahiPrioQueueNode *n) {
 259     assert(q);
 260     assert(n);
 261     assert(n->queue == q);
 262
 263     /* Move up until the position is OK */
 264     while (n->parent && q->compare(n->parent->data, n->data) > 0)
 265         exchange_nodes(q, n, n->parent);
 266
 267     /* Move down until the position is OK */
 268     for (;;) {
 269         AvahiPrioQueueNode *min;
 270
 271         if (!(min = n->left)) {
 272             /* No children */
 273             assert(!n->right);
 274             break;
 275         }
 276
 277         if (n->right && q->compare(n->right->data, min->data) < 0)
 278             min = n->right;
 279
 280         /* min now contains the smaller one of our two children */
 281
 282         if (q->compare(n->data, min->data) <= 0)
 283             /* Order OK */
 284             break;
 285
 286         exchange_nodes(q, n, min);
 287     }
 288 }
 289
 290 AvahiPrioQueueNode* avahi_prio_queue_put(AvahiPrioQueue *q, void* data) {
 291     AvahiPrioQueueNode *n;
 292     assert(q);
 293
 294     if (!(n = avahi_new(AvahiPrioQueueNode, 1)))
 295         return NULL; /* OOM */
 296
 297     n->queue = q;
 298     n->data = data;
 299
 300     if (q->last) {
 301         assert(q->root);
 302         assert(q->n_nodes);
 303
 304         n->y = q->last->y;
 305         n->x = q->last->x+1;
 306
 307         if (n->x >= ((unsigned) 1 << n->y)) {
 308             n->x = 0;
 309             n->y++;
 310         }
 311
 312         q->last->next = n;
 313         n->prev = q->last;
 314
 315         assert(n->y > 0);
 316         n->parent = get_node_at_xy(q, n->x/2, n->y-1);
 317
 318         if (n->x & 1)
 319             n->parent->right = n;
 320         else
 321             n->parent->left = n;
 322     } else {
 323         assert(!q->root);
 324         assert(!q->n_nodes);
 325
 326         n->y = n->x = 0;
 327         q->root = n;
 328         n->prev = n->parent = NULL;
 329     }
 330
 331     n->next = n->left = n->right = NULL;
 332     q->last = n;
 333     q->n_nodes++;
 334
 335     avahi_prio_queue_shuffle(q, n);
 336
 337     return n;
 338 }
 339
 340 void avahi_prio_queue_remove(AvahiPrioQueue *q, AvahiPrioQueueNode *n) {
 341     assert(q);
 342     assert(n);
 343     assert(q == n->queue);
 344
 345     if (n != q->last) {
 346         AvahiPrioQueueNode *replacement = q->last;
 347         exchange_nodes(q, replacement, n);
 348         avahi_prio_queue_remove(q, n);
 349         avahi_prio_queue_shuffle(q, replacement);
 350         return;
 351     }
 352
 353     assert(n == q->last);
 354     assert(!n->next);
 355     assert(!n->left);
 356     assert(!n->right);
 357
 358     q->last = n->prev;
 359
 360     if (n->prev) {
 361         n->prev->next = NULL;
 362         assert(n->parent);
 363     } else
 364         assert(!n->parent);
 365
 366     if (n->parent) {
 367         assert(n->prev);
 368         if (n->parent->left == n) {
 369             assert(n->parent->right == NULL);
 370             n->parent->left = NULL;
 371         } else {
 372             assert(n->parent->right == n);
 373             assert(n->parent->left != NULL);
 374             n->parent->right = NULL;
 375         }
 376     } else {
 377         assert(q->root == n);
 378         assert(!n->prev);
 379         assert(q->n_nodes == 1);
 380         q->root = NULL;
 381     }
 382
 383     avahi_free(n);
 384
 385     assert(q->n_nodes > 0);
 386     q->n_nodes--;
 387 }
 388