2 #include "prio-queue.h"
4 static inline int compare(struct prio_queue
*queue
, int i
, int j
)
6 int cmp
= queue
->compare(queue
->array
[i
], queue
->array
[j
],
11 static inline void swap(struct prio_queue
*queue
, int i
, int j
)
13 void *tmp
= queue
->array
[i
];
14 queue
->array
[i
] = queue
->array
[j
];
15 queue
->array
[j
] = tmp
;
18 void prio_queue_reverse(struct prio_queue
*queue
)
22 if (queue
->compare
!= NULL
)
23 die("BUG: prio_queue_reverse() on non-LIFO queue");
24 for (i
= 0; i
<= (j
= (queue
->nr
- 1) - i
); i
++)
28 void clear_prio_queue(struct prio_queue
*queue
)
36 void prio_queue_put(struct prio_queue
*queue
, void *thing
)
40 /* Append at the end */
41 ALLOC_GROW(queue
->array
, queue
->nr
+ 1, queue
->alloc
);
42 queue
->array
[queue
->nr
++] = thing
;
46 /* Bubble up the new one */
47 for (ix
= queue
->nr
- 1; ix
; ix
= parent
) {
48 parent
= (ix
- 1) / 2;
49 if (compare(queue
, parent
, ix
) <= 0)
52 swap(queue
, parent
, ix
);
56 void *prio_queue_get(struct prio_queue
*queue
)
64 return queue
->array
[--queue
->nr
]; /* LIFO */
66 result
= queue
->array
[0];
70 queue
->array
[0] = queue
->array
[queue
->nr
];
72 /* Push down the one at the root */
73 for (ix
= 0; ix
* 2 + 1 < queue
->nr
; ix
= child
) {
74 child
= ix
* 2 + 1; /* left */
75 if (child
+ 1 < queue
->nr
&&
76 compare(queue
, child
, child
+ 1) >= 0)
77 child
++; /* use right child */
79 if (compare(queue
, ix
, child
) <= 0)
82 swap(queue
, child
, ix
);