khashの構造

mrubyでは、hashの基本実装としてkhash (include/mruby/khash.h) というものが使われている。「xxxのためのハッシュ構造」を扱うための宣言や定義がマクロKHASH_DEFINE(xxx)等で生成される仕組み。 xxxに入るキーワードはいろいろあるが、内部構造的には全部同じ。

データ構造

typedef uint32_t khint_t;
#define KHASH_DECLARE(name, khkey_t, khval_t, kh_is_map)                \
  typedef struct kh_##name {                                            \
    khint_t n_buckets;      /* keysやvalsの容量(2の冪乗かつ8以上) */    \
    khint_t size;           /* 登録されている要素の数 */                \
    khint_t n_occupied;     /* 不明 */                                  \
    khint_t upper_bound;    /* 不明 */                                  \
    uint8_t *e_flags;       /* 空きフラグ */                            \
    uint8_t *d_flags;       /* 削除済みフラグ */                        \
    khkey_t *keys;          /* キーの配列(n_buckets個分の領域)*/        \
    khval_t *vals;          /* 値の配列(n_buckets個分の領域)*/          \
    khint_t mask;           /* 不明 */                                  \
    khint_t inc;            /* 不明 */                                  \
    mrb_state *mrb;                                                     \
  } kh_##name##_t;                                                      \
  /* 続き省略 */