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/* 17TODO: 18-fix the includes 19-makefile: ntpdsim-ntp_prio_q.o - make sure it's okay 20*/ 21 22 23/* helpers */ 24 25typedef struct Element 26{ 27 char str[37]; // 37 seems like a nice candidate to break stuff 28 int number; 29 30} element; 31 32static int/*BOOL*/ 33compare_elements(const void * e1, const void * e2) 34{ 35 return ((const element*)e1)->number < ((const element*)e2)->number; 36} 37 38/* tests */ 39 40extern void test_AllocateDeallocateNode(void); 41void test_AllocateDeallocateNode(void) 42{ 43 element* e_ptr = debug_get_node(sizeof(element)); 44 free_node(e_ptr); 45} 46 47 48extern void test_EmptyQueue(void); 49void 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 63extern void test_OneElementQueue(void); 64void 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 92extern void test_MultipleElementQueue(void); 93void 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 131extern void test_CustomOrderQueue(void); 132void 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 189extern void test_DestroyNonEmptyQueue(void); 190void 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 213extern void test_AppendQueues(void); 214void 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