Malloc function error: sysmalloc: Assertion failed in C

0

I'm implementing a Red Black Tree in C, and when I go to allocate memory for the second node, it gives the error:

  

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

I have already researched and imagined 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). Here is 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);
}
    
asked by anonymous 07.11.2018 / 04:27

1 answer

2

The error is on the line where you allocate memory for the node, within 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 on a 32-bit system, a pointer has only 4 bytes . Only you are using this type to check the size of the structure, 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 actual structure.

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

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

And, correcting, its structure does not have only 8 bytes. On a 32-bit system, the individual fields 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

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

Do not forget to deallocate the memory of these nodes by using the free() function (more about it here ). Here is an example of how to release the nodes of 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);
}

It is a recursive function. You fire it by passing the first node, the parent of all, and it continues calling itself to the child nodes until it reaches the end, and back releasing the memory allocated to the structure of each node, backwards. First with the left side, then the right side.

So you have to be careful not to overflow the stack, the famous stack overflow , which can happen if the number of nodes is very large.

    
07.11.2018 / 05:58