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