lua のお勉強[5]
先週は微妙に忙しかったのと、 GC まわりをどうしたものか悩んでいて書けなかった。
next
さて、あと ltable.c で見ていない関数は luaH_next だ。これは lua の next 関数に対応する(API の lua_next はけっきょく luaH_next を呼んでいる)。 next は、引数としてテーブルとインデックスを取る。インデックスを省略すると「最初の」キーと値のペアを返す。インデックスを与えると、そのインデックスをキーとして、その「次の」キーと値のペアを返す。以上を前提として、 luaH_next は次のようになる。
static int luaH_index (lua_State *L, Table *t, StkId key) {
int i;
if (ttisnil(key)) return -1; /* first iteration */
i = arrayindex(key);
if (0 <= i && i <= t->sizearray) { /* is `key' inside array part? */
return i-1; /* yes; that's the index (corrected to C) */
}
else {
const TObject *v = luaH_get(t, key);
if (v == &luaO_nilobject)
luaG_runerror(L, "invalid key for `next'");
i = cast(int, (cast(const lu_byte *, v) -
cast(const lu_byte *, gval(gnode(t, 0)))) / sizeof(Node));
return i + t->sizearray; /* hash elements are numbered after array ones */
}
}
int luaH_next (lua_State *L, Table *t, StkId key) {
int i = luaH_index(L, t, key); /* find original element */
for (i++; i < t->sizearray; i++) { /* try first array part */
if (!ttisnil(&t->array[i])) { /* a non-nil value? */
setnvalue(key, cast(lua_Number, i+1));
setobj2s(key+1, &t->array[i]);
return 1;
}
}
for (i -= t->sizearray; i < sizenode(t); i++) { /* then hash part */
if (!ttisnil(gval(gnode(t, i)))) { /* a non-nil value? */
setobj2s(key, gkey(gnode(t, i)));
setobj2s(key+1, gval(gnode(t, i)));
return 1;
}
}
return 0; /* no more elements */
}引数として与えられた key は luaH_index でインデックスを計算される。インデックスが省略されるときには key は nil になっていて、そのときには -1 が返る。あとは配列要素ならそのインデックスが、配列の範囲外であったりそもそも数値じゃなければハッシュ部のインデックスが返される。ここでハッシュ部か配列部かを区別するために sizearray が足されている。
luaH_next では、この結果を受けて、配列部のとき(-1またはsizearrayより小さいとき)には配列パートを調べて最小のものを返す。見つからなければ次はハッシュパートを小さい方から順番に辿っていって、一番小さい「キーのあるノード」を発見したらそれを返すようにしている。値の返し方はあとで、たぶん ldo か lvm を調べるときにわかるようになると思う。
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 しなおしているだけなので解説は省略する。
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 という関数で計算されている。これはやっぱり型でディスパッチする関数であるが、だいたいポインタの値(アドレス)をもとにハッシュ値を計算すると考えてよいようだ。
どうでもいいが
（（））な「脚注記法」は pre 中でも有効なのか。そういうもんか？
lstring
lstring は文字列を取り扱っている。まずヘッダファイルを見てみる。たとえば次の定義は文字列の長さを計算するものであるようだ。
#define sizestring(l) (cast(lu_mem, sizeof(union TString))+ \
(cast(lu_mem, l)+1)*sizeof(char))cast というのはマクロで、次のように定義されている。つまり、キャストを行うだけのものだ。
#define cast(t, exp) ((t)(exp))
キャストは厳密にやろうとするとカッコが頻出してわかりづらくなるからこのようにしているのだろう。 TString は、先週の lobject.h にひっそりと定義されている。
typedef union TString {
L_Umaxalign dummy; /* ensures maximum alignment for strings */
struct {
CommonHeader;
lu_byte reserved;
lu_hash hash;
size_t len;
} tsv;
} TString;reserved はおそらく確保されている文字列のサイズ、 len は文字列の長さ、hashはハッシュ値だろう。つまり文字列の(lua上の)オブジェクトのメタデータを持っているデータオブジェクトである。ハッシュ値をあらかじめ計算しておくというスタイルなのは、 lua がテーブルを多用し、また、キーには文字列が非常に多いため、効率の問題だろうか？
で、ようするに TString のサイズと文字列それ自体の長さから文字列データのメモリ上の大きさを計算するというマクロが sizestring であるようだ。ユーザプログラムから使うものではなくて、ほかのところで使うのだろう(grepすると lgc.c と lstring.c でしか使われていない)。 TString でない方の記述がもうひとつよくわからないが、気にせず進む。
ヘッダファイルをもう少し見ると、 luaS_new と luaS_newliteral という2つが lua で文字列を確保するための基本関数であることがわかる。またさらに、これらはマクロで、実体は luaS_newstr だということがわかる(文字列の長さを明示的に指定するときにはこちらを使うようだ)。 new と newliteral の差は、後者は(Cレベルでの)文字列リテラルしか受け付けないところにある。 "a" "b" という表現は C で可能だが(2つの文字列を連結したものと解釈される)、これを利用してコンパイル段階でエラーとして弾いている。
さて、 luaS_newstr の実装は次のようになる。
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
GCObject *o;
lu_hash h = (lu_hash)l; /* seed */
size_t step = (l>>5)+1; /* if string is too long, don't hash all its chars */
size_t l1;
for (l1=l; l1>=step; l1-=step) /* compute hash */
h = h ^ ((h<<5)+(h>>2)+(unsigned char)(str[l1-1]));
for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
o != NULL;
o = o->gch.next) {
TString *ts = gcotots(o);
if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0))
return ts;
}
return newlstr(L, str, l, h); /* not found */
}lua_State は初出で筆者もよくわからないが、 VM の状態(変数とか、定義済の定数とか)を管理している実体だと思う。たぶん。この関数では、主にハッシュの計算をしている。ハッシュの計算方法はなかなか複雑で、文字列の長さを初期のキーとし、末尾からstep文字ごとに計算をしている。で、このハッシュはどう使うかというと、先述したのとちょっと違っている。 G は lua_state のグローバルステートを取り出すもので、 strt は stringtable 。つまり lua の VM は「いま取り扱っている文字列」というのをぜんぶ持っているというわけだ。もし新しい文字列を取り出そうというときに、もうそれがあるならそれを返しておしまい。発見されなかったら newlstr で新しいものを作る、ということだろう。
newlstr の実装は次のとおり。
static TString *newlstr (lua_State *L, const char *str, size_t l, lu_hash h) {
TString *ts = cast(TString *, luaM_malloc(L, sizestring(l)));
stringtable *tb;
ts->tsv.len = l;
ts->tsv.hash = h;
ts->tsv.marked = 0;
ts->tsv.tt = LUA_TSTRING;
ts->tsv.reserved = 0;
memcpy(ts+1, str, l*sizeof(char));
((char *)(ts+1))[l] = '\0'; /* ending 0 */
tb = &G(L)->strt;
h = lmod(h, tb->size);
ts->tsv.next = tb->hash[h]; /* chain new entry */
tb->hash[h] = valtogco(ts);
tb->nuse++;
if (tb->nuse > cast(ls_nstr, tb->size) && tb->size <= MAX_INT/2)
luaS_resize(L, tb->size*2); /* too crowded */
return ts;
}というわけで sizestring はここで使われている。 luaM_malloc はたぶん、 GC 用に malloc するというものだと思うのでその時まで詳細ははぶく。 sizestring には、メモリ確保用の l が使われている。つまり「文字列の長さが l のときの『lua上の文字列を表現したデータオブジェクト』のサイズ」が sizestring ということだ。 sizestring で +1 しているのは、文字列がつねに null 終端するために1文字余計に必要だから。
最初はヘッダ部にデータを与えている。 reserved は 0 のママなので、筆者の予想とは違っているようだ。このフィールドを使う場面まで後回し。ちなみに marked と tt というのは CommonHeader の方に入っている。
次の memcpy はちょっと特殊だが、ようするに「TStringなパートと文字列部分」がそのまま連結されたものを luaM_malloc で返させているということだろう。
確保したものは strt の hash 番目にプッシュしている。そして nuse (number of use＝つまり利用されている文字列の個数)をインクリメントしている。ハッシュ表で nuse が size を越えているときにはハッシュが密になりすぎていると判断してハッシュの大きさを変えているようだ。ハッシュの大きさを変更する luaS_resize は、大筋はそんなに難しくないので割愛する。
lstring には、なぜか user data を確保する luaS_newudata もあるが、こちらも詳細は省く。
