| /*** |
| 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 <assert.h> |
| #include <stdlib.h> |
| |
| #include "avahi-common/avahi-malloc.h" |
| |
| #include "prioq.h" |
| |
| AvahiPrioQueue* avahi_prio_queue_new(AvahiPQCompareFunc compare) { |
| AvahiPrioQueue *q; |
| assert(compare); |
| |
| if (!(q = avahi_new(AvahiPrioQueue, 1))) |
| return NULL; /* OOM */ |
| |
| q->root = q->last = NULL; |
| q->n_nodes = 0; |
| q->compare = compare; |
| |
| return q; |
| } |
| |
| void avahi_prio_queue_free(AvahiPrioQueue *q) { |
| assert(q); |
| |
| while (q->last) |
| avahi_prio_queue_remove(q, q->last); |
| |
| assert(!q->n_nodes); |
| avahi_free(q); |
| } |
| |
| static AvahiPrioQueueNode* get_node_at_xy(AvahiPrioQueue *q, unsigned x, unsigned y) { |
| unsigned r; |
| AvahiPrioQueueNode *n; |
| assert(q); |
| |
| n = q->root; |
| assert(n); |
| |
| for (r = 0; r < y; r++) { |
| assert(n); |
| |
| if ((x >> (y-r-1)) & 1) |
| n = n->right; |
| else |
| n = n->left; |
| } |
| |
| 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; |
| unsigned t; |
| assert(q); |
| assert(a); |
| assert(b); |
| 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) { |
| 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) |
| exchange_nodes(q, n, n->parent); |
| |
| /* Move down until the position is OK */ |
| for (;;) { |
| AvahiPrioQueueNode *min; |
| |
| if (!(min = n->left)) { |
| /* No children */ |
| 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, void* data) { |
| AvahiPrioQueueNode *n; |
| assert(q); |
| |
| if (!(n = avahi_new(AvahiPrioQueueNode, 1))) |
| return NULL; /* OOM */ |
| |
| n->queue = q; |
| n->data = data; |
| |
| if (q->last) { |
| assert(q->root); |
| assert(q->n_nodes); |
| |
| n->y = q->last->y; |
| n->x = q->last->x+1; |
| |
| if (n->x >= ((unsigned) 1 << n->y)) { |
| n->x = 0; |
| n->y++; |
| } |
| |
| q->last->next = n; |
| n->prev = q->last; |
| |
| 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 { |
| assert(!q->root); |
| 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) { |
| assert(q); |
| assert(n); |
| assert(q == n->queue); |
| |
| 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; |
| } |
| |
| assert(n == q->last); |
| assert(!n->next); |
| assert(!n->left); |
| assert(!n->right); |
| |
| q->last = n->prev; |
| |
| if (n->prev) { |
| n->prev->next = NULL; |
| assert(n->parent); |
| } else |
| assert(!n->parent); |
| |
| if (n->parent) { |
| assert(n->prev); |
| if (n->parent->left == n) { |
| assert(n->parent->right == NULL); |
| n->parent->left = NULL; |
| } else { |
| assert(n->parent->right == n); |
| assert(n->parent->left != NULL); |
| n->parent->right = NULL; |
| } |
| } else { |
| assert(q->root == n); |
| assert(!n->prev); |
| assert(q->n_nodes == 1); |
| q->root = NULL; |
| } |
| |
| avahi_free(n); |
| |
| assert(q->n_nodes > 0); |
| q->n_nodes--; |
| } |
| |