[php-src読書録]その７: ハッシュ

php-srcのコードリーディングした内容をコツコツ残すテスト。その７

今回はハッシュ

<?php

$tmp = ['hoge' => true];
$tmp['hoge'];
$tmp['fuga'] = false;

opcode

$_main:
     ; (lines=6, args=0, vars=1, tmps=3)
     ; (before optimizer)
     ; /path/to/7.php:1-6
     ; return  [] RANGE[0..0]
0000 ASSIGN CV0($tmp) array(...)
0001 T2 = FETCH_DIM_R CV0($tmp) string("hoge")
0002 FREE T2
0003 ASSIGN_DIM CV0($tmp) string("fuga")
0004 OP_DATA bool(false)
0005 RETURN int(1)

FETCH_DIM_R, ASSIGN_DIM, OP_DATAなど基本的にはarrayと同じopcodeを使っている。

zend_compile_array() => zend_try_ct_eval_array() 経由で zend_symtable_update() を呼び出す
https://github.com/php/php-src/blob/PHP-8.1.4/Zend/zend_compile.c#L8533:L8533

zend_symtable_update() は zend_hash_update() を呼び出す
https://github.com/php/php-src/blob/PHP-8.1.4/Zend/zend_hash.h#L464:L464

_zend_hash_add_or_update_i() を呼び出される zend_stringからハッシュキーを算出。key.h にセットされる
https://github.com/php/php-src/blob/PHP-8.1.4/Zend/zend_hash.c#L736:L736

初期化時に zend_hash_real_init_mixed() が呼ばれる
https://github.com/php/php-src/blob/PHP-8.1.4/Zend/zend_hash.c#L741:L741

emalloc() でハッシュテーブルの領域が確保される
https://github.com/php/php-src/blob/PHP-8.1.4/Zend/zend_hash.c#L172

以下のバケット配列のサイズとハッシュテーブルのサイズを足した領域が確保される

バケットのサイズ: (size_t)(8) * sizeof(Bucket)
ハッシュのサイズ: ((size_t)(uint32_t)-(int32_t)((uint32_t)(-16))) * sizeof(uint32_t)

一番最初はデータの領域8要素分、ハッシュの領域16要素分の領域が確保される。

並びとしてはハッシュの領域 => バケット（データ）の領域という感じで並ぶ（後述）で、バケットの領域の先頭領域を指すようにポインタを操作している↓
https://github.com/php/php-src/blob/PHP-8.1.4/Zend/zend_hash.c#L217

そのため、ハッシュの領域にはマイナスのインデックスでアクセスすることになる（後述）

その後、こちらで実際のデータが格納される
https://github.com/php/php-src/blob/PHP-8.1.4/Zend/zend_hash.c#L791-L804

1. arDataに順番に格納していく

arData = ht->arData;
p = arData + idx;
p->key = key;
p->h = h = ZSTR_H(key);

2. ハッシュをindexに変換

nIndex = h | ht->nTableMask;

3. ハッシュとバケットにデータを追加（格納されていたindexを p->val.u2.nextにセットして、新しいindexをセット）

Z_NEXT(p->val) = HT_HASH_EX(arData, nIndex);
// p->val.u2.next = arData[nIndex] （古いindexをu2.nextに入れる）
HT_HASH_EX(arData, nIndex) = HT_IDX_TO_HASH(idx);
// arData[nIndex] = idx （新しいindexをセット

arDataには以下の２つの値が格納されることになる。

ハッシュ値のindex => index
バケットのindex => zval

コメントにもこんな感じなわかりやすい図が書いてある

/*
 * HashTable Data Layout
 * =====================
 *
 *                 +=============================+
 *                 | HT_HASH(ht, ht->nTableMask) |
 *                 | ...                         |
 *                 | HT_HASH(ht, -1)             |
 *                 +-----------------------------+
 * ht->arData ---> | Bucket[0]                   |
 *                 | ...                         |
 *                 | Bucket[ht->nTableSize-1]    |
 *                 +=============================+
 */

ハッシュはarDataに対してマイナスのインデックスでアクセスすることになるし、バケットへのアクセスはプラスのインデックスでアクセスすることになる。

ZEND_FETCH_DIM_R_SPEC_CV_CONST_HANDLER では

zend_fetch_dimension_address_inner()
=> zend_hash_find_ex()
=> zend_hash_find()
=> zend_hash_find_bucket()

でバケットを取得する。

zend_hash_find_bucket() の処理はこんな感じ
https://github.com/php/php-src/blob/PHP-8.1.4/Zend/zend_hash.c#L640-L680

やっていることはこんな感じ↓

zend_stringのハッシュを取る
arData[(int32_t)nIndex] からidxを取得
arData[idx] からzvalを取得
ハッシュが衝突した場合は Z_NEXT(p->val) のlinked listでzvalを辿っていく

ZEND_ASSIGN_DIM_SPEC_CV_CONST_OP_DATA_CONST_HANDLER では

zend_fetch_dimension_address_inner_W_CONST()
=> zend_fetch_dimension_address_inner()
=> zend_hash_lookup()
=> _zend_hash_add_or_update_i()

と呼び出していき、 zend_hash_find_bucket() でデータが取得できればバケットのvalを更新。なければハッシュテーブルに追加している。
https://github.com/php/php-src/blob/PHP-8.1.4/Zend/zend_hash.c#L747-L781