From c58379bde376cb2298fca14f83a86626f1b76f2f Mon Sep 17 00:00:00 2001 From: Lennart Poettering Date: Sat, 7 May 2005 13:37:03 +0000 Subject: rename libavahi-core to avahi-core git-svn-id: file:///home/lennart/svn/public/avahi/trunk@57 941a03a8-eaeb-0310-b9a0-b1bbd8fe43fe --- avahi-core/prioq.c | 384 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 384 insertions(+) create mode 100644 avahi-core/prioq.c (limited to 'avahi-core/prioq.c') diff --git a/avahi-core/prioq.c b/avahi-core/prioq.c new file mode 100644 index 0000000..7e57ae5 --- /dev/null +++ b/avahi-core/prioq.c @@ -0,0 +1,384 @@ +/* $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 + USA. +***/ + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include "prioq.h" + +AvahiPrioQueue* avahi_prio_queue_new(gint (*compare) (gconstpointer a, gconstpointer b)) { + AvahiPrioQueue *q; + g_assert(compare); + + 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); + + while (q->last) + avahi_prio_queue_remove(q, q->last); + + g_assert(!q->n_nodes); + g_free(q); +} + +static AvahiPrioQueueNode* get_node_at_xy(AvahiPrioQueue *q, guint x, guint y) { + guint r; + AvahiPrioQueueNode *n; + g_assert(q); + + n = q->root; + g_assert(n); + + for (r = 0; r < y; r++) { + g_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); + + 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); + + /* Swap positions */ + t = a->x; a->x = b->x; b->x = t; + t = a->y; a->y = b->y; b->y = t; + + if (a->parent == b) { + /* B is parent of A */ + + p = b->parent; + b->parent = a; + + if ((a->parent = p)) { + if (a->parent->left == b) + a->parent->left = a; + else + a->parent->right = a; + } else + q->root = a; + + if (b->left == a) { + if ((b->left = a->left)) + b->left->parent = b; + a->left = b; + + r = a->right; + if ((a->right = b->right)) + a->right->parent = a; + if ((b->right = r)) + b->right->parent = b; + + } else { + if ((b->right = a->right)) + b->right->parent = b; + a->right = b; + + l = a->left; + if ((a->left = b->left)) + a->left->parent = a; + if ((b->left = l)) + b->left->parent = b; + } + } else if (b->parent == a) { + /* A ist parent of B */ + + p = a->parent; + a->parent = b; + + if ((b->parent = p)) { + if (b->parent->left == a) + b->parent->left = b; + else + b->parent->right = b; + } else + q->root = b; + + if (a->left == b) { + if ((a->left = b->left)) + a->left->parent = a; + b->left = a; + + r = a->right; + if ((a->right = b->right)) + a->right->parent = a; + if ((b->right = r)) + b->right->parent = b; + } else { + if ((a->right = b->right)) + a->right->parent = a; + b->right = a; + + l = a->left; + if ((a->left = b->left)) + a->left->parent = a; + if ((b->left = l)) + b->left->parent = b; + } + } else { + AvahiPrioQueueNode *apl = NULL, *bpl = NULL; + + /* Swap parents */ + ap = a->parent; + bp = b->parent; + + if (ap) + apl = ap->left; + if (bp) + bpl = bp->left; + + if ((a->parent = bp)) { + if (bpl == b) + bp->left = a; + else + bp->right = a; + } else + q->root = a; + + if ((b->parent = ap)) { + if (apl == a) + ap->left = b; + else + ap->right = b; + } else + q->root = b; + + /* Swap children */ + l = a->left; + r = a->right; + + if ((a->left = b->left)) + a->left->parent = a; + + if ((b->left = l)) + b->left->parent = b; + + if ((a->right = b->right)) + a->right->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 (a->next == b) { + /* A is predecessor of B */ + a->prev = b; + b->next = a; + + if ((a->next = bn)) + a->next->prev = a; + else + q->last = a; + + if ((b->prev = ap)) + b->prev->next = b; + + } else if (b->next == a) { + /* B is predecessor of A */ + a->next = b; + b->prev = a; + + if ((a->prev = bp)) + a->prev->next = a; + + if ((b->next = an)) + b->next->prev = b; + else + q->last = b; + + } else { + /* A is no neighbour of 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 + q->last = b; + } +} + +/* Move a node to the correct position */ +void avahi_prio_queue_shuffle(AvahiPrioQueue *q, AvahiPrioQueueNode *n) { + g_assert(q); + g_assert(n); + + /* Move up until the position is OK */ + while (n->parent && q->compare(n->parent->data, n->data) > 0) + exchange_nodes(q, n, n->parent); + + /* Move down until the position is OK */ + for (;;) { + AvahiPrioQueueNode *min; + + if (!(min = n->left)) { + /* No children */ + g_assert(!n->right); + break; + } + + if (n->right && q->compare(n->right->data, min->data) < 0) + min = n->right; + + /* min now contains the smaller one of our two children */ + + if (q->compare(n->data, min->data) <= 0) + /* Order OK */ + break; + + exchange_nodes(q, n, min); + } +} + +AvahiPrioQueueNode* avahi_prio_queue_put(AvahiPrioQueue *q, gpointer data) { + AvahiPrioQueueNode *n; + g_assert(q); + + 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; + + if (n->x >= ((guint) 1 << n->y)) { + n->x = 0; + n->y++; + } + + q->last->next = n; + n->prev = q->last; + + g_assert(n->y > 0); + n->parent = get_node_at_xy(q, n->x/2, n->y-1); + + if (n->x & 1) + n->parent->right = n; + else + n->parent->left = n; + } else { + g_assert(!q->root); + g_assert(!q->n_nodes); + + n->y = n->x = 0; + q->root = n; + n->prev = n->parent = NULL; + } + + n->next = n->left = n->right = NULL; + q->last = n; + q->n_nodes++; + + avahi_prio_queue_shuffle(q, n); + + return n; +} + +void avahi_prio_queue_remove(AvahiPrioQueue *q, AvahiPrioQueueNode *n) { + g_assert(q); + g_assert(n); + + if (n != q->last) { + AvahiPrioQueueNode *replacement = q->last; + exchange_nodes(q, replacement, n); + avahi_prio_queue_remove(q, n); + avahi_prio_queue_shuffle(q, replacement); + return; + } + + g_assert(n == q->last); + g_assert(!n->next); + g_assert(!n->left); + g_assert(!n->right); + + q->last = n->prev; + + if (n->prev) { + n->prev->next = NULL; + 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 { + g_assert(n->parent->right == n); + g_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); + q->root = NULL; + } + + g_free(n); + + g_assert(q->n_nodes > 0); + q->n_nodes--; +} + -- cgit