Malloc function error: sysmalloc: Assertion failed in C

I am implementing a Red Black Tree in C, and when I am going to allocate memory to the second node, it gives the error:

Sysmalloc: Assertion [...] failed. Aborted (core dumped)

I have already researched about and imagine that when I allocate memory for the second node C accesses some area in memory that is already allocated, I suppose it is because the size of struct is relatively large (8 bytes). Follow the Code: 

//struct que define os nodes
struct node {
       int key;
       struct node * left;
       struct node * right;
       struct node * parent;
       char c;
};
typedef struct node Node;

//função que seta os valores do no e retorna
Node* setNode(Node* parent, int value){
      Node* new = (Node *) malloc(sizeof(Node*));
      new->key = value;
      new->parent = parent;
      new->left = NULL;
      new->right = NULL;
      new->c = 'R';
      return new;
}

Node* insert(Node* node, Node* parent, int key){
      //checks if node is root
      if (node == NULL){
          //printf("%d\n", key);
          node = setNode(parent, key);
          //root node is always black
          //printf("%d\n", key);
          node->c = 'B';
          return node;
      }

      if (key < node->key){
          printf("entro aqui\n");
          return insert(node->left, node, key);
      }

      else
          return insert(node->right, node, key);
}
 0
cmalloc
Author: Pedro Gaspar, 2018-11-07
Source

1 answers

The error is on the line where you allocate memory for the node, inside the function setNode(): 

Node* new = (Node *) malloc(sizeof(Node*));

When you use Node* it is the same as saying that you are using " a pointer to the node structure", and, in a 32-bit system, a pointer has only 4 bytes. Only you are using this type to check the size of the structure by calling sizeof(Node*), so in this line you are actually allocating only 4 bytes in memory, because with this statement you are returning the size of the pointer to the structure, and not the size of the structure in fact.

The correct is to use the structure itself in the function sizeof(), without the asterisk, because then you will have the necessary size to store the entire structure: 

Node* new = (Node*) malloc(sizeof(Node));

And, to correct, its structure is not only 8 bytes. In a 32-bit system, the individual field sizes would be: 

int key             -> 4 bytes
struct node* left   -> 4 bytes
struct node* right  -> 4 bytes
struct node* parent -> 4 bytes
char c              -> 1 byte

Which would give a total of 17 bytes, but probably the return of sizeof(Node) will be 20 bytes because it is required to make a alignment (padding ) of the size of the structure.

Do not forget after deallocating the memory of these nodes using the function free() (more about it here). Here's an example of how to release nodes from a binary tree:

Algorithm-Deallocating binary-tree structure in C-Stack Overflow

Basically the code that is in the link is this: 

void freeTree(Node* node)
{
   if (node == NULL) return;
   freeTree(node->left);  
   freeTree(node->right);
   free(node);
}

Is a recursive function. You it fires her by passing the first node, the father of all, and she continues calling herself to the child nodes until she reaches the end, and returns releasing the memory allocated to the structure of each node, back and forth. First with the left side, then with the right.

Therefore, need to be careful not to occur the overflow of the pile, the famous stack overflow, that can happen if the number of nodes is too numerous.

 2
Author: Pedro Gaspar, 2018-11-07 09:34:42