Lines Matching defs:pq
33 void nghttp3_pq_init(nghttp3_pq *pq, nghttp3_less less,
35 pq->mem = mem;
36 pq->capacity = 0;
37 pq->q = NULL;
38 pq->length = 0;
39 pq->less = less;
42 void nghttp3_pq_free(nghttp3_pq *pq) {
43 nghttp3_mem_free(pq->mem, pq->q);
44 pq->q = NULL;
47 static void swap(nghttp3_pq *pq, size_t i, size_t j) {
48 nghttp3_pq_entry *a = pq->q[i];
49 nghttp3_pq_entry *b = pq->q[j];
51 pq->q[i] = b;
53 pq->q[j] = a;
57 static void bubble_up(nghttp3_pq *pq, size_t index) {
61 if (!pq->less(pq->q[index], pq->q[parent])) {
64 swap(pq, parent, index);
69 int nghttp3_pq_push(nghttp3_pq *pq, nghttp3_pq_entry *item) {
70 if (pq->capacity <= pq->length) {
74 ncapacity = nghttp3_max(4, (pq->capacity * 2));
76 nq = nghttp3_mem_realloc(pq->mem, pq->q,
81 pq->capacity = ncapacity;
82 pq->q = nq;
84 pq->q[pq->length] = item;
85 item->index = pq->length;
86 ++pq->length;
87 bubble_up(pq, pq->length - 1);
91 nghttp3_pq_entry *nghttp3_pq_top(const nghttp3_pq *pq) {
92 assert(pq->length);
93 return pq->q[0];
96 static void bubble_down(nghttp3_pq *pq, size_t index) {
102 if (j >= pq->length) {
105 if (pq->less(pq->q[j], pq->q[minindex])) {
112 swap(pq, index, minindex);
117 void nghttp3_pq_pop(nghttp3_pq *pq) {
118 if (pq->length > 0) {
119 pq->q[0] = pq->q[pq->length - 1];
120 pq->q[0]->index = 0;
121 --pq->length;
122 bubble_down(pq, 0);
126 void nghttp3_pq_remove(nghttp3_pq *pq, nghttp3_pq_entry *item) {
127 assert(pq->q[item->index] == item);
130 nghttp3_pq_pop(pq);
134 if (item->index == pq->length - 1) {
135 --pq->length;
139 pq->q[item->index] = pq->q[pq->length - 1];
140 pq->q[item->index]->index = item->index;
141 --pq->length;
143 if (pq->less(item, pq->q[item->index])) {
144 bubble_down(pq, item->index);
146 bubble_up(pq, item->index);
150 int nghttp3_pq_empty(const nghttp3_pq *pq) { return pq->length == 0; }
152 size_t nghttp3_pq_size(const nghttp3_pq *pq) { return pq->length; }
154 int nghttp3_pq_each(const nghttp3_pq *pq, nghttp3_pq_item_cb fun, void *arg) {
157 if (pq->length == 0) {
160 for (i = 0; i < pq->length; ++i) {
161 if ((*fun)(pq->q[i], arg)) {
168 void nghttp3_pq_clear(nghttp3_pq *pq) { pq->length = 0; }