第3章 名前と名前表

st_table

メソッドテーブルやインスタンス変数テーブルとしてst_tableは既に何度か登 場してきた。本章ではまずこのst_tableについて詳しい作りを見ていくことに しよう。

概要

st_tableはハッシュテーブルだということはもう言った。ではハッシュ テーブルは何かと言うと一対一対応を記録するデータ構造である。一対一の対 応とは例えば変数名とその値、関数名とその実体、などだ。

ただしもちろんハッシュテーブル以外でも一対一対応は表せる。 例えば次のような構造体のリストを使ってもいい。

struct entry {
    ID key;
    VALUE val;
    struct entry *next;  /* 次のエントリを指す */
};

しかしこの方法は「遅い」。もしリストが1000個あったら最悪1000回リンクを たぐって探さなければならない。つまり要素の個数に比例して検索時間が長く なってしまう。これはまずい、ということで古来からいろいろな高速化手法が 考えられてきた。ハッシュテーブルはそのような手法の一つである。つまりハッ シュテーブルは「それでないとダメ」というよりは高速化できるというところ に意義がある。

さて、それでst_tableを見ていくわけだが、このライブラリは まつもとさんのオリジナルではなく、

st.cのクレジット

   1  /* This is a public domain general purpose hash table package
         written by Peter Moore @ UCB. */

(st.c)

……だ、そうである。

ちなみにGoogleで見付けた他のバージョンのコメントからすると st_tableはSTring TABLEの略らしい。しかしgeneral purposeという文面と stringではまるきり矛盾していると思うのだが……。

ハッシュテーブルとは

ハッシュテーブルの考えかたはこうだ。まず n 個の長さを持つ配列 を用意しておく。例えば n=64 としよう(図1)。

(array)
図1: 配列

そしてキーから0〜 n-1 (0〜63)の範囲の整数 i を得る関数 f を用意す る。この f をハッシュ関数と言う。 f は同じキーに対しては常に同じ i を返さなくてはいけない。例えば キーが正の整数だけと仮定できるなら、キーを64で割れば余りは必ず0〜63に なるはずだ。だからこの計算式は関数 f になりうる。

対応関係を記録するときは、キーに対して f を呼んで i を求め、用意した配列の インデックス i に値を入れればよい(図2)。 ようするに、配列へのインデックスアクセスなら超高速なのだから、キーをな んとかして整数に変換してしまおうというのがアイデアの根幹だ。

(aset)
図2: 配列にセット

しかし世の中そうそううまい話はないわけで、このアイデアには致命的 な問題がある。 n は今64しかないから、64個以上の対応関係を記録しようと したら絶対に i が重複してしまう。64個未満だとしても別々のキーに対して同 じインデックスが割り振られてしまうかもしれない。例えば先程のハッシュ関数 「key % 64」の場合だと、キーが65でも129でもハッシュ値は1である。これを 「ハッシュ値の衝突(collision)」と言う。衝突を解決する方法は何種類か 存在する。

例えば衝突が起こったらその次の要素に入れる方法がある。 これは開番地法と言う(図3)。

(nexti)
図3: 開番地法

他に、配列をそのまま使うのではなくて、配列の要素一つ一つをリンクリ ストへのポインタにする方法もある。そして衝突が起こったらどんどん リストをつなげていく。こちらは連鎖法と言う(図4)。 st_tableはこの連鎖法を採用している。

(chain)
図4: 連鎖法

ところで、もし使う可能性のあるキーの集合が事前にわかっていたとしたら 「絶対に衝突の起こらないハッシュ関数」を考えることもできるかもしれない。 そのような関数を「完全ハッシュ関数」と言う。そして実は任意の文字列の集 合に対してこの完全ハッシュ関数を作ってくれるツールがある。 GNU gperfがソレだ。rubyのパーサの実装でも実際にこれを使っているの だが……まだその話をする時期ではない。これについては第二部で続きを話す ことにしよう。

データ構造

ここからは実際のソースコードに入る。序章で書いたとおり、 データとコードがあるならまずデータから読んだほうがいい。 以下にst_tableが使うデータ型を示す。

st_table

   9  typedef struct st_table st_table;

  16  struct st_table {
  17      struct st_hash_type *type;
  18      int num_bins;                   /* スロットの数 */
  19      int num_entries;                /* 格納している要素の総数*/
  20      struct st_table_entry **bins;   /* スロット */
  21  };

(st.h)

struct st_table_entry

  16  struct st_table_entry {
  17      unsigned int hash;
  18      char *key;
  19      char *record;
  20      st_table_entry *next;
  21  };

(st.c)

st_tableがメインのテーブルの構造で、st_table_entryが値一つを格納する ホルダである。st_table_entryにはnextという名前のメンバがあるのでこれは 当然リンクリストだ。連鎖法の連鎖の部分である。st_hash_typeという型が使 われているが、これはこの後で説明するのでまずはその他の部分について 図5と見比べつつ役割を確認していただきたい。

(sttable)
図5: st_tableのデータ構造

ではst_hash_typeについて註釈する。

struct st_hash_type

  11  struct st_hash_type {
  12      int (*compare)();   /* 比較関数 */
  13      int (*hash)();      /* ハッシュ関数 */
  14  };

(st.h)

なにぶんまだ第3章なのでやや丁寧に見ていこう。

int (*compare)()

の部分はもちろん「intを返す関数へのポインタ」型のメンバcompare、 を表している。hashも同様だ。こういう変数には次のように代入し、

int
great_function(int n)
{
    /* ToDo: なにかすごいことをする */
    return n;
}

{
    int (*f)();
    f = great_function;

次のように呼び出す。

    (*f)(7);
}

ここでst_hash_typeの解説に戻ろう。hash compareと二つあるメンバの うち、hashが前述のハッシュ関数 f を表している。

一方のcompareはキーが同じであるかどうかを判定する関数である。連鎖法 では同じハッシュ値 n のところに複数の要素が入ることがあるのだった。そ の要素のどれが本当に求めるものかを知るためには、今度は完全に信用できる 比較関数が必要になる。そのための関数がcompareだ。

このst_hash_typeはなかなかうまい汎用化技法である。ハッシュテーブル自 体は格納するキーがどんな型なのか特定できない。例えばrubyでは st_tableのキーとしてIDchar*VALUEを使っているのだが、それぞ れに全く同じ仕組みのハッシュを書いてやるのはいくらなんでもバカらしい。 キーの型が違ったところで変化するのはハッシュ関数などごく一部だけで、メ モリ割り当てや衝突検出など大部分のコードは同じだからだ。そこで型によっ て実装が違う部分「だけ」を関数としてくくりだし、それへのポインタを受け 取って使うことにするのである。これによってコードの大部分を占めるハッシュ テーブル自体の実装を使いまわすことができる。

オブジェクト指向言語だとそもそもオブジェクトに手続きをくっつけて持ち運 ぶことができるのでこういう仕組みは必要ない。あるいは、こういう仕組みを 言語の機能として組み込んでいる、というほうが正しいか。

st_hash_typeの例

st_hash_typeのような構造体を使う方法は確かに汎用化としてはうまいのだ が、実際にどんなコードを通るのかということは逆にわかりにくくなる。 hashcompareにどういう関数が使われるのか見てみないとどうも実感が つかめない。それには前章でも登場していたst_init_numtable()を見てみる といいだろう。これは整数型キーのためのテーブルを作る関数だ。

st_init_numtable()

 182  st_table*
 183  st_init_numtable()
 184  {
 185      return st_init_table(&type_numhash);
 186  }

(st.c)

st_init_table()がテーブルのメモリを割り当ててたりする関数で、 type_numhashst_hash_type(メンバ名で言うとtype)になる。 そのtype_numhashはと言うと……

type_numhash

  37  static struct st_hash_type type_numhash = {
  38      numcmp,
  39      numhash,
  40  };

 552  static int
 553  numcmp(x, y)
 554      long x, y;
 555  {
 556      return x != y;
 557  }

 559  static int
 560  numhash(n)
 561      long n;
 562  {
 563      return n;
 564  }

(st.c)

とても単純だ。rubyのインタプリタで使うテーブルは だいたいこのtype_numhashを使っている。

st_lookup()

では今度はこの構造を使う関数を見ていこう。最初は検索用の関数から見てい くのがいい。ハッシュテーブルを検索する関数st_lookup()を以下に示す。

st_lookup()

 247  int
 248  st_lookup(table, key, value)
 249      st_table *table;
 250      register char *key;
 251      char **value;
 252  {
 253      unsigned int hash_val, bin_pos;
 254      register st_table_entry *ptr;
 255
 256      hash_val = do_hash(key, table);
 257      FIND_ENTRY(table, ptr, hash_val, bin_pos);
 258
 259      if (ptr == 0) {
 260          return 0;
 261      }
 262      else {
 263          if (value != 0)  *value = ptr->record;
 264          return 1;
 265      }
 266  }

(st.c)

重要なところはほとんどdo_hash()FIND_ENTRY()で行われているようだ。 順番に見る。

do_hash()

  68  #define do_hash(key,table) (unsigned int)(*(table)->type->hash)((key))

(st.c)

念のため書くと、マクロ本体のややこしい部分は

(table)->type->hash

という関数ポインタから、keyを引数にして関数を起動する記法である。 *tableにはかからない。つまり型ごとに用意されたハッシュ関数 type->hashでもってkeyに対するハッシュ値を求めるのがこのマクロだ。

続いてFIND_ENTRY()を見る。

FIND_ENTRY()

 235  #define FIND_ENTRY(table, ptr, hash_val, bin_pos) do {\
 236      bin_pos = hash_val%(table)->num_bins;\
 237      ptr = (table)->bins[bin_pos];\
 238      if (PTR_NOT_EQUAL(table, ptr, hash_val, key)) {\
 239          COLLISION;\
 240          while (PTR_NOT_EQUAL(table, ptr->next, hash_val, key)) {\
 241              ptr = ptr->next;\
 242          }\
 243          ptr = ptr->next;\
 244      }\
 245  } while (0)

 227  #define PTR_NOT_EQUAL(table, ptr, hash_val, key) ((ptr) != 0 && \
          (ptr->hash != (hash_val) || !EQUAL((table), (key), (ptr)->key)))

  66  #define EQUAL(table,x,y) \
          ((x)==(y) || (*table->type->compare)((x),(y)) == 0)

(st.c)

COLLISIONはデバッグ用のマクロなので無視していい(すべきだ)。

FIND_ENTRY()の引数は前から

  1. st_table
  2. 使うべきテンポラリ変数
  3. ハッシュ値
  4. 検索キー

である。また二番目の引数には見付かったst_table_entry*が保存される。

それと一番外側には複数の式からなるマクロを安全にくくるためのdowhile(0)が使ってある。これはrubyの、と言うよりC言語のプリプロセッ サのイディオムだ。if(1)だとelseが付いてしまう恐れがある。 while(1)だと最後にbreakが必要になる。

while(0)のあとにセミコロンを置かないのもポイントだ。なぜなら、

FIND_ENTRY();

と普通に書いたときに文末のセミコロンが無駄にならないからである。

st_add_direct()

続いてハッシュテーブルに新しい関連付けを登録する関数st_add_direct()を 見よう。この関数はキーが既に登録されているかどうかを検査せず、無条件 に新しいエントリを追加する。それがつまり関数名の「direct」の意味だ。

st_add_direct()

 308  void
 309  st_add_direct(table, key, value)
 310      st_table *table;
 311      char *key;
 312      char *value;
 313  {
 314      unsigned int hash_val, bin_pos;
 315
 316      hash_val = do_hash(key, table);
 317      bin_pos = hash_val % table->num_bins;
 318      ADD_DIRECT(table, key, value, hash_val, bin_pos);
 319  }

(st.c)

先程と同じくハッシュ値を求めるマクロdo_hash()の呼び出しがある。その 次の計算もFIND_ENTRY()の最初にあったもので、ハッシュ値を実際のインデッ クスに変換する。

そして挿入操作自体はADD_DIRECT()で実行されているようだ。これも、名前 が大文字であることから想像できるように、マクロである。

ADD_DIRECT()

 268  #define ADD_DIRECT(table, key, value, hash_val, bin_pos) \
 269  do {                                                     \
 270      st_table_entry *entry;                               \
 271      if (table->num_entries / (table->num_bins)           \
                              > ST_DEFAULT_MAX_DENSITY) {      \
 272          rehash(table);                                   \
 273          bin_pos = hash_val % table->num_bins;            \
 274      }                                                    \
 275                                                           \
          /*(A)*/                                            \
 276      entry = alloc(st_table_entry);                       \
 277                                                           \
 278      entry->hash = hash_val;                              \
 279      entry->key = key;                                    \
 280      entry->record = value;                               \
          /*(B)*/                                            \
 281      entry->next = table->bins[bin_pos];                  \
 282      table->bins[bin_pos] = entry;                        \
 283      table->num_entries++;                                \
 284  } while (0)

(st.c)

最初のifは例外的な場合を扱っているので後にして、その次から。

(A)st_table_entryを割り当て、初期化して、

(B)entryをリストの先頭に追加する。 こちらはリストを扱うときのイディオムだ。つまり

entry->next = list_beg;
list_beg = entry;

でリストの先頭にエントリを追加することができる。Lispの用語を使って 「cons(コンス)する」と言うこともある。もしlist_begNULLでも このコードは通用することを確認しよう。

最後に、棚上げにしておいたコードを説明する。

ADD_DIRECT()rehash

 271      if (table->num_entries / (table->num_bins)           \
                              > ST_DEFAULT_MAX_DENSITY) {      \
 272          rehash(table);                                   \
 273          bin_pos = hash_val % table->num_bins;            \
 274      }                                                    \

(st.c)

DENSITYとは「濃度」。つまりこの条件式ではハッシュテーブルが「混んで いないか」確かめている。 st_tableでは同じbin_posを使っている値が増えるほどリンクリストが 長くなる、つまり検索が遅くなる。だからbinの数に対 して要素数が多くなりすぎたら、binを増やして混雑を緩和するわけだ。

現在ST_DEFAULT_MAX_DENSITY

ST_DEFAULT_MAX_DENSITY

  23  #define ST_DEFAULT_MAX_DENSITY 5

(st.c)

と設定されているから、全てのbin_posに五つのst_table_entryが連なって いるような状況になったらサイズを増やす、ということになる。

st_insert()

st_insert()st_add_direct()st_lookup()の組み合わせにすぎないので この二つが分かれば簡単である。

st_insert()

 286  int
 287  st_insert(table, key, value)
 288      register st_table *table;
 289      register char *key;
 290      char *value;
 291  {
 292      unsigned int hash_val, bin_pos;
 293      register st_table_entry *ptr;
 294
 295      hash_val = do_hash(key, table);
 296      FIND_ENTRY(table, ptr, hash_val, bin_pos);
 297
 298      if (ptr == 0) {
 299          ADD_DIRECT(table, key, value, hash_val, bin_pos);
 300          return 0;
 301      }
 302      else {
 303          ptr->record = value;
 304          return 1;
 305      }
 306  }

(st.c)

既に要素がテーブルに登録されているかどうか調べ、 登録されていないときにだけ追加する。 実際に追加したら真を返す。追加しなかったら偽を返す。

IDとシンボル

IDというものが何であるかということは既に述べた。任意の文字列と一対一 に対応する数値のことで、いろいろな名前を表すために使われる。実際の型は unsigned intだ。

char*からID

文字列からIDへの変換はrb_intern()で行っている。 この関数はやや長いので途中を省略して掲載しよう。

rb_intern()(簡約版)

5451  static st_table *sym_tbl;       /*  char* → ID   */
5452  static st_table *sym_rev_tbl;   /*  ID → char*   */

5469  ID
5470  rb_intern(name)
5471      const char *name;
5472  {
5473      const char *m = name;
5474      ID id;
5475      int last;
5476
          /* 既にnameに対応するIDが登録されていたらそれを返す */
5477      if (st_lookup(sym_tbl, name, &id))
5478          return id;

          /* 省略……新しいIDを作る */

          /* nameとIDの関連を登録する */
5538    id_regist:
5539      name = strdup(name);
5540      st_add_direct(sym_tbl, name, id);
5541      st_add_direct(sym_rev_tbl, id, name);
5542      return id;
5543  }

(parse.y)

文字列とIDの一対一対応はst_tableを使って実現できる。 特に難しいところはないだろう。

省略しているところでは何をしているかと言うと、グローバル変数名や インスタンス変数名を特別扱いしてフラグを立てているのである。 パーサで、IDから変数 の種類を知る必要があるからだ。だがIDの原理自体にはあまり関りがないこと なので、ここには載せない。

IDからchar*

rb_intern()の逆、IDからchar*を得るために使うのがrb_id2name()である。 御存知と思うが、id2nameの2はtoのことだ。toとtwoの発音が同じだから 代わりに使っているのだ。この記法はプログラムではわりとよく見かける。

この関数もIDの種別フラグをいろいろしているために長いので、思い切り 簡単にしてものを見ておくことにする。

rb_id2name()(簡約版)

char *
rb_id2name(id)
    ID id;
{
    char *name;

    if (st_lookup(sym_rev_tbl, id, &name))
        return name;
    return 0;
}

ちょっと簡単にしすぎたような気もするが、 実際に小細工を削ればこんなものなのだ。

ここで注目したいのは、検索したnameをコピーしていないことである。rubyの APIでは返り値は常に、free()する必要はない(してはならない)。また引数 を渡した場合は常にコピーして使ってくれる。つまり生成と解放が常にユーザか rubyか、片方で完結するようになっているのだ。

では生成と解放を対応させることができない(渡したら渡しっぱなしになる) 値の場合はどうするかというと、その時はRubyオブジェクトを使うようにする。 まだ話していないが、Rubyのオブジェクトは我々が面倒を見なくとも必要が なくなったときに自動的に解放されるからだ。

VALUEIDの変換

IDはRubyレベルではSymbolクラスのインスタンスとして表され、"string".internの ようにして得ることができる。そのString#internの実体がrb_str_intern()だ。

rb_str_intern()

2996  static VALUE
2997  rb_str_intern(str)
2998      VALUE str;
2999  {
3000      ID id;
3001
3002      if (!RSTRING(str)->ptr || RSTRING(str)->len == 0) {
3003          rb_raise(rb_eArgError, "interning empty string");
3004      }
3005      if (strlen(RSTRING(str)->ptr) != RSTRING(str)->len)
3006          rb_raise(rb_eArgError, "string contains `\\0'");
3007      id = rb_intern(RSTRING(str)->ptr);
3008      return ID2SYM(id);
3009  }

(string.c)

この関数はrubyのクラスライブラリのコード例としてもなかなか手頃だ。 RSTRING()を使ってキャストし、構造体メンバにアクセスしているところに 注目してほしい。

コードを読もう。まずrb_raise()は単なるエラー処理なのでとりあえず無視。 先程見たばかりのrb_intern()があり、ID2SYM()がある。ID2SYM()IDSymbolに変換するマクロだった。

またこの逆の操作はSymbol#to_sなどで行える。 その実体はsym_to_sである。

sym_to_s()

 522  static VALUE
 523  sym_to_s(sym)
 524      VALUE sym;
 525  {
 526      return rb_str_new2(rb_id2name(SYM2ID(sym)));
 527  }

(object.c)

SYM2ID()SymbolVALUE)をIDに変換するマクロである。

なんてことはない関数に見えるが、メモリ処理まわりには注意すべきだろう。 rb_id2name()free()してはならないchar*を返し、rb_str_new2()は引数の char*をコピーして使う(また引数を変更したりはしない)。このように 方針が一貫しているからこそ関数の連鎖だけで書けるのである。


御意見・御感想・誤殖の指摘などは 青木峰郎 <aamine@loveruby.net> までお願いします。

『Rubyソースコード完全解説』 はインプレスダイレクトで御予約・御購入いただけます (書籍紹介ページへ飛びます)。

Copyright (c) 2002-2004 Minero Aoki, All rights reserved.