warner@weiss.cs.unc.edu (Byron Warner) (03/27/91)
I was wondering, is it safe to unallocate a singly linked list like this:
struct list *head; /* top of list */
struct list *ptr = head;
while (ptr){
free(ptr);
ptr = ptr->next;
}
I am not sure if I can assume that
the value of ptr will not be corrupted
after it is freed.
--
----
Byron F. Warner warner@cs.unc.edu
University of North Carolina - Chapel Hill Computer Sci Department
"The opinions expressed here should be yours."
phil@ux1.cso.uiuc.edu (Phil Howard KA9WGN) (03/27/91)
warner@weiss.cs.unc.edu (Byron Warner) writes: >I was wondering, is it safe to unallocate a singly linked list like this: > >struct list *head; /* top of list */ >struct list *ptr = head; >while (ptr){ > free(ptr); > ptr = ptr->next; >} > >I am not sure if I can assume that >the value of ptr will not be corrupted >after it is freed. The value of "ptr" won't be corrupted, but that value is useless after you have done the "free(ptr)". What can be corrupted is "ptr->next" since that memory is now deallocated. It might appear to work on your system, but it cannot be trusted and is certainly wrong. Try this: struct list *head; /* top of list */ struct list *ptr = head; while (ptr){ register struct list *temp_ptr; temp_ptr = ptr->next; free(ptr); ptr = temp_ptr; } -- /***************************************************************************\ / Phil Howard -- KA9WGN -- phil@ux1.cso.uiuc.edu \ \ Lietuva laisva -- Brivu Latviju -- Eesti vabaks / \***************************************************************************/
dave@cs.arizona.edu (Dave Schaumann) (03/27/91)
In article <2636@borg.cs.unc.edu> warner@weiss.cs.unc.edu (Byron Warner) writes: >I was wondering, is it safe to unallocate a singly linked list like this: > >struct list *head; /* top of list */ >struct list *ptr = head; >while (ptr){ > free(ptr); > ptr = ptr->next; >} Who knows? Who cares, when it's so easy to get it right? struct list *head, *p, *q ; for( p = head ; p != NULL ; p = q ) { q = p->next ; free(p) } -- Dave Schaumann | dave@cs.arizona.edu | Short .sig's rule!
bhoughto@hopi.intel.com (Blair P. Houghton) (03/27/91)
In article <2636@borg.cs.unc.edu> warner@weiss.cs.unc.edu (Byron Warner) writes: >I was wondering, is it safe to unallocate a singly linked list like this: >struct list *head; /* top of list */ >struct list *ptr = head; >while (ptr){ > free(ptr); > ptr = ptr->next; >} Nope. Something will go wrong, and you can define the limits of its wrongness, and you can define prevention (I.e., if nothing _can_ go wrong, nothing will.) Rest assured that halfway through that list someone will fire up xtrek and while your program is swapped out the system will notice that suddenly there's half a megabyte you don't currently have malloc'ed... --Blair "You obviously know how, so I won't bore you with the correct method, unless someone wants to get into a STYLE WAR..."
warner@tsc.cs.unc.edu (Byron Warner) (03/28/91)
Thanks to all of you who responded, to my post.
To summarize:
In general it is not safe to assume anything about the
contents of freed data. Most people suggested using a
temporary variable, ie:
struct list *next;
while (ptr) { next = ptr->next; free(ptr); ptr = next; }
but also some one suggested recursion:
void listfree(List *l) {
if (l->next != NULL)
listfree(l->next);
free(l->data);
free(l);
}
--
----
Byron F. Warner warner@cs.unc.edu
University of North Carolina - Chapel Hill Computer Sci Department
"The opinions expressed here should be yours."
henry@zoo.toronto.edu (Henry Spencer) (03/28/91)
In article <2636@borg.cs.unc.edu> warner@weiss.cs.unc.edu (Byron Warner) writes: >I was wondering, is it safe to unallocate a singly linked list like this: >while (ptr){ > free(ptr); > ptr = ptr->next; >} No. This code is unsafe for three reasons. The first is that the free() may destroy the contents of the memory ptr points at, so ptr->next may no longer have its old value. (Some existing implementations leave the memory alone, and some programmers have carelessly come to rely on this, but that is unwise.) The second, more subtle, is that even the attempt to reference ptr->next may cause disaster, because the memory might not even be there any more -- it might have been given back to the operating system, so any reference to it will cause a trap. Third and subtlest, it is not entirely clear that you can even examine the value of the pointer safely when it no longer points to anything, although it would take a very strange machine to get you in trouble on this one. >I am not sure if I can assume that >the value of ptr will not be corrupted >after it is freed. The free() can't alter the value of ptr itself, but as mentioned above, there is some possibility that it will be unsafe to use that value, and considerable possibility that it won't do what you want. The right way to do this is to tuck the value of ptr->next away in a temporary variable before doing the free(). -- "[Some people] positively *wish* to | Henry Spencer @ U of Toronto Zoology believe ill of the modern world."-R.Peto| henry@zoo.toronto.edu utzoo!henry
gwyn@smoke.brl.mil (Doug Gwyn) (03/28/91)
In article <2636@borg.cs.unc.edu> warner@weiss.cs.unc.edu (Byron Warner) writes: > free(ptr); > ptr = ptr->next; >I am not sure if I can assume that >the value of ptr will not be corrupted >after it is freed. It's not ptr, but rather the region of storage to which ptr points, that can be clobbered by the call to free(). Indeed I made this mistake once (in an early release of my dirent implementation). I knew better, I just forgot.
bhoughto@hopi.intel.com (Blair P. Houghton) (03/28/91)
In article <2655@borg.cs.unc.edu> warner@tsc.cs.unc.edu (Byron Warner) writes: >struct list *next; >while (ptr) { next = ptr->next; free(ptr); ptr = next; } Quul. >but also some one suggested recursion: >void listfree(List *l) { > if (l->next != NULL) > listfree(l->next); > free(l->data); > free(l); > } Yes, this is, in the lispest of all possible worlds, the Way To Go, but here in this one we're constrained by time and space. Instead of declaring a word (`next'), you've declared a library element (`listfree') requiring compilation, testing, documentation, debugging, and any number of ancillary maintenances, with the net effect that you've quintupled the complexity of the code and saved automatic allocation of a lousy word. I got bit by a tightly-looping recursion just last week; it had to operate on such a large list that it clogged the stack frame and crowbarred me off the CPU. It should be obvious that in while freeing a list with elements that consist of a few bytes each you end up jamming possibly hundreds of bytes per element onto the stack... BUT if you just use the temporary, you increase by one word and it's all downhill from there; no stack pops, no rlimits, no nothing; plus you gain dramatically in speed, since the loop can spin with the pc, but the recursion has to slog blocks around just to get to the next list-element. (No, it doesn't really, but just pushing and popping stack-pointers is huge overhead compared to assigning temps...) --Blair "This did call for a discussion, didn't it?"
jludwig@pro-grouch.cts.com (Jerry Ludwig) (03/28/91)
In-Reply-To: message from dave@cs.arizona.edu Who cares - doubtful. Who knows - me. I have watched the Microsoft C 5.1 compiler change the value of a pointer during a free(pntr) operation. While I have no idea if this is a widespread approach (and I think it most likely isn't) approach ( and think it prabably isn't) Don't count on free leaving your pointers alone. Jerry. ---- ProLine: jludwig@pro-grouch Internet: jludwig@pro-grouch.cts.com UUCP: crash!pro-grouch!jludwig ARPA: crash!pro-grouch!jludwig@nosc.mil
scott@bbxsda.UUCP (Scott Amspoker) (03/28/91)
In article <548@bria> uunet!bria!mike writes: > while ( ptr != NULL ) { > >Personally, I think that the [not shown] `while' is not very nice; you should >explicitly test for NULL -- after all, a pointer is not an integer, >right? ...and neither is a '0' when compare to a pointer which is what is implied by 'while (ptr)'. The C compiler will assume a compare to a null pointer in such a case. -- Scott Amspoker | Touch the peripheral convex of every Basis International, Albuquerque, NM | kind, then various kinds of blaming (505) 345-5232 | sound can be sent forth. unmvax.cs.unm.edu!bbx!bbxsda!scott | - Instructions for a little box that | blurts out obscenities.
dgil@pa.reuter.COM (Dave Gillett) (04/02/91)
In <2636@borg.cs.unc.edu> warner@weiss.cs.unc.edu (Byron Warner) writes: >struct list *head; /* top of list */ >struct list *ptr = head; >while (ptr){ > free(ptr); > ptr = ptr->next; >} Even if the value of ptr is not changed by free(), you have absolutely no guarantee that the value at ptr->next is still valid. Some implementations of free() can corrupt data in the freed block; even if this is not true, in some environments that block might get allocated to somebody else before your dereference of ptr. You need another pointer: struct list *head, *p1; struct list *ptr = head; while (ptr){ p1 = ptr->next; free (ptr); ptr = p1; } Dave
scc@rlgvax.Reston.ICL.COM (Stephen Carlson) (04/03/91)
In article <846@saxony.pa.reuter.COM> dgil@pa.reuter.COM (Dave Gillett) writes: >In <2636@borg.cs.unc.edu> warner@weiss.cs.unc.edu (Byron Warner) writes: >> free(ptr); > Even if the value of ptr is not changed by free(), you have absolutely no Since C is call-by-value, free() cannot change the value of ptr. However, free() may release space back to operating system so that a subsequent inspection of ptr will trap. -- Stephen Carlson | ICL OFFICEPOWER Center | In theory, theory and scc@rlgvax.reston.icl.com | 11490 Commerce Park Drive | practice are the same. ..!uunet!rlgvax!scc | Reston, VA 22091 |