Ad

Null Pointer Error With Pre-allocated Memory?

- 1 answer

While doing a coding exercise in C, I had to allocate memory for a pointer to a structure (cur), even though the structure presumably already had memory pre-allocated for it, otherwise I would get an 'assignment to null pointer' type of error.

I was under the assumption that if the pointer was going to point to a structure with pre-allocated memory, allocating further memory would be reduntant? To clarify, the code compiles and runs without errors, just confused as to why I needed to allocate memory to achieve the intended behavior.

/* create a stack */
typedef struct {
    int top;
    struct TreeNode array[MAX_ARR_SIZE];
} Stack;

int node_comparator(const void *p, const void *q);

struct TreeNode *increasingBST(struct TreeNode *root) {
    /* add all the nodes to an array via DFT */
    int i, sorted_pos = 0;
    struct TreeNode *start, *cur;
    struct TreeNode sorted_nodes[MAX_ARR_SIZE];
    Stack *node_stack = malloc(sizeof(Stack));
    
    node_stack->top = -1; 
    node_stack->array[++node_stack->top] = *root;
    
   /* below is the pointer in question 
    * originally, this line was not here */
    cur = malloc(sizeof(struct TreeNode));
    
    while (node_stack->top != -1) {
        /* "pop" node off stack */
        *cur = node_stack->array[node_stack->top--];
        
        /* add node to array */
        sorted_nodes[sorted_pos++] = *cur;
        
        /* add right and left node to stack, if present */
        if (cur->right != NULL)
            node_stack->array[++node_stack->top] = *cur->right;
        
        if (cur->left != NULL)
            node_stack->array[++node_stack->top] = *cur->left;
    }
/* etc... */

Here's a link to a gist for full context. Thanks!

Ad

Answer

The extra memory isn't redundant since you want to save the node's details off the stack. However, you don't need to use malloc. You can declare cur at the top of your function (struct TreeNode cur;) and then use memcpy (from string.h).

memcpy(&cur,&node_stack->array[node_stack->top--],sizeof(cur));

Since cur is no longer a pointer, you would need to edit your code and replace occurrences of cur-> with cur..

Ad
source: stackoverflow.com
Ad