I am working on a project for school (Tonight!), And I am having serious memory problems. I'm new to C and I'm still rushing for the loop when it comes to mallocing pointers and something else, so I can really use some help.
The code is as follows. The order of the files is LinkedLists.h (Header for the LinkedList module), LinkedLists.c (LinkedList module) and TestList.c (Main module).
/****************************************************************************** * Base struct to contain data structure element information: deterimined by * the application needs. ******************************************************************************/ #ifndef _LINKED_LISTS_H_ #define _LINKED_LISTS_H_ typedef struct ElementStructs { int ElementPosition; char* ElementValue; } ElementStructs; /************** Nothing else in the module needs to be modified *************/ /****************************************************************************** * Base struct of list nodes, contains user information and link pointers. * The "ElementStructs" typemark must be defined based on specific needs of the * application. ******************************************************************************/ typedef struct LinkedListNodes { /* The user information field */ ElementStructs *ElementPtr; /* Link pointers */ struct LinkedListNodes *Next; struct LinkedListNodes *Previous; } LinkedListNodes; /****************************************************************************** * Base struct used to manage the linked list data structure. ******************************************************************************/ typedef struct LinkedLists { /* Number of elements in the list */ int NumElements; /* Pointer to the front of the list of elements, possibly NULL */ struct LinkedListNodes *FrontPtr; /* Pointer to the end of the list of elements, possibly NULL */ struct LinkedListNodes *BackPtr; } LinkedLists; /****************************************************************************** * Initialized the linked list data structure ******************************************************************************/ void InitLinkedList(LinkedLists *ListPtr); /****************************************************************************** * Adds a record to the front of the list. ******************************************************************************/ void AddToFrontOfLinkedList(LinkedLists *ListPtr, ElementStructs *DataPtr); /****************************************************************************** * Adds a record to the back of the list. ******************************************************************************/ void AddToBackOfLinkedList(LinkedLists *ListPtr, ElementStructs *DataPtr); /****************************************************************************** * Removes (and returns) a record from the front of the list ('works' even on * an empty list by returning NULL). ******************************************************************************/ ElementStructs *RemoveFromFrontOfLinkedList(LinkedLists *ListPtr); /****************************************************************************** * Removes (and returns) a record from the back of the list ('works' even on * an empty list by returning NULL). ******************************************************************************/ ElementStructs *RemoveFromBackOfLinkedList(LinkedLists *ListPtr); /****************************************************************************** * De-allocates the linked list and resets the struct fields as if the * list was empty. ******************************************************************************/ void DestroyLinkedList(LinkedLists *ListPtr); #endif /* _LINKED_LISTS_H_ */
LinkedLists.c:
/****************************************************************************** * Extracts and prints the first and last 6 elements from the specified data * set and prints the total number of words in the input file. Utilizes the * LinkedList module as specified in LinkedLists.h * Written by xxxxxxx ******************************************************************************/ #include <stdio.h> #include <stdlib.h> #include "LinkedLists.h" void InitLinkedList(LinkedLists *ListPtr) { ListPtr->NumElements = 0; ListPtr->FrontPtr = NULL; ListPtr->BackPtr = NULL; } void AddToFrontOfLinkedList(LinkedLists *ListPtr, ElementStructs *DataPtr) { /* If there are no other elements, create new node and add it, * assigning it to both the front and back pointers */ if(ListPtr->NumElements == 0) { ListPtr->FrontPtr = malloc(sizeof(LinkedListNodes)); ListPtr->FrontPtr->ElementPtr = DataPtr; ListPtr->FrontPtr->Next = NULL; ListPtr->FrontPtr->Previous = NULL; ListPtr->BackPtr = ListPtr->FrontPtr; } /* If there are other elements, create new node and add it to the front * while retaining previous node order */ else { /* Initialize new LinkedListNode */ ListPtr->FrontPtr->Previous = malloc(sizeof(LinkedListNodes)); ListPtr->FrontPtr->Previous->ElementPtr = DataPtr; ListPtr->FrontPtr->Previous->Next = ListPtr->FrontPtr; ListPtr->FrontPtr->Previous->Previous = NULL; /* Assign newly initialized node as front node of LinkedList */ ListPtr->FrontPtr = ListPtr->FrontPtr->Previous; } /* List size plus one */ (ListPtr->NumElements)++; } void AddToBackOfLinkedList(LinkedLists *ListPtr, ElementStructs *DataPtr) { /* If there are no other elements, create new node and add it, * assigning it to both the front and back pointers */ if(ListPtr->NumElements == 0) { ListPtr->FrontPtr = malloc(sizeof(LinkedListNodes)); ListPtr->FrontPtr->ElementPtr = DataPtr; ListPtr->FrontPtr->Next = NULL; ListPtr->FrontPtr->Previous = NULL; ListPtr->BackPtr = ListPtr->FrontPtr; /*printf("Adding %s\n", DataPtr->ElementValue);*/ } /* If there are other elements, create new node and add it to the back * while retaining previous node order */ else { /* Initialize new LinkedListNode */ ListPtr->BackPtr->Next = malloc(sizeof(LinkedListNodes)); ListPtr->BackPtr->Next->ElementPtr = DataPtr; ListPtr->BackPtr->Next->Previous = ListPtr->BackPtr; ListPtr->BackPtr->Next->Previous = ListPtr->BackPtr; ListPtr->BackPtr->Next->Next = NULL; /* Assign newly initialized node as back node of LinkedList */ ListPtr->BackPtr = ListPtr->BackPtr->Next; printf("Adding %s\n", ListPtr->BackPtr->ElementPtr->ElementValue); } /* List size plus one */ (ListPtr->NumElements)++; } ElementStructs *RemoveFromFrontOfLinkedList(LinkedLists *ListPtr) { if(ListPtr->NumElements > 0) { ElementStructs *removedElement = ListPtr->FrontPtr->ElementPtr; LinkedListNodes *removedNode = ListPtr->FrontPtr; if(ListPtr->NumElements == 1) { ListPtr->FrontPtr = NULL; } else { ListPtr->FrontPtr = ListPtr->FrontPtr->Next; ListPtr->FrontPtr->Previous = NULL; } (ListPtr->NumElements)--; free(removedNode); return removedElement; } else { ElementStructs *nullElement = NULL; return nullElement; } } ElementStructs *RemoveFromBackOfLinkedList(LinkedLists *ListPtr) { if(ListPtr->NumElements > 1) { ElementStructs *removedElement = ListPtr->BackPtr->ElementPtr; LinkedListNodes *removedNode = ListPtr->BackPtr; if(ListPtr->NumElements == 1) { ListPtr->BackPtr = NULL; } else { ListPtr->BackPtr = ListPtr->BackPtr->Previous; ListPtr->BackPtr->Next = NULL; } (ListPtr->NumElements)--; free(removedNode); return removedElement; } else { ElementStructs *nullElement = NULL; return nullElement; } } void DestroyLinkedList(LinkedLists *ListPtr) { while(ListPtr->FrontPtr != NULL) { LinkedListNodes *removedNode = ListPtr->FrontPtr; ListPtr->FrontPtr = ListPtr->FrontPtr->Next; /* Deallocate element in node */ free(removedNode->ElementPtr->ElementValue); free(removedNode->ElementPtr); /* Deallocate node */ free(removedNode); } free(ListPtr); }
TestList.c:
/****************************************************************************** * Tests the functionality of the LinkedList specified in LinkedLists.h using * the file "american-english-words". Reads in individual words and stores them * as node elements in the LinkedList. * Written by xxxxx *****************************************************************************/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include "LinkedLists.h" #define MAX_LENGTH 100 /* Length of longest word in any major English dictionary */ int main(int argc, char** args) { if(argc == 2) { /* Initialize LinkedList */ LinkedLists *LL; /* File pointer to input file */ FILE *fp; /* Node to store input data from file */ ElementStructs *NodeData; /* Loop completion boolean */ int Done; /* Loop position counter */ int Position; /* Iterator */ ElementStructs *CurElement; /* Open input file and check that it is readable. If not, exit */ fp = fopen(args[1], "r"); if(fp == NULL) { fprintf(stderr, "File open failed."); return 2; } /* Initialize linked list and other necessary variables */ LL = malloc(sizeof(*LL)); InitLinkedList(LL); Done = 0; Position = 0; do { if(!feof(fp)) { /* Allocate space for new node data */ NodeData = malloc(sizeof(ElementStructs)); /* Allocate space in node element for input string */ NodeData->ElementValue = malloc(MAX_LENGTH * sizeof(char)); /* Read new node data from file */ fscanf(fp, "%s", NodeData->ElementValue); /* Assign scanned values to node elements */ NodeData->ElementPosition = Position; /*strcpy(NodeData->ElementValue, readString);*/ /* Add data node to LinkedList */ AddToFrontOfLinkedList(LL, NodeData); } else Done = 1; Position++; }while(Done == 0); do { CurElement = RemoveFromFrontOfLinkedList(LL); if(CurElement != NULL) printf("Word #%d: %s\n", CurElement->ElementPosition, CurElement->ElementValue); }while(CurElement != NULL); /* Deallocate linked list */ DestroyLinkedList(LL); fclose(fp); } /* Bad command line input */ else { fprintf(stderr, "Incorrect number of arguments"); return 1; } return 0; }
The program compiles fine. However, on startup, it raises a seg error at the end of execution, and valgrind reports several memory leaks (shown below). Please, if you have any help, I would be extremely grateful. The problem is mainly related to the RemoveFromBackOfLinkedList and RemoveFromFrontOfLinkedList methods in the LinkedList.c module. There is a block of code in the main module (TestList.c) that calls one of these functions (I tried both of them, but they have almost identical functionality, and none of them work). The block is a do / while loop, shown below:
do { CurElement = RemoveFromFrontOfLinkedList(LL); if(CurElement != NULL) printf("Word #%d: %s\n", CurElement->ElementPosition, CurElement->ElementValue); }while(CurElement != NULL);
Valgrind Results:
Word #225921: stoich . . . . Word #6: Cam's Word #5: petrochemistry's Word #4: Tera Word #3: benedictions Word #2: wisted Word #1: toxins ==4849== Invalid write of size 8 ==4849== at 0x400B5C: RemoveFromFrontOfLinkedList (in /home/amb2189/hw3/TestList) ==4849== by 0x40085B: main (in /home/amb2189/hw3/TestList) ==4849== Address 0x10 is not stack'd, malloc'd or (recently) free'd ==4849== ==4849== ==4849== Process terminating with default action of signal 11 (SIGSEGV) ==4849== Access not within mapped region at address 0x10 ==4849== at 0x400B5C: RemoveFromFrontOfLinkedList (in /home/amb2189/hw3/TestList) ==4849== by 0x40085B: main (in /home/amb2189/hw3/TestList) ==4849== If you believe this happened as a result of a stack ==4849== overflow in your program main thread (unlikely but ==4849== possible), you can try to increase the size of the ==4849== main thread stack using the --main-stacksize= flag. ==4849== The main thread stack size used in this run was 8388608. ==4849== ==4849== HEAP SUMMARY: ==4849== in use at exit: 23,965,172 bytes in 413,185 blocks ==4849== total heap usage: 619,775 allocs, 206,590 frees, 28,923,332 bytes allocated ==4849== ==4849== 16 bytes in 1 blocks are possibly lost in loss record 1 of 9 ==4849== at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==4849== by 0x4007E2: main (in /home/amb2189/hw3/TestList) ==4849== ==4849== 200 bytes in 2 blocks are possibly lost in loss record 5 of 9 ==4849== at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==4849== by 0x4007F0: main (in /home/amb2189/hw3/TestList) ==4849== ==4849== 23,963,992 (3,305,392 direct, 20,658,600 indirect) bytes in 206,587 blocks are definitely lost in loss record 9 of 9 ==4849== at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==4849== by 0x4007E2: main (in /home/amb2189/hw3/TestList) ==4849== ==4849== LEAK SUMMARY: ==4849== definitely lost: 3,305,392 bytes in 206,587 blocks ==4849== indirectly lost: 20,658,600 bytes in 206,586 blocks ==4849== possibly lost: 216 bytes in 3 blocks ==4849== still reachable: 964 bytes in 9 blocks ==4849== suppressed: 0 bytes in 0 blocks ==4849== Reachable blocks (those to which a pointer was found) are not shown. ==4849== To see them, rerun with: --leak-check=full --show-reachable=yes ==4849== ==4849== For counts of detected and suppressed errors, rerun with: -v ==4849== Use --track-origins=yes to see where uninitialised values come from ==4849== ERROR SUMMARY: 5 errors from 5 contexts (suppressed: 2 from 2) Segmentation fault (core dumped)