X-Git-Url: http://git.meshlink.io/?a=blobdiff_plain;f=avahi-core%2Fprioq.c;h=28b50189dae7d5e26d8edddd672aa9aff0cbdab8;hb=4e88ffafebd622a212c4af7b3f7e1ef643644261;hp=7e57ae51e9fe0bd5b77b5267311fb967e421e068;hpb=c58379bde376cb2298fca14f83a86626f1b76f2f;p=catta diff --git a/avahi-core/prioq.c b/avahi-core/prioq.c index 7e57ae5..28b5018 100644 --- a/avahi-core/prioq.c +++ b/avahi-core/prioq.c @@ -1,18 +1,16 @@ -/* $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 @@ -23,59 +21,67 @@ #include #endif +#include +#include + +#include + #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; @@ -83,7 +89,7 @@ static void exchange_nodes(AvahiPrioQueue *q, AvahiPrioQueueNode *a, AvahiPrioQu if (a->parent == b) { /* B is parent of A */ - + p = b->parent; b->parent = a; @@ -105,7 +111,7 @@ static void exchange_nodes(AvahiPrioQueue *q, AvahiPrioQueueNode *a, AvahiPrioQu a->right->parent = a; if ((b->right = r)) b->right->parent = b; - + } else { if ((b->right = a->right)) b->right->parent = b; @@ -119,7 +125,7 @@ static void exchange_nodes(AvahiPrioQueue *q, AvahiPrioQueueNode *a, AvahiPrioQu } } else if (b->parent == a) { /* A ist parent of B */ - + p = a->parent; a->parent = b; @@ -154,7 +160,7 @@ static void exchange_nodes(AvahiPrioQueue *q, AvahiPrioQueueNode *a, AvahiPrioQu } } else { AvahiPrioQueueNode *apl = NULL, *bpl = NULL; - + /* Swap parents */ ap = a->parent; bp = b->parent; @@ -163,15 +169,15 @@ static void exchange_nodes(AvahiPrioQueue *q, AvahiPrioQueueNode *a, AvahiPrioQu 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; @@ -181,8 +187,8 @@ static void exchange_nodes(AvahiPrioQueue *q, AvahiPrioQueueNode *a, AvahiPrioQu 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; @@ -196,7 +202,7 @@ static void exchange_nodes(AvahiPrioQueue *q, AvahiPrioQueueNode *a, AvahiPrioQu if ((b->right = r)) b->right->parent = b; } - + /* Swap siblings */ ap = a->prev; an = a->next; bp = b->prev; bn = b->next; @@ -213,7 +219,7 @@ static void exchange_nodes(AvahiPrioQueue *q, AvahiPrioQueueNode *a, AvahiPrioQu if ((b->prev = ap)) b->prev->next = b; - + } else if (b->next == a) { /* B is predecessor of A */ a->next = b; @@ -232,15 +238,15 @@ static void exchange_nodes(AvahiPrioQueue *q, AvahiPrioQueueNode *a, AvahiPrioQu 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 @@ -250,8 +256,9 @@ static void exchange_nodes(AvahiPrioQueue *q, AvahiPrioQueueNode *a, AvahiPrioQu /* 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) @@ -263,7 +270,7 @@ void avahi_prio_queue_shuffle(AvahiPrioQueue *q, AvahiPrioQueueNode *n) { if (!(min = n->left)) { /* No children */ - g_assert(!n->right); + assert(!n->right); break; } @@ -280,30 +287,32 @@ void avahi_prio_queue_shuffle(AvahiPrioQueue *q, AvahiPrioQueueNode *n) { } } -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) @@ -311,9 +320,9 @@ AvahiPrioQueueNode* avahi_prio_queue_put(AvahiPrioQueue *q, gpointer data) { 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; @@ -329,8 +338,9 @@ AvahiPrioQueueNode* avahi_prio_queue_put(AvahiPrioQueue *q, gpointer data) { } 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; @@ -340,45 +350,39 @@ void avahi_prio_queue_remove(AvahiPrioQueue *q, AvahiPrioQueueNode *n) { 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) { - if (n->parent->right != NULL) { - g_message("fuck"); - for (;;); - - } - - 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--; }