Jump to: navigation, search

The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 6.05 on page 145

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



Solution by Paul Griffiths

int undef(char * name) {
    struct nlist * np1, * np2;

    if ((np1 = lookup(name)) == NULL)  /*  name not found  */
        return 1;

    for ( np1 = np2 = hashtab[hash(name)]; np1 != NULL;
          np2 = np1, np1 = np1->next ) {
        if ( strcmp(name, np1->name) == 0 ) {  /*  name found  */

            /*  Remove node from list  */

            if ( np1 == np2 )
                hashtab[hash(name)] = np1->next;
            else
                np2->next = np1->next;

            /*  Free memory  */

            free(np1->name);
            free(np1->defn);
            free(np1);

            return 0;
        }
    }

    return 1;  /*  name not found  */
}


Solution by Gregory Pietsch

void undef(char *s)
{
    struct nlist *np1, *np2;
    unsigned hashval = hash(s);

    for (np1 = hashtab[hashval], np2 = NULL; 
         np1 != NULL;
         np2 = np1, np1 = np1->next) 
        if (strcmp(s, np1->name) == 0) {
            /* found a match */
            free(np1->name);
            free(np1->defn);
            if (np2 == NULL) 
                /* at the beginning? */
                hashtab[hashval] = np1->next;
            else 
                /* in the middle or at the end? */
                np2->next = np1->next;
            free(np1);
            return;
        }
}

Solution by anonymous

I liked the simple functions written by Paul and Gregory, so I based my function on theirs. I also added the rest of the program and a printHashtable function which was useful for visualizing the data structure.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/*
    Exercise 6-5. Write a function undef that will remove a name and definition from the table maintained by lookup and install.
*/

#define HASHSIZE 101

struct nlist // table entry
{
    struct nlist *next; // next entry in chain
    char *name; // defined name
    char *defn; // replacement text
};

static struct nlist *hashtab[HASHSIZE]; // pointer table

struct nlist *lookup(char *s);
struct nlist *install(char *name, char *defn);
char *mystrdup(char *s);
unsigned hash(char *s);
void undef(char *s);
void printHashtable(void);

int main()
{
    install("consider", "value 1");
    install("three", "value 2");
    install("less", "value 3");
    install("taxes", "value 4");
    printHashtable();
    printf("Removing three\n");
    undef("three");
    printHashtable();
    return 0;
}

unsigned hash(char *s)
{
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

struct nlist *lookup(char *s)
{
    for (struct nlist *np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
            return np; // found
    return NULL; // not found
}

// put (name, defn) in hashtab
struct nlist *install(char *name, char *defn)
{
    struct nlist *np;
    unsigned hashval;

    if ((np = lookup(name)) == NULL) // not found
    {
        np = (struct nlist *) malloc(sizeof(*np));
        if (np == NULL || (np->name = mystrdup(name)) == NULL)
            return NULL;
        hashval = hash(name);
        np->next = hashtab[hashval]; // adds items in reverse order. First item points to null (default value of hashtab[i]). Second value points to first value and updates 
        hashtab[hashval] = np;       // the pointer in hashtab to itself, and so on. So hashtab[n] -> 1, 1->next -> NULL. Then hashtab[n] -> 2, 2->next -> 1, 1->next -> NULL 
    }
    else // already there
        free((void *) np->defn); // free memory used by previous defn
    if ((np->defn = mystrdup(defn)) == NULL)
        return NULL;
    return np;
}

char *mystrdup(char *s) // make a duplicate of s
{
    char *p = (char *) malloc(strlen(s) + 1); // + 1 for '\0'
    if (p != NULL)
        strcpy(p, s);
    return p;
}

void undef(char *s)
{
    unsigned hashval = hash(s);
    for (struct nlist *p = hashtab[hashval], *prev = NULL; p != NULL; prev = p, p = p->next)
        if (strcmp(s, p->name) == 0) // match found, now delete the contents, connect prev node to next node, and then delete node found
        {
            if (prev == NULL) // at the beginning
                hashtab[hashval] = p->next; // set the top value to the next value
            else
                prev->next = p->next; // update the previous to point to the next one so the middle one can be deleted
            free(p->name); // free the allocated memory for these strings from mystrdup/malloc
            free(p->defn);
            free(p); // then free the allocated memory for the nlist from install/malloc. Afterwards, no memory leaks and pointer is gone (if not root node) or null
            break;
        }
}

void printHashtable(void)
{
    struct nlist *p;
    for (int i = 0, j = 0; i < HASHSIZE; i++, j = 0)
    {
        p = hashtab[i];
        while (p != NULL)
        {
            for (int k = 0; k < j; k++)
                printf("\t");
            printf("%p %p %s %s\n", (void *) p, (void *) p->next, p->name, p->defn);
            p = p->next;
            j++;
        }
    }
}
Personal tools