#include "prioq.h"
-flxPrioQueue* flx_prio_queue_new(gint (*compare) (gpointer a, gpointer b)) {
- flxPrioQueue *q;
+AvahiPrioQueue* avahi_prio_queue_new(gint (*compare) (gconstpointer a, gconstpointer b)) {
+ AvahiPrioQueue *q;
g_assert(compare);
- q = g_new(flxPrioQueue, 1);
+ q = g_new(AvahiPrioQueue, 1);
q->root = q->last = NULL;
q->n_nodes = 0;
q->compare = compare;
return q;
}
-void flx_prio_queue_free(flxPrioQueue *q) {
+void avahi_prio_queue_free(AvahiPrioQueue *q) {
g_assert(q);
while (q->last)
- flx_prio_queue_remove(q, q->last);
+ avahi_prio_queue_remove(q, q->last);
g_assert(!q->n_nodes);
g_free(q);
}
-static flxPrioQueueNode* get_node_at_xy(flxPrioQueue *q, guint x, guint y) {
+static AvahiPrioQueueNode* get_node_at_xy(AvahiPrioQueue *q, guint x, guint y) {
guint r;
- flxPrioQueueNode *n;
+ AvahiPrioQueueNode *n;
g_assert(q);
n = q->root;
return n;
}
-static void exchange_nodes(flxPrioQueue *q, flxPrioQueueNode *a, flxPrioQueueNode *b) {
- flxPrioQueueNode *l, *r, *p, *ap, *an, *bp, *bn;
+static void exchange_nodes(AvahiPrioQueue *q, AvahiPrioQueueNode *a, AvahiPrioQueueNode *b) {
+ AvahiPrioQueueNode *l, *r, *p, *ap, *an, *bp, *bn;
gint t;
g_assert(q);
g_assert(a);
b->left->parent = b;
}
} else {
+ AvahiPrioQueueNode *apl = NULL, *bpl = NULL;
+
/* Swap parents */
- p = a->parent;
+ ap = a->parent;
+ bp = b->parent;
+
+ if (ap)
+ apl = ap->left;
+ if (bp)
+ bpl = bp->left;
- if ((a->parent = b->parent)) {
- if (a->parent->left == b)
- a->parent->left = a;
- else
- a->parent->right = a;
+ if ((a->parent = bp)) {
+ if (bpl == b)
+ bp->left = a;
+ else
+ bp->right = a;
} else
q->root = a;
- if ((b->parent = p)) {
- if (b->parent->left == a)
- b->parent->left = b;
+ if ((b->parent = ap)) {
+ if (apl == a)
+ ap->left = b;
else
- b->parent->right = b;
+ ap->right = b;
} else
q->root = b;
}
/* Move a node to the correct position */
-static void shuffle_node(flxPrioQueue *q, flxPrioQueueNode *n) {
+void avahi_prio_queue_shuffle(AvahiPrioQueue *q, AvahiPrioQueueNode *n) {
g_assert(q);
g_assert(n);
/* Move down until the position is OK */
for (;;) {
- flxPrioQueueNode *min;
+ AvahiPrioQueueNode *min;
if (!(min = n->left)) {
/* No children */
}
}
-flxPrioQueueNode* flx_prio_queue_put(flxPrioQueue *q, gpointer data) {
- flxPrioQueueNode *n;
+AvahiPrioQueueNode* avahi_prio_queue_put(AvahiPrioQueue *q, gpointer data) {
+ AvahiPrioQueueNode *n;
g_assert(q);
- n = g_new(flxPrioQueueNode, 1);
+ n = g_new(AvahiPrioQueueNode, 1);
n->queue = q;
n->data = data;
if (q->last) {
g_assert(q->root);
g_assert(q->n_nodes);
-
+
n->y = q->last->y;
n->x = q->last->x+1;
q->last = n;
q->n_nodes++;
- shuffle_node(q, n);
+ avahi_prio_queue_shuffle(q, n);
return n;
}
-void flx_prio_queue_remove(flxPrioQueue *q, flxPrioQueueNode *n) {
+void avahi_prio_queue_remove(AvahiPrioQueue *q, AvahiPrioQueueNode *n) {
g_assert(q);
g_assert(n);
if (n != q->last) {
- flxPrioQueueNode *replacement = q->last;
+ AvahiPrioQueueNode *replacement = q->last;
exchange_nodes(q, replacement, n);
- flx_prio_queue_remove(q, q->last);
- shuffle_node(q, replacement);
+ avahi_prio_queue_remove(q, n);
+ avahi_prio_queue_shuffle(q, replacement);
return;
}
q->last = n->prev;
- if (n->prev)
+ if (n->prev) {
n->prev->next = NULL;
- else
+ g_assert(n->parent);
+ } else
g_assert(!n->parent);
if (n->parent) {
g_assert(n->prev);
if (n->parent->left == n) {
+ if (n->parent->right != NULL) {
+ g_message("fuck");
+ for (;;);
+
+ }
+
g_assert(n->parent->right == NULL);
n->parent->left = NULL;
} else {
} else {
g_assert(q->root == n);
g_assert(!n->prev);
+ g_assert(q->n_nodes == 1);
q->root = NULL;
}
- q->n_nodes--;
-
g_free(n);
+
+ g_assert(q->n_nodes > 0);
+ q->n_nodes--;
}
+