HashTable の扱い

PHP の内部で多くの役割を提供するHashTable構造体は至る所で使われており、この機能を理解することはよいハッカーになるための必要条件です。

エンジンにおけるHashTableの実装は標準のHashTableです。つまりキー => 値をベースにした格納方式であり、キーは常に文字列で、そのハッシュ値はビルトインのハッシュアルゴリズム zend_inline_hash_func(const char* key, uint length)により計算されます。これは広く流通しており、妥当な利用法と言えます。

HashTableの内部構造や厳密な操作についてはこの文書の範疇を超えます。この文書では API の入手や最適な利用法などについてご紹介しています。HashTable に関する詳細な考え方等はZend/zend_hash.hを参照してください。

特に記載のない限り、これらの関数は何らかの原因で要求した操作ができない場合 FAILUREを返し、そうでなければSUCCESSを返します。

注意:
HashTable API 関数は通常、キーの長さは NULL で終端された文字列の長さに等しいことを期待していることに気をつけてください。これには NULL 終端の分も含みます。つまり、strlen(key) + 1を期待しているということです。

HashTableを使う際に知っておくべき typedef 定義を以下に記載します。これらのほとんどは定義そのものが説明のようになっているので、ハッカー はこれらのプロトタイプを深く理解できるはずです。

typedef ulong (*hash_func_t)(const char *arKey, uint nKeyLength); /* ほとんど冗長 */
typedef int  (*compare_func_t)(const void *, const void * TSRMLS_DC); /* 比較関数 */
typedef void (*sort_func_t)(void *, size_t, register size_t, compare_func_t TSRMLS_DC); /* ソート関数 */
typedef void (*dtor_func_t)(void *pDest); /* デストラクタ関数 */
typedef void (*copy_ctor_func_t)(void *pElement); /* コピーコンストラクタ */
typedef void (*copy_ctor_param_func_t)(void *pElement, void *pParam); /* 引数付きのコピーコンストラクタ */
typedef int (*apply_func_t)(void *pDest TSRMLS_DC); /* 適用関数 */
typedef int (*apply_func_arg_t)(void *pDest, void *argument TSRMLS_DC); /* 関数引数付きの適用関数 */
typedef int (*apply_func_args_t)(void *pDest TSRMLS_DC, int num_args, va_list args, zend_hash_key *hash_key); /* 複数の関数引数を伴う適用関数 */

**HashTable API**
`int zend_hash_init(HashTable* ht, uint size, hash_func_t hash, dtor_func_t destructor, zend_bool persistent)`
ハッシュテーブルを初期化して、少なくとも`size`個の要素を保持する。`hash`は歴史的な経緯により存在するだけで常に無視される。 `zend_inline_hash_func`が常にハッシュ関数として使われる。 `destructor`は`NULL`でもよい。
`int zend_hash_add(HashTable* ht, const char* key, uint klen, void* data, uint dlen, void** dest)`
指定された`key`を使ってテーブルに`data`を追加する。キーは`length`バイトの長さを持つ（そして`key`からテーブルにコピーされる）。キーが存在すると FAILURE が返される。
`int zend_hash_update(HashTable* ht, const char* key, uint klen, void* data, uint dlen, void** dest)`
指定された`key`を使ってテーブルに`data`を追加する。キーは`length`バイトの長さを持つ（そして`key`からテーブルにコピーされる）。キーが存在した場合、古いデータに対して`dtor_func_t` が呼ばれ、既存のデータは`data`で上書きされる。
`int zend_hash_find(HashTable* ht, const char* key, uint klen, void** data)`
テーブルを`key`で検索し、見つかったら`*data` をセットして SUCCESS を返す。
`zend_bool zend_hash_exists(HashTable* ht, const char* key, uint klen)`
`ht`に`key`があれば正の値を返す。
`int zend_hash_del(HashTable* ht, const char* key, uint klen)`
テーブル内に`key`で特定されるエントリがあれば削除する。
`int zend_hash_index_update(HashTable* ht, ulong index, void* data, uint dsize, void** dest)`
`ht`の中の`index`で指定されたエントリのデータを `data`で更新する。
`int zend_hash_index_del(HashTable* ht, ulong index)`
`ht`から`index`で指定されたエントリを削除する。
`int zend_hash_index_find(HashTable* ht, ulong index, void** data)`
`ht`の中で`index`で指定されたデータを `*data`にリダイレクトする。
`int zend_hash_index_exists(HashTable* ht, ulong index)`
`ht`に`index`があれば正の値を返す。
`ulong zend_hash_next_free_element(HashTable* ht)`
`ht`の中で次に利用可能な要素のインデックスを返す。

警告

zend_hash_* 関数のうちvoid* dataを受け付けるものは、通常それを(void**) (すなわち(void**) &data)にキャストしなければいけません。

HashTable の中を行き来しなければならない場合も少なくありません。これを行うには、HashTableへのポインタに加えてHashPosition オプションを指定します。これは HashTable API への内部構造であり、HashTable の内部位置に影響を与えずに内部を移動できるようになります。以下の移動用関数が提供されており、以下にその利用例を示します。

**HashTable 内の移動 API**
`int zend_hash_internal_pointer_reset(HashTable* ht)`
`ht`の内部ポインタを開始位置にリセットする。
`int zend_hash_internal_pointer_reset_ex(HashTable* ht, HashPosition position)`
`position`を`ht`の開始位置にセットする。
`int zend_hash_get_current_data(HashTable* ht, void* data)`
`ht`の現在位置にあるデータを取得する。`data` は`void`にキャストしなければならない（すなわち`(void) &data`）。
`int zend_hash_get_current_data_ex(HashTable* ht, void* data, HashPosition position)`
`ht`の中で`data`を`position` の位置にセットする。
`int zend_hash_get_current_key(HashTable* ht, void* data, char**key, uint klen, ulong index, zend_bool duplicate)`
現在位置のキーの情報から `key`, `klen`, `index` を取得する。戻り値として HASH_KEY_IS_STRING や HASH_KEY_IS_LONG が返される場合があるが、これは現在位置にその種類のキーがあったことを表している。
`int zend_hash_get_current_key_ex(HashTable* ht, void* data, char**key, uint klen, ulong index, zend_bool duplicate, HashPosition position)`
`position`位置のキーの情報から `key`, `klen`, `index` を取得する。戻り値として HASH_KEY_IS_STRING や HASH_KEY_IS_LONG が返される場合があるが、これは現在位置にその種類のキーがあったことを表している。
`int zend_hash_move_forward(HashTable* ht)`
`ht`の内部ポインタを`ht`内の次のエントリに動かす。
`int zend_hash_move_forward_ex(HashTable* ht, HashPosition position)`
`position`を`ht`内の次のエントリに動かす。

前述の関数は、HashTable内部を通常のループのように移動できます。たとえば以下のように使います。

HashPosition position;
zval **data = NULL;

for (zend_hash_internal_pointer_reset_ex(ht, &position);
     zend_hash_get_current_data_ex(ht, (void**) &data, &position) == SUCCESS;
     zend_hash_move_forward_ex(ht, &position)) {
     
     /* ここではすでにデータがセットされているので、
         Z_ マクロを使って型や変数データにアクセスできます。 */

     char *key = NULL;
     uint  klen;
     ulong index;

     if (zend_hash_get_current_key_ex(ht, &key, &klen, &index, 0, &position) == HASH_KEY_IS_STRING) {
         /* キーは文字列で、key と klen がセットされます */
     } else {
         /* キーを long 値とみなし、index がセットされます */
     }
}

注意:
HashTableをエンジンに渡した場合、意図しない事態にならないように、ユーザーランドでは zend_hash_*_ex API を使うとよいでしょう。

注意:
キーのduplicateを要求してHAS_KEY_IS_STRING が返された場合、呼び出し元は重複キーをefreeしなければなりません。

内部移動以外にも、エンジンではハッシュテーブルのマージ、コピー、比較といった API を提供しています。ハッカーはこれらのどの概念にも精通していなければなりません。関数の適用 (apply) という概念にはなじみがない人もいるかもしれません。要するにこれは、HashTable API の機能を使ってコールバック関数を渡して、 HashTable中のすべてのエントリでそれを実行させる仕組みのことです。

**コピー、マージ、ソート**
`void zend_hash_copy(HashTable target, HashTable source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size)`
`source`の中身を`target`にコピーする。 `tmp`にはコピーの中で使われる領域確保されていない適切な型のポインタを、`size`には各要素の個数を指定する。
`void zend_hash_merge(HashTable target, HashTable source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size, zend_bool overwrite)`
`source`の中身を`destination`にマージする。 `overwrite`が真の場合、既存のエントリを置き換える。
`void int zend_hash_sort(HashTable *ht, sort_func_t sort_func, compare_func_t compare_func, int renumber TSRMLS_DC)`
`renumber`はインデックスを保持するかどうかを制御する。詳細はこの章の最初に出てきた typedef を参照のこと。

注意:
ある関数がcopy_ctor_func_t pCopyConstructorを受け付ける場合、一緒に渡された関数はHashTable内で新しいエントリが生成されるたびに実行されます。エンジン内で使われる通常のコピーコンストラクタのほとんどは、 ZVAL_COPY_CTORマクロのzval_copy_ctorのラッパーです。