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