]>
Commit | Line | Data |
---|---|---|
b4b594a3 | 1 | #include "cache.h" |
b4b594a3 JH |
2 | #include "prio-queue.h" |
3 | ||
6d63baa4 JK |
4 | static inline int compare(struct prio_queue *queue, int i, int j) |
5 | { | |
6 | int cmp = queue->compare(queue->array[i], queue->array[j], | |
7 | queue->cb_data); | |
8 | return cmp; | |
9 | } | |
10 | ||
11 | static inline void swap(struct prio_queue *queue, int i, int j) | |
12 | { | |
13 | void *tmp = queue->array[i]; | |
14 | queue->array[i] = queue->array[j]; | |
15 | queue->array[j] = tmp; | |
16 | } | |
17 | ||
da24b104 JH |
18 | void prio_queue_reverse(struct prio_queue *queue) |
19 | { | |
20 | int i, j; | |
21 | ||
22 | if (queue->compare != NULL) | |
23 | die("BUG: prio_queue_reverse() on non-LIFO queue"); | |
6d63baa4 JK |
24 | for (i = 0; i <= (j = (queue->nr - 1) - i); i++) |
25 | swap(queue, i, j); | |
da24b104 JH |
26 | } |
27 | ||
b4b594a3 JH |
28 | void clear_prio_queue(struct prio_queue *queue) |
29 | { | |
30 | free(queue->array); | |
31 | queue->nr = 0; | |
32 | queue->alloc = 0; | |
33 | queue->array = NULL; | |
34 | } | |
35 | ||
36 | void prio_queue_put(struct prio_queue *queue, void *thing) | |
37 | { | |
b4b594a3 JH |
38 | int ix, parent; |
39 | ||
40 | /* Append at the end */ | |
41 | ALLOC_GROW(queue->array, queue->nr + 1, queue->alloc); | |
42 | queue->array[queue->nr++] = thing; | |
6d63baa4 | 43 | if (!queue->compare) |
b4b594a3 JH |
44 | return; /* LIFO */ |
45 | ||
46 | /* Bubble up the new one */ | |
47 | for (ix = queue->nr - 1; ix; ix = parent) { | |
48 | parent = (ix - 1) / 2; | |
6d63baa4 | 49 | if (compare(queue, parent, ix) <= 0) |
b4b594a3 JH |
50 | break; |
51 | ||
6d63baa4 | 52 | swap(queue, parent, ix); |
b4b594a3 JH |
53 | } |
54 | } | |
55 | ||
56 | void *prio_queue_get(struct prio_queue *queue) | |
57 | { | |
6d63baa4 | 58 | void *result; |
b4b594a3 | 59 | int ix, child; |
b4b594a3 JH |
60 | |
61 | if (!queue->nr) | |
62 | return NULL; | |
6d63baa4 | 63 | if (!queue->compare) |
b4b594a3 JH |
64 | return queue->array[--queue->nr]; /* LIFO */ |
65 | ||
66 | result = queue->array[0]; | |
67 | if (!--queue->nr) | |
68 | return result; | |
69 | ||
70 | queue->array[0] = queue->array[queue->nr]; | |
71 | ||
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 */ | |
6d63baa4 JK |
75 | if (child + 1 < queue->nr && |
76 | compare(queue, child, child + 1) >= 0) | |
b4b594a3 JH |
77 | child++; /* use right child */ |
78 | ||
6d63baa4 | 79 | if (compare(queue, ix, child) <= 0) |
b4b594a3 JH |
80 | break; |
81 | ||
6d63baa4 | 82 | swap(queue, child, ix); |
b4b594a3 JH |
83 | } |
84 | return result; | |
85 | } |