rename libavahi-core to avahi-core

git-svn-id: file:///home/lennart/svn/public/avahi/trunk@57 941a03a8-eaeb-0310-b9a0-b1bbd8fe43fe

1 files changed, 384 insertions, 0 deletions

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 <config.h>
+#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--;
+}
+