1 /*
2 * nghttp3
3 *
4 * Copyright (c) 2019 nghttp3 contributors
5 * Copyright (c) 2017 ngtcp2 contributors
6 * Copyright (c) 2012 nghttp2 contributors
7 *
8 * Permission is hereby granted, free of charge, to any person obtaining
9 * a copy of this software and associated documentation files (the
10 * "Software"), to deal in the Software without restriction, including
11 * without limitation the rights to use, copy, modify, merge, publish,
12 * distribute, sublicense, and/or sell copies of the Software, and to
13 * permit persons to whom the Software is furnished to do so, subject to
14 * the following conditions:
15 *
16 * The above copyright notice and this permission notice shall be
17 * included in all copies or substantial portions of the Software.
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
22 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
23 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
24 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
25 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
26 */
27 #include "nghttp3_pq.h"
28
29 #include <assert.h>
30
31 #include "nghttp3_macro.h"
32
nghttp3_pq_init(nghttp3_pq * pq,nghttp3_less less,const nghttp3_mem * mem)33 void nghttp3_pq_init(nghttp3_pq *pq, nghttp3_less less,
34 const nghttp3_mem *mem) {
35 pq->mem = mem;
36 pq->capacity = 0;
37 pq->q = NULL;
38 pq->length = 0;
39 pq->less = less;
40 }
41
nghttp3_pq_free(nghttp3_pq * pq)42 void nghttp3_pq_free(nghttp3_pq *pq) {
43 nghttp3_mem_free(pq->mem, pq->q);
44 pq->q = NULL;
45 }
46
swap(nghttp3_pq * pq,size_t i,size_t j)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];
50
51 pq->q[i] = b;
52 b->index = i;
53 pq->q[j] = a;
54 a->index = j;
55 }
56
bubble_up(nghttp3_pq * pq,size_t index)57 static void bubble_up(nghttp3_pq *pq, size_t index) {
58 size_t parent;
59 while (index != 0) {
60 parent = (index - 1) / 2;
61 if (!pq->less(pq->q[index], pq->q[parent])) {
62 return;
63 }
64 swap(pq, parent, index);
65 index = parent;
66 }
67 }
68
nghttp3_pq_push(nghttp3_pq * pq,nghttp3_pq_entry * item)69 int nghttp3_pq_push(nghttp3_pq *pq, nghttp3_pq_entry *item) {
70 if (pq->capacity <= pq->length) {
71 void *nq;
72 size_t ncapacity;
73
74 ncapacity = nghttp3_max(4, (pq->capacity * 2));
75
76 nq = nghttp3_mem_realloc(pq->mem, pq->q,
77 ncapacity * sizeof(nghttp3_pq_entry *));
78 if (nq == NULL) {
79 return NGHTTP3_ERR_NOMEM;
80 }
81 pq->capacity = ncapacity;
82 pq->q = nq;
83 }
84 pq->q[pq->length] = item;
85 item->index = pq->length;
86 ++pq->length;
87 bubble_up(pq, pq->length - 1);
88 return 0;
89 }
90
nghttp3_pq_top(const nghttp3_pq * pq)91 nghttp3_pq_entry *nghttp3_pq_top(const nghttp3_pq *pq) {
92 assert(pq->length);
93 return pq->q[0];
94 }
95
bubble_down(nghttp3_pq * pq,size_t index)96 static void bubble_down(nghttp3_pq *pq, size_t index) {
97 size_t i, j, minindex;
98 for (;;) {
99 j = index * 2 + 1;
100 minindex = index;
101 for (i = 0; i < 2; ++i, ++j) {
102 if (j >= pq->length) {
103 break;
104 }
105 if (pq->less(pq->q[j], pq->q[minindex])) {
106 minindex = j;
107 }
108 }
109 if (minindex == index) {
110 return;
111 }
112 swap(pq, index, minindex);
113 index = minindex;
114 }
115 }
116
nghttp3_pq_pop(nghttp3_pq * pq)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);
123 }
124 }
125
nghttp3_pq_remove(nghttp3_pq * pq,nghttp3_pq_entry * item)126 void nghttp3_pq_remove(nghttp3_pq *pq, nghttp3_pq_entry *item) {
127 assert(pq->q[item->index] == item);
128
129 if (item->index == 0) {
130 nghttp3_pq_pop(pq);
131 return;
132 }
133
134 if (item->index == pq->length - 1) {
135 --pq->length;
136 return;
137 }
138
139 pq->q[item->index] = pq->q[pq->length - 1];
140 pq->q[item->index]->index = item->index;
141 --pq->length;
142
143 if (pq->less(item, pq->q[item->index])) {
144 bubble_down(pq, item->index);
145 } else {
146 bubble_up(pq, item->index);
147 }
148 }
149
nghttp3_pq_empty(const nghttp3_pq * pq)150 int nghttp3_pq_empty(const nghttp3_pq *pq) { return pq->length == 0; }
151
nghttp3_pq_size(const nghttp3_pq * pq)152 size_t nghttp3_pq_size(const nghttp3_pq *pq) { return pq->length; }
153
nghttp3_pq_each(const nghttp3_pq * pq,nghttp3_pq_item_cb fun,void * arg)154 int nghttp3_pq_each(const nghttp3_pq *pq, nghttp3_pq_item_cb fun, void *arg) {
155 size_t i;
156
157 if (pq->length == 0) {
158 return 0;
159 }
160 for (i = 0; i < pq->length; ++i) {
161 if ((*fun)(pq->q[i], arg)) {
162 return 1;
163 }
164 }
165 return 0;
166 }
167
nghttp3_pq_clear(nghttp3_pq * pq)168 void nghttp3_pq_clear(nghttp3_pq *pq) { pq->length = 0; }
169