From 9e20ec260930db451a843df4470eba72b5784d5f Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Thu, 25 Jun 2015 23:03:48 -0400 Subject: [PATCH] Added singly linked list implementation --- source/data/bstree.h | 35 ++++++++ source/data/list.h | 43 ++++++++++ source/data/slist.c | 85 +++++++++++++++++++ source/data/slist.h | 39 +++++++++ tests/data/slist.c | 194 +++++++++++++++++++++++++++++++++++++++++++ tests/main.c | 1 + 6 files changed, 397 insertions(+) create mode 100644 source/data/bstree.h create mode 100644 source/data/list.h create mode 100644 source/data/slist.c create mode 100644 source/data/slist.h create mode 100644 tests/data/slist.c diff --git a/source/data/bstree.h b/source/data/bstree.h new file mode 100644 index 0000000..4beb87c --- /dev/null +++ b/source/data/bstree.h @@ -0,0 +1,35 @@ +/** + @file bstree.h +*/ +#ifndef BSTREE_H +#define BSTREE_H + +typedef struct bstree_node_t { + struct bstree_node_t* parent; + struct bstree_node_t* left; + struct bstree_node_t* right; +} bstree_node_t; + +typedef struct { + bstree_node_t* root; +} bstree_t; + +void bstree_init(bstree_t* bstree); + +bool bstree_empty(bstree_t* bstree); + +size_t bstree_size(bstree_t* bstree); + +void bstree_insert(bstree_t* bstree, bstree_node_t* node); + +bstree_node_t* bstree_lookup(bstree_t* bstree, bstree_node_t* node); + +bool bstree_node_hasnext(bstree_node_t* node); + +bstree_node_t* bstree_node_next(bstree_node_t* node); + +bool bstree_node_hasprev(bstree_node_t* node); + +bstree_node_t* bstree_node_prev(bstree_node_t* node); + +#endif /* BSTREE_H */ diff --git a/source/data/list.h b/source/data/list.h new file mode 100644 index 0000000..5a4141d --- /dev/null +++ b/source/data/list.h @@ -0,0 +1,43 @@ +/** + @file list.h +*/ +#ifndef LIST_H +#define LIST_H + +typedef struct list_node_t { + struct list_node_t* next; + struct list_node_t* prev; +} list_node_t; + +typedef struct { + list_node_t* head; + list_node_t* tail; +} list_t; + +void list_init(list_t* list); + +bool list_empty(list_t* list); + +size_t list_size(list_t* list); + +list_node_t* list_front(list_t* list); + +void list_push_front(list_t* list, list_node_t* node); + +list_node_t* list_pop_front(list_t* list); + +list_node_t* list_back(list_t* list); + +void list_push_back(list_t* list, list_node_t* node); + +list_node_t* list_pop_back(list_t* list); + +bool list_node_hasnext(list_node_t* node); + +list_node_t* list_node_next(list_node_t* node); + +bool list_node_hasprev(list_node_t* node); + +list_node_t* list_node_prev(list_node_t* node); + +#endif /* LIST_H */ diff --git a/source/data/slist.c b/source/data/slist.c new file mode 100644 index 0000000..ef5ed27 --- /dev/null +++ b/source/data/slist.c @@ -0,0 +1,85 @@ +#include + +void slist_init(slist_t* list) +{ + list->head = NULL; +} + +bool slist_empty(slist_t* list) +{ + return (list->head == NULL); +} + +size_t slist_size(slist_t* list) +{ + size_t sz = 0; + slist_node_t* node = list->head; + while (node != NULL) { + sz++; + node = node->next; + } + return sz; +} + +slist_node_t* slist_front(slist_t* list) +{ + return list->head; +} + +void slist_push_front(slist_t* list, slist_node_t* node) +{ + node->next = list->head; + list->head = node; +} + +slist_node_t* slist_pop_front(slist_t* list) +{ + slist_node_t* node = list->head; + list->head = node->next; + node->next = NULL; + return node; +} + +slist_node_t* slist_back(slist_t* list) +{ + slist_node_t* node = list->head; + while (node && node->next != NULL) + node = node->next; + return (node) ? node : NULL; +} + +void slist_push_back(slist_t* list, slist_node_t* node) +{ + slist_node_t* back = slist_back(list); + if (NULL != back) + back->next = node; + else + list->head = node; + node->next = NULL; +} + +slist_node_t* slist_pop_back(slist_t* list) +{ + slist_node_t* prev = NULL; + slist_node_t* curr = list->head; + while (curr && curr->next != NULL) { + prev = curr; + curr = curr->next; + } + if (prev != NULL) + prev->next = NULL; + if (list->head == curr) + list->head = NULL; + return curr; +} + +bool slist_node_has_next(slist_node_t* node) +{ + return (node->next != NULL); +} + +slist_node_t* slist_node_next(slist_node_t* node) +{ + return node->next; +} + diff --git a/source/data/slist.h b/source/data/slist.h new file mode 100644 index 0000000..730bc6e --- /dev/null +++ b/source/data/slist.h @@ -0,0 +1,39 @@ +/** + @file slist.h +*/ +#ifndef SLIST_H +#define SLIST_H + +#include + +typedef struct slist_node_t { + struct slist_node_t* next; +} slist_node_t; + +typedef struct { + slist_node_t* head; +} slist_t; + +void slist_init(slist_t* list); + +bool slist_empty(slist_t* list); + +size_t slist_size(slist_t* list); + +slist_node_t* slist_front(slist_t* list); + +void slist_push_front(slist_t* list, slist_node_t* node); + +slist_node_t* slist_pop_front(slist_t* list); + +slist_node_t* slist_back(slist_t* list); + +void slist_push_back(slist_t* list, slist_node_t* node); + +slist_node_t* slist_pop_back(slist_t* list); + +bool slist_node_has_next(slist_node_t* node); + +slist_node_t* slist_node_next(slist_node_t* node); + +#endif /* SLIST_H */ diff --git a/tests/data/slist.c b/tests/data/slist.c new file mode 100644 index 0000000..d364376 --- /dev/null +++ b/tests/data/slist.c @@ -0,0 +1,194 @@ +// Unit Test Framework Includes +#include "atf.h" + +// File To Test +#include + +//----------------------------------------------------------------------------- +// Begin Unit Tests +//----------------------------------------------------------------------------- +TEST_SUITE(SList) { + //------------------------------------------------------------------------- + // slist_init + //------------------------------------------------------------------------- + TEST(Verify_slist_init_initializesr_the_list) + { + slist_t list; + slist_init(&list); + CHECK(list.head == NULL); + } + + //------------------------------------------------------------------------- + // slist_empty + //------------------------------------------------------------------------- + TEST(Verify_slist_empty_returns_true_when_list_is_empty) + { + slist_t list = { NULL }; + CHECK(true == slist_empty(&list)); + } + + TEST(Verify_slist_empty_returns_false_when_list_is_not_empty) + { + slist_t alist = { (slist_node_t*)0x1234 }; + CHECK(false == slist_empty(&alist)); + } + + //------------------------------------------------------------------------- + // slist_size + //------------------------------------------------------------------------- + TEST(Verify_slist_size_should_return_0) + { + slist_t list = { 0 }; + CHECK(0 == slist_size(&list)); + } + + TEST(Verify_slist_size_should_return_1) + { + slist_node_t node = { NULL }; + slist_t list = { &node }; + CHECK(1 == slist_size(&list)); + CHECK(node.next == NULL); + } + + TEST(Verify_slist_size_should_return_2) + { + slist_node_t node2 = { NULL }; + slist_node_t node1 = { &node2 }; + slist_t list = { &node1 }; + CHECK(2 == slist_size(&list)); + CHECK(node1.next == &node2); + CHECK(node2.next == NULL); + } + + //------------------------------------------------------------------------- + // slist_front + //------------------------------------------------------------------------- + TEST(Verify_slist_front_should_return_the_head) + { + slist_node_t node2 = { NULL }; + slist_node_t node1 = { &node2 }; + slist_t list = { &node1 }; + CHECK(&node1 == slist_front(&list)); + } + + //------------------------------------------------------------------------- + // slist_push_front + //------------------------------------------------------------------------- + TEST(Verify_slist_push_front_should_push_the_node_to_the_head) + { + slist_node_t node = { NULL }; + slist_t list = { 0 }; + slist_push_front(&list, &node); + CHECK(!slist_empty(&list)); + CHECK(list.head == &node); + } + + //------------------------------------------------------------------------- + // slist_pop_front + //------------------------------------------------------------------------- + TEST(Verify_slist_pop_front_should_remove_the_head_element_from_the_list_and_return_it) + { + slist_node_t node = { NULL }; + slist_t list = { &node }; + CHECK(&node == slist_pop_front(&list)); + CHECK(slist_empty(&list)); + CHECK(list.head == NULL); + } + + //------------------------------------------------------------------------- + // slist_back + //------------------------------------------------------------------------- + TEST(Verify_slist_back_should_return_NULL_if_the_list_is_empty) + { + slist_t list = { NULL }; + CHECK(NULL == slist_back(&list)); + } + + TEST(Verify_slist_back_should_return_the_head_if_only_one_item_in_list) + { + slist_node_t node = { NULL }; + slist_t list = { &node }; + CHECK(&node == slist_back(&list)); + } + + TEST(Verify_slist_back_should_return_the_last_item_if_two_items_in_list) + { + slist_node_t node2 = { NULL }; + slist_node_t node1 = { &node2 }; + slist_t list = { &node1 }; + CHECK(&node2 == slist_back(&list)); + } + + //------------------------------------------------------------------------- + // slist_push_back + //------------------------------------------------------------------------- + TEST(Verify_slist_push_back_should_push_to_the_head) + { + slist_node_t node = { NULL }; + slist_t list = { NULL }; + slist_push_back(&list, &node); + CHECK(&node == list.head); + } + + TEST(Verify_slist_push_back_should_push_to_the_tail) + { + slist_node_t node2 = { NULL }; + slist_node_t node1 = { NULL }; + slist_t list = { &node1 }; + slist_push_back(&list, &node2); + CHECK(&node2 == list.head->next); + } + + //------------------------------------------------------------------------- + // slist_pop_back + //------------------------------------------------------------------------- + TEST(Verify_slist_pop_back_should_do_nothing_if_list_empty) + { + slist_t list = { NULL }; + CHECK(NULL == slist_pop_back(&list)); + CHECK(NULL == list.head); + } + + TEST(Verify_slist_pop_back_should_remove_the_only_item_in_the_list) + { + slist_node_t node = { NULL }; + slist_t list = { &node }; + CHECK(&node == slist_pop_back(&list)); + CHECK(NULL == list.head); + } + + TEST(Verify_slist_pop_back_should_remove_the_last_item_in_the_list) + { + slist_node_t node2 = { NULL }; + slist_node_t node1 = { &node2 }; + slist_t list = { &node1 }; + CHECK(&node2 == slist_pop_back(&list)); + CHECK(&node1 == list.head); + CHECK(NULL == list.head->next); + } + + //------------------------------------------------------------------------- + // slist_node_has_next + //------------------------------------------------------------------------- + TEST(Verify_slist_has_next_should_return_false_if_null) + { + slist_node_t node = { NULL }; + CHECK(!slist_node_has_next(&node)); + } + + TEST(Verify_slist_has_next_should_return_false_if_not_null) + { + slist_node_t node = { (slist_node_t*)0x1234 }; + CHECK(slist_node_has_next(&node)); + } + + //------------------------------------------------------------------------- + // slist_node_next + //------------------------------------------------------------------------- + TEST(Verify_slist_node_next_should_return_the_next_node) + { + slist_node_t node = { (slist_node_t*)0x1234 }; + CHECK((slist_node_t*)0x1234 == slist_node_next(&node)); + } +} + diff --git a/tests/main.c b/tests/main.c index cdaf8df..11ce75b 100644 --- a/tests/main.c +++ b/tests/main.c @@ -6,5 +6,6 @@ void main(int argc, char** argv) (void)argc; (void)argv; RUN_EXTERN_TEST_SUITE(RefCount); + RUN_EXTERN_TEST_SUITE(SList); exit(PRINT_TEST_RESULTS()); } -- 2.54.0