Lines Matching refs:pq
32 int nghttp2_pq_init(nghttp2_pq *pq, nghttp2_less less, nghttp2_mem *mem) in nghttp2_pq_init() argument
34 pq->mem = mem; in nghttp2_pq_init()
35 pq->capacity = 0; in nghttp2_pq_init()
36 pq->q = NULL; in nghttp2_pq_init()
37 pq->length = 0; in nghttp2_pq_init()
38 pq->less = less; in nghttp2_pq_init()
42 void nghttp2_pq_free(nghttp2_pq *pq) in nghttp2_pq_free() argument
44 nghttp2_mem_free(pq->mem, pq->q); in nghttp2_pq_free()
45 pq->q = NULL; in nghttp2_pq_free()
48 static void swap(nghttp2_pq *pq, size_t i, size_t j) in swap() argument
50 nghttp2_pq_entry *a = pq->q[i]; in swap()
51 nghttp2_pq_entry *b = pq->q[j]; in swap()
53 pq->q[i] = b; in swap()
55 pq->q[j] = a; in swap()
59 static void bubble_up(nghttp2_pq *pq, size_t index) in bubble_up() argument
64 if (!pq->less(pq->q[index], pq->q[parent])) { in bubble_up()
67 swap(pq, parent, index); in bubble_up()
72 int nghttp2_pq_push(nghttp2_pq *pq, nghttp2_pq_entry *item) in nghttp2_pq_push() argument
74 if (pq->capacity <= pq->length) { in nghttp2_pq_push()
78 ncapacity = nghttp2_max(4, (pq->capacity * 2)); in nghttp2_pq_push()
80 nq = nghttp2_mem_realloc(pq->mem, pq->q, in nghttp2_pq_push()
85 pq->capacity = ncapacity; in nghttp2_pq_push()
86 pq->q = nq; in nghttp2_pq_push()
88 pq->q[pq->length] = item; in nghttp2_pq_push()
89 item->index = pq->length; in nghttp2_pq_push()
90 ++pq->length; in nghttp2_pq_push()
91 bubble_up(pq, pq->length - 1); in nghttp2_pq_push()
95 nghttp2_pq_entry *nghttp2_pq_top(nghttp2_pq *pq) in nghttp2_pq_top() argument
97 if (pq->length == 0) { in nghttp2_pq_top()
100 return pq->q[0]; in nghttp2_pq_top()
104 static void bubble_down(nghttp2_pq *pq, size_t index) in bubble_down() argument
111 if (j >= pq->length) { in bubble_down()
114 if (pq->less(pq->q[j], pq->q[minindex])) { in bubble_down()
121 swap(pq, index, minindex); in bubble_down()
126 void nghttp2_pq_pop(nghttp2_pq *pq) in nghttp2_pq_pop() argument
128 if (pq->length > 0) { in nghttp2_pq_pop()
129 pq->q[0] = pq->q[pq->length - 1]; in nghttp2_pq_pop()
130 pq->q[0]->index = 0; in nghttp2_pq_pop()
131 --pq->length; in nghttp2_pq_pop()
132 bubble_down(pq, 0); in nghttp2_pq_pop()
136 void nghttp2_pq_remove(nghttp2_pq *pq, nghttp2_pq_entry *item) in nghttp2_pq_remove() argument
138 assert(pq->q[item->index] == item); in nghttp2_pq_remove()
141 nghttp2_pq_pop(pq); in nghttp2_pq_remove()
145 if (item->index == pq->length - 1) { in nghttp2_pq_remove()
146 --pq->length; in nghttp2_pq_remove()
150 pq->q[item->index] = pq->q[pq->length - 1]; in nghttp2_pq_remove()
151 pq->q[item->index]->index = item->index; in nghttp2_pq_remove()
152 --pq->length; in nghttp2_pq_remove()
154 if (pq->less(item, pq->q[item->index])) { in nghttp2_pq_remove()
155 bubble_down(pq, item->index); in nghttp2_pq_remove()
157 bubble_up(pq, item->index); in nghttp2_pq_remove()
161 int nghttp2_pq_empty(nghttp2_pq *pq) in nghttp2_pq_empty() argument
163 return pq->length == 0; in nghttp2_pq_empty()
166 size_t nghttp2_pq_size(nghttp2_pq *pq) in nghttp2_pq_size() argument
168 return pq->length; in nghttp2_pq_size()
171 void nghttp2_pq_update(nghttp2_pq *pq, nghttp2_pq_item_cb fun, void *arg) in nghttp2_pq_update() argument
175 if (pq->length == 0) { in nghttp2_pq_update()
178 for (i = 0; i < pq->length; ++i) { in nghttp2_pq_update()
179 rv |= (*fun)(pq->q[i], arg); in nghttp2_pq_update()
182 for (i = pq->length; i > 0; --i) { in nghttp2_pq_update()
183 bubble_down(pq, i - 1); in nghttp2_pq_update()
188 int nghttp2_pq_each(nghttp2_pq *pq, nghttp2_pq_item_cb fun, void *arg) in nghttp2_pq_each() argument
192 if (pq->length == 0) { in nghttp2_pq_each()
195 for (i = 0; i < pq->length; ++i) { in nghttp2_pq_each()
196 if ((*fun)(pq->q[i], arg)) { in nghttp2_pq_each()