git.meshlink.io Git - catta/blob - libavahi-core/prioq.c

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