2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Who wrote the rest of the program especially the lookup and install functions? \$\endgroup\$ – Cristian Ciupitu Apr 19 '14 at 19:31
  • \$\begingroup\$ They are extracted from k&r2, but they were adapted by me. As you can see, they look a little bit weird because I've tried to adapt them to work with a previous version of undef. I forgot to remove those changes. \$\endgroup\$ – cristid9 Apr 19 '14 at 19:55
  • 3
    \$\begingroup\$ Consider posting the entire program here. Links tend to go away after a while and that would render this question rather useless without the context. \$\endgroup\$ – Edward Apr 19 '14 at 21:30
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.