-/* $Id$ */
-
/***
This file is part of avahi.
-
+
avahi is free software; you can redistribute it and/or modify it
under the terms of the GNU Lesser General Public License as
published by the Free Software Foundation; either version 2.1 of the
License, or (at your option) any later version.
-
+
avahi is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
Public License for more details.
-
+
You should have received a copy of the GNU Lesser General Public
License along with avahi; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
if (!(q = avahi_new(AvahiPrioQueue, 1)))
return NULL; /* OOM */
-
+
q->root = q->last = NULL;
q->n_nodes = 0;
q->compare = compare;
-
+
return q;
}
for (r = 0; r < y; r++) {
assert(n);
-
+
if ((x >> (y-r-1)) & 1)
n = n->right;
else
if (a->parent == b) {
/* B is parent of A */
-
+
p = b->parent;
b->parent = a;
a->right->parent = a;
if ((b->right = r))
b->right->parent = b;
-
+
} else {
if ((b->right = a->right))
b->right->parent = b;
}
} else if (b->parent == a) {
/* A ist parent of B */
-
+
p = a->parent;
a->parent = b;
}
} else {
AvahiPrioQueueNode *apl = NULL, *bpl = NULL;
-
+
/* Swap parents */
ap = a->parent;
bp = b->parent;
apl = ap->left;
if (bp)
bpl = bp->left;
-
+
if ((a->parent = bp)) {
if (bpl == b)
bp->left = a;
- else
+ else
bp->right = a;
} else
q->root = a;
-
+
if ((b->parent = ap)) {
if (apl == a)
ap->left = b;
q->root = b;
/* Swap children */
- l = a->left;
- r = a->right;
+ l = a->left;
+ r = a->right;
if ((a->left = b->left))
a->left->parent = a;
if ((b->right = r))
b->right->parent = b;
}
-
+
/* Swap siblings */
ap = a->prev; an = a->next;
bp = b->prev; bn = b->next;
if ((b->prev = ap))
b->prev->next = b;
-
+
} else if (b->next == a) {
/* B is predecessor of A */
a->next = b;
if ((a->prev = bp))
a->prev->next = a;
-
+
if ((a->next = bn))
a->next->prev = a;
else
q->last = a;
-
+
if ((b->prev = ap))
b->prev->next = b;
-
+
if ((b->next = an))
b->next->prev = b;
else
if (!(n = avahi_new(AvahiPrioQueueNode, 1)))
return NULL; /* OOM */
-
+
n->queue = q;
n->data = data;
if (q->last) {
assert(q->root);
assert(q->n_nodes);
-
+
n->y = q->last->y;
n->x = q->last->x+1;
q->last->next = n;
n->prev = q->last;
-
+
assert(n->y > 0);
n->parent = get_node_at_xy(q, n->x/2, n->y-1);
} else {
assert(!q->root);
assert(!q->n_nodes);
-
+
n->y = n->x = 0;
q->root = n;
n->prev = n->parent = NULL;
assert(!n->right);
q->last = n->prev;
-
+
if (n->prev) {
n->prev->next = NULL;
assert(n->parent);