From 5facd714e8f19e68ad94233db3796572e1612946 Mon Sep 17 00:00:00 2001 From: "Mike D. Lowis" Date: Sun, 9 Dec 2012 15:48:37 -0500 Subject: [PATCH] added clear and empty functions and renamed functions to reflect conventions used by the C++ STL --- source/list/sll.c | 32 ++++++++++-- source/list/sll.h | 23 ++++++++- tests/test_sll.cpp | 120 ++++++++++++++++++++++++++++++++++++--------- 3 files changed, 147 insertions(+), 28 deletions(-) diff --git a/source/list/sll.c b/source/list/sll.c index fa2a8de..02abc54 100644 --- a/source/list/sll.c +++ b/source/list/sll.c @@ -64,7 +64,7 @@ sll_node_t* sll_back( sll_t* list ) return node; } -unsigned int sll_length(sll_t* list) +unsigned int sll_size(sll_t* list) { unsigned int length = 0; if( NULL != list) @@ -79,7 +79,13 @@ unsigned int sll_length(sll_t* list) return length; } -sll_node_t* sll_index(sll_t* list, unsigned int index) +int sll_empty(sll_t* list) +{ + return ((NULL == list) || ((NULL == list->head) && (NULL == list->tail))); +} + + +sll_node_t* sll_at(sll_t* list, unsigned int index) { sll_node_t* node = NULL; if( NULL != list ) @@ -187,7 +193,7 @@ sll_node_t* sll_insert( sll_t* list, unsigned int index, void* contents) } else { - sll_node_t* prev_node = sll_index( list, index - 1 ); + sll_node_t* prev_node = sll_at( list, index - 1 ); if( NULL != prev_node ) { sll_node_t* next_node = prev_node->next; @@ -218,7 +224,7 @@ sll_node_t* sll_delete( sll_t* list, unsigned int index, int free_contents) } else { - sll_node_t* prev = sll_index(list,index-1); + sll_node_t* prev = sll_at(list,index-1); node = (NULL == prev) ? NULL : prev->next; if (NULL != node) { @@ -235,3 +241,21 @@ sll_node_t* sll_delete( sll_t* list, unsigned int index, int free_contents) return node; } +sll_t* sll_clear(sll_t* list, int free_contents) +{ + if(NULL != list) + { + sll_node_t* node = list->head; + while(NULL != node) + { + sll_node_t* next = node->next; + sll_free_node(node,free_contents); + node = next; + } + list->head = NULL; + list->tail = NULL; + } + return list; +} + + diff --git a/source/list/sll.h b/source/list/sll.h index 5bf95f8..9e0e3fb 100644 --- a/source/list/sll.h +++ b/source/list/sll.h @@ -89,7 +89,16 @@ sll_node_t* sll_back( sll_t* list ); * * @return The number of elements in the list. **/ -unsigned int sll_length(sll_t* list); +unsigned int sll_size(sll_t* list); + +/** + * @brief Returns whether the list is empty or not. + * + * @param list The list to operate on. + * + * @return Whether the list is empty, 1 for true and 0 for false. + */ +int sll_empty(sll_t* list); /** * @brief Return the node at the specified index in a linked list. @@ -102,7 +111,7 @@ unsigned int sll_length(sll_t* list); * * @return A pointer to the node at the supplied index, NULL if out of range. **/ -sll_node_t* sll_index(sll_t* list, unsigned int index); +sll_node_t* sll_at(sll_t* list, unsigned int index); /** * @brief Adds a new node to the front of an existing linked list. @@ -185,6 +194,16 @@ sll_node_t* sll_insert( sll_t* list, unsigned int index, void* contents); **/ sll_node_t* sll_delete( sll_t* list, unsigned int index, int free_contents); +/** + * @brief Deletes all elements in the provided list + * + * @param list The list to be cleared + * @param free_contents Whether or not to also free the contents of every node. + * + * @return A pointer to the cleared list. + */ +sll_t* sll_clear(sll_t* list, int free_contents); + #ifdef __cplusplus } #endif diff --git a/tests/test_sll.cpp b/tests/test_sll.cpp index c9d9c65..a776a5e 100644 --- a/tests/test_sll.cpp +++ b/tests/test_sll.cpp @@ -133,85 +133,111 @@ namespace { } //------------------------------------------------------------------------- - // Test sll_length function + // Test sll_size function //------------------------------------------------------------------------- - TEST(Verify_sll_length_returns_0_when_passed_null_pointer) + TEST(Verify_sll_size_returns_0_when_passed_null_pointer) { - CHECK( 0 == sll_length(NULL) ); + CHECK( 0 == sll_size(NULL) ); } - TEST(Verify_sll_length_returns_0_when_list_is_empty) + TEST(Verify_sll_size_returns_0_when_list_is_empty) { sll_t* list = sll_new(); - CHECK( 0 == sll_length( list ) ); + CHECK( 0 == sll_size( list ) ); free( list ); } - TEST(Verify_sll_length_returns_1_when_list_is_length_1) + 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_length( &list ) ); + CHECK( 1 == sll_size( &list ) ); } - TEST(Verify_sll_length_returns_2_when_list_is_length_2) + 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_length( &list ) ); + CHECK( 2 == sll_size( &list ) ); } //------------------------------------------------------------------------- - // Test sll_index function + // Test sll_empty function //------------------------------------------------------------------------- - TEST(Verify_sll_index_returns_NULL_on_null_pointer) + TEST(Verify_sll_empty_returns_true_when_passed_null_pointer) { - CHECK( NULL == sll_index( NULL, 0 ) ); + CHECK( 1 == sll_empty( NULL ) ); } - TEST(Verify_sll_index_returns_NULL_when_list_is_empty) + TEST(Verify_sll_empty_returns_true_when_head_and_tail_are_null) { sll_t list = { NULL, NULL }; - CHECK( NULL == sll_index( &list, 0 ) ); + CHECK( 1 == sll_empty( &list ) ); } - TEST(Verify_sll_index_returns_NULL_when_index_out_of_range) + 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_on_null_pointer) + { + CHECK( NULL == sll_at( NULL, 0 ) ); + } + + 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_index( &list, 3 ) ); + CHECK( NULL == sll_at( &list, 3 ) ); } - TEST(Verify_sll_index_returns_node_at_index_0_of_3_element_list) + 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_index( &list, 0 ) ); + CHECK( &node1 == sll_at( &list, 0 ) ); } - TEST(Verify_sll_index_returns_node_at_index_1_of_3_element_list) + 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_index( &list, 1 ) ); + CHECK( &node2 == sll_at( &list, 1 ) ); } - TEST(Verify_sll_index_returns_node_at_index_2_of_3_element_list) + 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_index( &list, 2 ) ); + CHECK( &node3 == sll_at( &list, 2 ) ); } //------------------------------------------------------------------------- @@ -491,4 +517,54 @@ namespace { CHECK( list.head == &node1 ); CHECK( list.tail == &node1 ); } + + //------------------------------------------------------------------------- + // Test sll_clear function + //------------------------------------------------------------------------- + TEST(Verify_sll_clear_does_nothing_if_passed_a_NULL_pointer) + { + CHECK( NULL == sll_clear(NULL,0) ); + } + + 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