Thread: Unknown memory leak with linked lists...

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    21

    Unknown memory leak with linked lists...

    So my program is 99% towards completion. However, the program leaks memory. The deleteNode, deleteManager, and destroyList are the ones to blame, or so I think. When I delete a node other than the first one it works while leaking memory. However, when I try deleting the first node and then try to display the list again, the program crashes. Perhaps my deleteNode function needs some readjustment. In any case, here is the code and the input file.

    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<ctype.h>
    #include<crtdbg.h>
    
    #define FLUSH while (getchar () != '\n')
    #define FILE_IN "countries.txt"
    
    // Type Definitions 
    
    typedef char KEY_TYPE;
    typedef struct {
    	char *name;
    	char *capital;
    	long population;
    	} COUNTRY;
    
    typedef struct {
    	KEY_TYPE key[3];
    	COUNTRY list;
    	} DATA;
    
    typedef struct nodeTag {
    	DATA			data;
    	struct nodeTag*	link;
    	} NODE;
    
    // Prototype Declarations
    char getOption	  (void);
    void printMenu    (void);
    
    int   searchList  (NODE *pList, NODE **pPre, NODE **pCur, char target[]);
    NODE *insertNode  (NODE *pList, NODE *pPre,  DATA  item);
    NODE *deleteNode  (NODE *pList, NODE *pPre,  NODE *pCur);
    void  printList   (NODE *pList);
    NODE *destroyList (NODE *pList);
    
    NODE *buildList (void);
    
    NODE *processListManager (NODE *pList);
    void  searchManager      (NODE *pList);
    NODE *insertManager	     (NODE *pList);
    NODE *deleteManager      (NODE *pList);
    
    int getData ( FILE *spIn, DATA *data );
    void insertCommas ( NODE *pWalker, char *population );
    void printCountry ( NODE *list, char populationInCommas[] );
    int insertHandler ( DATA *data, char target[] );
    
    int main ( void )
    {
    //  Local Definitions 
        NODE *list = NULL;
    
    //  Statements 
        printf("\t\t LAB 8 - LINKED LISTS\n\n");
    
    	list = buildList();
        printMenu();
    	processListManager ( list );
    	list = destroyList ( list );
        
    	printf("\n\t\tEnd of LAB 8 - LINKED LISTS"
    		   "\n\t\tHave a great day!\n");
    
        
        printf( _CrtDumpMemoryLeaks() ? "Memory Leak\n" : "No Leak\n");
    
        return 0;
    
    }// main 
    
    /* ================================================================= */
    /* 
     *   Instructor
     *
    /* ================================================================= */
    
    /*	==================== getOption ====================
    	Gets and validates the user's option.
    		Pre		: nothing
    		Post	: valid option returned
        Written by  : Instructor
    */
    char getOption	(void)
    {
    //  Local Definitions 
    	char option;
    
    //  Statements 
    	printf ("\n\nPlease enter the option: ");
    	scanf  ("%c", &option);
        FLUSH;
    	option = toupper (option);
        while(strchr("LSIDME", option) == NULL)
        {
            printf("\..........* Invalid option! ***\n");
            printf("Enter one of the following letters: L, S, I, D, M, E: " );
            scanf  ("%c", &option);
            FLUSH;
    	    option = toupper (option);
        }
    
    	return option;
    
    } // getOption 
    
    /* ============================== printMenu ==============================
    	Prints the menu to the screen.
    	   PRE  : nothing
    	   POST : menu printed
           Written by  : Instructor
    */
    void printMenu (void)
    {
    //  Local Definitions 
    
    //  Statements 
    	printf("\n\t\t**********************"
               "\n\t\t*                    *"
    	       "\n\t\t*   L - List         *"
               "\n\t\t*   S - Search       *"
    	       "\n\t\t*   I - Insert       *"
    	       "\n\t\t*   D - Delete       *"
    	       "\n\t\t*   M - Print Menu   *"
    	       "\n\t\t*   E - Exit         *"
    	       "\n\t\t*                    *"
    	       "\n\t\t**********************");
    
    	return;
    
    } // printMenu 
    
    /* ============================== processListManager ====================
    	Process user's option by calling appropriate functions.
    	   PRE  : pList - a pointer to the first node of a linked list
    	   POST : pList - might be changed after inserting or deleting 
           Written by  : Instructor
    */
    
    NODE *processListManager (NODE *pList)
    {
    //  Local Definitions
    	char option;
    
    //  Statements
    	do
    	{
    		option = getOption();
    		switch(option)
    		{
    		    case 'L' : printList (pList);
    				       break;
    		    case 'S' : searchManager (pList);
    				       break;
    		    case 'I' : pList = insertManager (pList);
    				       break;
    		    case 'D' : pList = deleteManager (pList);
    				       break;
    		    case 'M' : printMenu ();
    				       break;
    		    case 'E' : printf("End of processing!\n");
                           break;
               default  :  break;
    		} 
    	} while (option != 'E');
    
    	return pList;
    
    } // processListManager 
    
    /* ================================================================= */
    /* 
     *   Me
     *
    /* ================================================================= */
    
    /* =============================buildList=================================
    	Builds the list for the countries' data from the input file.
    		PRE	: nothing
    		POST: pList - the complete list after reading from input file
    */
    NODE *buildList (void)
    {
    // Local Declarations
    	NODE *pList;
    	NODE *pPre;
    	NODE *pCur;
    	DATA data;
    	FILE *spIn;
    	int result;
    
    // Statements
    	if ( ! ( spIn = fopen ( FILE_IN, "r" ) ) )	{
    		printf("Error opening file %s\n", FILE_IN);
    		exit(100);
    	}
    	pList = NULL;
    	while ( getData ( spIn, &data ) ) {
    		result = searchList(pList, &pPre, &pCur, data.key);
    		if ( !result )
    			pList = insertNode(pList, pPre, data);
    	}
    	fclose ( spIn );
    	return pList;
    } // buildList
    
    /* ==============================getData==================================
    	Gathers the data from the input file and allocates memory for the
    	countries' names and capitals.
    		PRE	: spIn - the input file containing country data
    			  data - address of the data from buildList
    		POST: pList - the list after reading from input file
    */
    int getData ( FILE *spIn, DATA *data )
    {
    // Local Declarations
    	int result;
    
    // Statements
    	data->list.name = (char*)calloc(21, sizeof(char));
    	data->list.capital = (char*)calloc(16, sizeof(char));
    	result = fscanf ( spIn, "%2s %20[^;] %*c %15[^;] %*c %ld", 
    					  data->key, data->list.name, 
    					  data->list.capital, &(data->list.population) );
    	if ( result == 4 )
    		return 1;
    	else {
    		free ( data->list.name );
    		free ( data->list.capital );
    		return 0;
    	}
    } // getData
    
    /* ============================insertNode=================================
    	Inserts a node into the list.
    		PRE	: pList - the current list before adding a new node
    			  pPre  - the predescessor of the new node
    			  item  - country data to be copied into the new node
    		POST: pList - the list with the new node added
    */
    NODE *insertNode  (NODE *pList, NODE *pPre, DATA item)
    {
    // Local Declarations
    	NODE *pNew;
    
    // Statements
    	if ( ! ( pNew = (NODE*)malloc(sizeof(NODE))))
    		printf("Memory is unavailable.\n"),
    			exit(200);
    	pNew->data = item;
    	if ( pPre == NULL ) {
    		pNew->link = pList;
    		pList = pNew;
    	}
    	else {
    		pNew->link = pPre->link;
    		pPre->link = pNew;
    	}
       return pList;
    } // insertNode
    
    /* ============================searchList=================================
    	Searches the list for the target key.
    		PRE	: pList - the list with the countries' data
    			  pPre  - the predescessor of the walker node
    			  pCur  - walker node that walks through pList
    			  target- the inputted key for the search
    		POST: found - returns 1 if target is found, otherwise returns 0
    */
    int searchList (NODE *pList, NODE **pPre, NODE **pCur, char target[])
    {
    // Local Declarations
    	int found = 0;
    
    // Statements
    	*pPre = NULL;
    	*pCur = pList;
    	while (*pCur != NULL) {
    		if (strcmp ( target, (*pCur)->data.key) == 0 ){
    			found = 1;
    			break;
    		}
    		*pPre = *pCur;
    		*pCur = (*pCur)->link;
    	}
       return found;
    } // searchList
    
    /* =============================printList=================================
    	Prints the countries' IDs and names.
    		PRE	: pList - the current country list
    		POST: list is printed
    */
    void printList (NODE *pList)
    {
    // Local Declarations
    	NODE *pWalker;
    // Statements	
    	printf(	"== ====================\n"
    			"ID NAME                \n"
    			"== ====================\n");
    	pWalker = pList;
    	while ( pWalker ) {
    		printf("%s %-20s\n",
    			   pWalker->data.key, pWalker->data.list.name);
    		pWalker = pWalker->link;
    	}
    	printf( "=======================" );
       return;
    } // printList
    
    /* ============================insertCommas=================================
    	Inserts commas for the countries' populations when printed out.
    		PRE	: pWalker - points to a node
    		POST: commas are inserted in countries' populations
    */
    void insertCommas ( NODE *pWalker, char *population )
    {
    // Local Declarations
    	char printString[15];
    	char tempString[15];
    	char insertComma[] = ",";
    	int strLength;
    	int checkRmdr;
    	int i;
    // Statements
    	*printString = '\0';
    	sprintf(tempString, "%ld", pWalker->data.list.population);
    	strLength = strlen ( tempString );
    	checkRmdr = strLength % 3;
    	if ( checkRmdr > 0 ) {
    		strncat ( printString, tempString, checkRmdr );
    		strcat ( printString, insertComma );
    	}
    	for ( i = checkRmdr; i < (int) strlen ( tempString );  ) {
    		strncat ( printString, tempString + i, 3 );
    		i += 3;
    		strcat ( printString, insertComma );
    	}
    	printString[strlen(printString) - 1] = '\0';
    	strcpy (population, printString);
    	return;
    } // insertCommas
    
    /* ============================searchManager==============================
    	Prompts user for a key and searches for it. If found, calls the
    	printCountry funtion that prints out the country's ID, name, 
    	capital, and its population.
    		PRE	: pList - the current country list
    		POST: nothing
    */
    void searchManager (NODE *pList)
    {
    // Local Declarations
    	NODE *pPre;
    	NODE *pCur;
    	char target[3];
    	char populationInCommas[15];
    
    // Statements
    	printf("Please enter a key: ");
    	scanf("%2s", target);
    	FLUSH;
    	if ( searchList ( pList, &pPre, &pCur, target ) ) {
    		insertCommas(pCur, populationInCommas);
    		printCountry(pCur, populationInCommas);
    	}
    	else
    		printf("Country could not be found. Please try again.");
       return;
    } // searchManager
    
    /* ============================printCountry===============================
    	Prints country's ID, name, capital, and its population.
    		PRE	: list - the current country list
    			  populationInCommas - country's population with 
    			  inserted commas
    		POST: prints country data
    */
    void printCountry ( NODE *list, char populationInCommas[] )
    {
    // Statements
    	printf(	"\n        ID: %s\n"
    				"      Name: %s\n"
    			    "   Capital: %s\n"
    				"Population: %s\n", list->data.key, 
    									list->data.list.name,
    									list->data.list.capital, 
    									populationInCommas);
    } // printCountry
    
    /* ============================insertManager=================================
    	Inserts a node into the list by prompting the user to enter a key. It
    	will then call searchList to ensure that there are no duplicates. If not
    	found, it will proceed to gather more information from the user.
    		PRE	: pList - the current list before adding a new node
    		POST: pList - the list with the new node added
    */
    NODE *insertManager (NODE *pList)
    {
    // Local Declarations
    	NODE *pPre;
    	NODE *pCur;
    	DATA insertData;
    	int position;
    	char target[3];
    	int counter = 1;
    // Statements
    	printf("Please enter a key: ");
    	scanf("%2s", target);
    	FLUSH;
    	if ( ! ( searchList ( pList, &pPre, &pCur, target ) ) ) {
    		position = insertHandler ( &insertData, target );
    		
    		switch (position) {
    			case 1:	pPre = NULL;
    					break;
    			case 2:	pPre = pList;
    					while (pPre) {
    						pPre = pPre->link;
    						counter++;
    					}
    					counter /= 2;
    					pPre = pList;
    					while ( counter != 1 ) {
    						pPre = pPre->link;
    						counter--;
    					}
    					break;
    			case 3:	pPre->link = NULL;
    					break;
    		}
    		pList = insertNode( pList, pPre, insertData );
    	}
    	else
    		printf("That country ID already exists. Please try again.");
       return pList;
    } // insertManager
    
    /* ===========================insertHandler===============================
    	Inserts a node into the list.
    		PRE	: pList - the current list before adding a new node
    			  target - the new node's key
    		POST: position - integer that indicates the new node's position
    */
    int insertHandler ( DATA *data, char target[] )
    {
    // Local Declarations
    	int position = 0;
    // Statements
    	if ( ! ( data->list.name = (char*)calloc(21, sizeof(char)))) {
    		printf("Memory Unavailable.\n");
    		exit(300);
    	}
    	if ( ! ( data->list.capital = (char*)calloc(16, sizeof(char)))) {
    		printf("Memory Unavailable.\n");
    		exit(400);
    	}
    	strcpy ( data->key, target );
    	printf("Enter the country's name: ");
    	scanf("%s", data->list.name);
    	FLUSH;
    	printf("Enter the country's capital: ");
    	scanf("%s", data->list.capital);
    	FLUSH;
    	printf("Enter the country's population: ");
    	scanf("%ld", &(data->list.population));
    	FLUSH;
    	while ( position < 1 || position > 3 ) {
    		printf("Where would you like to place this new country?\n"
    			   "Beginning(1), Middle(2), End(3): ");
    		scanf("%d", &position);
    		FLUSH;
    		if ( position < 1 || position > 3 )
    			printf("Incorrect option. Please try again.\n");
    	}
       return position;
    } // insertHandler
    
    /* ============================deleteNode=================================
    	Deletes a node from the list.
    		PRE	: pList - the current list before deleting a node
    			  pPre  - the predescessor of the node to be deleted
    			  pCur  - the node to be deleted
    		POST: pList - the list with the node removed
    */
    NODE *deleteNode (NODE *pList, NODE *pPre, NODE *pCur)
    {
    // Statements
    	if ( pPre == NULL )
    		pList = pCur->link;
    	else
    		pPre->link = pCur->link;
    	free ( pCur );
       return pList;
    } // deleteNode
    
    /* ============================deleteManager==============================
    	Prompts user for a key for the node they want to delete. searchList is
    	called and if not found, no nodes will be deleted.
    		PRE	: pList - the current list before deleting a node
    		POST: pList - the list with or without the node to be deleted
    */
    NODE *deleteManager (NODE *pList)
    {
    // Local Declarations
    	NODE *pPre = NULL;
    	NODE *pCur;
    	char target[3];
    // Statements
    	printf("Please enter a key: ");
    	scanf("%2s", target);
    	FLUSH;
    	if ( searchList ( pList, &pPre, &pCur, target ) )
    		pList = deleteNode ( pList, pPre, pCur );
    	else
    		printf("Country could not be found. Please try again.");
       return pList;
    } // deleteManager
    
    /* ============================destroyList=================================
    	Deletes all the nodes in the list.
    		PRE	: pList - the current list before removing all data
    		POST: pList - an empty list
    */
    NODE *destroyList (NODE *pList)
    {
    // Local Declarations
    	NODE *pPre = NULL;
    	NODE *pCur;
    
    // Statements
    	while ( pList ) {
    		pCur = pList;
    		free ( pCur->data.list.name );
    		free ( pCur->data.list.capital );
    		pList = deleteNode ( pList, pPre, pCur );
    	}
       return pList;
    } // destroyList
    The input file:
    Code:
    HU Hungary; Budapest; 10006835
    MX Mexico; Mexico; 106202903
    CN China; Beijing; 1306313812
    NP Nepal; Kathmandu; 27676547
    MU Mauritius; Port Louis; 1230602
    FR France; Paris; 60656178
    ES Spain; Madrid; 40341462
    EG Egypt; Cairo; 77505756
    TW Taiwan; Taipei; 22894384
    GR Greece; Athens; 10668354
    US United States; Washington, DC; 295734134
    AU Australia; Canberra; 20090437
    LI Liechtenstein; Vaduz; 33717
    RU Russia; Moscow; 143420309
    CA Canada; Ottawa; 32805041
    MC Monaco; Monaco; 32409
    BR Brazil; Brasilia; 186112794
    IR Iran; Tehran; 68017860
    FR France; Paris; 60656178
    DO Dominican Republic; Santo Domingo; 8950034
    FJ Figi; Suva; 893354
    Last edited by RaDeuX; 12-07-2008 at 02:21 AM.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,334
    You don't free all the bits 'n' pieces when you delete a node (capital and name, like you do in destroyNode).

  3. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    21
    Quote Originally Posted by tabstop View Post
    You don't free all the bits 'n' pieces when you delete a node (capital and name, like you do in destroyNode).
    I commented out the free ( ...name) and free ( ...capital), but I'm still getting a memory leak error.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,334
    Well ... but why? The memory leak is you not freeing things, like oh say, name and capital.

  5. #5
    Registered User
    Join Date
    Nov 2008
    Posts
    21
    Quote Originally Posted by tabstop View Post
    Well ... but why? The memory leak is you not freeing things, like oh say, name and capital.
    Oh, I was a bit confused with what you said.

    Part of the issue was that I didn't give processListManager a return variable in main. Fixing it to
    Code:
    list = processListManager(list);
    so that's that. I'm still trying to see why I'm leaking though. Perhaps I'm overwriting my stack with scanf?

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,334
    Once you free everything (I just put that freeing of name and capital into the deleteNode so that it always got done whenever it needed to be done), the only memory leak, as your visual studio should tell you at the bottom there, is "Paris" and "France". Coincidentally, "France" and "Paris" is the only country/capital pair that appear in your data file twice.......

  7. #7
    Registered User
    Join Date
    Nov 2008
    Posts
    21
    Quote Originally Posted by tabstop View Post
    Once you free everything (I just put that freeing of name and capital into the deleteNode so that it always got done whenever it needed to be done), the only memory leak, as your visual studio should tell you at the bottom there, is "Paris" and "France". Coincidentally, "France" and "Paris" is the only country/capital pair that appear in your data file twice.......
    Oh wow you're right. When France comes up twice it just leaves that extra node. Thanks for your help again tabstop. I really appreciate it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 09-28-2006, 01:06 PM
  2. Multiple Linked Lists w/HeadNode
    By tofugirl in forum C Programming
    Replies: 12
    Last Post: 12-10-2005, 10:21 AM
  3. Linked list probs
    By mouse163 in forum C++ Programming
    Replies: 5
    Last Post: 02-19-2005, 05:41 PM
  4. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  5. Linked List of Linked lists Revisited.
    By Qui in forum C++ Programming
    Replies: 11
    Last Post: 04-11-2004, 09:45 PM