From 1398912683a19b653dbf5d044d5e48ab8cfaa96f Mon Sep 17 00:00:00 2001 From: "Mike D. Lowis" Date: Mon, 4 Jun 2012 16:23:47 -0400 Subject: [PATCH] Started rewrite of linked list with more efficient design --- source/lists/single_link/sll.c | 164 +++++++++++++----------------- source/lists/single_link/sll.h | 132 ++++++++++--------------- tests/test_sll.cpp | 176 ++++++++++++++++++++++++++++++++- 3 files changed, 294 insertions(+), 178 deletions(-) diff --git a/source/lists/single_link/sll.c b/source/lists/single_link/sll.c index 1a9b072..8c10e7e 100644 --- a/source/lists/single_link/sll.c +++ b/source/lists/single_link/sll.c @@ -1,144 +1,112 @@ -/****************************************************************************** - * Copyright (c) 2012, Michael D. Lowis - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * * Redistributions of source code must retain the above copyright notice, - * this list of conditions and the following disclaimer. - * - * * Redistributions in binary form must reproduce the above copyright notice, - * this list of conditions and the following disclaimer in the documentation - * and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - * POSSIBILITY OF SUCH DAMAGE. - *****************************************************************************/ #include "sll.h" #include -sll_node* sll_new( void* contents ) +sll_t* sll_new(void) { - sll_node* list = (sll_node*)malloc( sizeof(sll_node) ); - list->contents = contents; - list->next = NULL; + sll_t* list = (sll_t*)malloc( sizeof( sll_t ) ); + list->head = NULL; + list->tail = NULL; return list; } -sll_node* sll_front( sll_node* list ) +sll_node_t* sll_new_node(void* contents) { + sll_node_t* node = (sll_node_t*)malloc( sizeof( sll_node_t ) ); + node->contents = contents; + node->next = NULL; + return node; } -sll_node* sll_back( sll_node* list ) +void sll_free(sll_t* list, int free_contents) { - sll_node* node = list; - while((node != NULL) && (node->next != NULL)) + if( NULL != list ) { - node = node->next; + sll_node_t* node = list->head; + while( NULL != node ) + { + sll_node_t* next = node->next; + sll_free_node( node, free_contents ); + node = next; + } + free( list ); } - return node; } -sll_node* sll_index( sll_node* list, int index ) +void sll_free_node(sll_node_t* node, int free_contents) { - int current = 0; - sll_node* node = list; - sll_node* indexed_node = NULL; - while ((node != NULL)) + if( NULL != node ) { - if ( current == index ) + if( 1 == free_contents ) { - indexed_node = node; - break; + free( node->contents ); } - node = node->next; - current++; + free( node ); } - return indexed_node; } -sll_node* sll_push_back( sll_node* list, void* contents ) +unsigned int sll_length(sll_t* list) { - sll_node* node = sll_back( list ); - node->next = sll_new( contents ); + unsigned int length = 0; + if( NULL != list) + { + sll_node_t* node = list->head; + while( NULL != node ) + { + node = node->next; + length++; + } + } + return length; } -sll_node* sll_push_front( sll_node* list, void* contents ) +sll_node_t* sll_index(sll_t* list, unsigned int index) { + sll_node_t* node = NULL; + if( NULL != list ) + { + unsigned int cur_index = 0; + sll_node_t* cur_node = list->head; + while( NULL != cur_node ) + { + if( cur_index == index ) + { + node = cur_node; + break; + } + cur_node = cur_node->next; + cur_index++; + } + } + return node; } -sll_node* sll_pop_back( sll_node* list ) +sll_node_t* sll_push_front( sll_t* list, void* contents ) { + return 0; } -sll_node* sll_pop_front( sll_node* list ) +sll_node_t* sll_push_back( sll_t* list, void* contents ) { + return 0; } -sll_node* sll_insert( sll_node* list, int index, void* contents ) +sll_node_t* sll_pop_front( sll_t* list, int free_contents ) { - int req_index = ((index-1) < 0) ? 0 : index-1; - sll_node* node = sll_index( list, req_index ); - if(node != NULL) - { - sll_node* next_next = node->next; - node->next = sll_new( contents ); - node->next->next = next_next; - node = node->next; - } - return node; + return 0; } -sll_node* sll_delete( sll_node* list, int index, int free_contents) +sll_node_t* sll_pop_back( sll_t* list, int free_contents ) { - sll_node* node = sll_index( list, (index-1)); - if((node != NULL) && (node->next != NULL)) - { - sll_node* node_to_delete = node->next; - node->next = node_to_delete->next; - if (free_contents) - { - free(node_to_delete->contents); - } - free(node_to_delete); - node = node->next; - } - return node; + return 0; } -void sll_free( sll_node* list, int free_contents) +sll_node_t* sll_insert( sll_t* list, unsigned int index, void* contents) { - sll_node* node = list; - while( node != NULL ) - { - sll_node* next = node->next; - if (free_contents) - { - free(node->contents); - } - free(node); - node = next; - } + return 0; } -unsigned int sll_length(sll_node* list) +sll_node_t* sll_delete( sll_t* list, unsigned int index, int free_contents) { - unsigned int length = 0; - sll_node* item = list; - for ( item = list; item != NULL; item = item->next ) - { - length++; - } - return length; + return 0; } diff --git a/source/lists/single_link/sll.h b/source/lists/single_link/sll.h index e29d71b..a16b954 100644 --- a/source/lists/single_link/sll.h +++ b/source/lists/single_link/sll.h @@ -1,74 +1,73 @@ -/****************************************************************************** - * Copyright (c) 2012, Michael D. Lowis - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * * Redistributions of source code must retain the above copyright notice, - * this list of conditions and the following disclaimer. - * - * * Redistributions in binary form must reproduce the above copyright notice, - * this list of conditions and the following disclaimer in the documentation - * and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" - * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS - * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE - * POSSIBILITY OF SUCH DAMAGE. - *****************************************************************************/ #ifndef SLL_H #define SLL_H //! A linked list node. -typedef struct sll_node +typedef struct sll_node_t { //! Pointer to the contents the node void* contents; //! Pointer to next node in the list. - struct sll_node* next; -} sll_node; + struct sll_node_t* next; +} sll_node_t; + +//! A singly linked list +typedef struct sll_t +{ + //! Pointer to the first element in the list + sll_node_t* head; + //! Pointer to the last element in the list + sll_node_t* tail; +} sll_t; /** - * @brief Creates a new linked list node with the supplied value. - * - * This function allocates a new node and populates the node contents with the - * supplied contents pointer. + * @brief Creates a new empty linked list. * - * @param contents The contents of the newly created node. - * - * @return A pointer to the newly created node. + * @return A pointer to the newly created list. **/ -sll_node* sll_new( void* contents ); +sll_t* sll_new(void); /** - * @brief Finds and returns the first node in the supplied linked list. + * @brief Creates a new node with given contents. * - * This function returns a pointer to the first node in the given linked list. + * @param contents Pointer to the contents of this node. * - * @param list The linked list to search. + * @return Pointer to newly created node. + */ +sll_node_t* sll_new_node(void* contents); + +/** + * @brief Frees all memory used by a linked list. * - * @return Pointer to the last node in the supplied list. + * This function loops through the supplied list and frees all nodes. + * Also frees contents if free_contents is passed a non-zero value. + * + * @param list The list to be freed. + * @param free_contents Whether or not to also free the contents of each node. **/ -sll_node* sll_front(sll_node* list); +void sll_free(sll_t* list, int free_contents); + +/** + * @brief Frees all memory used by a node. + * + * This function frees all memory allocated to a node. Also frees contents if + * the free_contents is 1. + * + * @param node + * @param free_contents + */ +void sll_free_node(sll_node_t* node, int free_contents); /** - * @brief Finds and returns the last node in the supplied linked list. + * @brief Returns the number of elements in the list. * - * This function returns a pointer to the last node in the given linked list. + * This function loops through the supplied list and returns a count of the + * number of elements contained in the list. * - * @param list The linked list to search. + * @param list The list to be counted. * - * @return Pointer to the last node in the supplied list. + * @return The number of elements in the list. **/ -sll_node* sll_back(sll_node* list); +unsigned int sll_length(sll_t* list); /** * @brief Return the node at the specified index in a linked list. @@ -79,9 +78,9 @@ sll_node* sll_back(sll_node* list); * @param list The list to search for the supplied index. * @param index The index of the node to return. * - * @return A pointer to the node and the supplied index, NULL if out of range. + * @return A pointer to the node at the supplied index, NULL if out of range. **/ -sll_node* sll_index(sll_node* list, int index); +sll_node_t* sll_index(sll_t* list, unsigned int index); /** * @brief Adds a new node to the front of an existing linked list. @@ -94,7 +93,7 @@ sll_node* sll_index(sll_node* list, int index); * * @return Pointer to the newly added node. **/ -sll_node* sll_push_front( sll_node* list, void* contents ); +sll_node_t* sll_push_front( sll_t* list, void* contents ); /** * @brief Adds a new node to the end of an existing linked list. @@ -107,7 +106,7 @@ sll_node* sll_push_front( sll_node* list, void* contents ); * * @return Pointer to the newly added node. **/ -sll_node* sll_push_back( sll_node* list, void* contents ); +sll_node_t* sll_push_back( sll_t* list, void* contents ); /** * @brief Removes and returns a pointer to the first element of the list. @@ -122,7 +121,7 @@ sll_node* sll_push_back( sll_node* list, void* contents ); * * @return Pointer to the newly added node. **/ -void sll_pop_front( sll_node* list, int free_contents ); +sll_node_t* sll_pop_front( sll_t* list, int free_contents ); /** * @brief Removes and returns a pointer to the last element of the list. @@ -137,7 +136,7 @@ void sll_pop_front( sll_node* list, int free_contents ); * * @return Pointer to the newly added node. **/ -void sll_pop_back( sll_node* list, int free_contents ); +sll_node_t* sll_pop_back( sll_t* list, int free_contents ); /** * @brief Inserts a new node in a linked list at the specified index. @@ -152,7 +151,7 @@ void sll_pop_back( sll_node* list, int free_contents ); * * @return Pointer to the newly inserted node, NULL if index is out of range. **/ -sll_node* sll_insert( sll_node* list, int index, void* contents); +sll_node_t* sll_insert( sll_t* list, unsigned int index, void* contents); /** * @brief Deletes a node from the supplied list. @@ -168,29 +167,6 @@ sll_node* sll_insert( sll_node* list, int index, void* contents); * * @return Pointer to the node that is now at the supplied index. **/ -sll_node* sll_delete( sll_node* list, int index, int free_contents); - -/** - * @brief Frees all memory used by a linked list. - * - * This function loops through the supplied list and frees all nodes. - * Also frees contents if free_contents is passed a non-zero value. - * - * @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_node* list, int free_contents); - -/** - * @brief Returns the number of elements in the list. - * - * This function loops through the supplied list and returns a count of the - * number of elements contained in the list. - * - * @param list The list to be counted. - * - * @return The number of elements in the list. - **/ -unsigned int sll_length(sll_node* list); +sll_node_t* sll_delete( sll_t* list, unsigned int index, int free_contents); #endif diff --git a/tests/test_sll.cpp b/tests/test_sll.cpp index ffd8bf0..e139c3c 100644 --- a/tests/test_sll.cpp +++ b/tests/test_sll.cpp @@ -1,5 +1,6 @@ // Unit Test Framework Includes #include "UnitTest++.h" +#include // File To Test #include "sll.h" @@ -11,9 +12,180 @@ using namespace UnitTest; //----------------------------------------------------------------------------- namespace { //------------------------------------------------------------------------- - // Test XXX Function + // Test sll_new function //------------------------------------------------------------------------- - TEST(Verify_XXX) + 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_does_nothing_on_null_pointer) + { + sll_free( NULL, 0 ); + } + + 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_does_nothing_on_null_pointer) + { + sll_free_node( NULL, 0 ); + } + + 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_length function + //------------------------------------------------------------------------- + TEST(Verify_sll_length_returns_0_when_passed_null_pointer) + { + CHECK( 0 == sll_length(NULL) ); + } + + TEST(Verify_sll_length_returns_0_when_list_is_empty) + { + sll_t* list = sll_new(); + CHECK( 0 == sll_length( list ) ); + free( list ); + } + + TEST(Verify_sll_length_returns_1_when_list_is_length_1) + { + sll_node_t node1 = { NULL, NULL }; + sll_t list = { &node1, &node1 }; + + CHECK( 1 == sll_length( &list ) ); + } + + TEST(Verify_sll_length_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 ) ); + } + + //------------------------------------------------------------------------- + // Test sll_index function + //------------------------------------------------------------------------- + TEST(Verify_sll_index_returns_NULL_on_null_pointer) + { + CHECK( NULL == sll_index( NULL, 0 ) ); + } + + TEST(Verify_sll_index_returns_NULL_when_list_is_empty) + { + sll_t list = { NULL, NULL }; + CHECK( NULL == sll_index( &list, 0 ) ); + } + + TEST(Verify_sll_index_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 ) ); + } + + TEST(Verify_sll_index_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 ) ); + } + + TEST(Verify_sll_index_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 ) ); + } + + TEST(Verify_sll_index_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 ) ); + } + + //------------------------------------------------------------------------- + // Test sll_push_front function + //------------------------------------------------------------------------- + //------------------------------------------------------------------------- + // Test sll_push_back function + //------------------------------------------------------------------------- + //------------------------------------------------------------------------- + // Test sll_pop_front function + //------------------------------------------------------------------------- + //------------------------------------------------------------------------- + // Test sll_pop_back function + //------------------------------------------------------------------------- + //------------------------------------------------------------------------- + // Test sll_insert function + //------------------------------------------------------------------------- + //------------------------------------------------------------------------- + // Test sll_delete function + //------------------------------------------------------------------------- } -- 2.49.0