ltable

テーブルは Lua の最も重要なデータ構造だ。というか、コレクションタイプのデータ構造をこれしか持たない(配列とかは Lua にはない)。さて、ヘッダファイルを見ると、 luaH_ なるプレフィクス(Hはハッシュ表の H だろう)を持つ関数たちが用意されている。

まずはデータ構造からおさらいする。 Table は lobject.h に定義されている型で、テーブルを表す。

/*
** Tables
*/

typedef struct Node {
  TObject i_key;
  TObject i_val;
  struct Node *next;  /* for chaining */
} Node;


typedef struct Table {
  CommonHeader;
  lu_byte flags;  /* 1<<p means tagmethod(p) is not present */ 
  lu_byte lsizenode;  /* log2 of size of `node' array */
  struct Table *metatable;
  TObject *array;  /* array part */
  Node *node;
  Node *firstfree;  /* this position is free; all positions after it are full */
  GCObject *gclist;
  int sizearray;  /* size of `array' array */
} Table;

けっこう複雑だが、まずもって目につくのは array パートというのがあるという事実だ。なーんだ、そういう最適化はしているのね、と今更ながらに思う。残りのパートはよくわからないが、 node がノードリストであろうという気がする。なにせキーとバリューの構造体だ。でもなぜ linked list なのだろう。ハッシュの衝突かねぇ。

テーブルを作成する luaH_new はこうなっている。

Table *luaH_new (lua_State *L, int narray, int lnhash) {
  Table *t = luaM_new(L, Table);
  luaC_link(L, valtogco(t), LUA_TTABLE);
  t->metatable = hvalue(defaultmeta(L));
  t->flags = cast(lu_byte, ~0);
  /* temporary values (kept only if some malloc fails) */
  t->array = NULL;
  t->sizearray = 0;
  t->lsizenode = 0;
  t->node = NULL;
  setarrayvector(L, t, narray);
  setnodevector(L, t, lnhash);
  return t;
}

luaM_new は luaM_malloc をキャストつきで呼び出すマクロ。 luaC_link はガベコレまわりのようなので後で見ることにするが、たぶんマーク＆スイープするときに「Lから手繰っていくリンク」を登録するのではないかと思う。たしか Lua は世代的な GC だったはずだ。

メタテーブルは、たしか演算子の意味等を変えるためのものだ。最初はデフォルト値を渡す設計なのだろう(そしてデフォルト値は lua_State ごとに切り替えられると)。

最後の setarrayvector と setnodevector は、メモリを確保して nil をセットしているだけなので省略。というわけで luaH_new は、必要そうなメモリを確保するところまでをやるということだ。実際にいくつかの値をもとにテーブルを構成する場合は、まず必要な数のメモリを確保してから、書き込み作業を行うというわけだろう。

つぎにテーブルへのアクセス。まずは get の方が(簡単そうなので)見てみる。luaH_get は、見てみるとキーの型からディスパッチしているだけの関数で、実際には luaH_getstr (文字列)、luaH_getnum (数値)、 luaH_getany (それ以外)の3つに分けられる。順番に見るのだが、ハッシュ値を計算するところはマクロを(原意を損ねない程度に)展開しておく。

const TObject *luaH_getstr (Table *t, TString *key) {
  Node *n = t->node[lmod(key->tsv.hash, t->lsizenode)];
  do {  /* check whether `key' is somewhere in the chain */
    if (ttisstring(n->i_key) && tsvalue(n->ikey) == key)
      return n->i_val;  /* that's it */
    else n = n->next;
  } while (n);
  return &luaO_nilobject;
}

キーが文字列の場合、すでにハッシュ値は計算されているからそれを使う。発見されたノードは基本的に同じハッシュ値のはずなので、やはり同じ場合はリストで連結しているようだ。発見されない場合は nilobject が返る。ところで、内容が同じ文字列のとき、 luaS_new を使っていると常に同じデータオブジェクトを参照するはずなので、ポインタの一致で同等性を判断している。

const TObject *luaH_getnum (Table *t, int key) {
  if (1 <= key && key <= t->sizearray)
    return &t->array[key-1];
  else {
    lua_Number nk = cast(lua_Number, key);
    Node *n = hashnum(t, nk);
    do {  /* check whether `key' is somewhere in the chain */
      if (ttisnumber(n->i_key) && nvalue(n->i_key) == nk)
        return gval(n);  /* that's it */
      else n = n->next;
    } while (n);
    return &luaO_nilobject;
  }
}

数値がキーのときは、まず配列パートを探索してみるというステップが入るようだ。 hashnum はマクロではなくちゃんとした関数で、計算はちょっと面倒くさいのだが、端的に言うと lua_Number が int より長い場合を考慮にいれていろいろやっている。手元の環境では lua_Number は double になっている。

static const TObject *luaH_getany (Table *t, const TObject *key) {
  if (ttisnil(key)) return &luaO_nilobject;
  else {
    Node *n = luaH_mainposition(t, key);
    do {  /* check whether `key' is somewhere in the chain */
      if (luaO_rawequalObj(gkey(n), key)) return gval(n);  /* that's it */
      else n = n->next;
    } while (n);
    return &luaO_nilobject;
  }
}

getany の場合、ハッシュ値は mainposition という関数で計算されている。これはやっぱり型でディスパッチする関数であるが、だいたいポインタの値(アドレス)をもとにハッシュ値を計算すると考えてよいようだ。