1 #include <stdbool.h> 2 #include <stdlib.h> 3 #include <stdio.h> 4 5 #include "doubly-linked-list.h" 6 7 #ifndef EXIT_SUCCESS 8 #define EXIT_SUCCESS 0 9 #endif 10 11 #ifndef EXIT_FAILURE 12 #define EXIT_FAILURE 1 13 #endif 14 15 /* Implementation */ 16 17 typedef int T; 18 19 typedef struct ListNodeType 20 { 21 T value; 22 struct ListNodeType *next; 23 struct ListNodeType *prev; 24 } ListNodeType; 25 26 ListNodeType * l_new_node (T value) 27 { 28 ListNodeType *n = malloc (sizeof (ListNodeType)); 29 n->next = NULL; 30 n->prev = NULL; 31 n->value = value; 32 return n; 33 } 34 35 typedef struct LinkedListWrapperType 36 { 37 ListNodeType *first; 38 ListNodeType *last; 39 size_t size; 40 } LinkedListWrapperType; 41 42 int compare_nodes (const ListNodeType *n1, const ListNodeType *n2) 43 { 44 if (n1->value == n2->value) 45 return 0; 46 else if (n1->value < n2->value) 47 return -1; 48 else 49 return 1; 50 } 51 52 LINKED_LIST_MUTATIVE_OPS_PROTOTYPE (LinkedListWrapperType, ListNodeType, static); 53 LINKED_LIST_MERGE_SORT_PROTOTYPE (LinkedListWrapperType, ListNodeType, static); 54 55 LINKED_LIST_MUTATIVE_OPS_DECL (LinkedListWrapperType, ListNodeType, static) 56 LINKED_LIST_MERGE_SORT_DECL (LinkedListWrapperType, ListNodeType, static) 57 58 ListNodeType * find_last_node (ListNodeType *head) 59 { 60 if (head == NULL) 61 return NULL; 62 63 ListNodeType *n = head; 64 while (n->next != NULL) 65 n = n->next; 66 67 return n; 68 } 69 70 void l_print (ListNodeType *node) 71 { 72 for (ListNodeType *l = node; l != NULL; l = l->next) 73 printf ("%d ", l->value); 74 printf ("\n"); 75 } 76 77 void l_reverse_print (ListNodeType *last_node) 78 { 79 for (ListNodeType *l = last_node; l != NULL; l = l->prev) 80 printf ("%d ", l->value); 81 printf ("\n"); 82 } 83 84 struct test_data_t 85 { 86 T const *content; 87 size_t size; 88 }; 89 90 bool run_test (const struct test_data_t *expect, 91 LinkedListWrapperType *current, 92 bool reversed) 93 { 94 ListNodeType *node = (reversed) ? current->last : current->first; 95 bool passed = true; 96 for (int i=0; i<expect->size && node != NULL; ++i) 97 { 98 if (reversed) 99 { 100 if (expect->content[expect->size - 1 - i] != node->value) 101 { 102 printf ("FAIL: mismatching expected (%d) VS current (%d).\n", 103 expect->content[expect->size - 1 - i], node->value); 104 passed = false; 105 } 106 if (node->prev == NULL && current->first != node) 107 { 108 printf ("FAIL: first is not matching the first node.\n"); 109 passed = false; 110 } 111 } 112 else 113 { 114 if (expect->content[i] != node->value) 115 { 116 printf ("FAIL: mismatching expected (%d) VS current (%d).\n", 117 expect->content[i], node->value); 118 passed = false; 119 } 120 if (node->next == NULL && current->last != node) 121 { 122 printf ("FAIL: last_ is not matching the last node.\n"); 123 passed = false; 124 } 125 } 126 127 if (!passed) 128 return false; 129 130 if (reversed) 131 node = node->prev; 132 else 133 node = node->next; 134 } 135 136 if (node != NULL) 137 { 138 printf ("FAIL: the list is longer than expected.\n"); 139 passed = false; 140 } 141 if (expect->size != current->size) 142 { 143 printf ("FAIL: size (%ld) is not matching the real size of the list (%ld).\n", 144 current->size, expect->size); 145 passed = false; 146 } 147 148 return passed; 149 } 150 151 bool check(const char *op, 152 const struct test_data_t *expect, 153 LinkedListWrapperType *wrapper) 154 { 155 bool success = true; 156 bool res; 157 158 #define DUMP_LIST 0 159 160 if (DUMP_LIST) 161 l_print (wrapper->first); 162 163 res = run_test (expect, wrapper, false); 164 printf ("%s: test-linked-list::%s: check forward conformity\n", 165 res ? "PASS": "FAIL", op); 166 success &= res; 167 168 if (DUMP_LIST) 169 l_reverse_print (wrapper->last); 170 171 res = run_test (expect, wrapper, true); 172 printf ("%s: test-linked-list::%s: check backward conformity\n", 173 res ? "PASS": "FAIL", op); 174 success &= res; 175 176 if (DUMP_LIST) 177 printf("\n"); 178 179 return success; 180 } 181 182 const int EXPECT_0 [] = { 10, 4, 3, 1, 9, 2 }; 183 const int EXPECT_1 [] = { 1, 2, 3, 4, 9, 10 }; 184 const int EXPECT_2 [] = { 11, 1, 2, 3, 4, 9, 10 }; 185 const int EXPECT_3 [] = { 11, 1, 2, 3, 4, 9, 8, 10 }; 186 const int EXPECT_4 [] = { 11, 2, 3, 4, 9, 8, 10 }; 187 const int EXPECT_5 [] = { 10, 2, 3, 4, 9, 8, 11 }; 188 const int EXPECT_6 [] = { 10, 3, 2, 4, 9, 8, 11 }; 189 const int EXPECT_7 [] = { 10, 9, 2, 4, 3, 8, 11 }; 190 const int EXPECT_8 [] = { 2, 3, 4, 8, 9, 10, 11 }; 191 const int EXPECT_9 [] = { 3, 4, 8, 9, 10, 11 }; 192 const int EXPECT_10 [] = { 3, 4, 8, 9, 10 }; 193 const struct test_data_t test_data[] = { 194 { .content = EXPECT_0, .size = sizeof(EXPECT_0) / sizeof(EXPECT_0[0]) }, 195 { .content = EXPECT_1, .size = sizeof(EXPECT_1) / sizeof(EXPECT_1[0]) }, 196 { .content = EXPECT_2, .size = sizeof(EXPECT_2) / sizeof(EXPECT_2[0]) }, 197 { .content = EXPECT_3, .size = sizeof(EXPECT_3) / sizeof(EXPECT_3[0]) }, 198 { .content = EXPECT_4, .size = sizeof(EXPECT_4) / sizeof(EXPECT_4[0]) }, 199 { .content = EXPECT_5, .size = sizeof(EXPECT_5) / sizeof(EXPECT_5[0]) }, 200 { .content = EXPECT_6, .size = sizeof(EXPECT_6) / sizeof(EXPECT_6[0]) }, 201 { .content = EXPECT_7, .size = sizeof(EXPECT_7) / sizeof(EXPECT_7[0]) }, 202 { .content = EXPECT_8, .size = sizeof(EXPECT_8) / sizeof(EXPECT_8[0]) }, 203 { .content = EXPECT_9, .size = sizeof(EXPECT_9) / sizeof(EXPECT_9[0]) }, 204 { .content = EXPECT_10, .size = sizeof(EXPECT_10) / sizeof(EXPECT_10[0]) }, 205 }; 206 207 int main (void) 208 { 209 int failures = 0; 210 211 LinkedListWrapperType wrapper = { 212 .first = NULL, 213 .last = NULL, 214 .size = 0, 215 }; 216 217 /* Append nodes. */ 218 LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (10)); 219 LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (4)); 220 LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (3)); 221 LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (1)); 222 LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (9)); 223 LINKED_LIST_APPEND(ListNodeType) (&wrapper, l_new_node (2)); 224 225 failures += ! check ("append", &test_data[0], &wrapper); 226 227 /* Sort nodes (without updating wrapper). */ 228 wrapper.first = 229 LINKED_LIST_MERGE_SORT_(ListNodeType) (wrapper.first, compare_nodes); 230 wrapper.last = find_last_node (wrapper.first); 231 232 failures += ! check ("sort", &test_data[1], &wrapper); 233 234 /* Save a reference to this node for later. */ 235 ListNodeType *n_to_remove = wrapper.first; 236 237 /* Prepend node. */ 238 LINKED_LIST_PREPEND(ListNodeType) (&wrapper, l_new_node (11)); 239 failures += ! check ("prepend", &test_data[2], &wrapper); 240 241 /* Insert node. */ 242 LINKED_LIST_INSERT_BEFORE(ListNodeType) (&wrapper, l_new_node (8), wrapper.last); 243 failures += ! check ("insert_before", &test_data[3], &wrapper); 244 245 /* Remove a node. */ 246 LINKED_LIST_REMOVE(ListNodeType) (&wrapper, n_to_remove); 247 failures += ! check ("remove", &test_data[4], &wrapper); 248 249 /* Swap first and last. */ 250 LINKED_LIST_SWAP(ListNodeType) (&wrapper, wrapper.first, wrapper.last); 251 failures += ! check ("swap first and last", &test_data[5], &wrapper); 252 253 /* Swap adjacent nodes. */ 254 LINKED_LIST_SWAP(ListNodeType) (&wrapper, wrapper.first->next, 255 wrapper.first->next->next); 256 failures += ! check ("swap adjacent nodes", &test_data[6], &wrapper); 257 258 /* Swap non-adjacent nodes, but neither first nor last. */ 259 LINKED_LIST_SWAP(ListNodeType) (&wrapper, wrapper.first->next, 260 wrapper.first->next->next->next->next); 261 failures += ! check ("swap non-adjacent nodes", &test_data[7], &wrapper); 262 263 /* Sort nodes. */ 264 LINKED_LIST_MERGE_SORT(ListNodeType) (&wrapper, compare_nodes); 265 failures += ! check ("sort", &test_data[8], &wrapper); 266 267 /* Pop front. */ 268 LINKED_LIST_POP_FRONT(ListNodeType) (&wrapper); 269 failures += ! check ("pop_front", &test_data[9], &wrapper); 270 271 /* Pop back. */ 272 LINKED_LIST_POP_BACK(ListNodeType) (&wrapper); 273 failures += ! check ("pop_back", &test_data[10], &wrapper); 274 275 exit (failures ? EXIT_FAILURE : EXIT_SUCCESS); 276 } 277
Indexes created Mon Mar 16 00:23:04 UTC 2026