Programming Forums > Application Development > C

nnxion · Mar 17th, 2006, 6:37 AM

Well, I created a linked list. I would like to know if at adding, when I pass char * value, that value doesn't run out of scope and get overwritten. I am passing the value as parameter, so doesn't that run out of scope? If it does, then I got lucky, and my memory didn't get overwritten when testing.
Is there anything else I missed?

(Toggle Plain Text)

/* llnode.c */
#include <stdio.h>
#include <stdlib.h>

struct node
{
	char * data;
	struct node *next;
}*head, *tail;

/* add a node to the end */
void node_add(char * value)
{
	struct node *new_node = malloc(sizeof(struct node));

	if(head == NULL)
		head = new_node;

	new_node->data = value; <<<<<<<< Is there a problem HERE?
	new_node->next = NULL;

	if(tail != NULL)
		tail->next = new_node;

	tail = new_node;
}

/* free the first node */
void node_free_first()
{
    struct node *tmp;

	if (head != NULL)
	{
		if(head == tail)
			tail = NULL;

		tmp = head->next;
		free(head);
		head = tmp;
	}
}

/* free the whole list (all nodes) */
void list_free()
{
	struct node *tmp;

	while (head != NULL)
	{
		if(head == tail)
			tail = NULL;

		tmp = head->next;
		free(head);
		head = tmp;
	}
}

/* returns the length of the list */
int list_length()
{
	struct node * current = head;
	int count = 0;

	while(current != NULL)
	{
		count++;
		current = current->next;
	}
	return count;
}

void list_print()
{
	struct node * current = head;
	while (current != NULL)
	{
		printf("%s\n", current->data);
		current = current->next;
	}
}

main()
{
	node_add("hello");
	node_add("world");
	list_print();
	list_free();
}

Polyphemus_ · Mar 17th, 2006, 6:51 AM

I don't know what you mean by overwriting, because both variables (new_node->data and value) are the same type.

I think this piece of code is wrong, though:

(Toggle Plain Text)

	if(tail != NULL)
		tail->next = new_node;

	tail = new_node;
}

My guess is that you want this code:

(Toggle Plain Text)

if(tail != NULL)
	tail->next = new_node;
else
	tail = new_node;

DaWei · Mar 17th, 2006, 6:53 AM

(Toggle Plain Text)

	new_node->data = value; <<<<<<<< Is there a problem HERE?

This is not a problem. When you get the new node, it is allocated from the heap and a pointer is returned (new_node). You use the pointer to put information into the node. Perfectly valid. You then set 'tail' to new_node, which preserves the address of that heap memory. Then you return. "new_node" goes out of scope and 'disappears'. The memory on the heap, though, the node, is yours until you return it. It can be found via 'tail', for a while, or by the 'next' pointer in whichever node precedes this one (could be root, as well, at some point). You have 'lost' the original storage location pointer, but you have preserved the storage location elsewhere.

nnxion · Mar 17th, 2006, 7:09 AM

@Polyphemus: It's correct as I have it. If tail IS null (which it is before the first node is added) then it never gets anything else.

Thank you for looking though, appreciate it.

@DaWei: Thanks David, you're great.

The Dark · Mar 17th, 2006, 7:14 AM

Polyphemus_: nnixion's code is right. You want to set the tail to the new node in all cases - the new node is the last node in the list after appending.

nnixion:

(Toggle Plain Text)

	new_node->data = value; <<<<<<<< Is there a problem HERE?

That line of code isn't a problem as long as everyone who uses the linked list knows that the data pointed to by the pointer they pass in needs to exist for as long as it is in the linked list.
For example

(Toggle Plain Text)

int addHello();
{
  char temp[20];
  strcpy (temp, "hello");
  node_add(temp);         // <-- problem here as temp will go out of scope.
}

int main(int argc, char *argv[])
{
	addHello();
	node_add("world");
	list_print();
	list_free();
}

nnxion · Mar 17th, 2006, 7:34 AM

Thanks Peter. One more thing:

(Toggle Plain Text)

void someFunction(char * value)
{
	// value doesn't get referenced here so goes out of scope/deleted.
}

(Toggle Plain Text)

char * globalvalue = NULL;
void someFunction(char * value)
{
	// value gets referenced here so does not go out of scope/deleted.
	globalvalue = value;
}

Am I right?

DaWei · Mar 17th, 2006, 8:25 AM

You're correct, but global values, while not 'evil', are usually not a good idea. When you design your software, you can usually determine or 'see' the scope some variable is needed in. You declare it at the outermost scope requiring visibility. Then, if you need to modify it down in a nest somewhere, you pass a pointer (or, in C++, possibly a reference) and modify it. As with everything else, one needs to begin with a large overview and work down into the details. This is top-down design and works somewhat like making a really detailed PERT chart for the next couple years of activity. Sometimes, in executing the design, you'll need to go do some bottom-up implementation. In other words, you may need an actual low-level function sometimes, when a stub won't do. Those are my views, anyway, and they woiked fer me.

grumpy · Mar 17th, 2006, 4:40 PM

nnxion, Dawei's already answered your question. I'll answer in another way.

Your code is OK as long as the strings you pass to add_node() continue to exist at least as long as the nodes you create. In your example, they do. The strings are literals (i.e. constants) within main(), used within main(), and you clear the list before main() returns.

You would have problems if you did something like this;

(Toggle Plain Text)

/*   your list_ functions */

void get_number_node()
{
      static int value = 0;
      char buffer[10];
      sprintf(buffer, "%d", ++value);
      node_add(buffer);
}

int main()
{
        int i;
	node_add("hello");
	node_add("world");
        for (i = 0; i < 5; ++i)
            get_number_node();
	list_print();
	list_free();
}

as the pointer stored to your node refers to non-existent data when control is returned to main(). The result of this is that list_print() would give undefined behaviour.

The actual problem, in this example, is that add_number_node() function is violating a key assumption in your list functions: that the string passed to add_node() continues to exist at least as long as the node does.

Interestingly enough, making buffer static in add_number_node() avoids the undefined behaviour, but all of what I'm calling the "number nodes" in this example would have the same value (as the buffer would be reused). The program is then predictable, but not necessarily what is intended when adding multiple "number nodes".

DaWei · Mar 17th, 2006, 9:03 PM

There ain't no free beer. Not even green beer on St. Patrick's day. You could write a program to read some file by hard-coded name, and if someone renames the file, you're screwed. Murphy says you're gonna get hurt.

Mar 17th, 2006, 6:37 AM	#1
nnxion Programming Guru Join Date: Jun 2005 Location: elemental plane Posts: 1,429 Rep Power: 5	linked list problemos? Well, I created a linked list. I would like to know if at adding, when I pass char * value, that value doesn't run out of scope and get overwritten. I am passing the value as parameter, so doesn't that run out of scope? If it does, then I got lucky, and my memory didn't get overwritten when testing. Is there anything else I missed? (Toggle Plain Text) /* llnode.c / #include <stdio.h> #include <stdlib.h> struct node { char data; struct node next; }head, tail; / add a node to the end / void node_add(char value) { struct node new_node = malloc(sizeof(struct node)); if(head == NULL) head = new_node; new_node->data = value; <<<<<<<< Is there a problem HERE? new_node->next = NULL; if(tail != NULL) tail->next = new_node; tail = new_node; } / free the first node / void node_free_first() { struct node tmp; if (head != NULL) { if(head == tail) tail = NULL; tmp = head->next; free(head); head = tmp; } } /* free the whole list (all nodes) / void list_free() { struct node tmp; while (head != NULL) { if(head == tail) tail = NULL; tmp = head->next; free(head); head = tmp; } } /* returns the length of the list / int list_length() { struct node current = head; int count = 0; while(current != NULL) { count++; current = current->next; } return count; } void list_print() { struct node * current = head; while (current != NULL) { printf("%s\n", current->data); current = current->next; } } main() { node_add("hello"); node_add("world"); list_print(); list_free(); } /* llnode.c / #include <stdio.h> #include <stdlib.h> struct node { char data; struct node next; }head, tail; / add a node to the end / void node_add(char value) { struct node new_node = malloc(sizeof(struct node)); if(head == NULL) head = new_node; new_node->data = value; <<<<<<<< Is there a problem HERE? new_node->next = NULL; if(tail != NULL) tail->next = new_node; tail = new_node; } / free the first node / void node_free_first() { struct node tmp; if (head != NULL) { if(head == tail) tail = NULL; tmp = head->next; free(head); head = tmp; } } /* free the whole list (all nodes) / void list_free() { struct node tmp; while (head != NULL) { if(head == tail) tail = NULL; tmp = head->next; free(head); head = tmp; } } /* returns the length of the list / int list_length() { struct node current = head; int count = 0; while(current != NULL) { count++; current = current->next; } return count; } void list_print() { struct node * current = head; while (current != NULL) { printf("%s\n", current->data); current = current->next; } } main() { node_add("hello"); node_add("world"); list_print(); list_free(); } __________________ "Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for." -- Socrates

Mar 17th, 2006, 6:51 AM	#2
Polyphemus_ Expert Programmer Join Date: Aug 2005 Location: Rotterdam, the Netherlands Posts: 942 Rep Power: 4	I don't know what you mean by overwriting, because both variables (new_node->data and value) are the same type. I think this piece of code is wrong, though: (Toggle Plain Text) if(tail != NULL) tail->next = new_node; tail = new_node; } if(tail != NULL) tail->next = new_node; tail = new_node; } My guess is that you want this code: (Toggle Plain Text) if(tail != NULL) tail->next = new_node; else tail = new_node; if(tail != NULL) tail->next = new_node; else tail = new_node;

Mar 17th, 2006, 6:53 AM	#3
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	(Toggle Plain Text) new_node->data = value; <<<<<<<< Is there a problem HERE? new_node->data = value; <<<<<<<< Is there a problem HERE? This is not a problem. When you get the new node, it is allocated from the heap and a pointer is returned (new_node). You use the pointer to put information into the node. Perfectly valid. You then set 'tail' to new_node, which preserves the address of that heap memory. Then you return. "new_node" goes out of scope and 'disappears'. The memory on the heap, though, the node, is yours until you return it. It can be found via 'tail', for a while, or by the 'next' pointer in whichever node precedes this one (could be root, as well, at some point). You have 'lost' the original storage location pointer, but you have preserved the storage location elsewhere. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Mar 17th, 2006, 7:09 AM	#4
nnxion Programming Guru Join Date: Jun 2005 Location: elemental plane Posts: 1,429 Rep Power: 5	@Polyphemus: It's correct as I have it. If tail IS null (which it is before the first node is added) then it never gets anything else. Thank you for looking though, appreciate it. @DaWei: Thanks David, you're great. __________________ "Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for." -- Socrates

Mar 17th, 2006, 7:14 AM	#5
The Dark Expert Programmer Join Date: Jun 2005 Posts: 825 Rep Power: 4	Polyphemus_: nnixion's code is right. You want to set the tail to the new node in all cases - the new node is the last node in the list after appending. nnixion: (Toggle Plain Text) new_node->data = value; <<<<<<<< Is there a problem HERE? new_node->data = value; <<<<<<<< Is there a problem HERE? That line of code isn't a problem as long as everyone who uses the linked list knows that the data pointed to by the pointer they pass in needs to exist for as long as it is in the linked list. For example (Toggle Plain Text) int addHello(); { char temp[20]; strcpy (temp, "hello"); node_add(temp); // <-- problem here as temp will go out of scope. } int main(int argc, char argv[]) { addHello(); node_add("world"); list_print(); list_free(); } int addHello(); { char temp[20]; strcpy (temp, "hello"); node_add(temp); // <-- problem here as temp will go out of scope. } int main(int argc, char argv[]) { addHello(); node_add("world"); list_print(); list_free(); }

Mar 17th, 2006, 7:34 AM	#6
nnxion Programming Guru Join Date: Jun 2005 Location: elemental plane Posts: 1,429 Rep Power: 5	Thanks Peter. One more thing: (Toggle Plain Text) void someFunction(char * value) { // value doesn't get referenced here so goes out of scope/deleted. } void someFunction(char * value) { // value doesn't get referenced here so goes out of scope/deleted. } (Toggle Plain Text) char * globalvalue = NULL; void someFunction(char * value) { // value gets referenced here so does not go out of scope/deleted. globalvalue = value; } char * globalvalue = NULL; void someFunction(char * value) { // value gets referenced here so does not go out of scope/deleted. globalvalue = value; } Am I right? __________________ "Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for." -- Socrates

Mar 17th, 2006, 8:25 AM	#7
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	You're correct, but global values, while not 'evil', are usually not a good idea. When you design your software, you can usually determine or 'see' the scope some variable is needed in. You declare it at the outermost scope requiring visibility. Then, if you need to modify it down in a nest somewhere, you pass a pointer (or, in C++, possibly a reference) and modify it. As with everything else, one needs to begin with a large overview and work down into the details. This is top-down design and works somewhat like making a really detailed PERT chart for the next couple years of activity. Sometimes, in executing the design, you'll need to go do some bottom-up implementation. In other words, you may need an actual low-level function sometimes, when a stub won't do. Those are my views, anyway, and they woiked fer me. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Mar 17th, 2006, 4:40 PM	#8
grumpy Programming Guru Join Date: Jun 2005 Location: Adelaide, South Australia Posts: 1,209 Rep Power: 5	nnxion, Dawei's already answered your question. I'll answer in another way. Your code is OK as long as the strings you pass to add_node() continue to exist at least as long as the nodes you create. In your example, they do. The strings are literals (i.e. constants) within main(), used within main(), and you clear the list before main() returns. You would have problems if you did something like this; (Toggle Plain Text) /* your list_ functions / void get_number_node() { static int value = 0; char buffer[10]; sprintf(buffer, "%d", ++value); node_add(buffer); } int main() { int i; node_add("hello"); node_add("world"); for (i = 0; i < 5; ++i) get_number_node(); list_print(); list_free(); } / your list_ functions */ void get_number_node() { static int value = 0; char buffer[10]; sprintf(buffer, "%d", ++value); node_add(buffer); } int main() { int i; node_add("hello"); node_add("world"); for (i = 0; i < 5; ++i) get_number_node(); list_print(); list_free(); } as the pointer stored to your node refers to non-existent data when control is returned to main(). The result of this is that list_print() would give undefined behaviour. The actual problem, in this example, is that add_number_node() function is violating a key assumption in your list functions: that the string passed to add_node() continues to exist at least as long as the node does. Interestingly enough, making buffer static in add_number_node() avoids the undefined behaviour, but all of what I'm calling the "number nodes" in this example would have the same value (as the buffer would be reused). The program is then predictable, but not necessarily what is intended when adding multiple "number nodes".

Mar 17th, 2006, 9:03 PM	#9
DaWei Resident Grouch Join Date: Jun 2005 Posts: 6,453 Rep Power: 10	There ain't no free beer. Not even green beer on St. Patrick's day. You could write a program to read some file by hard-coded name, and if someone renames the file, you're screwed. Murphy says you're gonna get hurt. __________________ Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code. Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Programming Forums > Application Development > C

linked list problemos?