2 This file is part of catta.
4 catta is free software; you can redistribute it and/or modify it
5 under the terms of the GNU Lesser General Public License as
6 published by the Free Software Foundation; either version 2.1 of the
7 License, or (at your option) any later version.
9 catta is distributed in the hope that it will be useful, but WITHOUT
10 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
11 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
12 Public License for more details.
14 You should have received a copy of the GNU Lesser General Public
15 License along with catta; if not, write to the Free Software
16 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
27 #include <catta/malloc.h>
31 CattaPrioQueue* catta_prio_queue_new(CattaPQCompareFunc compare) {
35 if (!(q = catta_new(CattaPrioQueue, 1)))
36 return NULL; /* OOM */
38 q->root = q->last = NULL;
45 void catta_prio_queue_free(CattaPrioQueue *q) {
49 catta_prio_queue_remove(q, q->last);
55 static CattaPrioQueueNode* get_node_at_xy(CattaPrioQueue *q, unsigned x, unsigned y) {
57 CattaPrioQueueNode *n;
63 for (r = 0; r < y; r++) {
66 if ((x >> (y-r-1)) & 1)
78 static void exchange_nodes(CattaPrioQueue *q, CattaPrioQueueNode *a, CattaPrioQueueNode *b) {
79 CattaPrioQueueNode *l, *r, *p, *ap, *an, *bp, *bn;
87 t = a->x; a->x = b->x; b->x = t;
88 t = a->y; a->y = b->y; b->y = t;
91 /* B is parent of A */
96 if ((a->parent = p)) {
97 if (a->parent->left == b)
100 a->parent->right = a;
105 if ((b->left = a->left))
110 if ((a->right = b->right))
111 a->right->parent = a;
113 b->right->parent = b;
116 if ((b->right = a->right))
117 b->right->parent = b;
121 if ((a->left = b->left))
126 } else if (b->parent == a) {
127 /* A ist parent of B */
132 if ((b->parent = p)) {
133 if (b->parent->left == a)
136 b->parent->right = b;
141 if ((a->left = b->left))
146 if ((a->right = b->right))
147 a->right->parent = a;
149 b->right->parent = b;
151 if ((a->right = b->right))
152 a->right->parent = a;
156 if ((a->left = b->left))
162 CattaPrioQueueNode *apl = NULL, *bpl = NULL;
173 if ((a->parent = bp)) {
181 if ((b->parent = ap)) {
193 if ((a->left = b->left))
199 if ((a->right = b->right))
200 a->right->parent = a;
203 b->right->parent = b;
207 ap = a->prev; an = a->next;
208 bp = b->prev; bn = b->next;
211 /* A is predecessor of B */
223 } else if (b->next == a) {
224 /* B is predecessor of A */
237 /* A is no neighbour of B */
257 /* Move a node to the correct position */
258 void catta_prio_queue_shuffle(CattaPrioQueue *q, CattaPrioQueueNode *n) {
261 assert(n->queue == q);
263 /* Move up until the position is OK */
264 while (n->parent && q->compare(n->parent->data, n->data) > 0)
265 exchange_nodes(q, n, n->parent);
267 /* Move down until the position is OK */
269 CattaPrioQueueNode *min;
271 if (!(min = n->left)) {
277 if (n->right && q->compare(n->right->data, min->data) < 0)
280 /* min now contains the smaller one of our two children */
282 if (q->compare(n->data, min->data) <= 0)
286 exchange_nodes(q, n, min);
290 CattaPrioQueueNode* catta_prio_queue_put(CattaPrioQueue *q, void* data) {
291 CattaPrioQueueNode *n;
294 if (!(n = catta_new(CattaPrioQueueNode, 1)))
295 return NULL; /* OOM */
307 if (n->x >= ((unsigned) 1 << n->y)) {
316 n->parent = get_node_at_xy(q, n->x/2, n->y-1);
319 n->parent->right = n;
328 n->prev = n->parent = NULL;
331 n->next = n->left = n->right = NULL;
335 catta_prio_queue_shuffle(q, n);
340 void catta_prio_queue_remove(CattaPrioQueue *q, CattaPrioQueueNode *n) {
343 assert(q == n->queue);
346 CattaPrioQueueNode *replacement = q->last;
347 exchange_nodes(q, replacement, n);
348 catta_prio_queue_remove(q, n);
349 catta_prio_queue_shuffle(q, replacement);
353 assert(n == q->last);
361 n->prev->next = NULL;
368 if (n->parent->left == n) {
369 assert(n->parent->right == NULL);
370 n->parent->left = NULL;
372 assert(n->parent->right == n);
373 assert(n->parent->left != NULL);
374 n->parent->right = NULL;
377 assert(q->root == n);
379 assert(q->n_nodes == 1);
385 assert(q->n_nodes > 0);