ltable [2] テーブルに値をセットする
セット系の関数は次の2つ。
TObject *luaH_set (lua_State *L, Table *t, const TObject *key) {
const TObject *p = luaH_get(t, key);
t->flags = 0;
if (p != &luaO_nilobject)
return cast(TObject *, p);
else {
if (ttisnil(key)) luaG_runerror(L, "table index is nil");
else if (ttisnumber(key) && nvalue(key) != nvalue(key))
luaG_runerror(L, "table index is NaN");
return newkey(L, t, key);
}
}
TObject *luaH_setnum (lua_State *L, Table *t, int key) {
const TObject *p = luaH_getnum(t, key);
if (p != &luaO_nilobject)
return cast(TObject *, p);
else {
TObject k;
setnvalue(&k, cast(lua_Number, key));
return newkey(L, t, &k);
}
}一般的な set の方を見る。 luaH_set では、引数に key しか持たない。返り値が TObject になっているので、値を返して破壊的に変更するようだ。実際、luaH_set の利用例(lapi.c や lvm.c など)を見ると、 setobj を使って luaH_set で取得したものを書き換えている。 luaH_setnum は get と getnum の関係にある関数だ。 getnum で値を取得しているところが違う。
既存のキーがあればそれをそのまま返す。一方で偽のとき、 luaH_set ではキーが nil かどうかのチェックをしている。 lua では、キーが nil ではいけないらしい。調べてみる。
Lua 5.0.2 Copyright (C) 1994-2004 Tecgraf, PUC-Rio
> a = {}
> a[0] = 1;
> return a;
table: 0x8071db0
> a[nil] = 1;
stdin:1: table index is nil
stack traceback:
stdin:1: in main chunk
[C]: ?確かにこのエラーメッセージが出ている。
さて、キーがないときには実際には newkey という関数を呼出している。これは少々長い。そしてややこしい。
static TObject *newkey (lua_State *L, Table *t, const TObject *key) {
TObject *val;
Node *mp = luaH_mainposition(t, key);
if (!ttisnil(gval(mp))) { /* main position is not free? */
Node *othern = luaH_mainposition(t, gkey(mp)); /* `mp' of colliding node */
Node *n = t->firstfree; /* get a free place */
if (othern != mp) { /* is colliding node out of its main position? */
/* yes; move colliding node into free position */
while (othern->next != mp) othern = othern->next; /* find previous */
othern->next = n; /* redo the chain with `n' in place of `mp' */
*n = *mp; /* copy colliding node into free pos. (mp->next also goes) */
mp->next = NULL; /* now `mp' is free */
setnilvalue(gval(mp));
}
else { /* colliding node is in its own main position */
/* new node will go into free position */
n->next = mp->next; /* chain new position */
mp->next = n;
mp = n;
}
}
setobj2t(gkey(mp), key); /* write barrier */
lua_assert(ttisnil(gval(mp)));
for (;;) { /* correct `firstfree' */
if (ttisnil(gkey(t->firstfree)))
return gval(mp); /* OK; table still has a free place */
else if (t->firstfree == t->node) break; /* cannot decrement from here */
else (t->firstfree)--;
}
/* no more free places; must create one */
setbvalue(gval(mp), 0); /* avoid new key being removed */
rehash(L, t); /* grow table */
val = cast(TObject *, luaH_get(t, key)); /* get new position */
lua_assert(ttisboolean(val));
setnilvalue(val);
return val;
}難しいのは、変数の意味が理解されていないからだ。ここに来て登場した firstfree の値の意味を調べる。 grep してみると、 firstfree は ltable.c からしかアクセスされないメンバである。初期値はどうなっていたかというと、 luaH_new から最後に呼ばれる setnodevector でセットされていて、
t->firstfree = gnode(t, size-1); /* first free position to be used */
となっている。 setnodevector は、ハッシュ表の実際の表を所定の長さで初期化するという関数で、 firstfree はその末尾を指している。これを理解しつつ、 newkey の次の個所を見ると、
for (;;) { /* correct `firstfree' */
if (ttisnil(gkey(t->firstfree)))
return gval(mp); /* OK; table still has a free place */
else if (t->firstfree == t->node) break; /* cannot decrement from here */
else (t->firstfree)--;
}後ろからだんだん戻っていくということに気付く。先述したように key が nil であることはありえないので(というかたぶん、「そのスロットにはキーがない」ことを nil を使って表現しているのでありえないわけだが)、 firstfree のキー部が nil のときは、「まだ空きがある」として気にしない。node は配列＝先頭要素のアドレスだから、 firstfree がどんどん手前に戻って行ってこれ以上戻れないとわかると何らかの対処をしなければならない、ということを意味している。対処というのは要するに、サイズを拡張するという操作を意味する。
これを理解した上で、次の個所を見る。
if (!ttisnil(gval(mp))) { /* main position is not free? */
Node *othern = luaH_mainposition(t, gkey(mp)); /* `mp' of colliding node */
Node *n = t->firstfree; /* get a free place */
if (othern != mp) { /* is colliding node out of its main position? */
/* yes; move colliding node into free position */
while (othern->next != mp) othern = othern->next; /* find previous */
othern->next = n; /* redo the chain with `n' in place of `mp' */
*n = *mp; /* copy colliding node into free pos. (mp->next also goes) */
mp->next = NULL; /* now `mp' is free */
setnilvalue(gval(mp));
}
else { /* colliding node is in its own main position */
/* new node will go into free position */
n->next = mp->next; /* chain new position */
mp->next = n;
mp = n;
}
}新しくキーを挿入しようという個所にもう既にデータがあるとき、つまりハッシュの衝突が発生したときの意味だ。ところがややこしいのは、衝突があると回避のために firstfree を「消費」していくことがあることにある。つまり、本来のハッシュ値は違うのにたまたま衝突してしまうことがある。それが内部の if のときだ。そうでなくて、いわゆる本当の衝突の時は処理は簡単で、
/* new node will go into free position */
n->next = mp->next; /* chain new position */
mp->next = n;
mp = n;というように、 n (firstfree) を「本来のmp」の next に繋げてデータをセットさせている。
一方、↑のようなことがやられた結果、衝突したところのハッシュ値がもともと挿入したかったものを違うとき。
while (othern->next != mp) othern = othern->next; /* find previous */
othern->next = n; /* redo the chain with `n' in place of `mp' */
*n = *mp; /* copy colliding node into free pos. (mp->next also goes) */
mp->next = NULL; /* now `mp' is free */
setnilvalue(gval(mp));othern (そのスロットを占有しているノードの本来のハッシュ値)から next をどんどん手繰っていき、「次」が、いままさに書き換えたい mp になったら、 mp のデータを n (firstfree) にコピーする(struct は代入可能なのに注意)。そして othern->next も n にしておく。というわけで mp というスロットは空いたので、目出たくここが使えるというわけだ。図にした方がわかりやすいかな。
以上のアルゴリズムは、絶対に firstfree が空いていないと実行できない。また、キーを作ろうとしているところが firstfree になっている場合があるので、そのときは1つ前のスロットに戻す処理が必要になる。そこで、 for ループでこの2つの処理を同時に実行するわけだ。
で、 firstfree が node に到達した＝もうアキがないということで rehash される。これは次のような処理になる。
static void rehash (lua_State *L, Table *t) {
int nasize, nhsize;
numuse(t, &nasize, &nhsize); /* compute new sizes for array and hash parts */
resize(L, t, nasize, luaO_log2(nhsize)+1);
}配列パートのサイズとハッシュパートのサイズを計算し、それに従って再配置している。テーブルを作成してから、数値がキーであるようなペアが追加されることもあるかもしれない。そのとき、すでに見てきたように setnum からは array に追加するようなコードはないから、すべて node に追加されている。rehash を機会に、配列パートの適正なサイズを検討する必要がある。といった処理が入るので numuse はけっこう複雑である。
ところで luaO_log2 は対数を計算する関数で、 lobject.c で定義されている。べつに大して難しくはないので説明は省く。ようは、通常の log2 のように厳密な値を計算するわけではなく整数部だけがわかればよいように最適化している関数である。で、これを使っていることからわかるように、ハッシュのノード数は 2^n 個になっている。これはなぜかというと、ハッシュキーを計算するときに、下位ビットだけを参照して高速化をはかっているからだと思われる。通常はハッシュのサイズは素数が使われるのだが(なるべく均等に分散するため)、 lua ではそのようなアプローチは取られていない。ハッシュサイズが素数である方が使われる個所が散るのは、もともとキーになるハッシュ値に多少の偏りがあっても良いようにするためだ。たとえばポインタ値を使うと、基本的には4の倍数しかキーに現れなかったりする。ここで下位ビットだけを使うと、4の倍数番目のスロットしか使われなくて効率がよくない。ところが、 lua ではキーには文字列が使われるケースが圧倒的に多い。そして文字列のハッシュ値はちょっとややこしい方法で計算されていた。そこをちゃんと調べたわけではないが、たぶん文字列のハッシュ値がうまく計算されているので、下位ビットだけを使う方式でもそれほど強く偏りが生まれないのではないかと思われる。すると、逆に下位ビットを計算する方がコストが安いということになる。まあ全部想像ですが。
さて、 numuse はちょっと長いのだが、2つ前の段落の内容を理解していればさほど難しくはない。
static void numuse (const Table *t, int *narray, int *nhash) {
int nums[MAXBITS+1];
int i, lg;
int totaluse = 0;
/* count elements in array part */
for (i=0, lg=0; lg<=MAXBITS; lg++) { /* for each slice [2^(lg-1) to 2^lg) */
int ttlg = twoto(lg); /* 2^lg */
if (ttlg > t->sizearray) {
ttlg = t->sizearray;
if (i >= ttlg) break;
}
nums[lg] = 0;
for (; i<ttlg; i++) {
if (!ttisnil(&t->array[i])) {
nums[lg]++;
totaluse++;
}
}
}
for (; lg<=MAXBITS; lg++) nums[lg] = 0; /* reset other counts */
*narray = totaluse; /* all previous uses were in array part */
/* count elements in hash part */
i = sizenode(t);
while (i--) {
Node *n = &t->node[i];
if (!ttisnil(gval(n))) {
int k = arrayindex(gkey(n));
if (k >= 0) { /* is `key' an appropriate array index? */
nums[luaO_log2(k-1)+1]++; /* count as such */
(*narray)++;
}
totaluse++;
}
}
computesizes(nums, totaluse, narray, nhash);
}
前半の for 文では、配列パートを計上している。ここで、 nums[i] というのは「2のi乗くらいの値をキーとしたデータがどれくらいあるか」を意味すると考えればよい。どんどんカウントアップしていくことがわかる。そして次にハッシュパートをなめて、数値をキーとするものがあったら nums をカウントアップしていく。実際に配列パートの大きさを決めるのは computesizes だ。
static void computesizes (int nums[], int ntotal, int *narray, int *nhash) {
int i;
int a = nums[0]; /* number of elements smaller than 2^i */
int na = a; /* number of elements to go to array part */
int n = (na == 0) ? -1 : 0; /* (log of) optimal size for array part */
for (i = 1; a < *narray && *narray >= twoto(i-1); i++) {
if (nums[i] > 0) {
a += nums[i];
if (a >= twoto(i-1)) { /* more than half elements in use? */
n = i;
na = a;
}
}
}
lua_assert(na <= *narray && *narray <= ntotal);
*nhash = ntotal - na;
*narray = (n == -1) ? 0 : twoto(n);
lua_assert(na <= *narray && na >= *narray/2);
}数値をキーとするものをすべて配列パートにするのは、さすがに空間効率が良くない。そこで、 nums を下から累積していくが、利用率が半分を切ったらそれ以上は利用しないようにしている。ハッシュは、トータルから配列パートに入れられるぶんを取り除いたものになっている。
以上で計算ができたので、 resize するが、これは配列パートとハッシュパートをそれぞれ確保しなおし、 luaH_set しなおしているだけなので解説は省略する。
