X-Git-Url: http://git.meshlink.io/?a=blobdiff_plain;f=prioq.c;fp=prioq.c;h=0000000000000000000000000000000000000000;hb=f93eca3530bef2cc23ffe6c3a04493ad171c2aed;hp=2eedf27857dfa1c6feb8772df66a8a77e57de62e;hpb=42c9b99f2bb21d0ff1f1918314f9d5dd82a62763;p=catta

diff --git a/prioq.c b/prioq.c
deleted file mode 100644
index 2eedf27..0000000
--- a/prioq.c
+++ /dev/null
@@ -1,359 +0,0 @@
-#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--;
-}
-