1 /* $NetBSD: ntp_prio_q.c,v 1.3 2020/05/25 20:47:36 christos Exp $ */
2
3 #include "config.h"
4
5 #include "ntp.h"
6 #include "ntp_calendar.h"
7 #include "ntp_stdlib.h"
8
9 #include "ntp_prio_q.h"
10
11 #include "unity.h"
12
13
14
15 #include <string.h>
16 /*
17 TODO:
18 -fix the includes
19 -makefile: ntpdsim-ntp_prio_q.o - make sure it's okay
20 */
21
22
23 /* helpers */
24
25 typedef struct Element
26 {
27 char str[37]; // 37 seems like a nice candidate to break stuff
28 int number;
29
30 } element;
31
32 static int/*BOOL*/
compare_elements(const void * e1,const void * e2)33 compare_elements(const void * e1, const void * e2)
34 {
35 return ((const element*)e1)->number < ((const element*)e2)->number;
36 }
37
38 /* tests */
39
40 extern void test_AllocateDeallocateNode(void);
test_AllocateDeallocateNode(void)41 void test_AllocateDeallocateNode(void)
42 {
43 element* e_ptr = debug_get_node(sizeof(element));
44 free_node(e_ptr);
45 }
46
47
48 extern void test_EmptyQueue(void);
test_EmptyQueue(void)49 void test_EmptyQueue(void)
50 {
51 queue* q = create_queue();
52
53 TEST_ASSERT_NOT_NULL(q);
54 TEST_ASSERT_TRUE(empty(q));
55 TEST_ASSERT_NULL(queue_head(q));
56 TEST_ASSERT_NULL(dequeue(q));
57 TEST_ASSERT_EQUAL(0, get_no_of_elements(q));
58
59 destroy_queue(q);
60 }
61
62
63 extern void test_OneElementQueue(void);
test_OneElementQueue(void)64 void test_OneElementQueue(void)
65 {
66 queue* q = create_queue();
67
68 TEST_ASSERT_NOT_NULL(q);
69
70 element e = {"string", 3};
71 element* e_ptr = debug_get_node(sizeof(element));
72 enqueue(q, e_ptr);
73 *e_ptr = e;
74
75 TEST_ASSERT_FALSE(empty(q));
76 TEST_ASSERT_NOT_NULL(queue_head(q));
77 TEST_ASSERT_EQUAL(1, get_no_of_elements(q));
78
79 element* e_ptr_returned = dequeue(q);
80
81 TEST_ASSERT_NOT_NULL(e_ptr_returned);
82 TEST_ASSERT_EQUAL_STRING(e_ptr_returned->str, "string");
83 TEST_ASSERT_EQUAL_PTR(e_ptr_returned, e_ptr);
84 TEST_ASSERT_EQUAL(0, get_no_of_elements(q));
85 TEST_ASSERT_TRUE(empty(q));
86 TEST_ASSERT_NULL(dequeue(q));
87
88 destroy_queue(q);
89 }
90
91
92 extern void test_MultipleElementQueue(void);
test_MultipleElementQueue(void)93 void test_MultipleElementQueue(void)
94 {
95 queue* q = create_queue();
96
97 TEST_ASSERT_NOT_NULL(q);
98
99 element *e1_ptr, *e2_ptr, *e3_ptr;
100
101 e1_ptr = (element*)debug_get_node(sizeof(element));
102 e2_ptr = (element*)debug_get_node(sizeof(element));
103 e3_ptr = (element*)debug_get_node(sizeof(element));
104
105 enqueue(q, e1_ptr);
106 enqueue(q, e2_ptr);
107 enqueue(q, e3_ptr);
108
109 TEST_ASSERT_EQUAL(3, get_no_of_elements(q));
110
111 dequeue(q);
112 enqueue(q, e1_ptr);
113
114 TEST_ASSERT_EQUAL(3, get_no_of_elements(q));
115
116 dequeue(q);
117 dequeue(q);
118 enqueue(q, e3_ptr);
119 enqueue(q, e2_ptr);
120
121 TEST_ASSERT_EQUAL_PTR(dequeue(q), e1_ptr);
122 TEST_ASSERT_EQUAL_PTR(dequeue(q), e3_ptr);
123 TEST_ASSERT_EQUAL_PTR(dequeue(q), e2_ptr);
124 TEST_ASSERT_EQUAL(0, get_no_of_elements(q));
125 TEST_ASSERT_NULL(dequeue(q));
126
127 destroy_queue(q);
128 }
129
130
131 extern void test_CustomOrderQueue(void);
test_CustomOrderQueue(void)132 void test_CustomOrderQueue(void)
133 {
134 queue* q = debug_create_priority_queue(compare_elements);
135 element *e1_ptr, *e2_ptr, *e3_ptr, *e4_ptr, *e5_ptr, *e6_ptr;
136
137 e1_ptr = (element*)debug_get_node(sizeof(element));
138 e2_ptr = (element*)debug_get_node(sizeof(element));
139 e3_ptr = (element*)debug_get_node(sizeof(element));
140 e4_ptr = (element*)debug_get_node(sizeof(element));
141 e5_ptr = (element*)debug_get_node(sizeof(element));
142 e6_ptr = (element*)debug_get_node(sizeof(element));
143
144 e1_ptr->number = 1;
145 e2_ptr->number = 1;
146 e3_ptr->number = 10;
147 e4_ptr->number = 10;
148 e5_ptr->number = 100;
149 e6_ptr->number = 100;
150
151 enqueue(q, e3_ptr);
152 enqueue(q, e5_ptr);
153 enqueue(q, e2_ptr);
154 enqueue(q, e1_ptr);
155 enqueue(q, e4_ptr);
156 enqueue(q, e6_ptr);
157
158 TEST_ASSERT_EQUAL(((element*)queue_head(q))->number, 100);
159 TEST_ASSERT_EQUAL(((element*)dequeue(q))->number, 100);
160
161 TEST_ASSERT_EQUAL(((element*)queue_head(q))->number, 100);
162 TEST_ASSERT_EQUAL(((element*)dequeue(q))->number, 100);
163
164 TEST_ASSERT_EQUAL(((element*)queue_head(q))->number, 10);
165 TEST_ASSERT_EQUAL(((element*)dequeue(q))->number, 10);
166
167 TEST_ASSERT_EQUAL(((element*)queue_head(q))->number, 10);
168 TEST_ASSERT_EQUAL(((element*)dequeue(q))->number, 10);
169
170 TEST_ASSERT_EQUAL(((element*)queue_head(q))->number, 1);
171 TEST_ASSERT_EQUAL(((element*)dequeue(q))->number, 1);
172
173 TEST_ASSERT_EQUAL(((element*)queue_head(q))->number, 1);
174 TEST_ASSERT_EQUAL(((element*)dequeue(q))->number, 1);
175
176 TEST_ASSERT_TRUE(empty(q));
177
178 destroy_queue(q);
179
180 free_node(e1_ptr);
181 free_node(e2_ptr);
182 free_node(e3_ptr);
183 free_node(e4_ptr);
184 free_node(e5_ptr);
185 free_node(e6_ptr);
186 }
187
188
189 extern void test_DestroyNonEmptyQueue(void);
test_DestroyNonEmptyQueue(void)190 void test_DestroyNonEmptyQueue(void)
191 {
192 queue* q = create_queue();
193 element *e1_ptr, *e2_ptr, *e3_ptr, *e4_ptr, *e5_ptr, *e6_ptr;
194
195 e1_ptr = (element*)debug_get_node(sizeof(element));
196 e2_ptr = (element*)debug_get_node(sizeof(element));
197 e3_ptr = (element*)debug_get_node(sizeof(element));
198 e4_ptr = (element*)debug_get_node(sizeof(element));
199 e5_ptr = (element*)debug_get_node(sizeof(element));
200 e6_ptr = (element*)debug_get_node(sizeof(element));
201
202 enqueue(q, e3_ptr);
203 enqueue(q, e2_ptr);
204 enqueue(q, e4_ptr);
205 enqueue(q, e1_ptr);
206 enqueue(q, e6_ptr);
207 enqueue(q, e5_ptr);
208
209 destroy_queue(q);
210 }
211
212
213 extern void test_AppendQueues(void);
test_AppendQueues(void)214 void test_AppendQueues(void)
215 {
216 queue* q1 = create_queue();
217 queue* q2 = create_queue();
218 queue* q3 = create_queue();
219 queue* q4 = create_queue();
220 queue* q5 = create_queue();
221
222 // append empty queue to empty queue
223 append_queue(q1, q2); // destroys q2
224
225 element *e1_ptr, *e2_ptr, *e3_ptr, *e4_ptr, *e5_ptr, *e6_ptr;
226 e1_ptr = (element*)debug_get_node(sizeof(element));
227 e2_ptr = (element*)debug_get_node(sizeof(element));
228 e3_ptr = (element*)debug_get_node(sizeof(element));
229 e4_ptr = (element*)debug_get_node(sizeof(element));
230 e5_ptr = (element*)debug_get_node(sizeof(element));
231 e6_ptr = (element*)debug_get_node(sizeof(element));
232
233 enqueue(q1, e1_ptr);
234 enqueue(q1, e2_ptr);
235 enqueue(q1, e3_ptr);
236
237
238 // append empty queue to non empty queue
239 append_queue(q1, q3); // destroys q3
240 TEST_ASSERT_EQUAL(3, get_no_of_elements(q1));
241
242 // append non empty queue to empty queue
243 append_queue(q4, q1); // destroys q1
244 TEST_ASSERT_EQUAL(3, get_no_of_elements(q4));
245
246 enqueue(q5, e4_ptr);
247 enqueue(q5, e5_ptr);
248
249 // append non empty queue to non empty queue
250 append_queue(q4, q5); // destroys q5
251 TEST_ASSERT_EQUAL(5, get_no_of_elements(q4));
252
253 dequeue(q4);
254 dequeue(q4);
255 dequeue(q4);
256 dequeue(q4);
257 dequeue(q4);
258
259 free_node(e1_ptr);
260 free_node(e2_ptr);
261 free_node(e3_ptr);
262 free_node(e4_ptr);
263 free_node(e5_ptr);
264 free_node(e6_ptr);
265
266 TEST_ASSERT_EQUAL(0, get_no_of_elements(q4));
267
268 // destroy_queue(q1); // destroyed already
269 // destroy_queue(q2); // destroyed already
270 // destroy_queue(q3); // destroyed already
271 destroy_queue(q4);
272 // destroy_queue(q5); // destroyed already
273 }
274