Hello everyone,

I have a program that intends to create a doubly linked list of structures, using the following header (q1.h):

typedef struct lNode* ListNodePtr;

typedef struct lNode {
    char* string;
    ListNodePtr next;
    ListNodePtr prev;
} ListNode;

This is my implementation:

#include "q1.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

ListNodePtr tail = 0;

ListNodePtr newNode(void);
ListNodePtr addNode(ListNodePtr h, char *w);
void printList(ListNodePtr h);
void deleteNode(ListNodePtr h, char *w);

ListNodePtr newNode(void)
{
	ListNodePtr n;
	n = (ListNodePtr)malloc(sizeof(ListNode));

	n->prev = 0;
	n->next = 0;

	return n;
}

ListNodePtr addNode(ListNodePtr h, char *w)
{
	ListNodePtr a;

	if (h == 0 && tail == 0)
	{
		a = newNode();

		h = a;
		h->string = w;
		h->next = tail;
		tail = a;
		tail->prev = h;
	}
	else
	{
		a = newNode();

		a->prev = tail;
		tail->next = a;
		
		a->next = 0;
		tail = a;
		tail->string = w;
	}

	return h;
}

void printList(ListNodePtr h)
{
	if (h == NULL)
		printf("List is empty\n");
	else
	{
		while (h != 0)
		{
			printf("%s\n", h->string);
			h = h->next;
		}
	}
}

void deleteNode(ListNodePtr h, char *w)
{
	ListNodePtr temp;
	temp = h;

	if (h == 0)
		printf("List is empty\n");
	else
	{
		while (temp != 0)
		{
			if (temp->string == w)
			{
				if (temp == h) //if node is first
				{
					h = h->next;
					h->prev = 0;
				}
				else
				{
					if (temp->next == 0) //if node is last
						temp->prev->next = 0;
					else
					{
						temp->prev->next = temp->next;
						temp->next->prev = temp->prev;
					}
					
					free(temp);			
				}	
			}

			temp = temp->next;
		}
	}
} 

int main(void)
{
	char s[50] = "";
	char command[10];
	char word[50];
	int scanfReturnValue;
	ListNodePtr head = 0;
	
	while ((fgets(s,50,stdin)) != 0)
	{
		scanfReturnValue = sscanf(s, "%s %s", command, word);

		if (scanfReturnValue == 2)
		{
			if (strcmp(command, "insert") == 0)
			{
				head = addNode(head, word);
			}
			else if (strcmp(command, "delete") == 0)
				deleteNode(head, word);	
		}
		else if (scanfReturnValue == 1)
		{
			if (strcmp(command, "print") == 0)
				printList(head);
		}
	}
	
	return 0;
}

My addNode method is supposed to add nodes to the end of the list, which it does, but it seems to change the enclosed string in each node to the last value added.

For example, here is a sample run:

insert 1
print
1
insert 2
print
2
2
insert 3
print
3
3
3

I have tested some of the values in the list, and have verified that any time we add more than one value in it, it will change the head's string to the last string entered.

Also, the deleteNode method will always give a segmentation fault when attempting to remove a node with a particular string:

insert 1
print
1
delete 1
Segmentation fault

Thanks in advance for any help that can be offered

You are not allocating memory for the string value. Each time you add a node you are setting the string pointer to the same place and that place would be the memory of char word[50] .
To fix you need to do a malloc of 50 bytes to n->string = (char *)malloc(50); in newNode() and use strncpy() in addNode() . This will give each node its own memory to store the values. Also in deleteNode() you want to not check the values of the pointer but the value of the string. Like if (strcmp(temp->string,w) == 0 ) then you have found the correct value to delete. You also need to look at how you are freeing memory and add another free if you allocate memory for the string. In deleteNode() you are modifying to value of the head but not saving it, h is a pointer value that you are setting if it is the first value. I now see that you are modifying a global var tail which needs adjustment when deleting. Here is what I get if I modify some of the things about.

$ ./a.out
insert 1
insert 2
insert 3
print
1
2
3
delete 1
delete 2
delete 3
print
List is empty
insert 4
print
List is empty

Notice that after I delete all nodes I/you have an issue adding nodes back in.

Edited 4 Years Ago by histrungalot: n/a

Hi histrungalot,

Thanks for pointing out those two big problems in my add and delete methods. I had spent a lot of time searching through old posts here and on the internet, but couldn't figure it out on my own.

In deleteNode() you are modifying to value of the head but not saving it, h is a pointer value that you are setting if it is the first value.

Yeah, originally I had the head declared global like the tail, but then changed it to be local to main while trying to figure out what was wrong with my code.

I have now switched it back to be global.

Notice that after I delete all nodes I/you have an issue adding nodes back in.

I resolved this problem by setting both the head and tail back to NULL after removing the last entry in the list. My newNode method is set up so that it only creates the first entry in an empty list if head and tail are both NULL.

My remaining problems now are related to memory management, as you referenced in your post.

If I delete entries in the list from the head on down in sequence, I get no memory leaks.

If I delete the tail, or any entry in between, I get an invalid read of 8 bytes.

Here is a sample run through valgrind to illustrate my point:

insert hello
insert small
insert world
delete small
==17303== Invalid read of size 8
==17303==    at 0x40092C: deleteNode (in /cse/home/cse13177/cse2031/asst2/q1)
==17303==    by 0x4009EE: main (in /cse/home/cse13177/cse2031/asst2/q1)
==17303==  Address 0x4c34128 is 8 bytes inside a block of size 24 free'd
==17303==    at 0x4A050D7: free (vg_replace_malloc.c:366)
==17303==    by 0x400927: deleteNode (in /cse/home/cse13177/cse2031/asst2/q1)
==17303==    by 0x4009EE: main (in /cse/home/cse13177/cse2031/asst2/q1)

Here is my latest code:

#include "q1.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

ListNodePtr head = 0;
ListNodePtr tail = 0;

ListNodePtr newNode(void);
void addNode(char *w);
void printList(ListNodePtr h);
void deleteNode(char *w);

ListNodePtr newNode(void)
{
	ListNodePtr n;
	n = (ListNodePtr)malloc(sizeof(ListNode));

	n->prev = 0;
	n->next = 0;
	n->string = (char *)malloc(50);

	return n;
}

void addNode(char *w)
{
	ListNodePtr a = newNode();
	strncpy(a->string,w,50);

	if (head == 0 && tail == 0)
	{
		head = a;
		head->next = tail;

		tail = a;
		tail->prev = head;
	}
	else
	{
		a->prev = tail;
		tail->next = a;
		
		a->next = 0;
		tail = a;
	}
}

void printList(ListNodePtr h)
{
	if (h == NULL)
		printf("List is empty\n");
	else
	{
		while (h != 0)
		{
			printf("%s\n", h->string);
			h = h->next;
		}
	}
}

void deleteNode(char *w)
{
	ListNodePtr temp;
	temp = head;

	if (head == 0)
		printf("List is empty\n");
	else
	{
		while (temp != 0)
		{
			if (strcmp(temp->string, w) == 0)
			{
				if (temp == head) //if node is first
				{

					if (head->next != 0)
					{
						head = head->next;
						head->prev = 0;
					}
					else
					{
						head = 0;
						tail = 0;
					}
				}
				else
				{
					if (temp->next == 0) //if node is last
					{
						temp->prev->next = 0;
						tail = temp->prev;
					}
					else
					{
						temp->prev->next = temp->next;
						temp->next->prev = temp->prev;
					}
					
					free(temp);			
				}	
			}

			temp = temp->next;
		}
	}
} 

int main(void)
{
	char s[50] = "";
	char command[10];
	char word[50];
	int scanfReturnValue;
	
	while ((fgets(s,50,stdin)) != 0)
	{
		scanfReturnValue = sscanf(s, "%s %s", command, word);

		if (scanfReturnValue == 2)
		{
			if (strcmp(command, "insert") == 0)
				addNode(word);
			else if (strcmp(command, "delete") == 0)
				deleteNode(word);	
		}
		else if (scanfReturnValue == 1)
		{
			if (strcmp(command, "print") == 0)
				printList(head);
		}
	}
	
	return 0;
}

Once you find the node you want to delete you call free(temp) but later you try to set the new temp value using the pointer that you just freed (invalid read error). If you only want to delete one then you could break . If you want to delete all the you will need to change how you delete a little more.
You also need to call free on the string memory before you free temp. Freeing temp will not free the memory of the string, that is the leak (8 bytes inside error).

First off, thanks again for your assistance on this.

Once you find the node you want to delete you call free(temp) but later you try to set the new temp value using the pointer that you just freed (invalid read error).

If I move free(temp) outside of the non-head deletion portion of deleteNode, I get a clean valgrind report.

For example:

else
	                       {
					if (temp->next == 0) //if node is last
					{
						temp->prev->next = 0;
						tail = temp->prev;
					}
					else
					{
						temp->prev->next = temp->next;
						temp->next->prev = temp->prev;
					}		
				}	
			}

			temp = temp->next;
		}

                free(temp);

You also need to call free on the string memory before you free temp. Freeing temp will not free the memory of the string, that is the leak (8 bytes inside error).

This is interesting: it is only when I put the line free(temp->string) before the free(temp) above, that I get the same invalid read of size 8, this time when attempting to delete any node.

insert c
insert is
insert fun
delete c
==3801== Invalid read of size 8
Like if (strcmp(temp->string,w) == 0 )

is generally a bad idea. Rather, you should check if temp->string is NULL instead. Also, it is good programming practice to initialize all pointers to NULL. Why? Take a look at this code snippet:

char *pSomeString;

if (pSomeString != NULL)
{
free(pSomeString);
}

Since pSomeString is not explicity initialized to NULL, there is a high possibility that it will not be NULL, but some junk address (let's say 0xFA763D5 for the sake of simplicity). Therefore, the check if (pSomeString != NULL) will fail, thus resulting in a possible segmentation fault.

Its about where and when you free the memory. Once you free the memory you can't use temp anymore (that is were you get the invalid reads). Your latest code with these lines added in the right spot. Theses are the only calls to free() . Remember for every malloc you must have a free.

free(temp->string);
free(temp);
break;

Here is the run.

valgrind ./a.out
==15469== Memcheck, a memory error detector
==15469== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==15469== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
==15469== Command: ./a.out
==15469== 
insert a
insert b
insert c
print
a
b
c
delete b
delete c
delete a
print
List is empty
==15469== 
==15469== HEAP SUMMARY:
==15469==     in use at exit: 0 bytes in 0 blocks
==15469==   total heap usage: 6 allocs, 6 frees, 186 bytes allocated
==15469== 
==15469== All heap blocks were freed -- no leaks are possible
==15469== 
==15469== For counts of detected and suppressed errors, rerun with: -v
==15469== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 12 from 8)

I know it sounds stupid, but when dealing with pointers you might want to draw a picture of what you think the code is doing. Do it for my example of (a, b, c) then delete.

HEAD --> node <--+  +---> node <--+  +---> node  <-- TAIL
           (next)---|--+    (next)---|--+    (next) --> null
  null <---(prev)   +-------(prev)   +-------(prev) 
           (string)[a]      (string)[b]      (string)[c]

Edited 4 Years Ago by histrungalot: n/a

Yes MonsieurPointer is correct, if any of temp, temp->string or w were null bad things would happen. And for that matter, anytime a pointer is accessed should be checked to see that it is not null (again provide that you always init pointers to null).

Hello everyone,

I have been able to complete the functionality of my assignment, with the exception of one requirement that I have not been able to figure out.

We are supposed to read in a line using fgets, but give it an initial buffer size of 4, which is declared in the header as:

#define INITIAL_BUFSIZE 4

The requirement is to use INITIAL_BUFIZE as a starting point for the buffer size in fgets, and then double the buffer size if it doesn't hold the entire line. We should continue doubling the buffer size until the whole line can be read.

I am not sure how to compare (in the while loop) the length of the string it was able to store using the allotted buffer size, and the actual length it needs to store. This is because fgets will only store as much as it can in the string, and discard the rest.

This is my pseudocode for the if statement in my while loop:

char s[50] = "";
int bufsize = INITIAL_BUFSIZE;

while ((fgets(s,bufsize,stdin)) != 0)
{
if (sizemanaged < sizeneeded)
{
bufsize *= 2;
}
}

I can get "sizemanaged" by using strlen(s), but I am not sure how to get "sizeneeded" of the input string.

Thanks ahead of time for any suggestions that can be offered

Edited 4 Years Ago by abed1986: n/a

Post the code you have now so we can see the context of what you are asking.

Edited 4 Years Ago by histrungalot: n/a

Post the code you have now so we can see the context of what you are asking.

To clarify what has been added, the current program adds the functionality to add at an index and add at specified intervals before or after a chosen word.

I left the requirement to "dynamically" expand the buffer size of the input to the very end, which is where I find myself now. To save your time, you don't really need to get a grasp of what's going in my new features to approach the problem I am facing in my main method (at the bottom).

#include "q1.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

ListNodePtr head = 0;
ListNodePtr tail = 0;
int length = 0;

ListNodePtr newNode(void);
void addNode(char *w);
void printList(ListNodePtr h);
void deleteNode(char *w);
int listLength(void);
void addIndexNode(char *w, int p);
void addPositionNode(char *w, int p, char *ba, char *s);

ListNodePtr newNode(void)
{
	ListNodePtr n;
	n = (ListNodePtr)malloc(sizeof(ListNode));

	n->prev = 0;
	n->next = 0;
	n->string = (char *)malloc(50);

	return n;
}

void addNode(char *w)
{
	ListNodePtr a = newNode();
	strncpy(a->string,w,50);

	if (head == 0 && tail == 0)
	{
		head = a;
		tail = a;
	}
	else
	{
		ListNodePtr temp = head;
		int flag = 0;

		while (temp != 0)
		{
			if (strcmp(temp->string, w) == 0)
			{
				flag = 1;
				break;
			}

			temp = temp->next;
		}

		if (!flag)
		{
			a->prev = tail;
			tail->next = a;
		
			a->next = 0;
			tail = a;
		}
	}
}

void printList(ListNodePtr h)
{
	if (h == NULL)
		printf("List is empty\n");
	else
	{
		while (h != 0)
		{
			printf("%s\n", h->string);
			h = h->next;
		}
	}
}

void deleteNode(char *w)
{
	ListNodePtr temp = head;

	if (head == 0)
		printf("List is empty\n");
	else
	{
		while (temp != 0)
		{
			if (strcmp(temp->string, w) == 0)
			{
				if (temp == head) //if node is first
				{

					if (head->next != 0)
					{
						head = head->next;
						head->prev = 0;
					}
					else
					{
						head = 0;
						tail = 0;
					}
				}
				else
				{
					if (temp->next == 0) //if node is last
					{
						temp->prev->next = 0;
						tail = temp->prev;
					}
					else
					{
						temp->prev->next = temp->next;
						temp->next->prev = temp->prev;
					}
		
					free(temp->string);
					free(temp);
					break;
				}	
			}

			temp = temp->next;
		}
	}
}

int listLength(void)
{
	length = 0;
	ListNodePtr temp = head;
	
	while (temp != 0)
	{
		temp = temp->next;
		length++;
	}

	return length;
}

void addIndexNode(char *w, int p)
{
	length = listLength();
	ListNodePtr new = newNode();
	strncpy(new->string,w,50);

	if (p == 1 && head == 0 && tail == 0)
	{
		head = new;
		tail = new;
	}
	else if (p > 0 && p <= length)
	{
		ListNodePtr old = head;
		int count = 1;

		while (old != 0)
		{
			if (count != p)
			{
				old = old->next;
				count++;
			}
			else
				break;		
		}

		if (old->prev == 0)
			head = new;
		else
			old->prev->next = new;

		new->prev = old->prev;
		new->next = old;
		old->prev = new;
	}
	else
		printf("Invalid index\n");
}

void addPositionNode(char *w, int p, char *ba, char *s)
{
	ListNodePtr new = newNode();
	strncpy(new->string,w,50);

	ListNodePtr find = head;
	int flag = 0;

	while (find != 0)
	{
		if (strcmp(find->string, w) == 0)
		{
			flag = 1;
			break;
		}

		find = find->next;
	}
	
	if (!flag)
	{
		if (head == 0 && tail == 0)
		{
			head = new;
			tail = new;	
		}
		else if (strcmp(ba, "after") == 0)
		{
			ListNodePtr temp = head;
			int match = 0;

			while (temp != 0)
			{
				if (strcmp(temp->string, s) == 0)
				{
					match = 1;
					break;
				}

				temp = temp->next;
			}

			if (!match)
				addNode(w);
			else
			{
				ListNodePtr old = temp;
				int count = 0;
					
				while (old != 0)
				{
					if (count < p)
					{
						old = old->next;
						count++;
					}
					else
						break;
				}

				if (old == 0)
					addNode(w);
				else
				{
					if (old->prev == 0)
						head = new;
					else
						old->prev->next = new;

					new->prev = old->prev;
					new->next = old;
					old->prev = new;
				}
			}		
		}
		else if (strcmp(ba, "before") == 0)
		{
			ListNodePtr temp = tail;
			int match = 0;

			while (temp != 0)
			{
				if (strcmp(temp->string, s) == 0)
				{
					match = 1;
					break;
				}

				temp = temp->prev;
			}

			if (!match)
			{
				new->next = head;
				head = new;	
			}
			else
			{
				ListNodePtr old = temp;
				int count = 0;

				while (old != 0)
				{
					if (count < p)
					{
						old = old->prev;
						count++;	
					}
					else
						break;
				}
		
				if (old == 0)
				{
					new->next = head;
					head = new;
				}
				else
				{
					new->prev = old;
					new->next = old->next;
					old->next = new;
				}
			}
		}
	}
} 

int main(void)
{
	char s[50] = "";
	char command[10];
	char word[50];
	char position[10];
	char word2[50];
	int scanfReturnValue;
	int index;
	int bufsize = INITIAL_BUFSIZE;
	
	while ((fgets(s,bufsize,stdin)) != 0)
	{
		int length = (int) strlen(s);
		if () //stuck on what to put here
		{
			bufsize *= 2;
		}

		scanfReturnValue = sscanf(s, "%s %s %d %s %s", command, word, &index, position, word2);

		if (scanfReturnValue == 2)
		{
			if (strcmp(command, "insert") == 0)
				addNode(word);
			else if (strcmp(command, "delete") == 0)
				deleteNode(word);	
		}
		else if (scanfReturnValue == 1)
		{
			if (strcmp(command, "print") == 0)
				printList(head);
		}
		else if (scanfReturnValue == 3)
		{
			if (strcmp(command, "insert") == 0)
				addIndexNode(word, index);	
		}
		else if (scanfReturnValue == 5)
		{
			if (strcmp(command, "insert") == 0)
				addPositionNode(word, index, position, word2); 
		}
	}
	
	return 0;
}

Edited 4 Years Ago by abed1986: n/a

Something like this. Also keep in mind that if the string you read in is greater than 50 it will be truncated by the strncpy(a->string,w,50); and a->string wouldn't have a null terminator.
Don't forget to add error checking for the mallocs.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INITIAL_BUFSIZE 4
int main(void)
{
   char *tmp,
           /* Make s dynamic */
           *s = (char *)malloc(INITIAL_BUFSIZE);
   int indx=0;
   int bufsize = INITIAL_BUFSIZE;
   while ((fgets(&s[indx],bufsize,stdin)) != 0)
   {
/*
DESCRIPTION
     The fgets() function reads at most one less than the number of 
     characters specified by n from the given stream and stores them
     in the string s.  Reading stops when a newline character is found, 
     at end-of-file or error.  --> The newline, if any, is retained. <-- 
     If any characters are read and there is no error, a `\0' character is
     appended to end the string.
*/
       if (/* Is something not there*/) 
       {
           bufsize *= 2;
           printf("Increasing to %d\n",bufsize);
           /* Keep track were you are */
           /* Get new memory          */
           /* Copy what you have      */
           /* Remove old memory       */
           /* Store new value         */
           continue;
       }
       indx = 0;
       printf("Read in: %s",s);
   }
   /* Don't forget to free */
   free(s);
   return 0;
}

I have implemented something that reallocates memory and expands the buffer size, as instructed, but I wasn't able to follow all of the points you mentioned.

First off, my code:

int main(void)
{
	char *tmp;
	char *s = (char *)malloc(INITIAL_BUFSIZE);

	if (s == 0)
	{
		printf("memory alloc failed!\n");
		exit(1);
	}

	char command[10];
	char word[50];
	char position[10];
	char word2[50];
	int scanfReturnValue;
	int index;
	int i = 0;
	int bufsize = INITIAL_BUFSIZE;
	
	while ((fgets((s+i),bufsize,stdin)) != 0)
	{
		if (strchr(s, '\n') == 0) //if the null terminating char is not found
		{
			bufsize *= 2;
			//keep track of where you were
			tmp = realloc(s, bufsize);

			if (tmp == 0)
			{
				printf("memory realloc failed!\n");
				free(s);
				s = 0;
				break;
			}
			else
			{
				printf("reallocated\n");
				s = tmp;
				tmp = 0;

				continue;
			}
			i = 0;
		}

		scanfReturnValue = sscanf(s, "%s %s %d %s %s", command, word, &index, position, word2);

		if (scanfReturnValue == 2)
		{
			if (strcmp(command, "insert") == 0)
				addNode(word);
			else if (strcmp(command, "delete") == 0)
				deleteNode(word);	
		}
		else if (scanfReturnValue == 1)
		{
			if (strcmp(command, "print") == 0)
				printList(head);
		}
		else if (scanfReturnValue == 3)
		{
			if (strcmp(command, "insert") == 0)
				addIndexNode(word, index);	
		}
		else if (scanfReturnValue == 5)
		{
			if (strcmp(command, "insert") == 0)
				addPositionNode(word, index, position, word2); 
		}
	}
	
	free(s);
	return 0;
}

Some things to note:

1) I am not allowed to use array notation in my assignment, which is why I changed &s[indx] to (s+indx).
2) I didn't know how to write code to "keep track of where you were", which is why I left the comment as a placeholder.
3) I also don't think I carried out the following three tasks properly:

/* Copy what you have */

/* Remove old memory */

/* Store new value */

Please don't hesitate to point out if what I am doing is wrong or insufficient.

Thanks for all your help

/* Copy what you have */
/* Remove old memory */

Is handled by the realloc

/* Store new value */

Is handled by setting s = tmp;

I didn't know how to write code to "keep track of where you were", which is why I left the comment as a placeholder.

Put this in.

if (strchr(s, '\n') == 0) //if the null terminating char is not found
		{
			bufsize *= 2;
			//keep track of where you were
                        i = strlen(s);     // <---- Why?
// ....
// ....
      // Need to reset the start index
      i = 0;  
      scanfReturnValue = sscanf(s, "%s %s %d %s %s", command, word, &index, position, word2);

If you don't keep track you will lose the start of the string.

I guess I am not too clear on where to use i. Because when I add just i = strlen(s), the program is no longer able to insert, even after space has been reallocated.

Without it, however, it works as needed.

Edited 4 Years Ago by abed1986: n/a

You just need to set and reset the value if i in the right spots. You had the i=0 inside the if (strchr(s, '\n') == 0) which is not what you want. You want it outside the if check.

int bufsize = INITIAL_BUFSIZE;

while ((fgets((s+i),bufsize,stdin)) != 0)
{
    if (strchr(s, '\n') == 0) //if the null terminating char is not found
    {
            bufsize *= 2;
            i = strlen(s);   // <----- Here to keep track of where you were
            tmp = realloc(s, bufsize);

            if (tmp == 0)
            {
                    printf("memory realloc failed!\n");
                    free(s);
                    s = 0;
                    break;
            }
            else
            {
                    s = tmp;
                    printf("reallocated\n");
                    tmp = 0;

                    continue;
            }
    }
    i = 0;  // <----- Here to reset

    scanfReturnValue = sscanf(s, "%s %s %d %s %s", command, word, &index, position, word2);

Oh, that was silly of me! That did it. I am actually coding in the vi editor, so I don't have any syntax highlighting.

I just need to clean up my program now, and it will be ready for submission, as far as I can tell. If I don't encounter any further problems, I will mark this thread as solved.

Thanks for your assistance throughout!

Lastly, remember that if you try to store a string larger than 50 characters it will get truncated and will not have a '\0' at the end.
Otherwise, it works and I hope you get a good grade!

Turns out I still have an issue with memory management, which is not too surprising since it is a fairly new topic to me.

Functionality-wise, the program works the way it is supposed to, and it passes my instructor's test case. I just receive all sorts of memory problems when running it through valgrind, and am at a loss at how to resolve them.

Here is my latest code:

#include "q1.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

ListNodePtr head = 0;
ListNodePtr tail = 0;
int length = 0;

ListNodePtr newNode(void);
void addNode(char *w);
void printList(ListNodePtr h);
void deleteNode(char *w);
void addPositionNode(char *w, int p, char *ba, char *s);

ListNodePtr newNode(void)
{
	ListNodePtr n;
	n = (ListNodePtr)malloc(sizeof(ListNode));

	if (n == 0)
	{
		printf("memory alloc failed!\n");
		exit(1);
	}

	n->prev = 0;
	n->next = 0;
	n->string = (char *)malloc(50);

	if (n->string == 0)
	{
		printf("memory alloc failed!\n");
		exit(1);
	}

	return n;
}

void addNode(char *w)
{
	ListNodePtr a = newNode();
	strncpy(a->string,w,50);

	if (head == 0 && tail == 0)
	{
		head = a;
		tail = a;
	}
	else
	{
		ListNodePtr temp = head;
		int flag = 0;

		while (temp != 0)
		{
			if (strcmp(temp->string, w) == 0)
			{
				flag = 1;
				break;
			}

			temp = temp->next;
		}

		if (!flag)
		{
			a->prev = tail;
			tail->next = a;
		
			a->next = 0;
			tail = a;
		}
	}
}

void printList(ListNodePtr h)
{
	if (h == NULL)
	{
		//printf("List is empty\n");
	}
	else
	{
		while (h != 0)
		{
			printf("%s\n", h->string);
			h = h->next;
		}
	}
}

void deleteNode(char *w)
{
	ListNodePtr temp = head;

	if (head == 0)
	{
		//printf("List is empty\n");
	}
	else
	{
		while (temp != 0)
		{
			if (strcmp(temp->string, w) == 0)
			{
				if (temp == head) //if node is first
				{

					if (head->next != 0)
					{
						head = head->next;
						head->prev = 0;
					}
					else
					{
						head = 0;
						tail = 0;
					}
				}
				else
				{
					if (temp->next == 0) //if node is last
					{
						temp->prev->next = 0;
						tail = temp->prev;
					}
					else
					{
						temp->prev->next = temp->next;
						temp->next->prev = temp->prev;
					}
		
					free(temp->string);
					free(temp);
					break;
				}	
			}

			temp = temp->next;
		}
	}
}

void addPositionNode(char *w, int p, char *ba, char *s)
{
	ListNodePtr new = newNode();
	strncpy(new->string,w,50);

	ListNodePtr find = head;
	int flag = 0;

	while (find != 0)
	{
		if (strcmp(find->string, w) == 0)
		{
			flag = 1;
			break;
		}

		find = find->next;
	}
	
	if (!flag)
	{
		if (head == 0 && tail == 0)
		{
			head = new;
			tail = new;	
		}
		else if (strcmp(ba, "after") == 0)
		{
			ListNodePtr temp = head;
			int match = 0;

			while (temp != 0)
			{
				if (strcmp(temp->string, s) == 0)
				{
					match = 1;
					break;
				}

				temp = temp->next;
			}

			if (!match)
				addNode(w);
			else
			{
				ListNodePtr old = temp;
				int count = 0;
					
				while (old != 0)
				{
					if (count < p)
					{
						old = old->next;
						count++;
					}
					else
						break;
				}

				if (old == 0)
					addNode(w);
				else
				{
					if (old->prev == 0)
						head = new;
					else
						old->prev->next = new;

					new->prev = old->prev;
					new->next = old;
					old->prev = new;
				}
			}		
		}
		else if (strcmp(ba, "before") == 0)
		{
			ListNodePtr temp = tail;
			int match = 0;

			while (temp != 0)
			{
				if (strcmp(temp->string, s) == 0)
				{
					match = 1;
					break;
				}

				temp = temp->prev;
			}

			if (!match)
			{
				//printf("no match\n");
				new->next = head;
				head = new;	
			}
			else
			{
				ListNodePtr old = temp;
				int count = 0;

				while (old != 0)
				{
					if (count < p)
					{
						old = old->prev;
						count++;	
					}
					else
						break;
				}
		
				if (old == 0)
				{
					//printf(temp->string);
					//printf("old is null\n");
					new->next = head;
					head = new;
				}
				else
				{
					//printf(old->string);
					new->prev = old;
					new->next = old->next;
					old->next = new;
				}
			}
		}
	}
} 

int main(void)
{
	char *tmp;
	char *s = (char *)malloc(INITIAL_BUFSIZE);

	if (s == 0)
	{
		printf("memory alloc failed!\n");
		exit(1);
	}

	char command[10];
	char word[50];
	char position[10];
	char word2[50];
	int scanfReturnValue;
	int index;
	int i = 0;
	int bufsize = INITIAL_BUFSIZE;
	
	while ((fgets((s+i),bufsize,stdin)) != 0)
	{
		if (strchr(s, '\n') == 0) //if the null terminating char is not found
		{
			bufsize *= 2;
			i = strlen(s);
			tmp = realloc(s, bufsize);

			if (tmp == 0)
			{
				printf("memory realloc failed!\n");
				free(s);
				s = 0;
				break;
			}
			else
			{
				//printf("reallocated\n");
				s = tmp;
				tmp = 0;

				continue;
			}
		}
		i = 0;

		scanfReturnValue = sscanf(s, "%s %s %d %s %s", command, word, &index, position, word2);

		if (scanfReturnValue == 2)
		{
			if (strcmp(command, "insert") == 0)
				addNode(word);
			else if (strcmp(command, "delete") == 0)
				deleteNode(word);	
		}
		else if (scanfReturnValue == 1)
		{
			if (strcmp(command, "print") == 0)
				printList(head);
		}
		else if (scanfReturnValue == 5)
		{
			if (strcmp(command, "insert") == 0)
				addPositionNode(word, index, position, word2); 
		}
	}
	
	free(s);
	return 0;
}

And here is a run through valgrind where, for the purpose of brevity, I have only copied the first memory error:

==22655== Command: q1
==22655==
insert a
==22655== Invalid write of size 1

Edited 4 Years Ago by abed1986: n/a

Yes, you are correct. I/we have an error.

int bufsize = INITIAL_BUFSIZE;

while ((fgets((s+i),bufsize-i,stdin)) != 0)   // <------ RIGHT HERE, need the -i

And the deleteNode() still needs some help.

while (temp != 0)
{
      if (strcmp(temp->string, w) == 0)
      {
              if (temp == head) //if node is first
              {
                      if (head->next != 0)
                      {
                              head = head->next;
                              head->prev = 0;
                      }
                      else
                      {
                              head = 0;
                              tail = 0;
                      }
              }
              else
              {
                      if (temp->next == 0) //if node is last
                      {
                              temp->prev->next = 0;
                              tail = temp->prev;
                      }
                      else
                      {
                              temp->prev->next = temp->next;
                              temp->next->prev = temp->prev;
                      }
              }
              free(temp->string);  // <------- RIGHT HERE
              free(temp);          // <------- RIGHT HERE
              break;               // <------- RIGHT HERE
      }

      temp = temp->next;
}

Fixed

$ valgrind --leak-check=full ./a.out
==7592== Memcheck, a memory error detector
==7592== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==7592== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
==7592== Command: ./a.out
==7592== 
insert a
reallocated to 8
reallocated to 16
insert 4
print
a
4
delete a
delete 4
==7592== 
==7592== HEAP SUMMARY:
==7592==     in use at exit: 0 bytes in 0 blocks
==7592==   total heap usage: 7 allocs, 7 frees, 152 bytes allocated
==7592== 
==7592== All heap blocks were freed -- no leaks are possible
==7592== 
==7592== For counts of detected and suppressed errors, rerun with: -v
==7592== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 12 from 8)

I have changed my delete function to the following, putting my memory frees at the very of if(strcmp(temp->string, w) == 0):

void deleteNode(char *w)
{
	ListNodePtr temp = head;

	if (head == 0)	//if the list is empty, then do nothing
	{
		//printf("List is empty\n");
	}
	else
	{
		while (temp != 0)
		{
			if (strcmp(temp->string, w) == 0)
			{
				if (temp == head) //if node is first, ..
				{

					if (head->next != 0)
					{	//..then make the next element the new head
						head = head->next;
						head->prev = 0;
					}
					else	
					{	
					//if deleting head makes the list empty, then initialize head and tail back to null (i.e. make empty list)
						head = 0;
						tail = 0;
					}
				}
				else
				{
					if (temp->next == 0) //if node is last, ..
					{
					//..then set up the new tail
						temp->prev->next = 0;
						tail = temp->prev;
					}
					else
					//if node isn't last, then link up its neighbours  
					{
						temp->prev->next = temp->next;
						temp->next->prev = temp->prev;
					}
				}

				//free up allocated memory
				free(temp->string);
				free(temp);
				break;	
			}

			temp = temp->next;
		}
	}
}

Using your test case, I am able to get:

total heap usage: 7 allocs, 6 frees, 176 bytes allocated

So, I am still not making one free somewhere. I believe it is because I am not freeing tmp (temporary char *) in main, but I have not figured out where to put the free.

I have to get to class now, but I just thought I would post this update here to keep you posted.

Edited 4 Years Ago by abed1986: n/a

I was doing Ctrl-C, but Ctrl-D gives me a clean valgrind check with all allocated memory freed!

I didn't even know about Ctrl-D, I will use that from now on instead.

BTW- I will definitely be coming to this forum for assistance in the future because of the nice help that I have received. I will also recommend it to other fellow practicing programmers.

I only wish that I had more reputation points to give to histrungalot!

Okay, so I have been running some more in-depth test cases with this, and there are still some big problems.

Here is a valgrind run that I just did, I put it in quote tags so I could put the problems in bold:

==27969== Command: q1
==27969==
insert java
print
java
insert pascal 1 after java
print
java
pascal
insert cobal 1 before pascal
print
java
cobal
pascal
insert basic
print
java
cobal
pascal
basic
insert cplusplus 2 before basic
print
java
cplusplus
cobal
pascal
basic
insert csharp 3 after java
print
java
csharp
pascal
basic
delete pascal
print
java
csharp
basic
delete csharp
print
java
basic
delete basic
print
java
delete java
print
==27969==
==27969== HEAP SUMMARY:
==27969== in use at exit: 222 bytes in 6 blocks
==27969== total heap usage: 19 allocs, 13 frees, 642 bytes allocated
==27969==
==27969== LEAK SUMMARY:
==27969== definitely lost: 48 bytes in 2 blocks
==27969== indirectly lost: 174 bytes in 4 blocks
==27969== possibly lost: 0 bytes in 0 blocks
==27969== still reachable: 0 bytes in 0 blocks
==27969== suppressed: 0 bytes in 0 blocks
==27969== Rerun with --leak-check=full to see details of leaked memory
==27969==
==27969== For counts of detected and suppressed errors, rerun with: -v
==27969== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 6)

I quit with Ctrl-D, and still had 6 frees less than allocs.

Here is my latest-code (with comments added):

#include "q1.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

ListNodePtr head = 0;
ListNodePtr tail = 0;
int length = 0;

ListNodePtr newNode(void);
void addNode(char *w);
void printList(ListNodePtr h);
void deleteNode(char *w);
void addPositionNode(char *w, int p, char *ba, char *s);

ListNodePtr newNode(void)
{
	ListNodePtr n;
	n = (ListNodePtr)malloc(sizeof(ListNode));	//allocate space for the new node

	if (n == 0)
	{
		printf("memory alloc failed!\n");
		exit(1);
	}

	n->prev = 0;
	n->next = 0;
	n->string = (char *)malloc(50);	//allocate enough space to store the string

	if (n->string == 0)
	{
		printf("memory alloc failed!\n");
		exit(1);
	}

	return n;
}

void addNode(char *w)
{
	ListNodePtr a = newNode();
	strncpy(a->string,w,50);	//copy in the passed string into the new node

	if (head == 0 && tail == 0)	//if list is empty, create a new list
	{
		head = a;
		tail = a;
	}
	else
	{
		ListNodePtr temp = head;
		int flag = 0;

		while (temp != 0)
		{
			if (strcmp(temp->string, w) == 0)
			//if the passed string is already present, ..
			{
				flag = 1;	//..then make the flag true
				break;
			}

			temp = temp->next;
		}

		if (!flag)
		//if flag is false, then insert the node at the end of the list
		{
			a->prev = tail;
			tail->next = a;
		
			a->next = 0;
			tail = a;
		}
	}
}

void printList(ListNodePtr h)
{
	if (h == NULL)
	{
		//printf("List is empty\n");
	}
	else	//if the list is non-empty, .. 
	{
		while (h != 0)	//..then print it out
		{
			printf("%s\n", h->string);
			h = h->next;
		}
	}
}

void deleteNode(char *w)
{
	ListNodePtr temp = head;

	if (head == 0)	//if the list is empty, then do nothing
	{
		//printf("List is empty\n");
	}
	else
	{
		while (temp != 0)
		{
			if (strcmp(temp->string, w) == 0)
			{
				if (temp == head) //if node is first, ..
				{

					if (head->next != 0)
					{	//..then make the next element the new head
						head = head->next;
						head->prev = 0;
					}
					else	
					{	
					//if deleting head makes the list empty, then initialize head and tail back to null (i.e. make empty list)
						head = 0;
						tail = 0;
					}
				}
				else
				{
					if (temp->next == 0) //if node is last, ..
					{
					//..then set up the new tail
						temp->prev->next = 0;
						tail = temp->prev;
					}
					else
					//if node isn't last, then link up its neighbours  
					{
						temp->prev->next = temp->next;
						temp->next->prev = temp->prev;
					}
				}

				//free up allocated memory
				free(temp->string);
				free(temp);
				break;	
			}

			temp = temp->next;
		}
	}
}

void addPositionNode(char *w, int p, char *ba, char *s)
{
	ListNodePtr new = newNode();
	strncpy(new->string,w,50);	//copy in the passed string into the new node

	ListNodePtr find = head;
	int flag = 0;

	while (find != 0)
	{
		if (strcmp(find->string, w) == 0)
		//if the string to be inserted is already present, ..
		{
			flag = 1;	//..then make the flag true
			break;
		}

		find = find->next;
	}
	
	if (!flag)	//if flag is false, then enter insertion phase
	{
		if (head == 0 && tail == 0)
		{
			head = new;
			tail = new;	
		}
		else if (strcmp(ba, "after") == 0)
		{
			ListNodePtr temp = head;
			int match = 0;

			while (temp != 0)
			{
				if (strcmp(temp->string, s) == 0)
				{
				//if the string to be matched is already present, ..
					match = 1;	//..then make the flag true
					break;
				}

				temp = temp->next;
			}

			if (!match)
			//if the string to be matched is not present, then add the new nodeto the end of the list
				addNode(w);
			else
			{
				ListNodePtr old = temp;
				int count = 0;
					
				while (old != 0)
				{
				//find the position of the node to be replaced
					if (count < p)
					{
						old = old->next;
						count++;
					}
					else
						break;
				}

				if (old == 0)
				//if we go over the end of the list, add the node to the end
					addNode(w);
				else
				{
				//if we can insert the node in the proper place, link it up to its new neighbours
					if (old->prev == 0)
						head = new;
					else
						old->prev->next = new;

					new->prev = old->prev;
					new->next = old;
					old->prev = new;
				}
			}		
		}
		else if (strcmp(ba, "before") == 0)
		{
			ListNodePtr temp = tail;
			int match = 0;

			while (temp != 0)
			{
				if (strcmp(temp->string, s) == 0)
				//if the string to be matched is already present, ..
				{
					match = 1;	//..then make the flag true
					break;
				}

				temp = temp->prev;
			}

			if (!match)
			{
			//if the string to be matched is not present, then insert the new node to the front of the list
				//printf("no match\n");
				new->next = head;
				head = new;	
			}
			else
			{
				ListNodePtr old = temp;
				int count = 0;

				while (old != 0)
				{
				//find the position of the node to be replaced
					if (count < p)
					{
						old = old->prev;
						count++;	
					}
					else
						break;
				}
		
				if (old == 0)
				{
				//if we go over the start of the list, add the new node to the front
					//printf(temp->string);
					//printf("old is null\n");
					new->next = head;
					head = new;
				}
				else
				{
				//if we can insert the node in the proper place, link it up to its new neighbours
					//printf(old->string);
					new->prev = old;
					new->next = old->next;
					old->next = new;
				}
			}
		}
	}
} 

int main(void)
{
	char *tmp;
	//allocate 4 bytes to a pointer to char
	char *s = (char *)malloc(INITIAL_BUFSIZE);

	if (s == 0)
	{
		printf("memory alloc failed!\n");
		exit(1);
	}

	char command[10];
	char word[50];
	char position[10];
	char word2[50];
	int scanfReturnValue;
	int index;
	int i = 0;	//keeps track of the end of cut-off strings
	int bufsize = INITIAL_BUFSIZE;
	
	while ((fgets((s+i),bufsize-i,stdin)) != 0)
	{
		if (strchr(s, '\n') == 0)
		{
		//if the null terminating char is not found (i.e. string could not fit), ..
			bufsize *= 2;	//..then double the size of the buffer
			i = strlen(s);	//keep track of where the string ended
			//copy what you already have into tmp, and remove the old memory
			tmp = realloc(s, bufsize);

			if (tmp == 0)
			{
				printf("memory realloc failed!\n");
				free(s);
				s = 0;
				break;
			}
			else
			{
			//if the memory realloc didn't fail, ..
				//printf("reallocated\n");
				s = tmp;	//..then store the new value into s
				tmp = 0;

				//go to the next iteration of the while loop
				continue;
			}
		}
		i = 0;	//reset back to 0

		scanfReturnValue = sscanf(s, "%s %s %d %s %s", command, word, &index, position, word2);

		if (scanfReturnValue == 2)
		{
			if (strcmp(command, "insert") == 0)
				addNode(word);
			else if (strcmp(command, "delete") == 0)
				deleteNode(word);	
		}
		else if (scanfReturnValue == 1)
		{
			if (strcmp(command, "print") == 0)
				printList(head);
		}
		else if (scanfReturnValue == 5)
		{
			if (strcmp(command, "insert") == 0)
				addPositionNode(word, index, position, word2); 
		}
	}
	
	free(s);
	return 0;
}

You need to make the "after" code look more like the "before" code. You are calling addNode in "after" but you have allocated the memory when you first came into the function. You also need to make "before" look like "after" in that in "after" you are checking for null pointer when you stitch the node in. Make addPositionNode work without calling addNode (that is part of your leak) and draw a picture of how you think you are inserting nodes and check that picture againest what the code is doing. I did those things and got a good valgrind run with your test above.

I removed the calls to addNode in "after" by replacing them with the code for adding to the end of a list. This is what is in "after" right now:

if (old == 0)
				//if we go over the end of the list, add the node to the end
				{
					new->prev = tail;
					tail->next = new;

					new->next = 0;
					tail = new;
				}
				else
				{
				//if we can insert the node in the proper place, link it up to its new neighbours
					if (old->prev == 0)
						head = new;
					else
						old->prev->next = new;

					new->prev = old->prev;
					new->next = old;
					old->prev = new;
				}

You also need to make "before" look like "after" in that in "after" you are checking for null pointer when you stitch the node in.

Are you referring to the line "if (old->prev == 0)"? Because I have tried to use that, along with:

new->prev = old;
					new->next = old->next;
					old->next = new;

but that doesn't seem to solve the problem.

Edited 4 Years Ago by abed1986: n/a

Post the current addPositionNode.

void addPositionNode(char *w, int p, char *ba, char *s)
{
	ListNodePtr new = newNode();
	strncpy(new->string,w,50);	//copy in the passed string into the new node

	ListNodePtr find = head;
	int flag = 0;

	while (find != 0)
	{
		if (strcmp(find->string, w) == 0)
		//if the string to be inserted is already present, ..
		{
			flag = 1;	//..then make the flag true
			break;
		}

		find = find->next;
	}
	
	if (!flag)	//if flag is false, then enter insertion phase
	{
		if (head == 0 && tail == 0)
		{
			head = new;
			tail = new;	
		}
		else if (strcmp(ba, "after") == 0)
		{
			ListNodePtr temp = head;
			int match = 0;

			while (temp != 0)
			{
				if (strcmp(temp->string, s) == 0)
				{
				//if the string to be matched is already present, ..
					match = 1;	//..then make the flag true
					break;
				}

				temp = temp->next;
			}

			if (!match)
			//if the string to be matched is not present, then add the new node to the end of the list
			{
				new->prev = tail;
				tail->next = new;

				new->next = 0;
				tail = new;	
			}
			else
			{
				ListNodePtr old = temp;
				int count = 0;
					
				while (old != 0)
				{
				//find the position of the node to be replaced
					if (count < p)
					{
						old = old->next;
						count++;
					}
					else
						break;
				}

				if (old == 0)
				//if we go over the end of the list, add the node to the end
				{
					new->prev = tail;
					tail->next = new;

					new->next = 0;
					tail = new;
				}
				else
				{
				//if we can insert the node in the proper place, link it up to its new neighbours
					if (old->prev == 0)
						head = new;
					else
						old->prev->next = new;

					new->prev = old->prev;
					new->next = old;
					old->prev = new;
				}
			}		
		}
		else if (strcmp(ba, "before") == 0)
		{
			ListNodePtr temp = tail;
			int match = 0;

			while (temp != 0)
			{
				if (strcmp(temp->string, s) == 0)
				//if the string to be matched is already present, ..
				{
					match = 1;	//..then make the flag true
					break;
				}

				temp = temp->prev;
			}

			if (!match)
			{
			//if the string to be matched is not present, then insert the new node to the front of the list
				//printf("no match\n");
				new->next = head;
				head->prev = new;
				head = new;	
			}
			else
			{
				ListNodePtr old = temp;
				int count = 0;

				while (old != 0)
				{
				//find the position of the node to be replaced
					if (count < p)
					{
						old = old->prev;
						count++;	
					}
					else
						break;
				}
		
				if (old == 0)
				{
				//if we go over the start of the list, add the new node to the front
					//printf(temp->string);
					//printf("old is null\n");
					new->next = head;
					head->prev = new;
					head = new;
				}
				else
				{
				//if we can insert the node in the proper place, link it up to its new neighbours
					
					new->prev = old;
					new->next = old->next;
					old->next = new;
				}
			}
		}
	}
}

Lines 145-152 in function should look like:

else   // <---- Line 145 in addPositionNode function
{
    // You did something similar in the after function.  That what I meant about 
    // making "before" look like "after" 
    if (old->next == 0)
       tail = new;
    else
       old->next->prev = new;
    new->prev = old;
    new->next = old->next;
    old->next = new;
}
valgrind ./a.out
==30198== Memcheck, a memory error detector
==30198== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==30198== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
==30198== Command: ./a.out
==30198== 
insert java
insert pascal 1 after java
insert cobal 1 before pascal
insert basic
insert cplus 2 before basic
insert csharp 3 after java
print
java
cobal
cplus
csharp
pascal
basic
delete pascal
delete csharp
delete basic
delete java
print
cobal
cplus
delete cobal
delete cplus
print
==30198== 
==30198== HEAP SUMMARY:
==30198==     in use at exit: 0 bytes in 0 blocks
==30198==   total heap usage: 16 allocs, 16 frees, 432 bytes allocated
==30198== 
==30198== All heap blocks were freed -- no leaks are possible
==30198== 
==30198== For counts of detected and suppressed errors, rerun with: -v
==30198== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 12 from 8)
This question has already been answered. Start a new discussion instead.