-/* $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
#include <config.h>
#endif
+#include <assert.h>
+#include <stdlib.h>
+
+#include <avahi-common/malloc.h>
+
#include "prioq.h"
-AvahiPrioQueue* avahi_prio_queue_new(gint (*compare) (gconstpointer a, gconstpointer b)) {
+AvahiPrioQueue* avahi_prio_queue_new(AvahiPQCompareFunc compare) {
AvahiPrioQueue *q;
- g_assert(compare);
+ assert(compare);
+
+ if (!(q = avahi_new(AvahiPrioQueue, 1)))
+ return NULL; /* OOM */
- q = g_new(AvahiPrioQueue, 1);
q->root = q->last = NULL;
q->n_nodes = 0;
q->compare = compare;
+
return q;
}
void avahi_prio_queue_free(AvahiPrioQueue *q) {
- g_assert(q);
+ assert(q);
while (q->last)
avahi_prio_queue_remove(q, q->last);
- g_assert(!q->n_nodes);
- g_free(q);
+ assert(!q->n_nodes);
+ avahi_free(q);
}
-static AvahiPrioQueueNode* get_node_at_xy(AvahiPrioQueue *q, guint x, guint y) {
- guint r;
+static AvahiPrioQueueNode* get_node_at_xy(AvahiPrioQueue *q, unsigned x, unsigned y) {
+ unsigned r;
AvahiPrioQueueNode *n;
- g_assert(q);
+ assert(q);
n = q->root;
- g_assert(n);
+ assert(n);
for (r = 0; r < y; r++) {
- g_assert(n);
-
+ assert(n);
+
if ((x >> (y-r-1)) & 1)
n = n->right;
else
n = n->left;
}
- g_assert(n->x == x);
- g_assert(n->y == y);
+ assert(n->x == x);
+ assert(n->y == y);
return n;
}
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);
- g_assert(b);
- g_assert(a != b);
+ unsigned t;
+ assert(q);
+ assert(a);
+ assert(b);
+ assert(a != b);
/* Swap positions */
t = a->x; a->x = b->x; b->x = t;
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
/* Move a node to the correct position */
void avahi_prio_queue_shuffle(AvahiPrioQueue *q, AvahiPrioQueueNode *n) {
- g_assert(q);
- g_assert(n);
+ assert(q);
+ assert(n);
+ assert(n->queue == q);
/* Move up until the position is OK */
while (n->parent && q->compare(n->parent->data, n->data) > 0)
if (!(min = n->left)) {
/* No children */
- g_assert(!n->right);
+ assert(!n->right);
break;
}
}
}
-AvahiPrioQueueNode* avahi_prio_queue_put(AvahiPrioQueue *q, gpointer data) {
+AvahiPrioQueueNode* avahi_prio_queue_put(AvahiPrioQueue *q, void* data) {
AvahiPrioQueueNode *n;
- g_assert(q);
+ assert(q);
+
+ if (!(n = avahi_new(AvahiPrioQueueNode, 1)))
+ return NULL; /* OOM */
- n = g_new(AvahiPrioQueueNode, 1);
n->queue = q;
n->data = data;
if (q->last) {
- g_assert(q->root);
- g_assert(q->n_nodes);
-
+ assert(q->root);
+ assert(q->n_nodes);
+
n->y = q->last->y;
n->x = q->last->x+1;
- if (n->x >= ((guint) 1 << n->y)) {
+ if (n->x >= ((unsigned) 1 << n->y)) {
n->x = 0;
n->y++;
}
q->last->next = n;
n->prev = q->last;
-
- g_assert(n->y > 0);
+
+ assert(n->y > 0);
n->parent = get_node_at_xy(q, n->x/2, n->y-1);
if (n->x & 1)
else
n->parent->left = n;
} else {
- g_assert(!q->root);
- g_assert(!q->n_nodes);
-
+ assert(!q->root);
+ assert(!q->n_nodes);
+
n->y = n->x = 0;
q->root = n;
n->prev = n->parent = NULL;
}
void avahi_prio_queue_remove(AvahiPrioQueue *q, AvahiPrioQueueNode *n) {
- g_assert(q);
- g_assert(n);
+ assert(q);
+ assert(n);
+ assert(q == n->queue);
if (n != q->last) {
AvahiPrioQueueNode *replacement = q->last;
return;
}
- g_assert(n == q->last);
- g_assert(!n->next);
- g_assert(!n->left);
- g_assert(!n->right);
+ assert(n == q->last);
+ assert(!n->next);
+ assert(!n->left);
+ assert(!n->right);
q->last = n->prev;
-
+
if (n->prev) {
n->prev->next = NULL;
- g_assert(n->parent);
+ assert(n->parent);
} else
- g_assert(!n->parent);
+ assert(!n->parent);
if (n->parent) {
- g_assert(n->prev);
+ assert(n->prev);
if (n->parent->left == n) {
- g_assert(n->parent->right == NULL);
+ assert(n->parent->right == NULL);
n->parent->left = NULL;
} else {
- g_assert(n->parent->right == n);
- g_assert(n->parent->left != NULL);
+ assert(n->parent->right == n);
+ assert(n->parent->left != NULL);
n->parent->right = NULL;
}
} else {
- g_assert(q->root == n);
- g_assert(!n->prev);
- g_assert(q->n_nodes == 1);
+ assert(q->root == n);
+ assert(!n->prev);
+ assert(q->n_nodes == 1);
q->root = NULL;
}
- g_free(n);
+ avahi_free(n);
- g_assert(q->n_nodes > 0);
+ assert(q->n_nodes > 0);
q->n_nodes--;
}
projects / catta / blobdiff