1 /*
2 * nghttp2 - HTTP/2 C Library
3 *
4 * Copyright (c) 2012 Tatsuhiro Tsujikawa
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 */
25 #include "nghttp2_pq.h"
26
27 #include <stdio.h>
28 #include <assert.h>
29
30 #include "nghttp2_helper.h"
31
nghttp2_pq_init(nghttp2_pq * pq,nghttp2_less less,nghttp2_mem * mem)32 int 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;
38 return 0;
39 }
40
nghttp2_pq_free(nghttp2_pq * pq)41 void nghttp2_pq_free(nghttp2_pq *pq) {
42 nghttp2_mem_free(pq->mem, pq->q);
43 pq->q = NULL;
44 }
45
swap(nghttp2_pq * pq,size_t i,size_t j)46 static void swap(nghttp2_pq *pq, size_t i, size_t j) {
47 nghttp2_pq_entry *a = pq->q[i];
48 nghttp2_pq_entry *b = pq->q[j];
49
50 pq->q[i] = b;
51 b->index = i;
52 pq->q[j] = a;
53 a->index = j;
54 }
55
bubble_up(nghttp2_pq * pq,size_t index)56 static void bubble_up(nghttp2_pq *pq, size_t index) {
57 size_t parent;
58 while (index != 0) {
59 parent = (index - 1) / 2;
60 if (!pq->less(pq->q[index], pq->q[parent])) {
61 return;
62 }
63 swap(pq, parent, index);
64 index = parent;
65 }
66 }
67
nghttp2_pq_push(nghttp2_pq * pq,nghttp2_pq_entry * item)68 int nghttp2_pq_push(nghttp2_pq *pq, nghttp2_pq_entry *item) {
69 if (pq->capacity <= pq->length) {
70 void *nq;
71 size_t ncapacity;
72
73 ncapacity = nghttp2_max(4, (pq->capacity * 2));
74
75 nq = nghttp2_mem_realloc(pq->mem, pq->q,
76 ncapacity * sizeof(nghttp2_pq_entry *));
77 if (nq == NULL) {
78 return NGHTTP2_ERR_NOMEM;
79 }
80 pq->capacity = ncapacity;
81 pq->q = nq;
82 }
83 pq->q[pq->length] = item;
84 item->index = pq->length;
85 ++pq->length;
86 bubble_up(pq, pq->length - 1);
87 return 0;
88 }
89
nghttp2_pq_top(nghttp2_pq * pq)90 nghttp2_pq_entry *nghttp2_pq_top(nghttp2_pq *pq) {
91 if (pq->length == 0) {
92 return NULL;
93 } else {
94 return pq->q[0];
95 }
96 }
97
bubble_down(nghttp2_pq * pq,size_t index)98 static void bubble_down(nghttp2_pq *pq, size_t index) {
99 size_t i, j, minindex;
100 for (;;) {
101 j = index * 2 + 1;
102 minindex = index;
103 for (i = 0; i < 2; ++i, ++j) {
104 if (j >= pq->length) {
105 break;
106 }
107 if (pq->less(pq->q[j], pq->q[minindex])) {
108 minindex = j;
109 }
110 }
111 if (minindex == index) {
112 return;
113 }
114 swap(pq, index, minindex);
115 index = minindex;
116 }
117 }
118
nghttp2_pq_pop(nghttp2_pq * pq)119 void nghttp2_pq_pop(nghttp2_pq *pq) {
120 if (pq->length > 0) {
121 pq->q[0] = pq->q[pq->length - 1];
122 pq->q[0]->index = 0;
123 --pq->length;
124 bubble_down(pq, 0);
125 }
126 }
127
nghttp2_pq_remove(nghttp2_pq * pq,nghttp2_pq_entry * item)128 void nghttp2_pq_remove(nghttp2_pq *pq, nghttp2_pq_entry *item) {
129 assert(pq->q[item->index] == item);
130
131 if (item->index == 0) {
132 nghttp2_pq_pop(pq);
133 return;
134 }
135
136 if (item->index == pq->length - 1) {
137 --pq->length;
138 return;
139 }
140
141 pq->q[item->index] = pq->q[pq->length - 1];
142 pq->q[item->index]->index = item->index;
143 --pq->length;
144
145 if (pq->less(item, pq->q[item->index])) {
146 bubble_down(pq, item->index);
147 } else {
148 bubble_up(pq, item->index);
149 }
150 }
151
nghttp2_pq_empty(nghttp2_pq * pq)152 int nghttp2_pq_empty(nghttp2_pq *pq) { return pq->length == 0; }
153
nghttp2_pq_size(nghttp2_pq * pq)154 size_t nghttp2_pq_size(nghttp2_pq *pq) { return pq->length; }
155
nghttp2_pq_update(nghttp2_pq * pq,nghttp2_pq_item_cb fun,void * arg)156 void nghttp2_pq_update(nghttp2_pq *pq, nghttp2_pq_item_cb fun, void *arg) {
157 size_t i;
158 int rv = 0;
159 if (pq->length == 0) {
160 return;
161 }
162 for (i = 0; i < pq->length; ++i) {
163 rv |= (*fun)(pq->q[i], arg);
164 }
165 if (rv) {
166 for (i = pq->length; i > 0; --i) {
167 bubble_down(pq, i - 1);
168 }
169 }
170 }
171
nghttp2_pq_each(nghttp2_pq * pq,nghttp2_pq_item_cb fun,void * arg)172 int nghttp2_pq_each(nghttp2_pq *pq, nghttp2_pq_item_cb fun, void *arg) {
173 size_t i;
174
175 if (pq->length == 0) {
176 return 0;
177 }
178 for (i = 0; i < pq->length; ++i) {
179 if ((*fun)(pq->q[i], arg)) {
180 return 1;
181 }
182 }
183 return 0;
184 }
185