プログラミング言語 C
hash関数による テーブル参照が わからないので、訳しながら 読んでみる。
このセクションでは、構造体の より特色のある面の 説明のために、table-lookup package の 中身を 書くことにしよう。
そのコードには、マクロや コンパイラにおける symbol table management に 特徴的な ルーティンが 見出される。 例えば、#define での statement を 考えてみよう。
#define IN 1
という line が 見つかると、name "IN" と それに 置き換わる text "1" とが 1つの table に 格納される。
その後、この statement の中で name "IN" が でてくると
state = IN;
"1" と 取り換えられる。
(このように) name と 置き換える text とを 処理するには、2つの ルーティンが (必要になる)。
install(s, t) によって、name "s" と それを置き換える text "t" とを 1つの table に 記憶させる。 ここでの s と t とは 文字列である。
lookup(s) では、table から "s" を 検索し、探しだすと その place の ポインタを 返し、なければ NULL を 返す。
この algorithm を hash-search と いい、入ってくる name は 符号がつかない 小さな整数へと 変換され、それが ポインタ配列の index として 使われている。
配列の element は、それの hash値をもつ name が 記された block の リンクリストの 初め (beginning) を 指している。 hash値をもつ name が ない (element は) NULL である。
(element) (block) (block)
・-----> ・ -----> 0 (list)
0 ・→ ・→ name
0 ・→ ・→ defn ・-----> 0
0 ・→ name
・→ defn
list の中の block は 構造体であり、name と text それに 次の block に 繋げる next への (それぞれの) ポインタから なっている。 next が NULL ポインタを 指すと、それは list の 終わりを あらわす。
struct nlist { /* table entry */
struct nlist *next; /* next entry in chain */
char *name; /* defined name */
char *defn; /* replacement text */
};ここでは ポインタ配列が (次のように 使われている)。
#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE];
lookup および install で 使われる hash 関数は、文字列の中の 各文字の value を 混ぜ合わせながら 加算して、さらに array size で 割って その余り (modulo) を (戻り値として) 返している。
これは 最良の algorithm では ないが、しかし 短いし 効果的である。
/* hash: form hash value for string s */unsigned hash(char *s)
{
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}
hash値が マイナスに ならないことは unsigned 演算によって 保証されている。
hash処理によって、配列 hashtab に list の starting index が つくられる。 文字列が 見つかると、そこから 始まってる block の list に 含まれている (ことになる)。
検索は lookup によって 行なう。 lookup では、その entry が すでに 含まれていれば そのポインタを (戻り値として) 返し、なければ NULL を 返す。
/* lookup: look for s in hashtab */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; /* found */
return NULL; /* not found */
}
lookup での for ループは、リンクリストを たどっていくときに よく使われる やり方である。
for (ptr = head; ptr != NULL; ptr = ptr->next)
install では、lookup を 使って その name が すでに 含まれているかどうかを 調べている。 もしあれば 新しい定義が 古いそれと 入れ替わる。 そうでなければ 新しい entry を 作成する。
また install では、何らかの理由で 新しい entry を つくる 余地がないときは NULL を 返すようにする。(p174-176)
struct nlist *lookup(char *);
char *strdup(char *);/* install: 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 = strdup(name)) == NULL)
return NULL;
hashval = hash(name);
np->next = hashtab[hashval];
hashtab[hashbval] = np;
} else /* already there */
free((void*)np->defn); /* free previous defn */
if )((np->defn = strdup(defn))( == NULL)
return NULL;
return np;
}
(;_;)
