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_test.h"
26
27 #include <stdio.h>
28
29 #include "nghttp2_pq.h"
30
31 static const MunitTest tests[] = {
32 munit_void_test(test_nghttp2_pq),
33 munit_void_test(test_nghttp2_pq_update),
34 munit_void_test(test_nghttp2_pq_remove),
35 munit_test_end(),
36 };
37
38 const MunitSuite pq_suite = {
39 "/pq", tests, NULL, 1, MUNIT_SUITE_OPTION_NONE,
40 };
41
42 typedef struct {
43 nghttp2_pq_entry ent;
44 const char *s;
45 } string_entry;
46
string_entry_new(const char * s)47 static string_entry *string_entry_new(const char *s) {
48 nghttp2_mem *mem;
49 string_entry *ent;
50
51 mem = nghttp2_mem_default();
52
53 ent = nghttp2_mem_malloc(mem, sizeof(string_entry));
54 ent->s = s;
55
56 return ent;
57 }
58
string_entry_del(string_entry * ent)59 static void string_entry_del(string_entry *ent) { free(ent); }
60
pq_less(const void * lhs,const void * rhs)61 static int pq_less(const void *lhs, const void *rhs) {
62 return strcmp(((string_entry *)lhs)->s, ((string_entry *)rhs)->s) < 0;
63 }
64
test_nghttp2_pq(void)65 void test_nghttp2_pq(void) {
66 int i;
67 nghttp2_pq pq;
68 string_entry *top;
69
70 nghttp2_pq_init(&pq, pq_less, nghttp2_mem_default());
71 assert_true(nghttp2_pq_empty(&pq));
72 assert_size(0, ==, nghttp2_pq_size(&pq));
73 assert_int(0, ==, nghttp2_pq_push(&pq, &string_entry_new("foo")->ent));
74 assert_false(nghttp2_pq_empty(&pq));
75 assert_size(1, ==, nghttp2_pq_size(&pq));
76 top = (string_entry *)nghttp2_pq_top(&pq);
77 assert_string_equal("foo", top->s);
78 assert_int(0, ==, nghttp2_pq_push(&pq, &string_entry_new("bar")->ent));
79 top = (string_entry *)nghttp2_pq_top(&pq);
80 assert_string_equal("bar", top->s);
81 assert_int(0, ==, nghttp2_pq_push(&pq, &string_entry_new("baz")->ent));
82 top = (string_entry *)nghttp2_pq_top(&pq);
83 assert_string_equal("bar", top->s);
84 assert_int(0, ==, nghttp2_pq_push(&pq, &string_entry_new("C")->ent));
85 assert_size(4, ==, nghttp2_pq_size(&pq));
86
87 top = (string_entry *)nghttp2_pq_top(&pq);
88 assert_string_equal("C", top->s);
89 string_entry_del(top);
90 nghttp2_pq_pop(&pq);
91
92 assert_size(3, ==, nghttp2_pq_size(&pq));
93
94 top = (string_entry *)nghttp2_pq_top(&pq);
95 assert_string_equal("bar", top->s);
96 nghttp2_pq_pop(&pq);
97 string_entry_del(top);
98
99 top = (string_entry *)nghttp2_pq_top(&pq);
100 assert_string_equal("baz", top->s);
101 nghttp2_pq_pop(&pq);
102 string_entry_del(top);
103
104 top = (string_entry *)nghttp2_pq_top(&pq);
105 assert_string_equal("foo", top->s);
106 nghttp2_pq_pop(&pq);
107 string_entry_del(top);
108
109 assert_true(nghttp2_pq_empty(&pq));
110 assert_size(0, ==, nghttp2_pq_size(&pq));
111 assert_null(nghttp2_pq_top(&pq));
112
113 /* Add bunch of entry to see realloc works */
114 for (i = 0; i < 10000; ++i) {
115 assert_int(0, ==, nghttp2_pq_push(&pq, &string_entry_new("foo")->ent));
116 assert_size((size_t)(i + 1), ==, nghttp2_pq_size(&pq));
117 }
118 for (i = 10000; i > 0; --i) {
119 top = (string_entry *)nghttp2_pq_top(&pq);
120 assert_not_null(top);
121 nghttp2_pq_pop(&pq);
122 string_entry_del(top);
123 assert_size((size_t)(i - 1), ==, nghttp2_pq_size(&pq));
124 }
125
126 nghttp2_pq_free(&pq);
127 }
128
129 typedef struct {
130 nghttp2_pq_entry ent;
131 int key;
132 int val;
133 } node;
134
node_less(const void * lhs,const void * rhs)135 static int node_less(const void *lhs, const void *rhs) {
136 node *ln = (node *)lhs;
137 node *rn = (node *)rhs;
138 return ln->key < rn->key;
139 }
140
node_update(nghttp2_pq_entry * item,void * arg)141 static int node_update(nghttp2_pq_entry *item, void *arg) {
142 node *nd = (node *)item;
143 (void)arg;
144
145 if ((nd->key % 2) == 0) {
146 nd->key *= -1;
147 return 1;
148 } else {
149 return 0;
150 }
151 }
152
test_nghttp2_pq_update(void)153 void test_nghttp2_pq_update(void) {
154 nghttp2_pq pq;
155 node nodes[10];
156 int i;
157 node *nd;
158 int ans[] = {-8, -6, -4, -2, 0, 1, 3, 5, 7, 9};
159
160 nghttp2_pq_init(&pq, node_less, nghttp2_mem_default());
161
162 for (i = 0; i < (int)(sizeof(nodes) / sizeof(nodes[0])); ++i) {
163 nodes[i].key = i;
164 nodes[i].val = i;
165 nghttp2_pq_push(&pq, &nodes[i].ent);
166 }
167
168 nghttp2_pq_update(&pq, node_update, NULL);
169
170 for (i = 0; i < (int)(sizeof(nodes) / sizeof(nodes[0])); ++i) {
171 nd = (node *)nghttp2_pq_top(&pq);
172 assert_int(ans[i], ==, nd->key);
173 nghttp2_pq_pop(&pq);
174 }
175
176 nghttp2_pq_free(&pq);
177 }
178
push_nodes(nghttp2_pq * pq,node * dest,size_t n)179 static void push_nodes(nghttp2_pq *pq, node *dest, size_t n) {
180 size_t i;
181 for (i = 0; i < n; ++i) {
182 dest[i].key = (int)i;
183 dest[i].val = (int)i;
184 nghttp2_pq_push(pq, &dest[i].ent);
185 }
186 }
187
check_nodes(nghttp2_pq * pq,size_t n,int * ans_key,int * ans_val)188 static void check_nodes(nghttp2_pq *pq, size_t n, int *ans_key, int *ans_val) {
189 size_t i;
190 for (i = 0; i < n; ++i) {
191 node *nd = (node *)nghttp2_pq_top(pq);
192 assert_int(ans_key[i], ==, nd->key);
193 assert_int(ans_val[i], ==, nd->val);
194 nghttp2_pq_pop(pq);
195 }
196 }
197
test_nghttp2_pq_remove(void)198 void test_nghttp2_pq_remove(void) {
199 nghttp2_pq pq;
200 node nodes[10];
201 int ans_key1[] = {1, 2, 3, 4, 5};
202 int ans_val1[] = {1, 2, 3, 4, 5};
203 int ans_key2[] = {0, 1, 2, 4, 5};
204 int ans_val2[] = {0, 1, 2, 4, 5};
205 int ans_key3[] = {0, 1, 2, 3, 4};
206 int ans_val3[] = {0, 1, 2, 3, 4};
207
208 nghttp2_pq_init(&pq, node_less, nghttp2_mem_default());
209
210 push_nodes(&pq, nodes, 6);
211
212 nghttp2_pq_remove(&pq, &nodes[0].ent);
213
214 check_nodes(&pq, 5, ans_key1, ans_val1);
215
216 nghttp2_pq_free(&pq);
217
218 nghttp2_pq_init(&pq, node_less, nghttp2_mem_default());
219
220 push_nodes(&pq, nodes, 6);
221
222 nghttp2_pq_remove(&pq, &nodes[3].ent);
223
224 check_nodes(&pq, 5, ans_key2, ans_val2);
225
226 nghttp2_pq_free(&pq);
227
228 nghttp2_pq_init(&pq, node_less, nghttp2_mem_default());
229
230 push_nodes(&pq, nodes, 6);
231
232 nghttp2_pq_remove(&pq, &nodes[5].ent);
233
234 check_nodes(&pq, 5, ans_key3, ans_val3);
235
236 nghttp2_pq_free(&pq);
237 }
238