dynamic memory problem(i think)

[placid]

Hi all,

i have this struct for a binary tree node

typedef struct treenode
{
char *word;
struct treenode *right;
struct treenode *left;
}TreeNode;

and to the element *word, i dynamically allocate memory for it as below
(and also for the TreeNode too)


addNode(TreeNode*,char*);

char *token, buf[BUF_MAX], *memWord;
TreeNode *root;

/*do memory allocation check */

while((fgets(buf,BUF_MAX,filePtr)) != NULL)
{
/* do buffer handling here */
token = strtok(buf,"\n");
while (token != NULL)
{
/* is the following right ? */
memWord = malloc(sizeof(char) * strlen(token);
strcpy(memWord,token);

addNode(root,memWord);
token = strtok(NULL, "\n");
}
}


the code above reads a line from a file and then tokenizes the line
read into tokens and then allocates memory in the same length of the
token, then copies the token into memWord and passes to a function to
add it to the BST pointed by root.

My question and problem is that , when i delete a node from the list
and free the memory for both the word inside the node and the node
itself, i get no memory leaks or whatsoever (because according to
valgrind i have more free's then allocations) and then print them out
(in-order), well, i get weird characters and mumble jumble for insted
of words. But if i dont free the word inside the node (and get some
memory leaks) then print them out it actually works, i.e the nodes that
deleted are gone and there is no weird characters and all. So anyway
here is the code that i use to delete a node (recursive)

delete(char *w, TreeNode T)
{
TreeNode tmpNode;
if (T == NULL)
return T;
if (strcmp(w, T->word) < 0 )
T->left = delete(w,T->left);
else
if (strcmp(w, T->word) > 0)
T->right = delete(w,T->right);
else
{
if(T->left && T->right)
{
tmpNode = findMin(T->right);
T->word = tmpNode -> word;
T->right = delete(w,T->right);
}
else
{
tmpNode = T;
if (T->left == NULL)
T= T->right;
else if (T->right == NULL)
T= T->left;

free(tmpNode->word);
free(tmpNode);
}

}

return T;
}

 

[Artie Gold]

Hi all,

i have this struct for a binary tree node

typedef struct treenode
{
char *word;
struct treenode *right;
struct treenode *left;
}TreeNode;

and to the element *word, i dynamically allocate memory for it as below
(and also for the TreeNode too)

Please post *real* code. Copy and paste!

addNode(TreeNode*,char*);

char *token, buf[BUF_MAX], *memWord;
TreeNode *root;

/*do memory allocation check */

while((fgets(buf,BUF_MAX,filePtr)) != NULL)
{
/* do buffer handling here */
token = strtok(buf,"\n");
while (token != NULL)
{
/* is the following right ? */
memWord = malloc(sizeof(char) * strlen(token);

Here's your problem.
First of all, sizeof(char) == 1 by definition, so it's superfluous.
More important, however, is that you've allocated one char too few; you
haven't left room for the null char that terminates the string.

Make the above line:
memWord = malloc(strlen(token) + 1));

[BTW - I know you haven't posted *real* code as you're missing a closing
paren above.]

You also need to check that malloc() did not return NULL.

strcpy(memWord,token);

Now, since you haven't allocated enough memory, your call to strcpy()
invokes undefined behavior. You were fortunate that nasal demons(tm) did
not ensue!

[snip]

HTH,
--ag

 

[placid]

Please post *real* code. Copy and paste!

yeah, see for some reason i always have two copies of code(really bad
idea) one on my laptop and one a UNIX server, so i had to type it out
all again so i was just trying to save some time. Sorry man

addNode(TreeNode*,char*);

char *token, buf[BUF_MAX], *memWord;
TreeNode *root;

/*do memory allocation check */

while((fgets(buf,BUF_MAX,filePtr)) != NULL)
{
/* do buffer handling here */
token = strtok(buf,"\n");
while (token != NULL)
{
/* is the following right ? */
memWord = malloc(sizeof(char) * strlen(token);

Here's your problem.
First of all, sizeof(char) == 1 by definition, so it's superfluous.
More important, however, is that you've allocated one char too few; you
haven't left room for the null char that terminates the string.

so then strlen does not include the null character in the lenght count

Make the above line:
memWord = malloc(strlen(token) + 1));

[BTW - I know you haven't posted *real* code as you're missing a closing
paren above.]

You also need to check that malloc() did not return NULL.

sacrificed for code readablity !

Now, since you haven't allocated enough memory, your call to strcpy()
invokes undefined behavior. You were fortunate that nasal demons(tm) did
not ensue!

thats why i get "weird characters and mumble jumble"

[snip]

HTH,
--ag

your a life saver man

greatly appreciated

 

[Giannis Papadopoulos]

Hi all,

i have this struct for a binary tree node

typedef struct treenode
{
char *word;
struct treenode *right;
struct treenode *left;
}TreeNode;

and to the element *word, i dynamically allocate memory for it as below
(and also for the TreeNode too)

Please post *real* code. Copy and paste!

addNode(TreeNode*,char*);

char *token, buf[BUF_MAX], *memWord;
TreeNode *root;

/*do memory allocation check */

while((fgets(buf,BUF_MAX,filePtr)) != NULL)
{
/* do buffer handling here */
token = strtok(buf,"\n");
while (token != NULL)
{
/* is the following right ? */
memWord = malloc(sizeof(char) * strlen(token);

Here's your problem.
First of all, sizeof(char) == 1 by definition, so it's superfluous.

However, using

memWord = malloc( (sizeof *memWord) * (strlen(token)+1) );

is a much better practice...


--
one's freedom stops where others' begin

Giannis Papadopoulos
http://dop.users.uth.gr/
University of Thessaly
Computer & Communications Engineering dept.

 

[Anand]

placid wrote:
[snip]

Here's your problem.
First of all, sizeof(char) == 1 by definition, so it's superfluous.
More important, however, is that you've allocated one char too few; you
haven't left room for the null char that terminates the string.

Make the above line:
memWord = malloc(strlen(token) + 1));

I know FAQ 7.8 covers exactly the above point
but I also noticed in the errata section
(http://www.eskimo.com/~scs/C-faq/book/Errata.html) 1.1
that the sizeof(char) is *atleast* 8 bits.

So 'theoritically' speaking [probably 'practically' in some cases but
not in my experience] sizeof(char) is not really superfluous in the
situations..

-Anand

 

[Anand]

placid wrote:
[snip]


Here's your problem.
First of all, sizeof(char) == 1 by definition, so it's superfluous.
More important, however, is that you've allocated one char too few;
you haven't left room for the null char that terminates the string.

Make the above line:
memWord = malloc(strlen(token) + 1));

I know FAQ 7.8 covers exactly the above point
but I also noticed in the errata section
(http://www.eskimo.com/~scs/C-faq/book/Errata.html) 1.1
that the sizeof(char) is *atleast* 8 bits.

So 'theoritically' speaking [probably 'practically' in some cases but
not in my experience] sizeof(char) is not really superfluous in the
situations..

-Anand

Sorry.. typed too fast.. upon going through the C99 std and also going
through news groups more thoroughly found the following article titled:
"Type sizes (Was:big-endian vs. little-endian...)"
http://groups.google.com/group/comp...ytes+C+Compiler&rnum=1&hl=en#ab81ff433d688fa6


-Anand
PS: Is there any way to point to another news group article through some
kind of link (apart from this looong google link)?

 

[Clark S. Cox III]

placid wrote:
[snip]

Here's your problem.
First of all, sizeof(char) == 1 by definition, so it's superfluous.
More important, however, is that you've allocated one char too few; you
haven't left room for the null char that terminates the string.

Make the above line:
memWord = malloc(strlen(token) + 1));

I know FAQ 7.8 covers exactly the above point
but I also noticed in the errata section
(http://www.eskimo.com/~scs/C-faq/book/Errata.html) 1.1
that the sizeof(char) is *atleast* 8 bits.

So 'theoritically' speaking [probably 'practically' in some cases but
not in my experience] sizeof(char) is not really superfluous in the
situations..

Even when char is more than 8-bits, sizeof(char) is *always* 1. Char
could be 135 bits, and it would still be one byte in size, as that is
C's definition of "byte".

 

[Flash Gordon]

placid wrote:
[snip]


Here's your problem.
First of all, sizeof(char) == 1 by definition, so it's superfluous.
More important, however, is that you've allocated one char too few;
you haven't left room for the null char that terminates the string.

Make the above line:
memWord = malloc(strlen(token) + 1));

I know FAQ 7.8 covers exactly the above point
but I also noticed in the errata section
(http://www.eskimo.com/~scs/C-faq/book/Errata.html) 1.1
that the sizeof(char) is *atleast* 8 bits.

No, sizeof(char) is always EXACTLY 1 on all conforming implementations.
CHAR_BIT (i.e. the number of bits in a char) *may* me more than 8, but
since all allocations, the result of strlen, the result of sizeof are
all working on the basis of the number of bytes (in C terms 1 char is
the size of 1 byte ALWAYS, even if 1 byte is 932754937 bits long).

So 'theoritically' speaking [probably 'practically' in some cases but
not in my experience] sizeof(char) is not really superfluous in the
situations..

sizeof(char) is, by definition, ALWAYS 1, but that is 1 C byte which
could be more than 8 bits.

IMHO it is misleading for the FAQ Errata to say, "sizeof(char) is at
least 8 bits". It should say, "The size of one char is at least 8 bits".

Also, note that there are conforming implementations where
sizeof(char)==sizeof(int) where both int and char are 16 bits.

 

[Artie Gold]

Hi all,

i have this struct for a binary tree node

typedef struct treenode
{
char *word;
struct treenode *right;
struct treenode *left;
}TreeNode;

and to the element *word, i dynamically allocate memory for it as below
(and also for the TreeNode too)

Please post *real* code. Copy and paste!

addNode(TreeNode*,char*);

char *token, buf[BUF_MAX], *memWord;
TreeNode *root;

/*do memory allocation check */

while((fgets(buf,BUF_MAX,filePtr)) != NULL)
{
/* do buffer handling here */
token = strtok(buf,"\n");
while (token != NULL)
{
/* is the following right ? */
memWord = malloc(sizeof(char) * strlen(token);

Here's your problem.
First of all, sizeof(char) == 1 by definition, so it's superfluous.

However, using

memWord = malloc( (sizeof *memWord) * (strlen(token)+1) );

is a much better practice...

In general, yes. In this case, however, the type is effectively
constrained by the use of strlen() anyway. (And in any case the parens
around the `sizeof' expression are superfluous.)

But I'm just nit-picking...

Cheers,
--ag

 

[Christopher Benson-Manica]

so then strlen does not include the null character in the lenght count

No.

 

[placid]

delete(char *w, TreeNode T)
{
TreeNode tmpNode;
if (T == NULL)
return T;
if (strcmp(w, T->word) < 0 )
T->left = delete(w,T->left);
else
if (strcmp(w, T->word) > 0)
T->right = delete(w,T->right);
else
{
if(T->left && T->right)
{
tmpNode = findMin(T->right);
T->word = tmpNode -> word;
T->right = delete(w,T->right);
}
else
{
tmpNode = T;
if (T->left == NULL)
T= T->right;
else if (T->right == NULL)
T= T->left;

free(tmpNode->word);
free(tmpNode);
}

}

return T;
}

aghh..

Ok.. i tried adding one to memWord = malloc(strlen(token) + 1)
that fixes the funny character problem, but like i said when i delete a
node from the tree and print it out im still getting data that is just
mumble jumble
i found out that when i call

free(tmpNode->word);

is the problem. when i run valgrind with that code commented (and print
the BST out it works) i get memory leaks (obviously) but the amount of
free's is equals to the amount of allocations. But when i use that line
of code then run valgrind (and print the BST out, i get mumble jumble)
i get more free's the allocations. and this is on a mandrake 10.1
official system (im beginning to think its an OS problem ).

 

[Joakim Hove]

Well,

I really feel you should have

TreeNode * deleta(char *w, TreeNode *T) {

}

i.e. the variable T should be a *pointer to* TreeNode instance, and
that applies to the 'left' and 'right' fields of TreeNode struct as
well.

HTH - Joakim



--
Joakim Hove
hove AT ift uib no /
Tlf: +47 (55 5)8 27 13 / Stabburveien 18
Fax: +47 (55 5)8 94 40 / N-5231 Paradis
http://www.ift.uib.no/~hove/ / 55 91 28 18 / 92 68 57 04

 

[Joakim Hove]

Hello,

[....] and that applies to the 'left' and 'right' fields of
TreeNode struct as well [....]

and that was indeed the case, I remembered the definition of TreeNode
{} incorrectly. Sorry.



Joakim

--
Joakim Hove
hove AT ift uib no /
Tlf: +47 (55 5)8 27 13 / Stabburveien 18
Fax: +47 (55 5)8 94 40 / N-5231 Paradis
http://www.ift.uib.no/~hove/ / 55 91 28 18 / 92 68 57 04

 

[placid]

delete(char *w, TreeNode T)
{
TreeNode tmpNode;
if (T == NULL)
return T;
if (strcmp(w, T->word) < 0 )
T->left = delete(w,T->left);
else
if (strcmp(w, T->word) > 0)
T->right = delete(w,T->right);
else
{
if(T->left && T->right)
{
tmpNode = findMin(T->right);

T->word = tmpNode -> word;

assign the char * T->word to point to the word inside tmpNode->word but
its wrong for some reason

T->word is a pointer to a dynamically allocated char's, so the correct
way of doing it is ..

strcpy(T->word,tmpNode->word);

but why would that make a difference i dont know. (But it works).

T->right = delete(w,T->right);
}
else
{
tmpNode = T;
if (T->left == NULL)
T= T->right;
else if (T->right == NULL)
T= T->left;

free(tmpNode->word);
free(tmpNode);
}

}

return T;
}

Everybody thanks for the help

 

[Chris Torek]

typedef struct treenode {
char *word;
struct treenode *right;
struct treenode *left;
} TreeNode;

... when i delete a node from the list and free the memory for both
the word inside the node and the node itself, i get no memory leaks
or whatsoever (because according to valgrind i have more free's then
allocations)

*More* free() calls than malloc() calls indicates there is a serious
bug.

and then print them out (in-order), well, i get weird characters and
mumble jumble for insted of words. But if i dont free the word inside
the node (and get some memory leaks) then print them out it actually
works, i.e the nodes that deleted are gone and there is no weird
characters and all.

This suggests you are free()ing the same word(s) twice.

Now, you do not show the complete code for addnode(), but you
do show this:

/* is the following right ? */
memWord = malloc(sizeof(char) * strlen(token);
strcpy(memWord,token);

which is wrong -- memWord should point to strlen(token)+1 bytes,
to account for the '\0' that terminates the string. (I think
someone else pointed this out elsethread.) Of course, you should
also test the result of malloc() to see if it returned NULL, for
"out of memory". I suspect this is not the source of the observed
problem, however.

Here is your delete() function in its entirety as you posted it:

delete(char *w, TreeNode T)
{
TreeNode tmpNode;
if (T == NULL)
return T;
if (strcmp(w, T->word) < 0 )
T->left = delete(w,T->left);
else
if (strcmp(w, T->word) > 0)
T->right = delete(w,T->right);
else
{
if(T->left && T->right)
{
tmpNode = findMin(T->right);
T->word = tmpNode -> word;
T->right = delete(w,T->right);
}
else
{
tmpNode = T;
if (T->left == NULL)
T= T->right;
else if (T->right == NULL)
T= T->left;

free(tmpNode->word);
free(tmpNode);
}

}

return T;
}

Clearly something is missing and something is incorrect: the function
has a return value of type "TreeNode", which is an alias for "struct
treenode". As such it should be "TreeNode delete" or "struct
treenode delete". At the same time, however, you test T for NULL
and use "T->", which implies that T has type "pointer to struct
treenode", not "struct treenode". Perhaps the typedef named TreeNode
is an alias for "struct treenode *", and the posting-error is near
the top, rather than multiple missing "*"s in the delete() function
itself.

In any case, there is clearly a logic error as well. The delete()
function returns a pointer to the new tree so that you can keep
your tree somewhat balanced, hence the call to findMin() if there
are both left and right branches at the point you are deleting.

Now, if there are *not* two sub-trees at the point being deleted
(so that tmpNode=T and then T=T->left?T->left:T->right), you call
free() on two values: tmpNode->word and tmpNode itself. But if
there *are* two sub-trees, you find the minimum node on the right
sub-tree:

tmpNode = findMin(T->right);

While findMin() is not shown, I think we can assume that it
simply finds an appropriate node in the right-hand sub-tree
(and thus does no malloc()s and no free()s). Then you do this:

T->word = tmpNode->word;
T->right = delete(w, T->right);

The first assignment copies a pointer from tmpNode, which is some
sub-node of the right-hand tree. The second assignment calls
delete() recursively, and will free() some sub-node of the right-hand
tree *and* its word. Sine findMin() did not get "w" as a parameter,
there is no obvious strong connection between the node that findMin()
found and the node that delete() will delete -- but there is some
chance that T->word now points to the word that delete() has deleted
(i.e., the memory free()d by the call free(T->word) in the
sub-delete()); and if not, T->word points to the word in the node
findMin() found, so that two different tree nodes are sharing the
same T->word value.

In either case, this is quite wrong.

(I am not going to provide a fix, as there are lots of different
ways to fix this and you have to decide which method(s) you prefer
and why.)