Lines Matching defs:pq
32 void nghttp2_pq_init(nghttp2_pq *pq, nghttp2_less less, nghttp2_mem *mem) {
33 pq->mem = mem;
34 pq->capacity = 0;
35 pq->q = NULL;
36 pq->length = 0;
37 pq->less = less;
40 void nghttp2_pq_free(nghttp2_pq *pq) {
41 nghttp2_mem_free(pq->mem, pq->q);
42 pq->q = NULL;
45 static void swap(nghttp2_pq *pq, size_t i, size_t j) {
46 nghttp2_pq_entry *a = pq->q[i];
47 nghttp2_pq_entry *b = pq->q[j];
49 pq->q[i] = b;
51 pq->q[j] = a;
55 static void bubble_up(nghttp2_pq *pq, size_t index) {
59 if (!pq->less(pq->q[index], pq->q[parent])) {
62 swap(pq, parent, index);
67 int nghttp2_pq_push(nghttp2_pq *pq, nghttp2_pq_entry *item) {
68 if (pq->capacity <= pq->length) {
72 ncapacity = nghttp2_max(4, (pq->capacity * 2));
74 nq = nghttp2_mem_realloc(pq->mem, pq->q,
79 pq->capacity = ncapacity;
80 pq->q = nq;
82 pq->q[pq->length] = item;
83 item->index = pq->length;
84 ++pq->length;
85 bubble_up(pq, pq->length - 1);
89 nghttp2_pq_entry *nghttp2_pq_top(nghttp2_pq *pq) {
90 if (pq->length == 0) {
93 return pq->q[0];
97 static void bubble_down(nghttp2_pq *pq, size_t index) {
103 if (j >= pq->length) {
106 if (pq->less(pq->q[j], pq->q[minindex])) {
113 swap(pq, index, minindex);
118 void nghttp2_pq_pop(nghttp2_pq *pq) {
119 if (pq->length > 0) {
120 pq->q[0] = pq->q[pq->length - 1];
121 pq->q[0]->index = 0;
122 --pq->length;
123 bubble_down(pq, 0);
127 void nghttp2_pq_remove(nghttp2_pq *pq, nghttp2_pq_entry *item) {
128 assert(pq->q[item->index] == item);
131 nghttp2_pq_pop(pq);
135 if (item->index == pq->length - 1) {
136 --pq->length;
140 pq->q[item->index] = pq->q[pq->length - 1];
141 pq->q[item->index]->index = item->index;
142 --pq->length;
144 if (pq->less(item, pq->q[item->index])) {
145 bubble_down(pq, item->index);
147 bubble_up(pq, item->index);
151 int nghttp2_pq_empty(nghttp2_pq *pq) { return pq->length == 0; }
153 size_t nghttp2_pq_size(nghttp2_pq *pq) { return pq->length; }
155 void nghttp2_pq_update(nghttp2_pq *pq, nghttp2_pq_item_cb fun, void *arg) {
158 if (pq->length == 0) {
161 for (i = 0; i < pq->length; ++i) {
162 rv |= (*fun)(pq->q[i], arg);
165 for (i = pq->length; i > 0; --i) {
166 bubble_down(pq, i - 1);
171 int nghttp2_pq_each(nghttp2_pq *pq, nghttp2_pq_item_cb fun, void *arg) {
174 if (pq->length == 0) {
177 for (i = 0; i < pq->length; ++i) {
178 if ((*fun)(pq->q[i], arg)) {