From 5a7e2d503884b23db1da2f99bd64a66c975df272 Mon Sep 17 00:00:00 2001 From: Pat Thoyts Date: Sat, 19 Jun 2010 00:57:10 +0100 Subject: [PATCH] C style for linked list implementation and unit testing. This removes a memory leak in the swap and sort functions. Also an off by one error in the push function. Ensure the sort does so by alpha and then size. Signed-off-by: Pat Thoyts --- src/linked.c | 323 ++++++++++++++++++++++++++++--------------------- src/linked.h | 20 ++- src/unittest.h | 32 ++++- 3 files changed, 222 insertions(+), 153 deletions(-) diff --git a/src/linked.c b/src/linked.c index 45fd8d2..1cffb8a 100644 --- a/src/linked.c +++ b/src/linked.c @@ -1,167 +1,208 @@ /* -Anagramarama - A word game. Like anagrams? You'll love anagramarama! -Copyright (C) 2003 Colm Gallagher + Anagramarama - A word game. Like anagrams? You'll love anagramarama! + Copyright (C) 2003 Colm Gallagher -This program is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 2 of the License, or -(at your option) any later version. + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. -This program is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. -You should have received a copy of the GNU General Public License -along with this program; if not, write to the Free Software -Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA -Contact Details: colm@coralquest.com - 12 Weston Terrace, West Kilbride, KA23 9JX. Scotland. + Contact Details: colm@coralquest.com + 12 Weston Terrace, West Kilbride, KA23 9JX. Scotland. */ #include #include #include "linked.h" -/***********************************************************/ -int Length(struct node* head){ +/* + * Count the length of the linked list. + */ + +int +Length(struct node *head) +{ + struct node *current = head; + int count = 0; + for ( ; current; current = current->next) { + ++count; + } + return count; +} -struct node* current = head; -int count = 0; +/* + * swap the data content of two linked list nodes without changing + * the position of the node within the list + */ + +void +swap(struct node **from, struct node **to) +{ + char *word = (*from)->anagram; + int len = (*from)->length; + + (*from)->anagram = (*to)->anagram; + (*from)->length = (*to)->length; + (*to)->anagram = word; + (*to)->length = len; +} - while (current != NULL){ - //printf("%s\n", current->anagram); - count++; - current = current->next; +/* + * sort the list first alphabetically and then by increasing word length + */ + +void +sort(struct node **headRef) +{ + struct node* left, *right; + int completed = 0; + + while (!completed) { + left = *headRef; + right = left->next; + completed = 1; + for (; left && right; left = left->next, right = right->next) { + if (strcmp(left->anagram, right->anagram) > 0) { + swap(&left, &right); + completed = 0; + } } + } + + completed = 0; + while (!completed) { + left = *headRef; + right = left->next; + completed = 1; + for (; left && right; left = left->next, right = right->next) { + if (left->length > right->length) { + swap(&left, &right); + completed = 0; + } + } + } +} - return count; +/* + * Free the list and the allocated data in each node + */ + +void +destroyAnswers(struct node** headRef) +{ + struct node* current = *headRef; + struct node* previous = *headRef; + + while (current != NULL){ + free(current->anagram); + previous = current; + current = current->next; + free(previous); + previous = NULL; + } + + *headRef = NULL; } -/***********************************************************/ -void swap(struct node** from, struct node** to){ -// swaps the contents of 2 linked list nodes -// doesn't disturb the pointers -char* swap; - - swap = malloc(sizeof((*from)->anagram)); - strcpy(swap, (*from)->anagram); - (*from)->anagram = (*to)->anagram; - (*from)->length = (*to)->length; - (*to)->anagram = swap; - (*to)->length = strlen(swap); - -} /***********************************************************/ -void sort(struct node** headRef){ -// sort the linked list alpha/num of chars -struct node* current = *headRef; -struct node* next = malloc(sizeof(struct node)); -int done = 0; -int swaps = 0; - - // walk the list - while (!done){ - while (current !=NULL){ - next = current->next; - if (next != NULL){ - //printf("%s, %s - %i\n", next->anagram, current->anagram, strcmp(next->anagram, current->anagram)); - if (strcmp(next->anagram, current->anagram)<0){ - swap(&next, ¤t); - swaps++; - } - } - current = current->next; - } - if (!swaps){ - done = 1; - } - else{ - swaps = 0; - current = *headRef; - } - } - - done = 0; - current = *headRef; - swaps = 0; - - // walk the list - while (!done){ - while (current !=NULL){ - next = current->next; - if (next != NULL){ - //printf("%s, %s \n", next->anagram, current->anagram); - if (strlen(next->anagram) < strlen(current->anagram)){ - swap(&next, ¤t); - swaps++; - } - } - current = current->next; - } - if (!swaps){ - done = 1; - } - else{ - swaps = 0; - current = *headRef; - } - } - - free(next); +void +push(struct node **headRef, const char *anagram) +{ + struct node * current = *headRef; + int len; + int duplicate = 0; + + /* walk the list first, so we can ignore duplicates... + * this is probably slower than clearing duplicates at the end + * but simpler to write in the first instance + */ + while (current != NULL) { + if (!strcmp(anagram, current->anagram)){ + duplicate = 1; + break; + } + current = current->next; + } + + if (!duplicate) { + struct node *newNode = malloc(sizeof(struct node)); + len = strlen(anagram); + newNode->anagram = strdup(anagram); + newNode->length = len; + newNode->found = 0; + newNode->guessed = 0; + newNode->next = *headRef; + + *headRef = newNode; + } } -/***********************************************************/ -void destroyAnswers(struct node** headRef){ -// destroy the whole answers list - -struct node* current = *headRef; -struct node* previous = *headRef; - - while (current != NULL){ - free(current->anagram); - previous = current; - current = current->next; - free(previous); - previous = NULL; - } - - *headRef = NULL; +#ifdef UNIT_TEST +#include "unittest.h" + +static int test_list_creation() +{ + struct node *head = NULL, *node = NULL; + const char *words[] = {"one", "two", "three", "four", "five" }; + const char *ordrd[] = {"one", "two", "five", "four", "three" }; + size_t n, word_count = sizeof(words)/sizeof(words[0]); + + for (n = 0; n < word_count;++n) { + push(&head, (char *)words[n]); + } + test_equals_int("check list length", 5, Length(head)); + + for (node = head, n = word_count; node; --n, node = node->next) { + if (strcmp(words[n-1], node->anagram) != 0) + test_fail("incorrect node value"); + if (strlen(words[n-1]) != node->length) + test_fail("incorrect node value length"); + } + + node = head->next; + swap(&head, &node); + test_equals_str("check swapped nodes", words[3], head->anagram); + test_equals_str("check swapped nodes", words[4], head->next->anagram); + + sort(&head); + + for (node = head, n = 0; node; ++n, node = node->next) { + if (strcmp(ordrd[n], node->anagram) != 0) + test_fail("incorrect node value"); + } + + destroyAnswers(&head); + test_equals_ptr("check list destroyed", head, NULL); + return 0; } +struct unit_test_t unit_tests[] = { + { NULL, test_list_creation, NULL} +}; - -/***********************************************************/ -void push(struct node** headRef, char* anagram){ - -struct node* newNode = malloc(sizeof(struct node)); -int len; -struct node* current = *headRef; -int duplicate = 0; - - // walk the list first, so we can ignore duplicates... - // this is probably slower than clearing duplicates at the end - // but simpler to write in the first instance - while (current != NULL){ - if (!strcmp(anagram, current->anagram)){ - duplicate = 1; - break; - } - current = current->next; - } - - if (!duplicate){ - len = strlen(anagram+1); - newNode->anagram = malloc(sizeof(char)*(len + 1)); - strcpy(newNode->anagram, anagram); - newNode->length = len + 1; - newNode->found = 0; - newNode->guessed = 0; - newNode->next = *headRef; // dereference back the the real head pointer - - *headRef = newNode; // ditto when replacing it with the new one - } +int +main(void) +{ + run_tests(unit_tests); + return 0; } +#endif /* UNIT_TEST */ + +/* + * Local variables: + * mode: c + * c-basic-offset: 4 + * indent-tabs-mode: nil + * End: + */ diff --git a/src/linked.h b/src/linked.h index 4c6d772..7af17c1 100644 --- a/src/linked.h +++ b/src/linked.h @@ -21,15 +21,23 @@ Contact Details: colm@coralquest.com */ struct node { - char* anagram; - int found; - int guessed; - int length; - struct node* next; + char* anagram; + int found; + int guessed; + int length; + struct node *next; }; int Length(struct node* head); void swap(struct node** from, struct node** to); void sort(struct node** headRef); void destroyAnswers(struct node** headRef); -void push(struct node** headRef, char* anagram); +void push(struct node** headRef, const char *anagram); + +/* + * Local variables: + * mode: c + * c-basic-offset: 4 + * indent-tabs-mode: nil + * End: + */ diff --git a/src/unittest.h b/src/unittest.h index 9b4e7fc..9450efc 100644 --- a/src/unittest.h +++ b/src/unittest.h @@ -64,6 +64,18 @@ typedef unsigned __int64 uint64_t; #include #endif +#ifdef __GNUC__ +#define NOWARN __attribute__((unused)) +#else +#define NOWARN +#endif +static void test_equals_int(const char *what, const int a, const int b) NOWARN; +static void test_equals_wide(const char *what, const uint64_t a, const uint64_t b) NOWARN; +static void test_equals_ptr(const char *what, const void *a, const void *b) NOWARN; +static void test_equals_str(const char *what, const char *a, const char *b) NOWARN; +static void test_equals_strn(const char *what, const char *a, const char *b, size_t n) NOWARN; +static void test_non_null_ptr(const char *what, const void *a) NOWARN; + typedef void * (unit_test_setup_t)(); typedef int (unit_test_run_t)(void *); typedef void (unit_test_teardown_t)(void *); @@ -79,7 +91,7 @@ static int fail_count = 0; #define RUN(what) printf("\t%s\n", what); test_count++; -static test_fail(const char *what) +static void test_fail(const char *what) { printf("\tFAIL: %s\n", what); fflush(stdout); @@ -100,15 +112,15 @@ static void test_equals_ptr(const char *what, const void *a, const void *b) RUN(what); if (a != b) test_fail(what); } -static void test_equals_str(const char *what, const uint8_t *a, const uint8_t *b) +static void test_equals_str(const char *what, const char *a, const char *b) { RUN(what); - if (strcmp((const char *)a,(const char *)b)) test_fail(what); + if (strcmp(a,b)) test_fail(what); } -static void test_equals_strn(const char *what, const uint8_t *a, const uint8_t *b, size_t n) +static void test_equals_strn(const char *what, const char *a, const char *b, size_t n) { RUN(what); - if (strncmp((const char *)a,(const char *)b,n)) test_fail(what); + if (strncmp(a,b,n)) test_fail(what); } static void test_non_null_ptr(const char *what, const void *a) { @@ -123,7 +135,7 @@ test_print_results() } static int -run_tests(const struct unit_test_t *testPtr) +run_test(const struct unit_test_t *testPtr) { int r = 0; void *clientData = NULL; @@ -134,3 +146,11 @@ run_tests(const struct unit_test_t *testPtr) testPtr->tearDown(clientData); return r; } + +#define run_tests(tests) do { \ + size_t n; \ + for (n = 0; n < sizeof(tests)/sizeof(tests[0]); ++n) { \ + run_test(&tests[n]); \ + } \ + test_print_results(); \ + } while(0); -- 2.23.0