why will "malloc" change unrelated pointer in my case?

Question

I’m trying to implement a binary search tree (BST) in C. I have tried to add several elements to the BST, but when I add the third one, the code doesn’t work. I debug it in gdb and find that when it executes malloc for the new node, the second node’s parent changes from a correct address value to 0x13.

Since I feel that there is no relation between the new node’s memory allocation and the old node’s parent, I have no idea why does this happens…

Here is my InsertBST function:

int InsertBST(Bst *p, int val)
{
    PNode pnode = (PNode)malloc(sizeof(PNode));
    if (pnode != NULL)
    {
        pnode->data = val;
        pnode->lc = NULL;
        pnode->rc = NULL;
        if (p->root == NULL)
        {
            pnode->parent = NULL;
            p->root = pnode;
            p->size++;
            return 1;
        }
        else
        {
            PNode tem = FindVal(p->root, val);
            if (tem != NULL)
            {
                printf("Sorry, the value %d has appeared!\n", val);
                return 0;
            }
            else
            {
                tem = p->root;
                while (tem->lc != NULL && tem->rc != NULL)
                {
                    if (tem->data > val)
                        tem = tem->lc;
                    else
                        tem = tem->rc;
                }
                pnode->parent = tem;
                if (tem->data > val)
                {
                    tem->lc = pnode;
                }
                else
                {
                    tem->rc = pnode;
                }
                p->size++;
            }
            return 1;
        }
    }
    else
    {
        printf("Allocate memory failed!\n");
        return 0;
    }
}

p is pointer to a structure like this:

typedef struct BST
{
    PNode root;
    int size;
}Bst;

and PNode is pointer to a structure like this:

typedef struct NODE
{
    int data;
    PNode lc;
    PNode rc;
    PNode parent;
}Node;

Did you use a [memory leak](http://en.wikipedia.org/wiki/Memory_leak) detector like [valgrind](http://valgrind.org/) ? Did you compile with `gcc -Wall -g`? Did you use the `gdb` debugger? On which operating system are you running (Linux is probably easier). — Basile Starynkevitch, Jan 11 '14 at 11:57
[Don't cast the return value of `malloc()`](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc/605858#605858)! — , Jan 11 '14 at 11:59
A good example how typecasting a pointer type confuses. Don't do that, it is not worth it. `Node*` is perfectly fine in all your interfaces. — Jens Gustedt, Jan 11 '14 at 12:37

score 6 · Accepted Answer · answered Jan 11 '14 at 11:57

6

malloc(sizeof(PNode))

will allocate the memory needed for a pointer, not for the node structure behind it.

Try

malloc(sizeof(*PNode))

or

malloc(sizeof(Node))

answered Jan 11 '14 at 11:57

Guntram Blohm

9,667
2
24
31

1

That's to say I allocate less space than needed.But I'm still confused about why every thing seems all right except the tree's parent?Could you help to analyse it? – user3162587 Jan 11 '14 at 13:36
There's not much to analyze. Let's assume the memory that `malloc()` and `free()` manages starts at address 0x10000, and malloc() needs 4 bytes for its own housekeeping, and your pointer size is 4 bytes as well. First malloc() will write 4 housekeeping bytes to 0x10000-0x10003, return address 0x10004 to you, and remember the next block starts at 0x10008. Second malloc will use 0x10008-0x1000b for housekeeping, and return 0x1000c to you. Now when you write to first->data, you write to 0x10004-0x1000c. When you write to first->lc, you overwrite malloc()s internal data at 0x100008. – Guntram Blohm Jan 11 '14 at 16:02
And when you write to first->rc, you write to 0x1000c, which happens to be the same memory address as second->data. Of course, the details depend on the malloc implementation, pointer size, and so on, but i guess it's safe to say 'the Nodes behind your PNodes share the same memory, so writing to one component of one Node will write to a different component of a different Node as well'. – Guntram Blohm Jan 11 '14 at 16:04

why will "malloc" change unrelated pointer in my case?

1 Answers1