22         unsigned *idx;  member
72         assert(!q->items[j].idx || *(q->items[j].idx) == j);  in swap()
73         assert(!q->items[k].idx || *(q->items[k].idx) == k);  in swap()
76         SWAP_TWO(q->items[j].idx, q->items[k].idx);  in swap()
78         if (q->items[j].idx)  in swap()
79                 *q->items[j].idx = j;  in swap()
81         if (q->items[k].idx)  in swap()
82                 *q->items[k].idx = k;  in swap()
85 static unsigned shuffle_up(Prioq *q, unsigned idx) {  in shuffle_up()  argument
87         assert(idx < q->n_items);  in shuffle_up()
89         while (idx > 0) {  in shuffle_up()
92                 k = (idx-1)/2;  in shuffle_up()
94                 if (q->compare_func(q->items[k].data, q->items[idx].data) <= 0)  in shuffle_up()
97                 swap(q, idx, k);  in shuffle_up()
98                 idx = k;  in shuffle_up()
101         return idx;  in shuffle_up()
104 static unsigned shuffle_down(Prioq *q, unsigned idx) {  in shuffle_down()  argument
110                 k = (idx+1)*2; /* right child */  in shuffle_down()
116                 if (q->compare_func(q->items[j].data, q->items[idx].data) < 0)  in shuffle_down()
122                         s = idx;  in shuffle_down()
133                 if (s == idx)  in shuffle_down()
137                 swap(q, idx, s);  in shuffle_down()
138                 idx = s;  in shuffle_down()
141         return idx;  in shuffle_down()
144 int prioq_put(Prioq *q, void *data, unsigned *idx) {  in prioq_put()  argument
166         i->idx = idx;  in prioq_put()
168         if (idx)  in prioq_put()
169                 *idx = k;  in prioq_put()
176 int prioq_ensure_put(Prioq **q, compare_func_t compare_func, void *data, unsigned *idx) {  in prioq_ensure_put()  argument
183         return prioq_put(*q, data, idx);  in prioq_ensure_put()
206                 i->idx = l->idx;  in remove_item()
207                 if (i->idx)  in remove_item()
208                         *i->idx = k;  in remove_item()
216 _pure_ static struct prioq_item* find_item(Prioq *q, void *data, unsigned *idx) {  in find_item()  argument
224         if (idx) {  in find_item()
225                 if (*idx == PRIOQ_IDX_NULL ||  in find_item()
226                     *idx >= q->n_items)  in find_item()
229                 i = q->items + *idx;  in find_item()
242 int prioq_remove(Prioq *q, void *data, unsigned *idx) {  in prioq_remove()  argument
248         i = find_item(q, data, idx);  in prioq_remove()
256 int prioq_reshuffle(Prioq *q, void *data, unsigned *idx) {  in prioq_reshuffle()  argument
262         i = find_item(q, data, idx);  in prioq_reshuffle()
272 void *prioq_peek_by_index(Prioq *q, unsigned idx) {  in prioq_peek_by_index()  argument
276         if (idx >= q->n_items)  in prioq_peek_by_index()
279         return q->items[idx].data;  in prioq_peek_by_index()