hash.c おさらい

gauche

って思ってたんですがちょっとマテ。なんで hash.c なんだったっけ、と冷静になり module.c の中の Scm_FindBinding() 手続き見てて Scm_HashTableRef() 手続きを掘りはじめたのがきっかけだった事が先程判明。
という事で一旦おらさいしてみます。微妙にへろへろですが ...

という事で

洗い出し。

$ grep '^[a-zA-Z]' hash.c
typedef struct EntryRec {
typedef Entry *SearchProc(ScmHashCore *core, intptr_t key, ScmDictOp op);
static unsigned int round2up(unsigned int val);
u_long Scm_EqHash(ScmObj obj)
u_long Scm_EqvHash(ScmObj obj)
u_long Scm_Hash(ScmObj obj)
u_long Scm_HashString(ScmString *str, u_long modulo)
static Entry *insert_entry(ScmHashCore *table,
static Entry *delete_entry(ScmHashCore *table,
static Entry *address_access(ScmHashCore *table,
static u_long address_hash(const ScmHashCore *ht, intptr_t obj)
static int address_cmp(const ScmHashCore *ht, intptr_t key, intptr_t k2)
static u_long eqv_hash(const ScmHashCore *table, intptr_t key)
static int eqv_cmp(const ScmHashCore *table, intptr_t key, intptr_t k2)
static u_long equal_hash(const ScmHashCore *table, intptr_t key)
static int equal_cmp(const ScmHashCore *table, intptr_t key, intptr_t k2)
static Entry *string_access(ScmHashCore *table, intptr_t k, ScmDictOp op)
static u_long string_hash(const ScmHashCore *table, intptr_t key)
static int string_cmp(const ScmHashCore *table, intptr_t k1, intptr_t k2)
static u_long multiword_hash(const ScmHashCore *table, intptr_t key)
static Entry *multiword_access(ScmHashCore *table, intptr_t k, ScmDictOp op)
static Entry *general_access(ScmHashCore *table, intptr_t key, ScmDictOp op)
static void hash_core_init(ScmHashCore *table,
int  hash_core_predef_procs(ScmHashType type,
void Scm_HashCoreInitSimple(ScmHashCore *core,
void Scm_HashCoreInitGeneral(ScmHashCore *core,
int Scm_HashCoreTypeToProcs(ScmHashType type,
void Scm_HashCoreCopy(ScmHashCore *dst, const ScmHashCore *src)
void Scm_HashCoreClear(ScmHashCore *table)
ScmDictEntry *Scm_HashCoreSearch(ScmHashCore *table, intptr_t key,
int Scm_HashCoreNumEntries(ScmHashCore *table)
void Scm_HashIterInit(ScmHashIter *iter, ScmHashCore *table)
ScmDictEntry *Scm_HashIterNext(ScmHashIter *iter)
static void hash_print(ScmObj obj, ScmPort *port, ScmWriteContext *ctx);
SCM_DEFINE_BUILTIN_CLASS(Scm_HashTableClass, hash_print, NULL, NULL, NULL,
ScmObj Scm_MakeHashTableSimple(ScmHashType type, int initSize)
ScmObj Scm_HashTableCopy(ScmHashTable *src)
ScmObj Scm_HashTableRef(ScmHashTable *ht, ScmObj key, ScmObj fallback)
ScmObj Scm_HashTableSet(ScmHashTable *ht, ScmObj key, ScmObj value, int flags)
ScmObj Scm_HashTableDelete(ScmHashTable *ht, ScmObj key)
ScmObj Scm_HashTableKeys(ScmHashTable *table)
ScmObj Scm_HashTableValues(ScmHashTable *table)
ScmObj Scm_HashTableStat(ScmHashTable *table)
static void hash_print(ScmObj obj, ScmPort *port, ScmWriteContext *ctx)
static unsigned int round2up(unsigned int val)
ScmHashEntry *Scm_HashTableGet(ScmHashTable *ht, ScmObj key)
ScmHashEntry *Scm_HashTableAdd(ScmHashTable *ht, ScmObj key, ScmObj value)
ScmHashEntry *Scm_HashTablePut(ScmHashTable *ht, ScmObj key, ScmObj value)
void Scm__HashIterInitCompat(ScmHashTable *table, ScmHashIter *iter)
ScmHashEntry *Scm__HashIterNextCompat(ScmHashIter *iter)
ScmObj Scm_MakeHashTableMultiWord(int keysize, int initsize)
ScmObj Scm_MakeHashTableFull(ScmClass *klass, int type, ScmHashProc hashfn,
ScmObj Scm_MakeHashTable(ScmHashProc *hashfn,
$

えーと上記全部が hash.c 内で定義されてる関数な情報でもないですし、漏れがある事もあり得ます。外 (hash.c の) との i/f になっていると思われる手続きは以下?

$ grep '^Scm' hash.c
ScmDictEntry *Scm_HashCoreSearch(ScmHashCore *table, intptr_t key,
ScmDictEntry *Scm_HashIterNext(ScmHashIter *iter)
ScmObj Scm_MakeHashTableSimple(ScmHashType type, int initSize)
ScmObj Scm_HashTableCopy(ScmHashTable *src)
ScmObj Scm_HashTableRef(ScmHashTable *ht, ScmObj key, ScmObj fallback)
ScmObj Scm_HashTableSet(ScmHashTable *ht, ScmObj key, ScmObj value, int flags)
ScmObj Scm_HashTableDelete(ScmHashTable *ht, ScmObj key)
ScmObj Scm_HashTableKeys(ScmHashTable *table)
ScmObj Scm_HashTableValues(ScmHashTable *table)
ScmObj Scm_HashTableStat(ScmHashTable *table)
ScmHashEntry *Scm_HashTableGet(ScmHashTable *ht, ScmObj key)
ScmHashEntry *Scm_HashTableAdd(ScmHashTable *ht, ScmObj key, ScmObj value)
ScmHashEntry *Scm_HashTablePut(ScmHashTable *ht, ScmObj key, ScmObj value)
ScmHashEntry *Scm__HashIterNextCompat(ScmHashIter *iter)
ScmObj Scm_MakeHashTableMultiWord(int keysize, int initsize)
ScmObj Scm_MakeHashTableFull(ScmClass *klass, int type, ScmHashProc hashfn,
ScmObj Scm_MakeHashTable(ScmHashProc *hashfn,
$

特に ScmObj 戻すのなんて絶対 i/f だよな、と。しかし grep ばっかしてねぇで、きちっと読めよって話ですな。あ、駄目だ。void がスルーされてるし

$ grep '^Scm\|^void' hash.c
void Scm_HashCoreInitSimple(ScmHashCore *core,
void Scm_HashCoreInitGeneral(ScmHashCore *core,
void Scm_HashCoreCopy(ScmHashCore *dst, const ScmHashCore *src)
void Scm_HashCoreClear(ScmHashCore *table)
ScmDictEntry *Scm_HashCoreSearch(ScmHashCore *table, intptr_t key,
void Scm_HashIterInit(ScmHashIter *iter, ScmHashCore *table)
ScmDictEntry *Scm_HashIterNext(ScmHashIter *iter)
ScmObj Scm_MakeHashTableSimple(ScmHashType type, int initSize)
ScmObj Scm_HashTableCopy(ScmHashTable *src)
ScmObj Scm_HashTableRef(ScmHashTable *ht, ScmObj key, ScmObj fallback)
ScmObj Scm_HashTableSet(ScmHashTable *ht, ScmObj key, ScmObj value, int flags)
ScmObj Scm_HashTableDelete(ScmHashTable *ht, ScmObj key)
ScmObj Scm_HashTableKeys(ScmHashTable *table)
ScmObj Scm_HashTableValues(ScmHashTable *table)
ScmObj Scm_HashTableStat(ScmHashTable *table)
ScmHashEntry *Scm_HashTableGet(ScmHashTable *ht, ScmObj key)
ScmHashEntry *Scm_HashTableAdd(ScmHashTable *ht, ScmObj key, ScmObj value)
ScmHashEntry *Scm_HashTablePut(ScmHashTable *ht, ScmObj key, ScmObj value)
void Scm__HashIterInitCompat(ScmHashTable *table, ScmHashIter *iter)
ScmHashEntry *Scm__HashIterNextCompat(ScmHashIter *iter)
ScmObj Scm_MakeHashTableMultiWord(int keysize, int initsize)
ScmObj Scm_MakeHashTableFull(ScmClass *klass, int type, ScmHashProc hashfn,
ScmObj Scm_MakeHashTable(ScmHashProc *hashfn,
$

あ。static だったり int 戻すのもあるな。

static unsigned int round2up(unsigned int val);
static Entry *insert_entry(ScmHashCore *table,
static Entry *delete_entry(ScmHashCore *table,
static Entry *address_access(ScmHashCore *table,
static u_long address_hash(const ScmHashCore *ht, intptr_t obj)
static int address_cmp(const ScmHashCore *ht, intptr_t key, intptr_t k2)
static u_long eqv_hash(const ScmHashCore *table, intptr_t key)
static int eqv_cmp(const ScmHashCore *table, intptr_t key, intptr_t k2)
static u_long equal_hash(const ScmHashCore *table, intptr_t key)
static int equal_cmp(const ScmHashCore *table, intptr_t key, intptr_t k2)
static Entry *string_access(ScmHashCore *table, intptr_t k, ScmDictOp op)
static u_long string_hash(const ScmHashCore *table, intptr_t key)
static int string_cmp(const ScmHashCore *table, intptr_t k1, intptr_t k2)
static u_long multiword_hash(const ScmHashCore *table, intptr_t key)
static Entry *multiword_access(ScmHashCore *table, intptr_t k, ScmDictOp op)
static Entry *general_access(ScmHashCore *table, intptr_t key, ScmDictOp op)
static void hash_core_init(ScmHashCore *table,
int  hash_core_predef_procs(ScmHashType type,
void Scm_HashCoreInitSimple(ScmHashCore *core,
void Scm_HashCoreInitGeneral(ScmHashCore *core,
int Scm_HashCoreTypeToProcs(ScmHashType type,
void Scm_HashCoreCopy(ScmHashCore *dst, const ScmHashCore *src)
void Scm_HashCoreClear(ScmHashCore *table)
ScmDictEntry *Scm_HashCoreSearch(ScmHashCore *table, intptr_t key,
int Scm_HashCoreNumEntries(ScmHashCore *table)
void Scm_HashIterInit(ScmHashIter *iter, ScmHashCore *table)
ScmDictEntry *Scm_HashIterNext(ScmHashIter *iter)
static void hash_print(ScmObj obj, ScmPort *port, ScmWriteContext *ctx);
ScmObj Scm_MakeHashTableSimple(ScmHashType type, int initSize)
ScmObj Scm_HashTableCopy(ScmHashTable *src)
ScmObj Scm_HashTableRef(ScmHashTable *ht, ScmObj key, ScmObj fallback)
ScmObj Scm_HashTableSet(ScmHashTable *ht, ScmObj key, ScmObj value, int flags)
ScmObj Scm_HashTableDelete(ScmHashTable *ht, ScmObj key)
ScmObj Scm_HashTableKeys(ScmHashTable *table)
ScmObj Scm_HashTableValues(ScmHashTable *table)
ScmObj Scm_HashTableStat(ScmHashTable *table)
static void hash_print(ScmObj obj, ScmPort *port, ScmWriteContext *ctx)
static unsigned int round2up(unsigned int val)
ScmHashEntry *Scm_HashTableGet(ScmHashTable *ht, ScmObj key)
ScmHashEntry *Scm_HashTableAdd(ScmHashTable *ht, ScmObj key, ScmObj value)
ScmHashEntry *Scm_HashTablePut(ScmHashTable *ht, ScmObj key, ScmObj value)
void Scm__HashIterInitCompat(ScmHashTable *table, ScmHashIter *iter)
ScmHashEntry *Scm__HashIterNextCompat(ScmHashIter *iter)
ScmObj Scm_MakeHashTableMultiWord(int keysize, int initsize)
ScmObj Scm_MakeHashTableFull(ScmClass *klass, int type, ScmHashProc hashfn,
ScmObj Scm_MakeHashTable(ScmHashProc *hashfn,
$

わはは。なんだこのエントリ。無駄に長いぞ。
アタマに static 付いてるのは i/f になり得ないのでとりあえずスルーとして、コンストラクタくさいのは

  • void Scm_HashCoreInitSimple(ScmHashCore *core,
  • void Scm_HashCoreInitGeneral(ScmHashCore *core,
  • ScmObj Scm_MakeHashTableSimple(ScmHashType type, int initSize)

くらい?
ってか、微妙に gdgd 進めてる感満点でスミマセン。どうやらコンストラクタは Scm_MakeHashTableSimple() 手続きらしくはあるんですが weak.c に定義されてる Scm_MakeWeakHashTableSimple() 手続きもそうらしい。

なんか gdgd 杉なんで

とりあえずコンストラクタと思われる Scm_MakeHashTableSimple() 手続きを起点に掘ってみる事にします。以下なカンジ。

SCM_DEFINE_BUILTIN_CLASS(Scm_HashTableClass, hash_print, NULL, NULL, NULL,
                         SCM_CLASS_DICTIONARY_CPL);

ScmObj Scm_MakeHashTableSimple(ScmHashType type, int initSize)
{
    ScmHashTable *z;
    /* We only allow ScmObj in <hash-table> */
    if (type > SCM_HASH_GENERAL) {
        Scm_Error("Scm_MakeHashTableSimple: wrong type arg: %d", type);
    }
    z = SCM_NEW(ScmHashTable);
    SCM_SET_CLASS(z, SCM_CLASS_HASH_TABLE);
    Scm_HashCoreInitSimple(&z->core, type, initSize, NULL);
    z->type = type;
    return SCM_OBJ(z);
}

とりあえず、直上でナニされてるマクロ見てみる。gauche.h にて以下な定義。

/* Define built-in class statically -- full-featured version */
#define SCM_DEFINE_BUILTIN_CLASS(cname, printer, compare, serialize, allocate, cpa) \
    SCM__DEFINE_CLASS_COMMON(cname, 0,                    \
                             SCM_CLASS_BUILTIN,           \
                             printer, compare, serialize, allocate, cpa)

このあたり、明日きちっとトレイスします。脱線しそうなんで ...

Hash のコンストラクタ

ざくっと以下。

    /* We only allow ScmObj in <hash-table> */
    if (type > SCM_HASH_GENERAL) {
        Scm_Error("Scm_MakeHashTableSimple: wrong type arg: %d", type);
    }

な部分ですが SCM_HASH_GENERAL より type が大きかったらナニ、との事にて定義が hash.h にて以下。

/* Hash types */
typedef enum {
    SCM_HASH_EQ,
    SCM_HASH_EQV,
    SCM_HASH_EQUAL,
    SCM_HASH_STRING,
    SCM_HASH_GENERAL,

    SCM_HASH_WORD
} ScmHashType;

上記によれば gauche での hash table な種類は 5 種類らしい。ここも別途で先を確認。

    z = SCM_NEW(ScmHashTable);
    SCM_SET_CLASS(z, SCM_CLASS_HASH_TABLE);
    Scm_HashCoreInitSimple(&z->core, type, initSize, NULL);
    z->type = type;
    return SCM_OBJ(z);
}

ポイント高いと思われるのは Scm_HashCoreInitSimple() 手続きですな。

ってか

このあたりも二番煎じな気がしてきた ...
と言いつつ Scm_HashCoreInitSimple() 手続きを見るんですが以下なカンジ。

void Scm_HashCoreInitSimple(ScmHashCore *core,
                            ScmHashType type,
                            unsigned int initSize,
                            void *data)
{
    SearchProc  *accessfn;
    ScmHashProc *hashfn;
    ScmHashCompareProc *cmpfn;

    if (hash_core_predef_procs(type, &accessfn, &hashfn, &cmpfn) == FALSE) {
        Scm_Error("[internal error]: wrong TYPE argument passed to Scm_HashCoreInitSimple: %d", type);
    }
    hash_core_init(core, accessfn, hashfn, cmpfn, initSize, data);
}

hash_core_predef_procs() 手続きで

  • accessfn
  • hashfn
  • cmpfn

なポインタに適切な手続きのポインタがセットされたら hash_core_init() 手続きでそれらを含めた属性値のセットですかそうですか。