Line | Count | Source |
1 | | #include "git-compat-util.h" |
2 | | #include "prio-queue.h" |
3 | | |
4 | | static inline int compare(struct prio_queue *queue, size_t i, size_t j) |
5 | 0 | { |
6 | 0 | int cmp = queue->compare(queue->array[i].data, queue->array[j].data, |
7 | 0 | queue->cb_data); |
8 | 0 | if (!cmp) |
9 | 0 | cmp = (queue->array[i].ctr > queue->array[j].ctr) - |
10 | 0 | (queue->array[i].ctr < queue->array[j].ctr); |
11 | 0 | return cmp; |
12 | 0 | } |
13 | | |
14 | | static inline void swap(struct prio_queue *queue, size_t i, size_t j) |
15 | 0 | { |
16 | 0 | SWAP(queue->array[i], queue->array[j]); |
17 | 0 | } |
18 | | |
19 | | void prio_queue_reverse(struct prio_queue *queue) |
20 | 0 | { |
21 | 0 | size_t i, j; |
22 | |
|
23 | 0 | if (queue->compare) |
24 | 0 | BUG("prio_queue_reverse() on non-LIFO queue"); |
25 | 0 | if (!queue->nr_) |
26 | 0 | return; |
27 | 0 | for (i = 0; i < (j = (queue->nr_ - 1) - i); i++) |
28 | 0 | swap(queue, i, j); |
29 | 0 | } |
30 | | |
31 | | void clear_prio_queue(struct prio_queue *queue) |
32 | 0 | { |
33 | 0 | FREE_AND_NULL(queue->array); |
34 | 0 | queue->nr_ = 0; |
35 | 0 | queue->alloc = 0; |
36 | 0 | queue->insertion_ctr = 0; |
37 | 0 | queue->get_pending = 0; |
38 | 0 | } |
39 | | |
40 | | static void sift_down_root(struct prio_queue *queue) |
41 | 0 | { |
42 | 0 | size_t ix, child; |
43 | | |
44 | | /* Push down the one at the root */ |
45 | 0 | for (ix = 0; ix * 2 + 1 < queue->nr_; ix = child) { |
46 | 0 | child = ix * 2 + 1; /* left */ |
47 | 0 | if (child + 1 < queue->nr_ && |
48 | 0 | compare(queue, child, child + 1) >= 0) |
49 | 0 | child++; /* use right child */ |
50 | |
|
51 | 0 | if (compare(queue, ix, child) <= 0) |
52 | 0 | break; |
53 | | |
54 | 0 | swap(queue, child, ix); |
55 | 0 | } |
56 | 0 | } |
57 | | |
58 | | static inline void flush_get(struct prio_queue *queue) |
59 | 0 | { |
60 | 0 | if (!queue->get_pending) |
61 | 0 | return; |
62 | 0 | queue->get_pending = 0; |
63 | 0 | queue->array[0] = queue->array[--queue->nr_]; |
64 | 0 | sift_down_root(queue); |
65 | 0 | } |
66 | | |
67 | | void prio_queue_put(struct prio_queue *queue, void *thing) |
68 | 0 | { |
69 | 0 | size_t ix, parent; |
70 | |
|
71 | 0 | if (queue->get_pending) { |
72 | 0 | queue->get_pending = 0; |
73 | 0 | queue->array[0].ctr = queue->insertion_ctr++; |
74 | 0 | queue->array[0].data = thing; |
75 | 0 | sift_down_root(queue); |
76 | 0 | return; |
77 | 0 | } |
78 | | |
79 | | /* Append at the end */ |
80 | 0 | ALLOC_GROW(queue->array, queue->nr_ + 1, queue->alloc); |
81 | 0 | queue->array[queue->nr_].ctr = queue->insertion_ctr++; |
82 | 0 | queue->array[queue->nr_].data = thing; |
83 | 0 | queue->nr_++; |
84 | 0 | if (!queue->compare) |
85 | 0 | return; /* LIFO */ |
86 | | |
87 | | /* Bubble up the new one */ |
88 | 0 | for (ix = queue->nr_ - 1; ix; ix = parent) { |
89 | 0 | parent = (ix - 1) / 2; |
90 | 0 | if (compare(queue, parent, ix) <= 0) |
91 | 0 | break; |
92 | | |
93 | 0 | swap(queue, parent, ix); |
94 | 0 | } |
95 | 0 | } |
96 | | |
97 | | void *prio_queue_get(struct prio_queue *queue) |
98 | 0 | { |
99 | 0 | if (queue->nr_ <= queue->get_pending) { |
100 | 0 | queue->nr_ = 0; |
101 | 0 | queue->get_pending = 0; |
102 | 0 | return NULL; |
103 | 0 | } |
104 | 0 | if (!queue->compare) |
105 | 0 | return queue->array[--queue->nr_].data; /* LIFO */ |
106 | | |
107 | 0 | flush_get(queue); |
108 | |
|
109 | 0 | queue->get_pending = 1; |
110 | 0 | return queue->array[0].data; |
111 | 0 | } |
112 | | |
113 | | void *prio_queue_peek(struct prio_queue *queue) |
114 | 0 | { |
115 | 0 | if (queue->nr_ <= queue->get_pending) { |
116 | 0 | queue->nr_ = 0; |
117 | 0 | queue->get_pending = 0; |
118 | 0 | return NULL; |
119 | 0 | } |
120 | 0 | if (!queue->compare) |
121 | 0 | return queue->array[queue->nr_ - 1].data; |
122 | | |
123 | 0 | flush_get(queue); |
124 | |
|
125 | 0 | return queue->array[0].data; |
126 | 0 | } |