diff options
Diffstat (limited to 'tests/linked_list.c')
| -rw-r--r-- | tests/linked_list.c | 219 |
1 files changed, 219 insertions, 0 deletions
diff --git a/tests/linked_list.c b/tests/linked_list.c new file mode 100644 index 0000000..a5704a3 --- /dev/null +++ b/tests/linked_list.c @@ -0,0 +1,219 @@ +#include <assert.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "linked_list.h" + +struct list_elem { + struct linked_list link; + char *content; +}; + +static void test_linked_list_init(void) { + struct linked_list list; + linked_list_init(&list); + + // Both next and prev should point to self + assert(list.next == &list && list.prev == &list); + + // The list should be empty + assert(linked_list_empty(&list)); +} + +static void test_linked_list_single_insert(void) { + struct linked_list list; + linked_list_init(&list); + + struct list_elem elem1 = {{0}, NULL}; + linked_list_insert(&list, &elem1.link); + + // Both next and prev on list should point to the elem + assert(list.next == &elem1.link && list.prev == &elem1.link); + + // Both next and prev on elem should point to the list + assert(elem1.link.next == &list && elem1.link.prev == &list); + + // The list and element should not be empty + assert(!linked_list_empty(&list)); + assert(!linked_list_empty(&elem1.link)); +} + +static void test_linked_list_single_remove(void) { + struct linked_list list; + linked_list_init(&list); + + struct list_elem elem1 = {{0}, NULL}; + linked_list_insert(&list, &elem1.link); + linked_list_remove(&elem1.link); + + // Both next and prev on elem be NULL + assert(elem1.link.next == NULL && elem1.link.prev == NULL); + + // Both next and prev should point to self + assert(list.next == &list && list.prev == &list); + + // The list should be empty + assert(linked_list_empty(&list)); +} + +static void test_linked_list_alternate_remove(void) { + struct linked_list list; + linked_list_init(&list); + + struct list_elem elem1 = {{0}, NULL}; + linked_list_insert(&list, &elem1.link); + linked_list_remove(&list); + + // Both next and prev on list be NULL + assert(list.next == NULL && list.prev == NULL); + + // Both next and prev should point to self + assert(elem1.link.next == &elem1.link && elem1.link.prev == &elem1.link); + + // The elem should be empty + assert(linked_list_empty(&elem1.link)); +} + +static void test_linked_list_sequential_remove(void) { + struct linked_list list; + linked_list_init(&list); + + struct list_elem elem1 = {{0}, NULL}, elem2 = {{0}, NULL}, elem3 = {{0}, NULL}; + linked_list_insert(&list, &elem1.link); + linked_list_insert(&elem1.link, &elem2.link); + linked_list_insert(&elem2.link, &elem3.link); + + // The order should now be list→elem1→elem2→elem3→list + assert(list.next == &elem1.link && list.prev == &elem3.link); + assert(elem1.link.next == &elem2.link && elem1.link.prev == &list); + assert(elem2.link.next == &elem3.link && elem2.link.prev == &elem1.link); + assert(elem3.link.next == &list && elem3.link.prev == &elem2.link); + + linked_list_remove(list.next); + + // The order should now be list→elem2→elem3→list + assert(list.next == &elem2.link && list.prev == &elem3.link); + assert(elem2.link.next == &elem3.link && elem2.link.prev == &list); + assert(elem3.link.next == &list && elem3.link.prev == &elem2.link); + assert(elem1.link.next == NULL && elem1.link.prev == NULL); + + linked_list_remove(list.next); + + // The order should now be list→elem3→list + assert(list.next == &elem3.link && list.prev == &elem3.link); + assert(elem3.link.next == &list && elem3.link.prev == &list); + assert(elem1.link.next == NULL && elem1.link.prev == NULL); + assert(elem2.link.next == NULL && elem2.link.prev == NULL); + + linked_list_remove(list.next); + + // The list should now be empty + assert(elem1.link.next == NULL && elem1.link.prev == NULL); + assert(elem2.link.next == NULL && elem2.link.prev == NULL); + assert(elem3.link.next == NULL && elem3.link.prev == NULL); + assert(list.next == &list && list.prev == &list); + assert(linked_list_empty(&list)); +} + +static void test_linked_list_insert_after(void) { + struct linked_list list; + linked_list_init(&list); + + struct list_elem elem1 = {{0}, NULL}, elem2 = {{0}, NULL}, elem3 = {{0}, NULL}; + linked_list_insert(&list, &elem1.link); + linked_list_insert(&elem1.link, &elem3.link); + linked_list_insert(&elem1.link, &elem2.link); + + // The order should now be list→elem1→elem2→elem3→list + assert(list.next == &elem1.link && list.prev == &elem3.link); + assert(elem1.link.next == &elem2.link && elem1.link.prev == &list); + assert(elem2.link.next == &elem3.link && elem2.link.prev == &elem1.link); + assert(elem3.link.next == &list && elem3.link.prev == &elem2.link); +} + +static void test_linked_list_remove_loop(void) { + struct linked_list list; + linked_list_init(&list); + + struct list_elem elem1 = {{0}, NULL}, elem2 = {{0}, NULL}, elem3 = {{0}, NULL}; + linked_list_insert(&list, &elem1.link); + linked_list_insert(&elem1.link, &elem2.link); + linked_list_insert(&elem2.link, &elem3.link); + + size_t cnt = 0; + while (!linked_list_empty(&list)) { + struct list_elem *elem = (struct list_elem *)list.next; + linked_list_remove(&elem->link); + cnt++; + } + assert(cnt == 3); + + // Link should now be empty, and next and prev on all elements hsould be NULL + assert(linked_list_empty(&list)); + assert(elem1.link.next == NULL && elem1.link.prev == NULL); + assert(elem2.link.next == NULL && elem2.link.prev == NULL); + assert(elem3.link.next == NULL && elem3.link.prev == NULL); +} + +static void test_linked_list_manual_iterate(void) { + struct linked_list list; + linked_list_init(&list); + + struct list_elem elem1 = {{0}, "elem1"}; + struct list_elem elem2 = {{0}, "elem2"}; + struct list_elem elem3 = {{0}, "elem3"}; + linked_list_insert(&list, &elem1.link); + linked_list_insert(&elem1.link, &elem2.link); + linked_list_insert(&elem2.link, &elem3.link); + + struct list_elem *ptr = NULL; + + ptr = (struct list_elem *)list.next; + assert(strcmp("elem1", ptr->content) == 0); + + ptr = (struct list_elem *)ptr->link.next; + assert(strcmp("elem2", ptr->content) == 0); + + ptr = (struct list_elem *)ptr->link.next; + assert(strcmp("elem3", ptr->content) == 0); + + assert(ptr->link.next == &list); +} + +static void test_linked_list_loop_iterate(void) { + struct linked_list list; + linked_list_init(&list); + + struct list_elem elem1 = {{0}, "elem"}; + struct list_elem elem2 = {{0}, "elem"}; + struct list_elem elem3 = {{0}, "elem"}; + linked_list_insert(&list, &elem1.link); + linked_list_insert(&elem1.link, &elem2.link); + linked_list_insert(&elem1.link, &elem3.link); + + size_t cnt = 0; + for (struct linked_list *ptr = list.next; ptr != &list; ptr = ptr->next) { + struct list_elem *elem = (struct list_elem *)ptr; + assert(strcmp("elem", elem->content) == 0); + cnt++; + } + assert(cnt == 3); +} + +int main(int argc, char *argv[]) { + (void)argc; + (void)argv; + + test_linked_list_init(); + test_linked_list_single_insert(); + test_linked_list_single_remove(); + test_linked_list_alternate_remove(); + test_linked_list_sequential_remove(); + test_linked_list_insert_after(); + test_linked_list_remove_loop(); + test_linked_list_manual_iterate(); + test_linked_list_loop_iterate(); + + return 0; +} |