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