Malloc Function Error: sysmalloc: Assertion failed in C

Question

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

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

I have already researched and imagine that when I allocate memory to the second node C accesses some area in memory that is already allocated, I suppose it is because the size of the struct is relatively large (8 bytes). Follows 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);
}

Answer 1

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

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

When you use Node* is the same as saying you’re 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 structure size by calling sizeof(Node*), So on this line you’re actually allocating only 4 bytes in memory, because with this instruction you’re returning the pointer size to the structure, and not the actual structure size.

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 whole structure:

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

And, correcting, its structure does not have only 8 bytes. In a 32-bit system, 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 necessary to make a alignment (padding) of structure size.

Do not forget after dislocating the memory of these nodes using the function free() (more about her here). See an example of how to release nodes from a binary tree:

Algorithm - Deallocating Binary-Tree Structure in C - Stack Overflow

Basically, the code that’s on the link is this:

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

It’s a recursive function. You fire it past the first knot, the father of them all, and it keeps calling itself to the child nodes until it reaches the end, and it comes back releasing the memory allocated to the structure of each knot, backwards. First with the left, then with the right.

Therefore, you need to be careful not to occur the pile burst, the famous stack overflow, which can happen if the amount of nodes is very numerous.