What the following line of code with malloc does?

Question

I have the following implementation to mirror the binary tree.

#include<stdio.h>
#include<stdlib.h>

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
};

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)

{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
}


/* Change a tree so that the roles of the  left and
    right pointers are swapped at every node.

 So the tree...
       4
      / \
     2   5
    / \
   1   3

 is changed to...
       4
      / \
     5   2
        / \
       3   1
*/
void mirror(struct node* node)
{
  if (node==NULL)
    return; 
  else
  {
    struct node* temp;

    /* do the subtrees */
    mirror(node->left);
    mirror(node->right);

    /* swap the pointers in this node */
    temp        = node->left;
    node->left  = node->right;
    node->right = temp;
  }
}


/* Helper function to test mirror(). Given a binary
   search tree, print out its data elements in
   increasing sorted order.*/
void inOrder(struct node* node)
{
  if (node == NULL)
    return;

  inOrder(node->left);
  printf("%d ", node->data);

  inOrder(node->right);
} 


/* Driver program to test mirror() */
int main()
{
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right = newNode(5);

  /* Print inorder traversal of the input tree */
  printf("\n Inorder traversal of the constructed tree is \n");
  inOrder(root);

  /* Convert tree to its mirror */
  mirror(root);

  /* Print inorder traversal of the mirror tree */
  printf("\n Inorder traversal of the mirror tree is \n"); 
  inOrder(root);

  getchar();
  return 0; 
}

I am talking about the following line:

  struct node* node = (struct node*)
                       malloc(sizeof(struct node));

I have intermediate knowledge of c/c++ but I am quite afraid of pointers. Even after several tries I have never been able to get pointers. I avoid them as far as possible but when come to implementing data structures like trees there is no other options. Why are we using malloc and sizeof here? Also why are we casting (struct node*)?

Solution 1

First of all casting when using malloc in C is not necessary. (see here)

You are malloc-ing because you are allocating heap memory of the size of a node struct. You see in C you have to keep in mind where all the variables are stored. Namely the stack and heap (see here)

Inside a function your variables are termed local variables, which is stored in the stack. Once you leave the function that variables in the stack are cleared.

To be able to reference or use local variables outside of the function you have to allocate memory in the heap, which is what you are doing here. You are allocating memory in the heap so that you can reuse the same variable in other functions as well.

In summary:

• Variables within a function are local to the function, hence the term local variable
• For other functions to access the local variable, you have to allocate memory in the heap to share that variable with other functions.

To give you an example why, consider the following code:

#include <stdio.h>
#include <string.h>

char *some_string_func()
{
    char some_str[13]; /* 12 chars (for "Hello World!") + 1 null '\0' char */

    strcpy(some_str, "Hello World!");

    return some_str;
}

int main()
{
    printf("%s\n", some_string_func());
    return 0;
}

Its pretty simple, main is simply calling a function some_str_func which returns a local variable some_str, compiling the above code would work, but not without warnings:

test.c: In function ‘some_string_func’:
test.c:11:9: warning: function returns address of local variable [enabled by default]

Although it compiles note that some_str in some_str_func() is returning a local variable to the function (i.e. in the function's stack). Since the stack is cleared once you leave the function some_str_func(), in main() it would not be possible to get the contents of some_str which is "Hello World".

If you attempt to run it you get:

$ gcc test.c
$ ./a.out

$

It prints nothing, cause it cannot access some_str. To remedy it you allocate some memory space for the string "Hello World" instead. like so:

#include <stdio.h>
#include <string.h>

char *some_string_func()
{
    char *some_str;

    /* allocate 12 chars (for "Hello World!") + 1 null '\0' char */
    some_str = calloc(13, sizeof(char));

    strcpy(some_str, "Hello World!");

    return some_str;
}

int main()
{
    char *str = some_string_func();
    printf("%s\n", str);

    free(str);  /* remember to free the allocated memory */
    return 0;
}

Now when you compile and run it, you get:

$ gcc test.c
$ ./a.out
Hello World!
$

If you are having a hard time understanding C, I know many people find "The C Programming Language" by Brian W. Kernighan and Dennis Ritchie a really good reference, however a more modern and graphical (even fun to read! seriously) book is Head First C By David and Dawn Griffiths, they explain many important C concepts such as Heap and Stack, difference between dynamic and static C libraries, why using Makefiles is a good idea, how does Make work, and many more concepts not previously explained in common C books, definitely worth a look.

Another good online resource is Zed Shaws Learn C the Hard way, in which he provides good code examples and notes.

Solution 2

Read: void *malloc(size_t size);

The malloc() function allocates size bytes and returns a pointer to the allocated memory. The memory is not initialized. If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be successfully passed to free().

Accordingly, in

struct node* node = (struct node*)malloc(sizeof(struct node));
  //                                     ^----size---------^

you are allocating memory chunk of size = sizeof naode bytes and address return from malloc stored in nodepointer.

Note You have mistake variable name shouldn't be node as it is struct name. You can! but Not good practice, though. Also, sizeof(*pointer) is preferred over sizeof(Type) in case the type is ever changed

Side note: It is safe to avoid not to cast return address by malloc and calloc function. read: Do I cast the result of malloc?

So correct preferable form of above statement is:

struct node* nd = malloc(sizeof *nd);
  //                     ^----size-^

Two rectifications: (1) Remove typecast and (2) change variable name to nd.

Solution 3

Using sizeof-

sizeof(T) will tell the number of bytes required to store a variable of type T

Using malloc-

Malloc allocates memory dynamically, that is, at the runtime (when your program is actually being executed by CPU and its in memory). We use this mostly when we are not sure about the amount of memory which is required at runtime. So we dynamically allocate it at runtime using malloc.

Using (struct node*)-

Malloc returns a pointer to a block of memory with the amount of space that you asked for (in its parameters). This space is just some space in memory. Thus this pointer has no type associated with it. We cast this pointer to (struct node*) because it will let the machine know that the variables of type (struct node) are going to be saved in this memory.