Re: Linked List & Dynamic Memory Allocation

The code is somewhere between sloppy and erroneous. It is a common failure, especially in
short examples, to ignore the notion of free(). But that's sloppy. Every allocation
should have a corresponding free(). But you don't free the data until you are done with
it. There's nothing that requires that the free be syntactically balanced with the
malloc. For example, here's some code I wrote this morning, in pseudo-code form:

CMyListBox c_Things; // in my dialog class

class CMyListBox : public CListBox {
public:
int AddThing(int n, const CString & value, BOOL busy);

int CMyListBox::AddThing(int n, const CString & value, BOOL busy)
{
return CListBox::AddString((LPCTSTR)new ThingDescriptor(n, value, busy));
}

void CMyListBox::OnDeleteItem(LPDELETEITEMSTRUCT dis)
{
ThingDescriptor * td = (ThingDescriptor*)dis->itemData;
delete td;
}

Note that the deletion does not occur until the item is destroyed. There is a deletion
for every allocation, as required.



On Wed, 29 Aug 2007 06:13:59 -0700, one-trick-pony <worldofpain.aamir@xxxxxxxxx> wrote:

I think my book has an error. Code is allocating memory with malloc
and I don't see a free call to match it.

void enterdata()
{
struct address *info;

for( ; ; )
{
info = (struct address *)malloc(sizeof(struct address));
// check here to see if memory was allocated

gets(info->name);
// if user enters null break out of for loop
gets(info->location);
****
This code is absolutely horrible beyond belief. For example, suppose
struct address {
char name[20];
char location[20];
};

now type in 35 characters of name and 70 characters of location, and read about your
program in the next critical-security-alert bulletin from Symantec. This is the problem
with toy programs; by eliminating all the important considerations, such as security,
safety, reliability, robustness, and correctness to simplify the examples, these books
teach poor programming practices. Today, writing code with fixed-size arrays and no
bounds checking is a firable offense in many companies (I'm not kidding). In VS2005,
gets_s could be used to guarantee the program will not fail catastrophically, but it will
also not work correctly.
****

// call another function here to create a link list in sorted
order(sorting based on name)

}
}

void printlist()
{
// print all the data user has entered
}

I don't see a free call anywhere. You guys mentioned to put free call
for every call to malloc but when I do that inside the for loop I end
up losing my data and when I try to print the list program crashes. I
guess my question is where to put the free call? And how would I know
how many times user entered data to match the number of malloc calls?
My guess is because it is only one pointer that is using malloc. By
calling free(info) will reclaim memory for ALL the malloc calls made.
But the only thing throwing me off is you guys mentioned free for
every malloc. Please help.
****
There must be a free for every malloc. But you would not call it until you were
completelyl finished with your processing and no longer needed the data.

In the example I gave above, there is a free for every malloc, but it might happen
(literally) *hours* after the allocation. And it only happens at the point where the
value is no longer needed! Also, note that mallocs may be in the order 1,2,3 but the
frees may be in any permutation. So if I'm done with the 3rd element and no longer need
it (the user has opted to delete the name from the list, for example), at that point, and
not before, will I do a free. So the first item freed is not the first item allocated.

Think of it this way: you have a shelf full of empty boxes. Each time you need to box
something up, you take down an unused box and fill it, put a little yellow sticky note on
the box that says "in use", and put the box back on the shelf. You attach a string to the
box, the string leads back to your desk, where you have a little tag that says "Lunch" and
that's your "pointer". Any box on the shelf that doesn't have a little sticky note on
it that says "in use" is free to be used. So if you put your lunch in the box, then free
it (removing the little note that says "in use"), I'm free to now take that box, and put
whatever I want in it. So fill it with broken glass, and put a little sticky note on it
saying "in use". But you still have a little label on it called "lunch". The only way
you can find your lunch is to start at the tag labeled "lunch" and follow it to the box on
the shelf. The box, howevever, is now filled with broken glass, and if you eat it, the
consequences are serious. This is what happens if you free an object but continue to use
the pointer. A typical technique is to do
Lunch * M =(Lunch *)malloc(sizeof(Lunch));
lunch.Sandwich = turkey;
lunch.Munchies = chips;
lunch.Fruit = apple;
Eat(M);
free(M);
M = NULL;

in this sense, by assigning NULL, you disconnect the string from the tag. If you later
try to follow the tag to get your lunch, you will not have a string connected to it, and
your brain will say "Exception 0xC0000005: Attempt to access nonexistent memory".

But if you fail to break the string off, you'll get to the box full of glass, e.g.,
Lunch * M = (Lunch *)malloc(sizeof(Lunch));
lunch.Sandwich = turkey;
lunch.Munchies = chips;
lunch.Fruit = apple;
free(M);
// a separate thread allocates the box and fills it with broken glass
Eat(M); // not a really good idea...

So I can now do
InMorning()
for(i = 0; i < students.GetSize(); i++)
{
students[i].lunch = (Lunch *)malloc(sizeof(Lunch));
...fill in student lunch fields
}

StudentEatsLunch(int i)
Lunch * M = students[i].lunch;
Eat(M);
free(M);
students[i].lunch = NULL;

Note that the allocation takes place at 7am when the student is going off to school, and
the free takes place at lunchtime, *after* the lunch has been eaten. Hours apart!

But there is one free per malloc.

You can continue this analogy. Suppose I have 1000 cubic feet of "memory". I start with
a box 10 feet on a side. I ask for 100 cubic feet of memory. I get a box that holds 100
cubic feet, and the old box is replaced by a smaller box of 900 cubic feet. This is
called "block splitting". Eventually, I have a bunch of different-sized boxes on the
shelves. If I free a box of 50 cubic feet, there's now an additional 50 cubic feet
available. But suppose this box was sitting next to another, already free, 50 cubic foot
box. I take these two boxes away and replace them with a single, 100 cubic foot box. This
is called "coalescing" of blocks. Suppose I need 100 cubic feet of space, then that box
will satisfy my requirement. But suppose I look at the shelves, and I have no 100 cubic
foot boxes available. Then I'm out of storage, and malloc returns NULL. I look at the
shelf, and realize that I have 20 20-cubic-foot boxes. That's 400 cubic feet. But none
of the boxes are adjacent. So I can't get the 100 cubic feet I need. I say that storage
is "fragmented". Storage fragmentation is the worst enemy of long-running applications.
And it isn't a straightforward problem to solve.

Now what is a "lost pointer" or a "storage leak"? Well, that's where I manage to lose the
tag. I might do something like
Thing * T = (Thing *)malloc(Thing);
T = (Thing*)malloc(Thing);
the first allocation is now "lost", in that I untied the string from the tag T and tied a
new string to it, but I have now lost the old string. I didn't attach it to any other
tag, so it's gone. I can't access a box without a tag with a string attached. So that
storage keeps its little sticky tag that says "in use" and no one will be able to use it
again.

What is a "dangling pointer"? The simple case was the one above, where I did a free but
then kept using the pointer. Well, consider the following: I assign the pointer to another
variable. So what happens is that I now have *two* tags connected to the box with two
strings: T1 and T2. So then I
Thing * T1 = (Thing *)malloc(Thing);
Thing * T2 = T1;
free(T1);
WorkOn(T2);
but once the free() is done, the box is available, so between the free(T1) and WorkOn(T2),
the box is filled with something inappropriate. Oops. This is a typical dangling pointer
problem.

What is a "smart pointer"? Well, it's a pointer which doesn't allow you to just break the
string, or assign a new one just by untying the old one. A "smart pointer" has a little
critter that is the agent by which you can attach the string. You don't do it yourself,
you hand it to the little critter, and it looks around and says "is there a string
attached already?". If so, it runs up, marks the box as "not in use" by removing the
sticky note, detaches the old string, and attaches the new string. If it sees that you
are about to throw the tag away, it does the same thing to the existing string. So you
don't lose objects when the variable goes out of scope; the little critter tracks it for
you. That's one of the things C++ is all about: you can create these little critters
(they're often called "wrapper classes") and give them responsibility for managing the
objects. CString, CArray, and CWnd are familiar examples.

Does this clarify things?
joe
****
Joseph M. Newcomer [MVP]
email: newcomer@xxxxxxxxxxxx
Web: http://www.flounder.com
MVP Tips: http://www.flounder.com/mvp_tips.htm
.

Relevant Pages

  • Re: Getting Start/End time, etc. from IPM.Schedule.Meeting.Resp.Po
    ... So, if I understand you correctly, I can get at these named properties by ... both marked with the same string. ... to GetIDsFromNames and "or" the returned tag with teh appropriate type (e.g. ... then iterating over the list and calling ...
    (microsoft.public.win32.programmer.messaging)
  • Re: Convert *.wma File Names to Text
    ... the value of the Tag property isn't used ... title As String * 30 ... Dim FileName As String ... Dim mp3info As MP3TagInfo ...
    (microsoft.public.vb.general.discussion)
  • Include Schema Name When Creating XML
    ... I have a Java program that creates an XML string and I wanted to pass ... public void startDocument ... This method will create the open tag for a new element. ...
    (comp.lang.java.programmer)
  • Re: Invalid Procedure Call
    ... This is done with about 9 SQL strings total, ... My problem is occuring in the SQL string that takes the raw ... Fields: tag, pointid, date ... This SQL statement is put into a string and executed in VBA. ...
    (microsoft.public.access.queries)
  • Re: strdup(NULL) supposed to create SIGSEGV?
    ... you ask it to copy a NULL pointer. ... would you be trying to copy a string where not having a string isn't ... But strdup uses malloc, which is a system call (from the strdup ... malloc isn't a system call. ...
    (freebsd-hackers)