Reading Gauche

scheme gauche

何故か今日も自宅合宿。

STRING_HASH マクロ

hash_core_predef_procs 手続きを掘り始めた。とりあえず strng_access の中で使われている STRING_HASH から着手。
基本的には文字列を対象とした hash 値の計算、なマクロなのは分かるんですが、定義が以下

#define STRING_HASH(hv, chars, size)                                    \
    do {                                                                \
        int i_ = (size);                                                \
        (hv) = 0;                                                       \
        while (i_-- > 0) {                                              \
            (hv) = ((hv)<<5) - (hv) + ((unsigned char)*chars++);        \
        }                                                               \
    } while (0)

具体的にどう動くのか、がイメージできず。5bits 左にシフトしてる、という事は 32 倍するんですが、それから元の値を引いて次の文字を加えている。む、32 倍して元の値を引くってコトは 31 倍か。
これはこーゆーモノだ、と思うしかないのかなぁ。hash 値の算出に関する文書ってのがインターネットに落ちてるハズですが探しきれず。

HASH2INDEX マクロ

うーん。呼び出し元が例えば以下

    index = HASH2INDEX(table->numBuckets, table->numBucketsLog2, hashval);

あるいは定義は以下

/* HASH2INDEX
   Map a hash value to bucket number.
   We fix the word length to 32bits, since the multiplication
   constant above is fixed. */
#define HASH2INDEX(tabsiz, bits, hashval) \
    (((hashval)+((hashval)>>(32-(bits)))) & ((tabsiz) - 1))

hash 値を bucket number に map する、とある。ちなみに直上には

#define ADDRESS_HASH(result, val) \
    (result) = ((SCM_WORD(val) >> 3)*2654435761UL)

なマクロがあったりして、コメントはそのあたりに関する記述では、と。
余談は置いといて、中身ですがケツの ((tabsiz) - 1) と & してるあたりは bucket の添字を取得するためのものですな。その前の計算がよく分かりませんが、hash 値をそのまま添字にするのではなく、((hashval)>>(32 - (bits))) したナニを加えている。
数学の素養が無いので numBucketsLog2 の意味するソレが想像できん。(を
を、Reading Gauche/gauche/hash.h/ScmHashCoreによると_エントリが入る量の概算_とあるな。格納されるデータ量の概算??
なんか違うな。hash って bucket 格納 8 割目安ってどっかで見た気がする。や、違うのかな? どちらにしても何故に ((hashval)>>(32 - (bits))) を加算するのか、は分からないまま概要を簡単に書いてしまえ (を

FOUND マクロとか delete_entry とか

結構色々見てる気がしますが (そうでもないか)、初めて GC の恩恵に、な部分を目にした。delete_entry 手続きの定義は以下なんですが

static Entry *delete_entry(ScmHashCore *table,
                           Entry *entry, Entry *prev,
                           int index)
{
    if (prev) prev->next = entry->next;
    else table->buckets[index] = (void*)entry->next;
    table->numEntries--;
    SCM_ASSERT(table->numEntries >= 0);
    entry->next = NULL;         /* GC friendliness */
    return entry;
}

削除される予定なモノから伸びるリンクも切っておいた方が良いのか。多分切らなくても良いのかもしれませんが、なあたりが _GC friendliness_ なコメントの所以かと。あるいは FOUND マクロもなかなか興味深いです。成程ねー、というカンジ。面白い。

insert_entry 手続き

ぬ。最初な部分はざくっと理解できるのですが、_テーブル拡張_ なコメントの処理ブロックの意味が微妙。特に

        Scm_HashIterInit(&iter, table);
        while ((f = (Entry*)Scm_HashIterNext(&iter)) != NULL) {
            index = HASH2INDEX(newsize, newbits, f->hashval);
            f->next = newb[index];
            newb[index] = f;
        }

なソレがナニ。もう少しきちんと見てみる。

続

hash を再配置してるクサいのは分かるのですが、ってこれはアレだな挿入してるんですな。やれやれ。ポインタ云々という世界から遠ざかってると、こんなコードもワケワカになるのか。今カーネルのソース読め、とか言われると微妙なんだろうな。
一応見通しが付いたので昼寝して再開予定。

numBucketsLog2 属性

insert_entry な手続きにて以下なソレが記述されている。

        int i, newsize = (table->numBuckets << EXTEND_BITS);
        int newbits = table->numBucketsLog2 + EXTEND_BITS;

上記は

(table->numEntries > table->numBuckets*MAX_AVG_CHAIN_LIMITS)

な条件が真の場合の hash 再構築な手続きにおいて出てくるナニ。上記の閾値を越えた場合、hash が非効率という事にて作り直し、な処理をしてるんですが、newsize とか newbits はそれぞれ最終的に

        table->numBuckets = newsize;
        table->numBucketsLog2 = newbits;

という風にそれぞれの属性に格納されている。という事は_エントリが入る量の概算_ではなくって 2 ^ n の指数になるのか。だから Log2 なんですな。いやはや。
てーコトは

#define HASH2INDEX(tabsiz, bits, hashval) \
    (((hashval)+((hashval)>>(32-(bits)))) & ((tabsiz) - 1))

は log2(table->numBuckets) を 32 から引いた数で右にシフトしたナニを加えてる、という事で宜しいでしょうか。それがどーゆー意味なのかは不明 (とほほほほ
もう少しがっつり頑張れば終わるのだろうか。掘り残しなソレを見るにまだまだ先は流そげ。とりあえず今日は python 方面に去ります。