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