Hi,
I have some (very strange for me) problem. My program stops working in some time, but when I'm debugging it everything is allright.
Here is my source #1449707 - Pastie
It's just a stupid push function to a binary tree. I hope someone could help me and tell what the real problem is o.O
> push(s+free, &root);
You should make a COPY of the string inside push(), rather than relying on tricky pointer arithmetic.
Once you've added more than 1024 chars of data (which is easily done outside of a simple test), you're running with buffer overflows.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
The array is not a problem. It's enough for what I am doing.
About this thing with the pointers - could they make the problem. And why they're not doing it when I'm debuging!?
Where is your run-time data?
Make a better debug test which uses your actual data.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
5
a
bc
def
ghij
klmno
this is an example. It stops working when it reaches the 'def' part.
Actually every time the program reaches the third element (for each kind of test) it stops working. If there are onlu one or two elements everything seems to be ok.
> tmp = malloc(sizeof(struct node *));
You're not allocating enough memory. You want a whole node, not just a node pointer.
Use this form instead - it's pretty fool-proof.
tmp = malloc( sizeof(*tmp) );
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
You never seem to update size in all of this.Code:else if (root->left == NULL) push(data, &(root->left)); else if (root->right == NULL) push(data, &(root->right)); else if (root->left->size <= root->right->size) push(data, &(root->left)); else push(data, &(root->right));
Oh, I have forgotten to add the 'root->size++;' line at position 68.Originally Posted by tabstop
I have it here, but it's still not working
Can you be a little more specific? After implementing the changes Salem and tabstop suggested, I can't replicate the problem. Do you end up with a seg fault? Does it produce unexpected output? Does it get stuck in an infinite loop?
Maybe it would also help if you explained the exact nature of your tree. What is the criteria for a node being a left node or a right node? Is it supposed to maintain any order or are you trying to make a complete binary tree?
Are you stupid!? I've posted the source, I've given you the test, I've posted the where and what line I had forgotten. The source is only 70 lines and it's quiet easy. What is the problem to look at it and to try and test it. You have everything that is needed and everything I have.
Besides, how could it possibly goes to an infinite loop when there is only one for in the main function (actually it can with some dark magic but that is not the point). If you had tried to test the program you would have seen that there is no unexpected output. It just brake down on the third element to be added. But when I am debuging it (I'm using CodeBlocks but I've to compile it trough the console with gcc and I've tried other editors) everything is ok and it is working normally.
It's irrational the problem for me but it's happening, please somebody help me (and it's not happening for the very first time).
NB. Oh, and it's just a binary tree, where the data is added to the subtree with smaller number of elements (and the data is string).
I've missed this. Now, I've tried it and it works o.O
But why it worked with two elements?
NB. It should have been:
tmp = malloc( sizeof(struct node) ); - without the * - I get it. I'm so stupid.
Thank you Salem
Last edited by torbalan; 01-12-2011 at 04:30 AM.
> But why it worked with two elements?
Pure dumb luck - nothing more.
Many malloc implementations pad the amount you ask for out to say a multiple of 8 bytes (or whatever the most restrictive alignment is on your machine). Small overruns can therefore go unnoticed for some time.
If you want better diagnosis, you need a tool like valgrind, or using another compiler.
Even with just one string, you see a lot of invalid write attempts, even though the end result is the program ending normally.Code:$ valgrind ./a.out 1 ==3120== Memcheck, a memory error detector ==3120== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al. ==3120== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info ==3120== Command: ./a.out ==3120== hello BOZA!!! ==3120== Invalid write of size 4 ==3120== at 0x804869B: push (foo.c:55) ==3120== by 0x80485E9: test (foo.c:34) ==3120== by 0x804853E: main (foo.c:18) ==3120== Address 0x419802c is 0 bytes after a block of size 4 alloc'd ==3120== at 0x4024F20: malloc (vg_replace_malloc.c:236) ==3120== by 0x804866C: push (foo.c:50) ==3120== by 0x80485E9: test (foo.c:34) ==3120== by 0x804853E: main (foo.c:18) ==3120== ==3120== Invalid write of size 4 ==3120== at 0x80486A4: push (foo.c:56) ==3120== by 0x80485E9: test (foo.c:34) ==3120== by 0x804853E: main (foo.c:18) ==3120== Address 0x4198030 is 4 bytes after a block of size 4 alloc'd ==3120== at 0x4024F20: malloc (vg_replace_malloc.c:236) ==3120== by 0x804866C: push (foo.c:50) ==3120== by 0x80485E9: test (foo.c:34) ==3120== by 0x804853E: main (foo.c:18) ==3120== ==3120== Invalid write of size 4 ==3120== at 0x80486AA: push (foo.c:57) ==3120== by 0x80485E9: test (foo.c:34) ==3120== by 0x804853E: main (foo.c:18) ==3120== Address 0x4198038 is 12 bytes after a block of size 4 alloc'd ==3120== at 0x4024F20: malloc (vg_replace_malloc.c:236) ==3120== by 0x804866C: push (foo.c:50) ==3120== by 0x80485E9: test (foo.c:34) ==3120== by 0x804853E: main (foo.c:18) ==3120== ==3120== Invalid read of size 4 ==3120== at 0x80486B4: push (foo.c:57) ==3120== by 0x80485E9: test (foo.c:34) ==3120== by 0x804853E: main (foo.c:18) ==3120== Address 0x4198038 is 12 bytes after a block of size 4 alloc'd ==3120== at 0x4024F20: malloc (vg_replace_malloc.c:236) ==3120== by 0x804866C: push (foo.c:50) ==3120== by 0x80485E9: test (foo.c:34) ==3120== by 0x804853E: main (foo.c:18) ==3120== ==3120== Invalid write of size 4 ==3120== at 0x80486BA: push (foo.c:57) ==3120== by 0x80485E9: test (foo.c:34) ==3120== by 0x804853E: main (foo.c:18) ==3120== Address 0x4198034 is 8 bytes after a block of size 4 alloc'd ==3120== at 0x4024F20: malloc (vg_replace_malloc.c:236) ==3120== by 0x804866C: push (foo.c:50) ==3120== by 0x80485E9: test (foo.c:34) ==3120== by 0x804853E: main (foo.c:18) ==3120== ==3120== ==3120== HEAP SUMMARY: ==3120== in use at exit: 4 bytes in 1 blocks ==3120== total heap usage: 1 allocs, 0 frees, 4 bytes allocated ==3120== ==3120== LEAK SUMMARY: ==3120== definitely lost: 4 bytes in 1 blocks ==3120== indirectly lost: 0 bytes in 0 blocks ==3120== possibly lost: 0 bytes in 0 blocks ==3120== still reachable: 0 bytes in 0 blocks ==3120== suppressed: 0 bytes in 0 blocks ==3120== Rerun with --leak-check=full to see details of leaked memory ==3120== ==3120== For counts of detected and suppressed errors, rerun with: -v ==3120== ERROR SUMMARY: 5 errors from 5 contexts (suppressed: 13 from 8)
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
I see
Thank you very much
You might want to work on your manners, I don't think people will feel inclined to help you as long as you insult them.
hth
-nv
She was so Blonde, she spent 20 minutes looking at the orange juice can because it said "Concentrate."
When in doubt, read the FAQ.
Then ask a smart question.
Apparently the only stupid thing I did was assume you could read. It was you that didn't read my post carefully, and you that missed Salem's post regarding your incorrect malloc usage. If you did read my post more carefully, you would have noticed the following:
That right there tells you that I did have a look at it and test it -- hell, I used your test and about 10 others that I came up with -- I just couldn't replicate the problem. I even mentioned explicitly two separate people who gave you two solutions. Careful reading should have made you realize there are multiple changes to implements (plural usage, not singular), the size issue tabstop mentioned, and the malloc call Salem mentioned. Salem's response was written 2 minutes earlier than tabstop's, so if you read tabstop's, it's only natural to assume you read Salem's too. Guess I was wrong.
I also wrote a print function to print out your tree so I could make sure it looked reasonable. It almost did. Your funky usage of a buffer in your test routine doesn't store null characters after each piece of input, so when you print node->data, and are expecting "a", you actually get the full input of the user, "abcdefghijklmno".
You actually could get into another infinite-loop-like situation if your recursive calls weren't handled correctly. I suppose a more accurate term would be infinite recursion, and it probably would have eventually caused a seg fault as the stack came crashing down into the heap, but the symptoms would be quite similar until then, which could have been why you thought you got stuck on the third input.
Since I assumed you implemented Salem's suggestion, I figured you must have encountered some other problem. Maybe it was the lack of null termination I mentioned above. Maybe a problem with your recursion. Maybe something else. Who knew? I figured it couldn't hurt to ask for clarification though.
As for your nota bene, yes, I knew what the program was doing, I just wasn't sure that's what you wanted it to be doing, since you never said "this is my program that does x". Again, this relied on me assuming you took Salem's advice and there was a new problem elsewhere.
Sorry I assumed you could read. Sorry I assumed you tried all the suggestions put forth. Sorry I asked for a more info so I could take time out of my busy day to try and help you. Sorry I...wait, I think it's you that should be apologizing to me.
