3 AvahiPrioQueue* avahi_prio_queue_new(gint (*compare) (gconstpointer a, gconstpointer b)) {
7 q = g_new(AvahiPrioQueue, 1);
8 q->root = q->last = NULL;
14 void avahi_prio_queue_free(AvahiPrioQueue *q) {
18 avahi_prio_queue_remove(q, q->last);
20 g_assert(!q->n_nodes);
24 static AvahiPrioQueueNode* get_node_at_xy(AvahiPrioQueue *q, guint x, guint y) {
26 AvahiPrioQueueNode *n;
32 for (r = 0; r < y; r++) {
35 if ((x >> (y-r-1)) & 1)
47 static void exchange_nodes(AvahiPrioQueue *q, AvahiPrioQueueNode *a, AvahiPrioQueueNode *b) {
48 AvahiPrioQueueNode *l, *r, *p, *ap, *an, *bp, *bn;
56 t = a->x; a->x = b->x; b->x = t;
57 t = a->y; a->y = b->y; b->y = t;
60 /* B is parent of A */
65 if ((a->parent = p)) {
66 if (a->parent->left == b)
74 if ((b->left = a->left))
79 if ((a->right = b->right))
85 if ((b->right = a->right))
90 if ((a->left = b->left))
95 } else if (b->parent == a) {
96 /* A ist parent of B */
101 if ((b->parent = p)) {
102 if (b->parent->left == a)
105 b->parent->right = b;
110 if ((a->left = b->left))
115 if ((a->right = b->right))
116 a->right->parent = a;
118 b->right->parent = b;
120 if ((a->right = b->right))
121 a->right->parent = a;
125 if ((a->left = b->left))
131 AvahiPrioQueueNode *apl = NULL, *bpl = NULL;
142 if ((a->parent = bp)) {
150 if ((b->parent = ap)) {
162 if ((a->left = b->left))
168 if ((a->right = b->right))
169 a->right->parent = a;
172 b->right->parent = b;
176 ap = a->prev; an = a->next;
177 bp = b->prev; bn = b->next;
180 /* A is predecessor of B */
192 } else if (b->next == a) {
193 /* B is predecessor of A */
206 /* A is no neighbour of B */
226 /* Move a node to the correct position */
227 void avahi_prio_queue_shuffle(AvahiPrioQueue *q, AvahiPrioQueueNode *n) {
231 /* Move up until the position is OK */
232 while (n->parent && q->compare(n->parent->data, n->data) > 0)
233 exchange_nodes(q, n, n->parent);
235 /* Move down until the position is OK */
237 AvahiPrioQueueNode *min;
239 if (!(min = n->left)) {
245 if (n->right && q->compare(n->right->data, min->data) < 0)
248 /* min now contains the smaller one of our two children */
250 if (q->compare(n->data, min->data) <= 0)
254 exchange_nodes(q, n, min);
258 AvahiPrioQueueNode* avahi_prio_queue_put(AvahiPrioQueue *q, gpointer data) {
259 AvahiPrioQueueNode *n;
262 n = g_new(AvahiPrioQueueNode, 1);
268 g_assert(q->n_nodes);
273 if (n->x >= ((guint) 1 << n->y)) {
282 n->parent = get_node_at_xy(q, n->x/2, n->y-1);
285 n->parent->right = n;
290 g_assert(!q->n_nodes);
294 n->prev = n->parent = NULL;
297 n->next = n->left = n->right = NULL;
301 avahi_prio_queue_shuffle(q, n);
306 void avahi_prio_queue_remove(AvahiPrioQueue *q, AvahiPrioQueueNode *n) {
311 AvahiPrioQueueNode *replacement = q->last;
312 exchange_nodes(q, replacement, n);
313 avahi_prio_queue_remove(q, n);
314 avahi_prio_queue_shuffle(q, replacement);
318 g_assert(n == q->last);
326 n->prev->next = NULL;
329 g_assert(!n->parent);
333 if (n->parent->left == n) {
334 if (n->parent->right != NULL) {
340 g_assert(n->parent->right == NULL);
341 n->parent->left = NULL;
343 g_assert(n->parent->right == n);
344 g_assert(n->parent->left != NULL);
345 n->parent->right = NULL;
348 g_assert(q->root == n);
350 g_assert(q->n_nodes == 1);
356 g_assert(q->n_nodes > 0);