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