C - Program crashes while using malloc

Question

So I'm making a XOR linked list, and whenever I'm trying to allocate memory for a new node, program crashes. Here's my code for insert function:

void add(DataType value, XORList ** xlist)
{
    XORListNode * node;
    node = ( XORListNode* )malloc( sizeof (XORListNode) );
    printf("node memory allocated\n");

    if ((*xlist)->head->prevPNext == NULL && (*xlist)->tail->prevPNext == NULL) //XOR linked list is empty: [ H - T ] + N => [ H<->T<->N ] => [ H<->A<->T ]
    {
        node->prevPNext = (*xlist)->tail; //new element points to tail
        (*xlist)->tail->prevPNext = ( XORListNode * )( (uintptr_t)(*xlist)->head ^ (uintptr_t)(*xlist)->tail ); //tail points to head and new value
        (*xlist)->head->prevPNext = (*xlist)->tail;

        (*xlist)->tail->value = value;
        (*xlist)->tail = node;
    }
    else    //Otherwise: [ H<->A<->B<-...->X<->T ] + N => [ H<->A<->B<-...->X<->T<->N ] => [ H<->A<->B<-...->X<->Y<->T ]
    {
        node->prevPNext = (*xlist)->tail;
        (*xlist)->tail->prevPNext = ( XORListNode * )( (uintptr_t)(*xlist)->tail->prevPNext ^ (uintptr_t)node );

        (*xlist)->tail->value = value;
        (*xlist)->tail = node;
    }
}

This is definition of XORList:

typedef struct XORList
{
    XORListNode * head, * tail;
} XORList;

And this is definition of XORListNode:

typedef struct XORListNode
{
    DataType value;
    struct XORListNode * prevPNext;
} XORListNode;

I would also appreciate any other comments about the code, because I'm not yet that experienced with pointers.

Thank you for your help.

Answer 1

The malloc is not the problem of your implementation. You can test this by removing the entire body of the function except of the first three lines.

As Sourav Ghosh pointed out, the main issue is that you don't check if xlist, *xlist, (*xlist)->head or (*xlist)->tail is NULL before using those pointers in if-clause if ((*xlist)->head->prevPNext == NULL && (*xlist)->tail->prevPNext == NULL).

So if you have an "uninitialized" list head and tail will be NULL (or if you've not set them to NULL they will be some value like 0xcccccccc or something completely undefined) resulting in an access violation since your're trying to access an address which is not available to your application.

To fix this you have to handle the following case in your add function:

void add(DataType value, XORList ** xlist)
{
    XORListNode * node;

    if ((xlist == NULL) || ((*xlist) == NULL))
    {
        printf("INVALID INPUT (xlist)\n");
        return;
    }

    node = ( XORListNode* )malloc( sizeof (XORListNode) );
    if (node == NULL)   // always check return values
    {
        printf("FAILED TO ALLOCATE !!!\n");
        return;
    }

    if (((*xlist)->head != NULL) && ((*xlist)->tail != NULL))
    {
        /* your current implementation goes here */
    }
    else
    {
        /*
        ** no item within list, yet!
        ** - initialize head and tail attributes of *xlist
        ** - set node->prevPNext to NULL
        */
    }
}

Three more things:

• I strongly suggest to implement a zero function for your XORList structure which ensures that the head and tail members are NULL. Otherwise they are uninitialized and a check if they are NULL will not work and you're having access violations again.
• Why do you use a double pointer to XORList in function add? A single pointer is sufficient for the code you've posted.
• Since malloc may fail in some cases you should implement a return value for function add. Otherwise the caller is unable to know if adding was successful or not. I would simply return the value of node. If the function failed the return value is NULL or nonzero in case of success.