Serendip

Web Studio

演習6-5

削除する名前と定義を見つけてテーブル（連結リスト）のリンクを繋ぎ直して、名前と定義と nlist をメモリから解放する。
見つかった場所がテーブルの先頭であれば、テーブルの先頭を次の項目を指すように変更する。

#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 *);
struct nlist *lookup(char *);
struct nlist *install(char *, char *);
char *my_strdup(char *);
char *search_defn(char *);
void undef(char *);

int main(void)
{
    char *name1 = "IN";
    char *defn1 = "1";
    char *name2 = "OUT";
    char *defn2 = "2";
    char *name3 = "SOME";
    char *defn3 = "3";
    char *defn4 = "4";

    install(name1, defn1);
    install(name2, defn2);
    install(name3, defn3);
    printf("%s is %s\n", name1, search_defn(name1));
    printf("%s is %s\n", name2, search_defn(name2));
    printf("%s is %s\n", name3, search_defn(name3));
    printf("----------\n");
    undef(name2); /* name2 の名前と定義を削除 */
    printf("%s is %s\n", name1, search_defn(name1));
    printf("%s is %s\n", name2, search_defn(name2));
    printf("%s is %s\n", name3, search_defn(name3));
    printf("----------\n");
    install(name2, defn4); /* name2 の名前と定義を再登録 */
    printf("%s is %s\n", name1, search_defn(name1));
    printf("%s is %s\n", name2, search_defn(name2));
    printf("%s is %s\n", name3, search_defn(name3));

    return 0;
}

/* undef : ハッシュテーブルから名前と定義を削除する */
void undef(char *s)
{
    struct nlist *np1, *np2; /* np1 は削除対象のポインタ */
    unsigned hashval = hash(s);

    for (np1 = np2 = hashtab[hashval]; np1 != NULL; np2 = np1, np1 = np1->next) {
        if (strcmp(s, np1->name) == 0) { /* s がハッシュテーブルに見つかった */
            if (np1 == np2) { /* リストの先頭の場合 */
                hashtab[hashval] = np1->next;
            } else { /* np2 が np1 の前の場合 */
                np2->next = np1->next;
            }
            free(np1->name);
            free(np1->defn);
            free(np1);
            break;
        }
    }

}

/* search_defn : 名前文字列 s からハッシュに登録されている定義文字列を探す */
char *search_defn(char *s)
{
    struct nlist *np;

    if ((np = lookup(s)) != NULL) { /* 見つかった */
        return np->defn;
    } else {
        return "not defined.";
    }
}

/* hash : 文字列 s に対しハッシュの値を求める */
unsigned hash(char *s)
{
    unsigned hashval;

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

/* lookup : hashtab の中で s を探す */
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; /* 見つからない */
}

/* install : hashtab の中に (name, defn) を置く */
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 = my_strdup(name)) == NULL) {
            return NULL;
        }
        hashval = hash(name);
        np->next = hashtab[hashval];
        hashtab[hashval] = np;
    } else { /* すでにある */
        free((void *) np->defn); /* 以前の defn を解放する */
    }
    if ((np->defn = my_strdup(defn)) == NULL) {
        return NULL;
    }
    return np;
}

/* my_strdup : s の複製を作る */
char *my_strdup(char *s)
{
    char *p;

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

実行結果

$ ./undef
IN is 1
OUT is 2
SOME is 3
----------
IN is 1
OUT is not defined.
SOME is 3
----------
IN is 1
OUT is 4
SOME is 3

プログラミング言語C 第2版 ANSI規格準拠

posted with amazlet at 09.11.27

B.W. カーニハン D.M. リッチー
共立出版
売り上げランキング: 9726

Amazon.co.jp で詳細を見る