C - テーブル参照 (lookup, install, undef)

プログラミング言語C 第2版 ANSI規格準拠
B.W. カーニハン D.M. リッチー (著)
石田 晴久 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: C
• Clang (コンパイラ)

プログラミング言語C 第2版 ANSI規格準拠 (B.W. カーニハン D.M. リッチー (著)、 石田 晴久 (翻訳)、共立出版)の第6章(構造体)、6.6(テーブル参照)、演習6-5を解いてみる。

その他参考書籍

• プログラミング言語Cアンサー・ブック 第2版 (クロビス・L．トンド、スコット・E．ギンペル(著)、矢吹 道郎(翻訳))

演習 6-5.

コード

sample.c

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

#define HASHSIZE 101

struct nlist {
    struct nlist *next;
    char *name;
    char *defn;
};

static struct nlist *hashtab[HASHSIZE];
unsigned hash(char *s);
struct nlist *lookup(char *s);
struct nlist *install(char *, char *);
void undef(char *);
char *strdup(char *);


int main()
{
    int i;
    install("programming", "python");
    install("blog", "blogger");
    install("web", "JavaScript");
    install("country", "jp");
    for (i = 0; i < HASHSIZE; i++)
        if (hashtab[i]) {
            printf("%s %s\n", hashtab[i]->name, hashtab[i]->defn);
        }
    undef("blog");
    printf("blogを削除後\n");
    for (i = 0; i < HASHSIZE; i++)
        if (hashtab[i] != NULL)
            printf("%s %s\n", hashtab[i]->name, hashtab[i]->defn);
    install("blog", "blogspot");
    install("programming", "c");
    printf("もう一度install、さらに既にあるのにもinstall後\n");
    for (i = 0; i < HASHSIZE; i++)
        if (hashtab[i] != NULL)
            printf("%s %s\n", hashtab[i]->name, hashtab[i]->defn);
    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)
{
    struct nlist *np;
    
    for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
            return np;
    return NULL;
}

struct nlist *install(char *name, char *defn)
{
    struct nlist *np;
    unsigned hashval;
    
    if ((np = lookup(name)) == NULL) {
        np = (struct nlist *) malloc(sizeof(*np));
        if (np == NULL || (np->name = strdup(name)) == NULL)
            return NULL;
        hashval = hash(name);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    } else
        free((void *) np->defn);
    if ((np->defn = strdup(defn)) == NULL)
        return NULL;
    return np;
}

void undef(char *s)
{
    struct nlist *pre, *np;
    unsigned hashval = hash(s);
    for (np = hashtab[hashval]; np != NULL; np = np->next) {
        if (strcmp(s, np->name) == 0)
            break;
        pre = np;
    }
    if (np != NULL) {
        if (pre == NULL)
            hashtab[hashval] = np->next;
        else
            pre->next = np->next;
        free((void *) np->name);
        free((void *) np->defn);
        free((void *) np);
    }
}

char *strdup(char *s)
{
    char *p;
    
    p = (char *) malloc(strlen(s) + 1);
    if (p != NULL)
        strcpy(p, s);
    return p;
}

入出力結果(Terminal)

$ ./a.out
web JavaScript
programming python
blog blogger
country jp
blogを削除後
web JavaScript
programming python
 
country jp
もう一度install、さらに既にあるのにもinstall後
web JavaScript
programming c
blog blogspot
country jp
$