Implementation of the undef function

Question

Write a function undef that will remove a name and a definition from the maintained by lookup and install.

Here is my solution:

void undef(char *name)
{
    struct Nlist *tmp  = hashtab[hash(name)];

    if(!strcmp(tmp->name, name)) { // delete the head node
        hashtab[hash(name)] = tmp->next;
        free(tmp->name);
        free(tmp);
        return;
    }

    for(; strcmp(tmp->next->name, name); tmp = tmp->next)
        ;

    struct Nlist *save = tmp->next; // save the desired node for deletion
    tmp->next          = tmp->next->next; // adjust the links
    free(save->name);
    free(save);
}

There are 2 main cases. The first is when we want to delete the head node, and when we want to delete a node from the rest of the list.

I will explain how my function works in the second case. The for loop will run until tmp will point to the node that precedes the desired node. Then I adjust the links and free the memory occupied by the desired node.

This approach is not good if the desired value is located at the head node, so I use a if-statement to check if the desired value is located at the head node. If it is, I adjust the head pointer and free the memory.

Here is the code for the entire program: http://ideone.com/t0bjiA.

Answer 1

It's not necessary to special-case the head of the list if you think about it in a different way. In particular, each entry in your hashtable is a pointer to an Nlist structure, so if you take the address of the hashtable entry, you can treat it just like any other node. Specifically, you can use this:

void undef(char *name)
{
    struct Nlist **tmp = &hashtab[hash(name)];
    struct Nlist *old;

    /* find our matching node */
    for ( ; *tmp && strcmp(name, (*tmp)->name); tmp=&((*tmp)->next));

    /* if we have found it, delete and adjust pointer */
    if (*tmp != NULL) {
        old = *tmp;
        free(old->name);
        free(old->defn);
        *tmp = old->next;
        free(old);
    }
}

Also note that defn was not being deleted in your original code, resulting in a memory leak.