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
].data
, queue
->array
[j
].data
,
9 cmp
= queue
->array
[i
].ctr
- queue
->array
[j
].ctr
;
13 static inline void swap(struct prio_queue
*queue
, int i
, int j
)
15 SWAP(queue
->array
[i
], queue
->array
[j
]);
18 void prio_queue_reverse(struct prio_queue
*queue
)
22 if (queue
->compare
!= NULL
)
23 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
)
30 FREE_AND_NULL(queue
->array
);
33 queue
->insertion_ctr
= 0;
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
].ctr
= queue
->insertion_ctr
++;
43 queue
->array
[queue
->nr
].data
= thing
;
48 /* Bubble up the new one */
49 for (ix
= queue
->nr
- 1; ix
; ix
= parent
) {
50 parent
= (ix
- 1) / 2;
51 if (compare(queue
, parent
, ix
) <= 0)
54 swap(queue
, parent
, ix
);
58 void *prio_queue_get(struct prio_queue
*queue
)
66 return queue
->array
[--queue
->nr
].data
; /* LIFO */
68 result
= queue
->array
[0].data
;
72 queue
->array
[0] = queue
->array
[queue
->nr
];
74 /* Push down the one at the root */
75 for (ix
= 0; ix
* 2 + 1 < queue
->nr
; ix
= child
) {
76 child
= ix
* 2 + 1; /* left */
77 if (child
+ 1 < queue
->nr
&&
78 compare(queue
, child
, child
+ 1) >= 0)
79 child
++; /* use right child */
81 if (compare(queue
, ix
, child
) <= 0)
84 swap(queue
, child
, ix
);
89 void *prio_queue_peek(struct prio_queue
*queue
)
94 return queue
->array
[queue
->nr
- 1].data
;
95 return queue
->array
[0].data
;