From 15ae431a33d0fcbbe05c35cda6c38aa16be30cfe Mon Sep 17 00:00:00 2001 From: "Mike D. Lowis" Date: Fri, 12 Apr 2013 13:39:15 -0400 Subject: [PATCH] Rename sll file to list. There will only be one list implementation --- source/list/{sll.c => list.c} | 88 +++--- source/list/{sll.h => list.h} | 52 ++-- tests/test_list.cpp | 500 ++++++++++++++++++++++++++++++++++ tests/test_sll.cpp | 500 ---------------------------------- 4 files changed, 570 insertions(+), 570 deletions(-) rename source/list/{sll.c => list.c} (56%) rename source/list/{sll.h => list.h} (83%) create mode 100644 tests/test_list.cpp delete mode 100644 tests/test_sll.cpp diff --git a/source/list/sll.c b/source/list/list.c similarity index 56% rename from source/list/sll.c rename to source/list/list.c index 66ddf4c..67f3100 100644 --- a/source/list/sll.c +++ b/source/list/list.c @@ -1,35 +1,35 @@ #include -#include "sll.h" +#include "list.h" -sll_t* sll_new(void) +list_t* list_new(void) { - sll_t* list = (sll_t*)malloc( sizeof( sll_t ) ); + list_t* list = (list_t*)malloc( sizeof( list_t ) ); list->head = NULL; list->tail = NULL; return list; } -sll_node_t* sll_new_node(void* contents) +list_node_t* list_new_node(void* contents) { - sll_node_t* node = (sll_node_t*)malloc( sizeof( sll_node_t ) ); + list_node_t* node = (list_node_t*)malloc( sizeof( list_node_t ) ); node->contents = contents; node->next = NULL; return node; } -void sll_free(sll_t* list, bool free_contents) +void list_free(list_t* list, bool free_contents) { - sll_node_t* node = list->head; + list_node_t* node = list->head; while( NULL != node ) { - sll_node_t* next = node->next; - sll_free_node( node, free_contents ); + list_node_t* next = node->next; + list_free_node( node, free_contents ); node = next; } free( list ); } -void sll_free_node(sll_node_t* node, bool free_contents) +void list_free_node(list_node_t* node, bool free_contents) { if( free_contents ) { @@ -38,20 +38,20 @@ void sll_free_node(sll_node_t* node, bool free_contents) free( node ); } -sll_node_t* sll_front( sll_t* list ) +list_node_t* list_front( list_t* list ) { return list->head; } -sll_node_t* sll_back( sll_t* list ) +list_node_t* list_back( list_t* list ) { return list->tail; } -size_t sll_size(sll_t* list) +size_t list_size(list_t* list) { size_t length = 0; - sll_node_t* node = list->head; + list_node_t* node = list->head; while( NULL != node ) { node = node->next; @@ -60,17 +60,17 @@ size_t sll_size(sll_t* list) return length; } -bool sll_empty(sll_t* list) +bool list_empty(list_t* list) { return ((NULL == list->head) && (NULL == list->tail)); } -sll_node_t* sll_at(sll_t* list, size_t index) +list_node_t* list_at(list_t* list, size_t index) { - sll_node_t* node = NULL; + list_node_t* node = NULL; size_t cur_index = 0; - sll_node_t* cur_node = list->head; + list_node_t* cur_node = list->head; while( NULL != cur_node ) { if( cur_index == index ) @@ -84,9 +84,9 @@ sll_node_t* sll_at(sll_t* list, size_t index) return node; } -sll_node_t* sll_push_front( sll_t* list, void* contents ) +list_node_t* list_push_front( list_t* list, void* contents ) { - sll_node_t* node = sll_new_node( contents ); + list_node_t* node = list_new_node( contents ); node->next = list->head; list->head = node; if( NULL == list->tail ) @@ -96,9 +96,9 @@ sll_node_t* sll_push_front( sll_t* list, void* contents ) return node; } -sll_node_t* sll_push_back( sll_t* list, void* contents ) +list_node_t* list_push_back( list_t* list, void* contents ) { - sll_node_t* node = sll_new_node( contents ); + list_node_t* node = list_new_node( contents ); node->next = NULL; if( NULL == list->tail ) { @@ -113,9 +113,9 @@ sll_node_t* sll_push_back( sll_t* list, void* contents ) return node; } -sll_node_t* sll_pop_front( sll_t* list ) +list_node_t* list_pop_front( list_t* list ) { - sll_node_t* node = NULL; + list_node_t* node = NULL; if( NULL != list->head ) { node = list->head; @@ -128,9 +128,9 @@ sll_node_t* sll_pop_front( sll_t* list ) return node; } -sll_node_t* sll_pop_back( sll_t* list ) +list_node_t* list_pop_back( list_t* list ) { - sll_node_t* node = NULL; + list_node_t* node = NULL; if ( list->head == list->tail ) { node = list->head; @@ -139,7 +139,7 @@ sll_node_t* sll_pop_back( sll_t* list ) } else { - sll_node_t* next_tail = list->head; + list_node_t* next_tail = list->head; while( next_tail->next != list->tail ) { next_tail = next_tail->next; @@ -151,20 +151,20 @@ sll_node_t* sll_pop_back( sll_t* list ) return node; } -sll_node_t* sll_insert( sll_t* list, size_t index, void* contents) +list_node_t* list_insert( list_t* list, size_t index, void* contents) { - sll_node_t* new_node = NULL; + list_node_t* new_node = NULL; if( 0 == index ) { - new_node = sll_push_front( list, contents ); + new_node = list_push_front( list, contents ); } else { - sll_node_t* prev_node = sll_at( list, index - 1 ); + list_node_t* prev_node = list_at( list, index - 1 ); if( NULL != prev_node ) { - sll_node_t* next_node = prev_node->next; - new_node = sll_new_node( contents ); + list_node_t* next_node = prev_node->next; + new_node = list_new_node( contents ); new_node->next = next_node; prev_node->next = new_node; if( NULL == next_node ) @@ -176,22 +176,22 @@ sll_node_t* sll_insert( sll_t* list, size_t index, void* contents) return new_node; } -sll_node_t* sll_delete( sll_t* list, size_t index, bool free_contents) +list_node_t* list_delete( list_t* list, size_t index, bool free_contents) { - sll_node_t* node = NULL; + list_node_t* node = NULL; if (0 == index) { - node = sll_pop_front(list); + node = list_pop_front(list); if (NULL != node) { - sll_free_node(node,free_contents); - node = sll_front(list); + list_free_node(node,free_contents); + node = list_front(list); } } else { - sll_node_t* prev = sll_at(list,index-1); + list_node_t* prev = list_at(list,index-1); node = (NULL == prev) ? NULL : prev->next; if (NULL != node) { @@ -200,7 +200,7 @@ sll_node_t* sll_delete( sll_t* list, size_t index, bool free_contents) { list->tail = prev; } - sll_free_node(node,free_contents); + list_free_node(node,free_contents); node = prev->next; } } @@ -208,13 +208,13 @@ sll_node_t* sll_delete( sll_t* list, size_t index, bool free_contents) return node; } -sll_t* sll_clear(sll_t* list, bool free_contents) +list_t* list_clear(list_t* list, bool free_contents) { - sll_node_t* node = list->head; + list_node_t* node = list->head; while(NULL != node) { - sll_node_t* next = node->next; - sll_free_node(node,free_contents); + list_node_t* next = node->next; + list_free_node(node,free_contents); node = next; } list->head = NULL; diff --git a/source/list/sll.h b/source/list/list.h similarity index 83% rename from source/list/sll.h rename to source/list/list.h index b49443c..5a146c2 100644 --- a/source/list/sll.h +++ b/source/list/list.h @@ -1,5 +1,5 @@ -#ifndef SLL_H -#define SLL_H +#ifndef LIST_H +#define LIST_H #ifdef __cplusplus extern "C" { @@ -8,29 +8,29 @@ extern "C" { #include /** A linked list node. */ -typedef struct sll_node_t +typedef struct list_node_t { /** Pointer to the contents the node */ void* contents; /** Pointer to next node in the list. */ - struct sll_node_t* next; -} sll_node_t; + struct list_node_t* next; +} list_node_t; /** A singly linked list */ -typedef struct sll_t +typedef struct list_t { /** Pointer to the first element in the list */ - sll_node_t* head; + list_node_t* head; /** Pointer to the last element in the list */ - sll_node_t* tail; -} sll_t; + list_node_t* tail; +} list_t; /** * @brief Creates a new empty linked list. * * @return A pointer to the newly created list. **/ -extern sll_t* sll_new(void); +extern list_t* list_new(void); /** * @brief Creates a new node with given contents. @@ -39,7 +39,7 @@ extern sll_t* sll_new(void); * * @return Pointer to newly created node. */ -sll_node_t* sll_new_node(void* contents); +list_node_t* list_new_node(void* contents); /** * @brief Frees all memory used by a linked list. @@ -50,7 +50,7 @@ sll_node_t* sll_new_node(void* contents); * @param list The list to be freed. * @param free_contents Whether or not to also free the contents of each node. **/ -void sll_free(sll_t* list, bool free_contents); +void list_free(list_t* list, bool free_contents); /** * @brief Frees all memory used by a node. @@ -61,7 +61,7 @@ void sll_free(sll_t* list, bool free_contents); * @param node * @param free_contents */ -void sll_free_node(sll_node_t* node, bool free_contents); +void list_free_node(list_node_t* node, bool free_contents); /** * @brief Returns pointer to first node in the list @@ -70,7 +70,7 @@ void sll_free_node(sll_node_t* node, bool free_contents); * * @return Pointer to the first element in the list. */ -sll_node_t* sll_front( sll_t* list ); +list_node_t* list_front( list_t* list ); /** * @brief Returns pointer to the last element in the list. @@ -79,7 +79,7 @@ sll_node_t* sll_front( sll_t* list ); * * @return Pointer to the last element in the list. */ -sll_node_t* sll_back( sll_t* list ); +list_node_t* list_back( list_t* list ); /** * @brief Returns the number of elements in the list. @@ -91,7 +91,7 @@ sll_node_t* sll_back( sll_t* list ); * * @return The number of elements in the list. **/ -size_t sll_size(sll_t* list); +size_t list_size(list_t* list); /** * @brief Returns whether the list is empty or not. @@ -100,7 +100,7 @@ size_t sll_size(sll_t* list); * * @return Whether the list is empty, 1 for true and 0 for false. */ -bool sll_empty(sll_t* list); +bool list_empty(list_t* list); /** * @brief Return the node at the specified index in a linked list. @@ -113,7 +113,7 @@ bool sll_empty(sll_t* list); * * @return A pointer to the node at the supplied index, NULL if out of range. **/ -sll_node_t* sll_at(sll_t* list, size_t index); +list_node_t* list_at(list_t* list, size_t index); /** * @brief Adds a new node to the front of an existing linked list. @@ -126,7 +126,7 @@ sll_node_t* sll_at(sll_t* list, size_t index); * * @return Pointer to the newly added node. **/ -sll_node_t* sll_push_front( sll_t* list, void* contents ); +list_node_t* list_push_front( list_t* list, void* contents ); /** * @brief Adds a new node to the end of an existing linked list. @@ -139,7 +139,7 @@ sll_node_t* sll_push_front( sll_t* list, void* contents ); * * @return Pointer to the newly added node. **/ -sll_node_t* sll_push_back( sll_t* list, void* contents ); +list_node_t* list_push_back( list_t* list, void* contents ); /** * @brief Removes and returns a pointer to the first element of the list. @@ -151,7 +151,7 @@ sll_node_t* sll_push_back( sll_t* list, void* contents ); * * @return Pointer to the newly added node. **/ -sll_node_t* sll_pop_front( sll_t* list ); +list_node_t* list_pop_front( list_t* list ); /** * @brief Removes and returns a pointer to the last element of the list. @@ -163,7 +163,7 @@ sll_node_t* sll_pop_front( sll_t* list ); * * @return Pointer to the newly added node. **/ -sll_node_t* sll_pop_back( sll_t* list ); +list_node_t* list_pop_back( list_t* list ); /** * @brief Inserts a new node in a linked list at the specified index. @@ -178,7 +178,7 @@ sll_node_t* sll_pop_back( sll_t* list ); * * @return Pointer to the newly inserted node, NULL if index is out of range. **/ -sll_node_t* sll_insert( sll_t* list, size_t index, void* contents); +list_node_t* list_insert( list_t* list, size_t index, void* contents); /** * @brief Deletes a node from the supplied list. @@ -194,7 +194,7 @@ sll_node_t* sll_insert( sll_t* list, size_t index, void* contents); * * @return Pointer to the node that is now at the supplied index. **/ -sll_node_t* sll_delete( sll_t* list, size_t index, bool free_contents); +list_node_t* list_delete( list_t* list, size_t index, bool free_contents); /** * @brief Deletes all elements in the provided list @@ -204,10 +204,10 @@ sll_node_t* sll_delete( sll_t* list, size_t index, bool free_contents); * * @return A pointer to the cleared list. */ -sll_t* sll_clear(sll_t* list, bool free_contents); +list_t* list_clear(list_t* list, bool free_contents); #ifdef __cplusplus } #endif -#endif +#endif /* LIST_H */ diff --git a/tests/test_list.cpp b/tests/test_list.cpp new file mode 100644 index 0000000..a13d67f --- /dev/null +++ b/tests/test_list.cpp @@ -0,0 +1,500 @@ +// Unit Test Framework Includes +#include "UnitTest++.h" +#include + +// File To Test +#include "list.h" + +using namespace UnitTest; + +//----------------------------------------------------------------------------- +// Begin Unit Tests +//----------------------------------------------------------------------------- +namespace { + //------------------------------------------------------------------------- + // Test list_new function + //------------------------------------------------------------------------- + TEST(Verify_list_new_returns_newly_allocated_empty_list) + { + list_t* list = list_new(); + CHECK( NULL != list ); + CHECK( NULL == list->head ); + CHECK( NULL == list->tail ); + free( list ); + } + + //------------------------------------------------------------------------- + // Test list_new_node function + //------------------------------------------------------------------------- + TEST(Verify_list_new_node_returns_newly_allocated_node_with_given_contents) + { + int stuff = 0; + list_node_t* node = list_new_node( &stuff ); + CHECK( NULL != node ); + CHECK( &stuff == node->contents ); + CHECK( NULL == node->next ); + free( node ); + } + + //------------------------------------------------------------------------- + // Test list_free function + //------------------------------------------------------------------------- + TEST(Verify_list_free_frees_the_given_empty_list) + { + list_t* list = list_new(); + list_free( list, 0 ); + } + + TEST(Verify_list_free_frees_the_given_list_including_nodes) + { + list_t* list = list_new(); + list->head = list_new_node(NULL); + list->tail = list->head; + list_free( list, 0 ); + } + + TEST(Verify_list_free_frees_the_given_list_including_nodes_and_node_contents) + { + list_t* list = list_new(); + int* foo = (int*)malloc( sizeof(int) ); + list->head = list_new_node( foo ); + list->tail = list->head; + list_free( list, 1 ); + } + + //------------------------------------------------------------------------- + // Test list_free_node function + //------------------------------------------------------------------------- + TEST(Verify_list_free_node_frees_the_given_node) + { + list_node_t* node = list_new_node( NULL ); + list_free_node( node, 0 ); + } + + TEST(Verify_list_free_node_frees_the_given_node_and_contents) + { + int* foo = (int*)malloc( sizeof(int) ); + list_node_t* node = list_new_node( foo ); + list_free_node( node, 1 ); + } + + //------------------------------------------------------------------------- + // Test list_front function + //------------------------------------------------------------------------- + TEST(Verify_list_front_returns_NULL_if_list_is_empty) + { + list_t list = { NULL, NULL }; + CHECK( NULL == list_front( &list ) ); + } + + TEST(Verify_list_front_returns_the_head_of_the_list) + { + list_node_t node2 = { NULL, NULL }; + list_node_t node1 = { NULL, &node2 }; + list_t list = { &node1, &node2 }; + CHECK( &node1 == list_front( &list ) ); + } + + //------------------------------------------------------------------------- + // Test list_back function + //------------------------------------------------------------------------- + TEST(Verify_list_back_returns_NULL_if_list_is_empty) + { + list_t list = { NULL, NULL }; + CHECK( NULL == list_back( &list ) ); + } + + TEST(Verify_list_back_returns_the_tail_of_the_list) + { + list_node_t node2 = { NULL, NULL }; + list_node_t node1 = { NULL, &node2 }; + list_t list = { &node1, &node2 }; + CHECK( &node2 == list_back( &list ) ); + } + + //------------------------------------------------------------------------- + // Test list_size function + //------------------------------------------------------------------------- + TEST(Verify_list_size_returns_0_when_list_is_empty) + { + list_t* list = list_new(); + CHECK( 0 == list_size( list ) ); + free( list ); + } + + TEST(Verify_list_size_returns_1_when_list_is_length_1) + { + list_node_t node1 = { NULL, NULL }; + list_t list = { &node1, &node1 }; + + CHECK( 1 == list_size( &list ) ); + } + + TEST(Verify_list_size_returns_2_when_list_is_length_2) + { + list_node_t node2 = { NULL, NULL }; + list_node_t node1 = { NULL, &node2 }; + list_t list = { &node1, &node2 }; + + CHECK( 2 == list_size( &list ) ); + } + + //------------------------------------------------------------------------- + // Test list_empty function + //------------------------------------------------------------------------- + TEST(Verify_list_empty_returns_true_when_head_and_tail_are_null) + { + list_t list = { NULL, NULL }; + CHECK( 1 == list_empty( &list ) ); + } + + TEST(Verify_list_empty_returns_false_when_head_is_not_null) + { + list_t list = { (list_node_t*)0x1234, NULL }; + CHECK( 0 == list_empty( &list ) ); + } + + TEST(Verify_list_empty_returns_false_when_tail_is_not_null) + { + list_t list = { NULL, (list_node_t*)0x1234 }; + CHECK( 0 == list_empty( &list ) ); + } + + //------------------------------------------------------------------------- + // Test list_at function + //------------------------------------------------------------------------- + TEST(Verify_list_at_returns_NULL_when_list_is_empty) + { + list_t list = { NULL, NULL }; + CHECK( NULL == list_at( &list, 0 ) ); + } + + TEST(Verify_list_at_returns_NULL_when_index_out_of_range) + { + list_node_t node3 = { NULL, NULL }; + list_node_t node2 = { NULL, &node3 }; + list_node_t node1 = { NULL, &node2 }; + list_t list = { &node1, &node3 }; + CHECK( NULL == list_at( &list, 3 ) ); + } + + TEST(Verify_list_at_returns_node_at_index_0_of_3_element_list) + { + list_node_t node3 = { NULL, NULL }; + list_node_t node2 = { NULL, &node3 }; + list_node_t node1 = { NULL, &node2 }; + list_t list = { &node1, &node3 }; + CHECK( &node1 == list_at( &list, 0 ) ); + } + + TEST(Verify_list_at_returns_node_at_index_1_of_3_element_list) + { + list_node_t node3 = { NULL, NULL }; + list_node_t node2 = { NULL, &node3 }; + list_node_t node1 = { NULL, &node2 }; + list_t list = { &node1, &node3 }; + CHECK( &node2 == list_at( &list, 1 ) ); + } + + TEST(Verify_list_at_returns_node_at_index_2_of_3_element_list) + { + list_node_t node3 = { NULL, NULL }; + list_node_t node2 = { NULL, &node3 }; + list_node_t node1 = { NULL, &node2 }; + list_t list = { &node1, &node3 }; + CHECK( &node3 == list_at( &list, 2 ) ); + } + + //------------------------------------------------------------------------- + // Test list_push_front function + //------------------------------------------------------------------------- + TEST(Verify_list_push_front_pushes_to_empty_list) + { + list_t list = { NULL, NULL }; + list_node_t* node = list_push_front( &list, (void*)0x1234 ); + CHECK( NULL != node ); + CHECK( (void*)0x1234 == node->contents ); + CHECK( NULL == node->next ); + CHECK( node == list.head ); + CHECK( node == list.tail ); + } + + TEST(Verify_list_push_front_pushes_to_front_of_list_of_length_1) + { + list_node_t node1 = { NULL, NULL }; + list_t list = { &node1, &node1 }; + list_node_t* node = list_push_front( &list, (void*)0x1234 ); + CHECK( NULL != node ); + CHECK( (void*)0x1234 == node->contents ); + CHECK( NULL != node->next ); + CHECK( node == list.head ); + CHECK( node != list.tail ); + } + + //------------------------------------------------------------------------- + // Test list_push_back function + //------------------------------------------------------------------------- + TEST(Verify_list_push_back_pushes_to_empty_list) + { + list_t list = { NULL, NULL }; + list_node_t* node = list_push_back( &list, (void*)0x1234 ); + CHECK( NULL != node ); + CHECK( (void*)0x1234 == node->contents ); + CHECK( NULL == node->next ); + CHECK( node == list.head ); + CHECK( node == list.tail ); + } + + TEST(Verify_list_push_back_pushes_to_back_of_list_of_length_1) + { + list_node_t node1 = { NULL, NULL }; + list_t list = { &node1, &node1 }; + list_node_t* node = list_push_back( &list, (void*)0x1234 ); + CHECK( NULL != node ); + CHECK( (void*)0x1234 == node->contents ); + CHECK( &node1 != node->next ); + CHECK( node != list.head ); + CHECK( node == list.tail ); + } + + //------------------------------------------------------------------------- + // Test list_pop_front function + //------------------------------------------------------------------------- + TEST(Verify_pop_front_returns_null_if_list_is_empty) + { + list_t list = { NULL, NULL }; + CHECK( NULL == list_pop_front( &list ) ); + } + + TEST(Verify_pop_front_removes_a_node_from_the_front_of_a_list_of_length_1) + { + list_node_t node1 = { NULL, NULL }; + list_t list = { &node1, &node1 }; + CHECK( &node1 == list_pop_front( &list ) ); + CHECK( NULL == list.head ); + CHECK( NULL == list.tail ); + } + + TEST(Verify_pop_front_removes_a_node_from_the_front_of_a_list_of_length_2) + { + list_node_t node2 = { NULL, NULL }; + list_node_t node1 = { NULL, &node2 }; + list_t list = { &node1, &node2 }; + CHECK( &node1 == list_pop_front( &list ) ); + CHECK( &node2 == list.head ); + CHECK( &node2 == list.tail ); + } + + TEST(Verify_pop_front_removes_a_node_from_the_front_of_a_list_of_length_3) + { + list_node_t node3 = { NULL, NULL }; + list_node_t node2 = { NULL, &node3 }; + list_node_t node1 = { NULL, &node2 }; + list_t list = { &node1, &node3 }; + CHECK( &node1 == list_pop_front( &list ) ); + CHECK( &node2 == list.head ); + CHECK( &node3 == list.tail ); + } + + //------------------------------------------------------------------------- + // Test list_pop_back function + //------------------------------------------------------------------------- + TEST(Verify_pop_back_does_nothing_if_list_is_empty) + { + list_t list = { NULL, NULL }; + CHECK( NULL == list_pop_back( &list ) ); + } + + TEST(Verify_pop_back_removes_a_node_from_the_back_of_a_list_of_length_1) + { + list_node_t node1 = { NULL, NULL }; + list_t list = { &node1, &node1 }; + CHECK( &node1 == list_pop_back( &list ) ); + CHECK( NULL == list.head ); + CHECK( NULL == list.tail ); + } + + TEST(Verify_pop_back_removes_a_node_from_the_back_of_a_list_of_length_2) + { + list_node_t node2 = { NULL, NULL }; + list_node_t node1 = { NULL, &node2 }; + list_t list = { &node1, &node2 }; + CHECK( &node2 == list_pop_back( &list ) ); + CHECK( &node1 == list.head ); + CHECK( &node1 == list.tail ); + } + + TEST(Verify_pop_back_removes_a_node_from_the_back_of_a_list_of_length_3) + { + list_node_t node3 = { NULL, NULL }; + list_node_t node2 = { NULL, &node3 }; + list_node_t node1 = { NULL, &node2 }; + list_t list = { &node1, &node3 }; + CHECK( &node3 == list_pop_back( &list ) ); + CHECK( &node1 == list.head ); + CHECK( &node2 == list.tail ); + } + + //------------------------------------------------------------------------- + // Test list_insert function + //------------------------------------------------------------------------- + TEST(Verify_insert_should_insert_into_empty_list) + { + list_t list = { NULL, NULL }; + list_node_t* node = list_insert( &list, 0, (void*)0x1234 ); + CHECK( node != NULL ); + CHECK( node->next == NULL ); + CHECK( node->contents == (void*)0x1234 ); + CHECK( list.head == node ); + CHECK( list.tail == node ); + } + + TEST(Verify_insert_should_push_to_the_front_of_the_list_if_index_is_0) + { + list_node_t node1 = { NULL, NULL }; + list_t list = { &node1, &node1 }; + list_node_t* node = list_insert( &list, 0, (void*)0x1234 ); + CHECK( NULL != node ); + CHECK( (void*)0x1234 == node->contents ); + CHECK( NULL != node->next ); + CHECK( node == list.head ); + CHECK( node != list.tail ); + } + + TEST(Verify_insert_should_insert_at_the_given_index_if_index_is_non_zero) + { + list_node_t node3 = { NULL, NULL }; + list_node_t node2 = { NULL, &node3 }; + list_node_t node1 = { NULL, &node2 }; + list_t list = { &node1, &node3 }; + list_node_t* node = list_insert( &list, 1, (void*)0x1234 ); + CHECK( NULL != node ); + CHECK( (void*)0x1234 == node->contents ); + CHECK( node1.next == node ); + CHECK( &node2 == node->next ); + } + + TEST(Verify_insert_should_set_the_tail_of_the_list_if_index_is_the_last_item) + { + list_node_t node2 = { NULL, NULL }; + list_node_t node1 = { NULL, &node2 }; + list_t list = { &node1, &node2 }; + list_node_t* node = list_insert( &list, 2, (void*)0x1234 ); + CHECK( NULL != node ); + CHECK( (void*)0x1234 == node->contents ); + CHECK( NULL == node->next ); + CHECK( node2.next == node ); + CHECK( list.tail == node ); + } + + TEST(Verify_insert_should_return_null_if_index_out_of_range) + { + list_node_t node2 = { NULL, NULL }; + list_node_t node1 = { NULL, &node2 }; + list_t list = { &node1, &node2 }; + list_node_t* node = list_insert( &list, 3, (void*)0x1234 ); + CHECK( NULL == node ); + } + + //------------------------------------------------------------------------- + // Test list_delete function + //------------------------------------------------------------------------- + TEST(Verify_delete_does_nothing_if_list_is_empty) + { + list_t list = { NULL, NULL }; + CHECK( NULL == list_delete( &list, 0, 0 ) ); + } + + TEST(Verify_delete_deletes_the_first_element_of_a_list_of_length_1) + { + list_node_t* node = list_new_node((void*)0x1234); + list_t list = { node, node }; + CHECK( NULL == list_delete( &list, 0, 0 ) ); + CHECK( list.head == NULL ); + CHECK( list.tail == NULL ); + } + + TEST(Verify_delete_deletes_the_first_element_of_a_list_of_length_2) + { + list_node_t* node1 = list_new_node((void*)0x1234); + list_node_t node2 = { (void*)0x1234, NULL }; + node1->next = &node2; + list_t list = { node1, &node2 }; + list_node_t* node = list_delete( &list, 0, 0 ); + CHECK( node == &node2 ); + CHECK( list.head == &node2 ); + CHECK( list.tail == &node2 ); + } + + TEST(Verify_delete_deletes_element_1_of_a_list_of_length_3) + { + list_node_t node1 = { (void*)0x1234, NULL }; + list_node_t* node2 = list_new_node((void*)0x1234); + list_node_t node3 = { (void*)0x1234, NULL }; + node1.next = node2; + node2->next = &node3; + list_t list = { &node1, &node3 }; + list_node_t* node = list_delete( &list, 1, 0 ); + CHECK( node == &node3 ); + CHECK( node1.next == &node3 ); + CHECK( list.head == &node1 ); + CHECK( list.tail == &node3 ); + } + + TEST(Verify_delete_deletes_element_1_of_a_list_of_length_2) + { + list_node_t node1 = { (void*)0x1234, NULL }; + list_node_t* node2 = list_new_node((void*)0x1234); + node1.next = node2; + list_t list = { &node1, node2 }; + list_node_t* node = list_delete( &list, 1, 0 ); + CHECK( node == NULL ); + CHECK( list.head == &node1 ); + CHECK( list.tail == &node1 ); + } + + //------------------------------------------------------------------------- + // Test list_clear function + //------------------------------------------------------------------------- + TEST(Verify_list_clear_does_nothing_for_an_empty_list) + { + list_t* list = list_new(); + CHECK( list == list_clear(list,0) ); + CHECK( NULL == list->head ); + CHECK( NULL == list->tail ); + list_free(list,0); + } + + TEST(Verify_list_clear_clears_a_list_of_length_1) + { + list_t* list = list_new(); + (void)list_push_front(list,(void*)0x1234); + CHECK( list == list_clear(list,0) ); + CHECK( NULL == list->head ); + CHECK( NULL == list->tail ); + list_free(list,0); + } + + TEST(Verify_list_clear_clears_a_list_of_length_2) + { + list_t* list = list_new(); + (void)list_push_front(list,(void*)0x1234); + (void)list_push_front(list,(void*)0x1234); + CHECK( list == list_clear(list,0) ); + CHECK( NULL == list->head ); + CHECK( NULL == list->tail ); + list_free(list,0); + } + + TEST(Verify_list_clear_clears_a_list_of_length_3) + { + list_t* list = list_new(); + (void)list_push_front(list,(void*)0x1234); + (void)list_push_front(list,(void*)0x1234); + (void)list_push_front(list,(void*)0x1234); + CHECK( list == list_clear(list,0) ); + CHECK( NULL == list->head ); + CHECK( NULL == list->tail ); + list_free(list,0); + } +} diff --git a/tests/test_sll.cpp b/tests/test_sll.cpp deleted file mode 100644 index a1bce50..0000000 --- a/tests/test_sll.cpp +++ /dev/null @@ -1,500 +0,0 @@ -// Unit Test Framework Includes -#include "UnitTest++.h" -#include - -// File To Test -#include "sll.h" - -using namespace UnitTest; - -//----------------------------------------------------------------------------- -// Begin Unit Tests -//----------------------------------------------------------------------------- -namespace { - //------------------------------------------------------------------------- - // Test sll_new function - //------------------------------------------------------------------------- - TEST(Verify_sll_new_returns_newly_allocated_empty_list) - { - sll_t* list = sll_new(); - CHECK( NULL != list ); - CHECK( NULL == list->head ); - CHECK( NULL == list->tail ); - free( list ); - } - - //------------------------------------------------------------------------- - // Test sll_new_node function - //------------------------------------------------------------------------- - TEST(Verify_sll_new_node_returns_newly_allocated_node_with_given_contents) - { - int stuff = 0; - sll_node_t* node = sll_new_node( &stuff ); - CHECK( NULL != node ); - CHECK( &stuff == node->contents ); - CHECK( NULL == node->next ); - free( node ); - } - - //------------------------------------------------------------------------- - // Test sll_free function - //------------------------------------------------------------------------- - TEST(Verify_sll_free_frees_the_given_empty_list) - { - sll_t* list = sll_new(); - sll_free( list, 0 ); - } - - TEST(Verify_sll_free_frees_the_given_list_including_nodes) - { - sll_t* list = sll_new(); - list->head = sll_new_node(NULL); - list->tail = list->head; - sll_free( list, 0 ); - } - - TEST(Verify_sll_free_frees_the_given_list_including_nodes_and_node_contents) - { - sll_t* list = sll_new(); - int* foo = (int*)malloc( sizeof(int) ); - list->head = sll_new_node( foo ); - list->tail = list->head; - sll_free( list, 1 ); - } - - //------------------------------------------------------------------------- - // Test sll_free_node function - //------------------------------------------------------------------------- - TEST(Verify_sll_free_node_frees_the_given_node) - { - sll_node_t* node = sll_new_node( NULL ); - sll_free_node( node, 0 ); - } - - TEST(Verify_sll_free_node_frees_the_given_node_and_contents) - { - int* foo = (int*)malloc( sizeof(int) ); - sll_node_t* node = sll_new_node( foo ); - sll_free_node( node, 1 ); - } - - //------------------------------------------------------------------------- - // Test sll_front function - //------------------------------------------------------------------------- - TEST(Verify_sll_front_returns_NULL_if_list_is_empty) - { - sll_t list = { NULL, NULL }; - CHECK( NULL == sll_front( &list ) ); - } - - TEST(Verify_sll_front_returns_the_head_of_the_list) - { - sll_node_t node2 = { NULL, NULL }; - sll_node_t node1 = { NULL, &node2 }; - sll_t list = { &node1, &node2 }; - CHECK( &node1 == sll_front( &list ) ); - } - - //------------------------------------------------------------------------- - // Test sll_back function - //------------------------------------------------------------------------- - TEST(Verify_sll_back_returns_NULL_if_list_is_empty) - { - sll_t list = { NULL, NULL }; - CHECK( NULL == sll_back( &list ) ); - } - - TEST(Verify_sll_back_returns_the_tail_of_the_list) - { - sll_node_t node2 = { NULL, NULL }; - sll_node_t node1 = { NULL, &node2 }; - sll_t list = { &node1, &node2 }; - CHECK( &node2 == sll_back( &list ) ); - } - - //------------------------------------------------------------------------- - // Test sll_size function - //------------------------------------------------------------------------- - TEST(Verify_sll_size_returns_0_when_list_is_empty) - { - sll_t* list = sll_new(); - CHECK( 0 == sll_size( list ) ); - free( list ); - } - - TEST(Verify_sll_size_returns_1_when_list_is_length_1) - { - sll_node_t node1 = { NULL, NULL }; - sll_t list = { &node1, &node1 }; - - CHECK( 1 == sll_size( &list ) ); - } - - TEST(Verify_sll_size_returns_2_when_list_is_length_2) - { - sll_node_t node2 = { NULL, NULL }; - sll_node_t node1 = { NULL, &node2 }; - sll_t list = { &node1, &node2 }; - - CHECK( 2 == sll_size( &list ) ); - } - - //------------------------------------------------------------------------- - // Test sll_empty function - //------------------------------------------------------------------------- - TEST(Verify_sll_empty_returns_true_when_head_and_tail_are_null) - { - sll_t list = { NULL, NULL }; - CHECK( 1 == sll_empty( &list ) ); - } - - TEST(Verify_sll_empty_returns_false_when_head_is_not_null) - { - sll_t list = { (sll_node_t*)0x1234, NULL }; - CHECK( 0 == sll_empty( &list ) ); - } - - TEST(Verify_sll_empty_returns_false_when_tail_is_not_null) - { - sll_t list = { NULL, (sll_node_t*)0x1234 }; - CHECK( 0 == sll_empty( &list ) ); - } - - //------------------------------------------------------------------------- - // Test sll_at function - //------------------------------------------------------------------------- - TEST(Verify_sll_at_returns_NULL_when_list_is_empty) - { - sll_t list = { NULL, NULL }; - CHECK( NULL == sll_at( &list, 0 ) ); - } - - TEST(Verify_sll_at_returns_NULL_when_index_out_of_range) - { - sll_node_t node3 = { NULL, NULL }; - sll_node_t node2 = { NULL, &node3 }; - sll_node_t node1 = { NULL, &node2 }; - sll_t list = { &node1, &node3 }; - CHECK( NULL == sll_at( &list, 3 ) ); - } - - TEST(Verify_sll_at_returns_node_at_index_0_of_3_element_list) - { - sll_node_t node3 = { NULL, NULL }; - sll_node_t node2 = { NULL, &node3 }; - sll_node_t node1 = { NULL, &node2 }; - sll_t list = { &node1, &node3 }; - CHECK( &node1 == sll_at( &list, 0 ) ); - } - - TEST(Verify_sll_at_returns_node_at_index_1_of_3_element_list) - { - sll_node_t node3 = { NULL, NULL }; - sll_node_t node2 = { NULL, &node3 }; - sll_node_t node1 = { NULL, &node2 }; - sll_t list = { &node1, &node3 }; - CHECK( &node2 == sll_at( &list, 1 ) ); - } - - TEST(Verify_sll_at_returns_node_at_index_2_of_3_element_list) - { - sll_node_t node3 = { NULL, NULL }; - sll_node_t node2 = { NULL, &node3 }; - sll_node_t node1 = { NULL, &node2 }; - sll_t list = { &node1, &node3 }; - CHECK( &node3 == sll_at( &list, 2 ) ); - } - - //------------------------------------------------------------------------- - // Test sll_push_front function - //------------------------------------------------------------------------- - TEST(Verify_sll_push_front_pushes_to_empty_list) - { - sll_t list = { NULL, NULL }; - sll_node_t* node = sll_push_front( &list, (void*)0x1234 ); - CHECK( NULL != node ); - CHECK( (void*)0x1234 == node->contents ); - CHECK( NULL == node->next ); - CHECK( node == list.head ); - CHECK( node == list.tail ); - } - - TEST(Verify_sll_push_front_pushes_to_front_of_list_of_length_1) - { - sll_node_t node1 = { NULL, NULL }; - sll_t list = { &node1, &node1 }; - sll_node_t* node = sll_push_front( &list, (void*)0x1234 ); - CHECK( NULL != node ); - CHECK( (void*)0x1234 == node->contents ); - CHECK( NULL != node->next ); - CHECK( node == list.head ); - CHECK( node != list.tail ); - } - - //------------------------------------------------------------------------- - // Test sll_push_back function - //------------------------------------------------------------------------- - TEST(Verify_sll_push_back_pushes_to_empty_list) - { - sll_t list = { NULL, NULL }; - sll_node_t* node = sll_push_back( &list, (void*)0x1234 ); - CHECK( NULL != node ); - CHECK( (void*)0x1234 == node->contents ); - CHECK( NULL == node->next ); - CHECK( node == list.head ); - CHECK( node == list.tail ); - } - - TEST(Verify_sll_push_back_pushes_to_back_of_list_of_length_1) - { - sll_node_t node1 = { NULL, NULL }; - sll_t list = { &node1, &node1 }; - sll_node_t* node = sll_push_back( &list, (void*)0x1234 ); - CHECK( NULL != node ); - CHECK( (void*)0x1234 == node->contents ); - CHECK( &node1 != node->next ); - CHECK( node != list.head ); - CHECK( node == list.tail ); - } - - //------------------------------------------------------------------------- - // Test sll_pop_front function - //------------------------------------------------------------------------- - TEST(Verify_pop_front_returns_null_if_list_is_empty) - { - sll_t list = { NULL, NULL }; - CHECK( NULL == sll_pop_front( &list ) ); - } - - TEST(Verify_pop_front_removes_a_node_from_the_front_of_a_list_of_length_1) - { - sll_node_t node1 = { NULL, NULL }; - sll_t list = { &node1, &node1 }; - CHECK( &node1 == sll_pop_front( &list ) ); - CHECK( NULL == list.head ); - CHECK( NULL == list.tail ); - } - - TEST(Verify_pop_front_removes_a_node_from_the_front_of_a_list_of_length_2) - { - sll_node_t node2 = { NULL, NULL }; - sll_node_t node1 = { NULL, &node2 }; - sll_t list = { &node1, &node2 }; - CHECK( &node1 == sll_pop_front( &list ) ); - CHECK( &node2 == list.head ); - CHECK( &node2 == list.tail ); - } - - TEST(Verify_pop_front_removes_a_node_from_the_front_of_a_list_of_length_3) - { - sll_node_t node3 = { NULL, NULL }; - sll_node_t node2 = { NULL, &node3 }; - sll_node_t node1 = { NULL, &node2 }; - sll_t list = { &node1, &node3 }; - CHECK( &node1 == sll_pop_front( &list ) ); - CHECK( &node2 == list.head ); - CHECK( &node3 == list.tail ); - } - - //------------------------------------------------------------------------- - // Test sll_pop_back function - //------------------------------------------------------------------------- - TEST(Verify_pop_back_does_nothing_if_list_is_empty) - { - sll_t list = { NULL, NULL }; - CHECK( NULL == sll_pop_back( &list ) ); - } - - TEST(Verify_pop_back_removes_a_node_from_the_back_of_a_list_of_length_1) - { - sll_node_t node1 = { NULL, NULL }; - sll_t list = { &node1, &node1 }; - CHECK( &node1 == sll_pop_back( &list ) ); - CHECK( NULL == list.head ); - CHECK( NULL == list.tail ); - } - - TEST(Verify_pop_back_removes_a_node_from_the_back_of_a_list_of_length_2) - { - sll_node_t node2 = { NULL, NULL }; - sll_node_t node1 = { NULL, &node2 }; - sll_t list = { &node1, &node2 }; - CHECK( &node2 == sll_pop_back( &list ) ); - CHECK( &node1 == list.head ); - CHECK( &node1 == list.tail ); - } - - TEST(Verify_pop_back_removes_a_node_from_the_back_of_a_list_of_length_3) - { - sll_node_t node3 = { NULL, NULL }; - sll_node_t node2 = { NULL, &node3 }; - sll_node_t node1 = { NULL, &node2 }; - sll_t list = { &node1, &node3 }; - CHECK( &node3 == sll_pop_back( &list ) ); - CHECK( &node1 == list.head ); - CHECK( &node2 == list.tail ); - } - - //------------------------------------------------------------------------- - // Test sll_insert function - //------------------------------------------------------------------------- - TEST(Verify_insert_should_insert_into_empty_list) - { - sll_t list = { NULL, NULL }; - sll_node_t* node = sll_insert( &list, 0, (void*)0x1234 ); - CHECK( node != NULL ); - CHECK( node->next == NULL ); - CHECK( node->contents == (void*)0x1234 ); - CHECK( list.head == node ); - CHECK( list.tail == node ); - } - - TEST(Verify_insert_should_push_to_the_front_of_the_list_if_index_is_0) - { - sll_node_t node1 = { NULL, NULL }; - sll_t list = { &node1, &node1 }; - sll_node_t* node = sll_insert( &list, 0, (void*)0x1234 ); - CHECK( NULL != node ); - CHECK( (void*)0x1234 == node->contents ); - CHECK( NULL != node->next ); - CHECK( node == list.head ); - CHECK( node != list.tail ); - } - - TEST(Verify_insert_should_insert_at_the_given_index_if_index_is_non_zero) - { - sll_node_t node3 = { NULL, NULL }; - sll_node_t node2 = { NULL, &node3 }; - sll_node_t node1 = { NULL, &node2 }; - sll_t list = { &node1, &node3 }; - sll_node_t* node = sll_insert( &list, 1, (void*)0x1234 ); - CHECK( NULL != node ); - CHECK( (void*)0x1234 == node->contents ); - CHECK( node1.next == node ); - CHECK( &node2 == node->next ); - } - - TEST(Verify_insert_should_set_the_tail_of_the_list_if_index_is_the_last_item) - { - sll_node_t node2 = { NULL, NULL }; - sll_node_t node1 = { NULL, &node2 }; - sll_t list = { &node1, &node2 }; - sll_node_t* node = sll_insert( &list, 2, (void*)0x1234 ); - CHECK( NULL != node ); - CHECK( (void*)0x1234 == node->contents ); - CHECK( NULL == node->next ); - CHECK( node2.next == node ); - CHECK( list.tail == node ); - } - - TEST(Verify_insert_should_return_null_if_index_out_of_range) - { - sll_node_t node2 = { NULL, NULL }; - sll_node_t node1 = { NULL, &node2 }; - sll_t list = { &node1, &node2 }; - sll_node_t* node = sll_insert( &list, 3, (void*)0x1234 ); - CHECK( NULL == node ); - } - - //------------------------------------------------------------------------- - // Test sll_delete function - //------------------------------------------------------------------------- - TEST(Verify_delete_does_nothing_if_list_is_empty) - { - sll_t list = { NULL, NULL }; - CHECK( NULL == sll_delete( &list, 0, 0 ) ); - } - - TEST(Verify_delete_deletes_the_first_element_of_a_list_of_length_1) - { - sll_node_t* node = sll_new_node((void*)0x1234); - sll_t list = { node, node }; - CHECK( NULL == sll_delete( &list, 0, 0 ) ); - CHECK( list.head == NULL ); - CHECK( list.tail == NULL ); - } - - TEST(Verify_delete_deletes_the_first_element_of_a_list_of_length_2) - { - sll_node_t* node1 = sll_new_node((void*)0x1234); - sll_node_t node2 = { (void*)0x1234, NULL }; - node1->next = &node2; - sll_t list = { node1, &node2 }; - sll_node_t* node = sll_delete( &list, 0, 0 ); - CHECK( node == &node2 ); - CHECK( list.head == &node2 ); - CHECK( list.tail == &node2 ); - } - - TEST(Verify_delete_deletes_element_1_of_a_list_of_length_3) - { - sll_node_t node1 = { (void*)0x1234, NULL }; - sll_node_t* node2 = sll_new_node((void*)0x1234); - sll_node_t node3 = { (void*)0x1234, NULL }; - node1.next = node2; - node2->next = &node3; - sll_t list = { &node1, &node3 }; - sll_node_t* node = sll_delete( &list, 1, 0 ); - CHECK( node == &node3 ); - CHECK( node1.next == &node3 ); - CHECK( list.head == &node1 ); - CHECK( list.tail == &node3 ); - } - - TEST(Verify_delete_deletes_element_1_of_a_list_of_length_2) - { - sll_node_t node1 = { (void*)0x1234, NULL }; - sll_node_t* node2 = sll_new_node((void*)0x1234); - node1.next = node2; - sll_t list = { &node1, node2 }; - sll_node_t* node = sll_delete( &list, 1, 0 ); - CHECK( node == NULL ); - CHECK( list.head == &node1 ); - CHECK( list.tail == &node1 ); - } - - //------------------------------------------------------------------------- - // Test sll_clear function - //------------------------------------------------------------------------- - TEST(Verify_sll_clear_does_nothing_for_an_empty_list) - { - sll_t* list = sll_new(); - CHECK( list == sll_clear(list,0) ); - CHECK( NULL == list->head ); - CHECK( NULL == list->tail ); - sll_free(list,0); - } - - TEST(Verify_sll_clear_clears_a_list_of_length_1) - { - sll_t* list = sll_new(); - (void)sll_push_front(list,(void*)0x1234); - CHECK( list == sll_clear(list,0) ); - CHECK( NULL == list->head ); - CHECK( NULL == list->tail ); - sll_free(list,0); - } - - TEST(Verify_sll_clear_clears_a_list_of_length_2) - { - sll_t* list = sll_new(); - (void)sll_push_front(list,(void*)0x1234); - (void)sll_push_front(list,(void*)0x1234); - CHECK( list == sll_clear(list,0) ); - CHECK( NULL == list->head ); - CHECK( NULL == list->tail ); - sll_free(list,0); - } - - TEST(Verify_sll_clear_clears_a_list_of_length_3) - { - sll_t* list = sll_new(); - (void)sll_push_front(list,(void*)0x1234); - (void)sll_push_front(list,(void*)0x1234); - (void)sll_push_front(list,(void*)0x1234); - CHECK( list == sll_clear(list,0) ); - CHECK( NULL == list->head ); - CHECK( NULL == list->tail ); - sll_free(list,0); - } -} -- 2.52.0