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が常にハッシュ関数として使われる。 destructorNULLでもよい。
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)
htkeyがあれば正の値を返す。
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)
htindexがあれば正の値を返す。
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)
positionhtの開始位置にセットする。
int zend_hash_get_current_data(HashTable* ht, void* data)
htの現在位置にあるデータを取得する。datavoid**にキャストしなければならない (すなわち(void**) &data)。
int zend_hash_get_current_data_ex(HashTable* ht, void* data, HashPosition position)
htの中でdataposition の位置にセットする。
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)
positionht内の次のエントリに動かす。

前述の関数は、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のラッパーです。