linked_list: Add unittest

2 files changed, 229 insertions, 0 deletions

diff --git a/meson.build b/meson.build
index f8bbf93..6d54a2b 100644
--- a/meson.build
+++ b/meson.build
@@ -168,6 +168,16 @@ if get_option('examples').enabled()
 	)
 endif
 
+test(
+        'linked_list',
+        executable(
+                'linked_list_test',
+                ['common/linked_list.c', 'tests/linked_list.c'],
+                include_directories: [include_directories('.', 'include')],
+        )
+)
+
+
 summary({
    'seatd': get_option('seatd').enabled() ? 1 : 0,
    'builtin': get_option('builtin').enabled() ? 1 : 0,
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;
+}