Linked List in C (memory problems)

Question

I'm creating a simple linked list in C in order to get used to some memory management. I've defined a node structure that holds a char* key, char* value and a node* next.

void newnode(node *n, int x, int y)
{
    n->key = malloc(x*sizeof(char));
    n->value = malloc(y*sizeof(char)); 
}

//This how i create a new node given a key and value to make sure that I have allocated the proper amount of space. x and y are the strlengths of the key and value being added.

// In the add function I use the following two lines (when it is valid to add a new key value pair)

current->next = malloc(sizeof(node));
node_newnode(current->next,strlen(key),strlen(value));

// My remove function then searches for a key and if that key exists in the structure it removes that node. I use a delete point to keep track of the node needing deletion.

void remove(dict *d, const char *key)
{
    node* delete;
    node* current;
    current = d->head;

    while(current->next != NULL){

        if(strcmp(current->next->key,key)==0){
            delete = current->next;
            if(current->next->next != NULL)
                current = current->next->next;
            else
                current->next = NULL;
            node_destroy(delete);
            break;
        }

        current = current->next;
    }
}

// Here is the node_destroy function I used in remove. 

void node_destroy(node* delete)
{ 
    free(delete->key); 
    free(delete->value); 
    free(delete); 
} 

I'm having problems with this remove function. Essentially it seems that it is not deleting key value nodes properly and is leaving remnants of a node instead of completely removing it. I have no idea why this is possible especially when I set pointers to point past the node needing deletion. At worst case, I feel I should just be leaking memory, but somehow these nodes aren't getting deleted and are still part of the structure when I print out the dictionary. I'm sort of new to having to pay attention to the layout of memory and I can't really see whats going wrong.

Any suggestions?

P.S. Is my node destroy function not properly freeing memory?

Answer 1

What can be said right away is that if your keys and values are strings (and they are, according to your code), then to store a string of length N in memory you need to allocate N+1 bytes, not N bytes. The extra byte is required for the zero terminator character. In your code you pass strlens of the corresponding strings as x and y parameters to the allocation function and then allocate exactly x and y chars for the key and value. This is already wrong.

You don't show how you fill out the allocated key and value memory (probably by strcpy), but it will certainly overrun the allocated memory by 1 byte all the time with disastrous consequences.

Answer 2

current->next = malloc(sizeof(node));

I assume you mean sizeof(node*)? Also, can I see the struct that you use to define node? Or perhaps the whole program?

Answer 3

For one thing, you are not allocating space for the null at the end of the strings...

Another possible issue is that you should make sure that you initialize n->next = NULL;

And finally,

current = current->next->next;

should be

current->next = ...

Answer 4

You're never removing the deleted node from the linked list. It should be something like (checking for edge cases):

current->next = current->next->next;

E.g. If you have:

{foo:bar} => {bar:baz} => {goo:gai}

and you're deleting {bar:baz}, you need to set foo's next pointer to point to goo. You're not setting current->next unless after deletion current becomes the last element.

Because of this, the freed memory was still present in your list, and you read it later. This is undefined behavior, but as you saw, the memory may not be reused right away.

Answer 5

current->next = malloc(sizeof(node));

should be current->next = calloc(1,sizeof(node)); /* because safe NULL test for ->next ! */

void newnode(node *n, int x, int y)
{
    n->key = malloc(x*sizeof(char));
    n->value = malloc(y*sizeof(char)); 
}

should be

void newnode(node *n, int x, int y)
{
    n->key = malloc(x+1); /* because x comes from strlen() and sizeof(char)==1 */
    n->value = malloc(y+1); /* because x comes from strlen() and sizeof(char)==1 */ 
}