Хэш-таблицы являются основным контейнером данных в Zend Engine
и активно используются как в Zend Engine
, так и в PHP Core
. Большинство API функций Zend Engine
так или иначе завязаны на хэш таблицы.
В хэш-таблицах данные, представленные в виде zval
структур, связываются с названием переменной (меткой); в хэш-таблицах хранятся ссылки на: пользовательские структуры данных, ресурсы, объекты, классы, пользовательские функции. Также в хэш таблицах хранятся суперглобальные массивы $_COOKIE
, $_POST
, $_GET
, $GLOBALG
, $_FILES
, $_SESSION
.
В хэш-таблице можно хранить любые данные любого размера. Хэш-таблица - представляет из себя двух связанный список векторов, это обеспечивает эффективное хранение и поиск данных.
Данный тип описан в файле Zend/zend_hash.h
:
typedef struct bucket {
ulong h; // числового индекса
uint nKeyLength; // длинна ассоциативного индекса
void *pData;
void *pDataPtr;
struct bucket *pListNext;
struct bucket *pListLast;
struct bucket *pNext;
struct bucket *pLast;
char arKey[1]; // ассоциативный индекс
} Bucket;
typedef struct _hashtable {
uint nTableSize; //размер хэш-таблицы
uint nTableMask; // всегда nTableSize - 1
uint nNumOfElements; // фактическое кол-во элементов
ulong nNextFreeElement; //следующий свободный числовой индекс
Bucket *pInternalPointer; // Внутренний указатель, используется для итерации по элементам хэш-таблицы
Bucket *pListHead; // указатель на первый элемент хэш-таблицы
Bucket *pListTail; // указатель на последний элемент хэш-таблицы
Bucket **arBuckets; // элементы хэш-таблицы
dtor_func_t pDestructor; // указатель на функцию-деструктор, которая будет вызываться при удалении или обновлении элемента
zend_bool persistent;
unsigned char nApplyCount;
zend_bool bApplyProtection;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable
Для примера рассмотрим уже известный макрос ZEND_SET_SYMBOL()
, который ранее использовался для связывания данных с именем переменной:
#define ZEND_SET_SYMBOL(symtable, name, var) \
{ \
char *_name = (name); \
ZEND_SET_SYMBOL_WITH_LENGTH(symtable, _name, strlen(_name)+1, var, 1, 0); \
}
#define ZEND_SET_SYMBOL_WITH_LENGTH(symtable, name, name_length, var, _refcount, _is_ref) \
{ \
zval **orig_var; \
if (zend_hash_find(symtable, (name), (name_length), (void **) &orig_var)==SUCCESS \
&& PZVAL_IS_REF(*orig_var)) { \
Z_SET_REFCOUNT_P(var, Z_REFCOUNT_PP(orig_var)); \
Z_SET_ISREF_P(var); \
if (_refcount) { \
Z_SET_REFCOUNT_P(var, Z_REFCOUNT_P(var) + _refcount - 1); \
} \
zval_dtor(*orig_var); \
**orig_var = *(var); \
FREE_ZVAL(var); \
} else { \
Z_SET_ISREF_TO_P(var, _is_ref); \
if (_refcount) { \
Z_SET_REFCOUNT_P(var, _refcount); \
} \
zend_hash_update(symtable, (name), (name_length), &(var), sizeof(zval *), NULL); \
} \
}
Обратите внимание на строки 10 и 25, в этих строках происходит обращение к хэш-таблицам с помощью функциий zend_hash_find()
и zend_hash_update()
.
// Создание строковой переменной
zval *var = NULL;
MAKE_STD_ZVAL(var);
var->type = IS_STRING;
var->value.str.len = strlen("String variable");
var->value.str.val = estrdup("String variable", strlen("String variable") + 1 );
// Связывание данных с меткой переменной
ZEND_SET_SYMBOL(EG(active_symbol_table), "my_str_var", var);
Здесь, при связывании имени переменной с данными, происходит размещение имени и указателя на данные *var
в хэш-таблице active_symbol_table
API функции для работы с хэш-таблицами
Для работы с хэш-таблицами первым делом необходимо необходимо выделить блок памяти и присвоить указатель на выделенный блок переменной типа HashTable
. Для выделения памяти под HashTable
необходимо использовать одну из функций: emalloc()
, pemalloc()
или макрос ALLOC_HASHTABLE(ht)
. Использование макроса ALLOC_HASHTABLE(ht)
как правило предпочтительнее, чем emalloc (sizeof(HashTable))
, так как это работает быстрее за счет использования предварительно рассчитанного значения размера блока памяти, который необходимо выделить, из специального пула.
HashTable *my_table = NULL;
// Выделение памяти под хэш-таблицу
ALLOC_HASHTABLE(my_table);
или
HashTable *my_table = NULL;
// Выделение памяти под хэш-таблицу
my_table = emalloc (sizeof(HashTable));
Для работы с хэш таблицами Zend Engine предоставляет семейство функций/макросов zend_hash_*()
, которые объявлены в файле Zend/zendhash.h_
Инициализация
int zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent)
- конструктор инициализации хэш-таблицы. Каждая хэш-таблица должна быть инициализирована с помощью вызова данного конструктора. Функция возвращает SUCCESS
в случае успеха, иначе FAILURE
.
Параметры:
ht
- указатель на HashTable, память под которую выделена динамически или статически.nSize
- максимальное кол-во элементов которое, как ожидается, будет содержатся в хэш-таблице. Если в таблицу будет добавлено элементов больше, чем указано в _nSize
, то это значение будет увеличено, но это потребует дополнительных затрат времени выполнения, так как Zend переиндексирует всю таблицу для вновь добавленных структур. ЕслиnSize
не является кратным степени числа 2, тоnSize
будет автоматически увеличено до следующего, ближайшего, числа кратного степени 2 по формуле:pow(2, ceil(log(nSize, 2)))
pHashFunction
- Данный параметр не используется и в качестве значение всегда должен передаватьсяNULL
. В более ранних версияхZend Engine
параметр использовался для указания функции альтернативного механизма хэширования который бы использовался вместо стандартногоDJBX33A
(Daniel J. Bernstein, Times 33 c Addition).
DJBX33A - быстрый, умеренно стойкий к коллизиям алгоритм хеширования буквенно-цифровых индексов
pDestructor
- указатель на функцию деструктор. Функция будет вызываться когда элемент в хэш-таблице изменяется или удаляется. Прототип функции деструктора:void method_name(void *pElement)
;.pElement
- указатель на удаляемый из таблицы элементpersistent
- флаг постоянной памяти. Если в качестве значения передана 1, то будет выделена постоянная память с использованием функцииmalloc()
и данные будут доступны между запросами. Иначе, для выделения блока памяти, будет использована функцияemalloc()
.int zend_hash_init_ex(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent, zend_bool bApplyProtection)
- данная функция отличается отint zend_hash_init()
дополнительным шестым параметромbApplyProtection
. Если передано не нулевое значение, то при попытке многократного перебора HashTable, перебор будет прерван на максимально возможном количество рекурсий.
Использование функции zend_hash_init(myTable, 64, NULL, NULL, 1)
эквивалентно использованию zend_hash_init_ex(myTable, 64, NULL, NULL, 1, 1)
Вычисление хэша ассоциативного индекса
При работе с ассоциативными индексами используется их преобразование в числовое представление(хэширование). Для получения хэша ассоциативного индекса используется алгоритм DJBX33A
. В более ранних версиях алгоритм можно было изменить указав параметр pHashFunction
в функции zend_hash_init()
Все функции для работы с данными, индексируемых ассоциативными индексами, вычисляют числовой хэш индекса. При выполнении большого кол-ва операций операций с одним и тем же ассоциативным ключом может быть полезно предварительно вычислить его хеш с помощью функции используя zend_get_hash_value()
. Когда индекс обрабатывается как цифровой, никакое вычисление хэша не производится. Предварительно вычисленный хэш используется в функциях zend_hash_quick_*()
ulong zend_get_hash_value(char *arKey, uint nKeyLength)
- функция вычисления хэша ассоциативного индекса
Параметры:
arrKey
- ассоциативный индексnKeyLength
- длина ассоциативного индекса
Пример:
unsigned long n_index = 0;
n_index = zend_get_hash_value("my_index", sizeof("my_index")); /* n_index = 3288307330 */
Добавление элементов
int zend_hash_add(HashTable *ht, char *arKey, uinit nKeyLength, void *pData, uinit nDataSize, void **pDest)
- функция добавления ассоциативно индексируемого элемента в хэш- таблицу. Функция возвращает SUCCESS
в случае успеха, иначе FAILURE
.
Параметры:
ht
- указатель на хэш-таблицу в которую добавляется элементarrKey
- ассоциативный индексnKeyLength
- длина ассоциативного индексаpData
- данныеnDataSize
- размер данныхpDest
- указатель, если передан, по которому будет скопирован указатель на скопированные данные. Назначение параметра такое же как и у одноименного параметра функцииzend_hash_find()
Пример:
zval *myvar = NULL;
MAKE_STD_ZVAL(myvar);
ZVAL_STRING(myvar, "My string", 1);
zend_hash_add(&EG(symbol_table), "my_var", sizeof("my_var"), (void **)&myvar, sizeof(zval*), NULL);
Стоит отметить, что если ассоциативный индекс, указанный в параметре arKey, уже используется, то функция не сработает. См. zend_hash_update()
int zend_hash_add_empty_element(HashTable *ht, const char *arKey, uint nKeyLength)
- функция добавления пустого ассоциативно индексируемого элемента в хэш-таблицу. Функция возвращает SUCCESS
в случае успеха, иначе FAILURE
.
Параметры:
ht
- указатель на хэш-таблицу в которую добавляется элементarrKey
- ассоциативный индексnKeyLength
- длина ассоциативного индекса
int zend_hash_next_index_insert(HashTable *ht, void *pData, uint nDataSize, void **pDest)
- функция добавления элемента, индексируемого числовым индексом, в хэш-таблицу. Функция возвращает SUCCESS
в случае успеха, иначе FAILURE
.
Параметры:
ht
- указатель на хэш-таблицу в которую добавляются элементpData
- данныеnDataSize
- размер данныхpDest
- указатель, если передан, по которому будет скопирован указатель на данные. Назначение параметра такое же как и у одноименного параметра функцииzend_hash_find()
Пример:
zval *myvar = NULL;
MAKE_STD_ZVAL(myvar);
ZVAL_STRING(myvar, "My string", 1);
zend_hash_next_index_insert(my_table,(void **)&myvar, sizeof(zval*), NULL);
Если необходимо сохранить индекс добавляемого элемента, то для получения индекса необходимо воспользоваться функцией zend_hash_next_free_element(HashTable *ht)
, а вместо функции zend_hash_next_index_insert()
использовать zend_hash_next_index_update()
:
unsigned int h = zend_hash_next_free_element(my_table);
zval *myvar = NULL;
MAKE_STD_ZVAL(myvar);
ZVAL_STRING(myvar, "My string", 1);
zend_hash_index_update(my_table, h, (void **)&myvar, sizeof(zval*), NULL);
int zend_hash_quick_add(HashTable *ht, char *arKey, uint nKeyLength, ulong hashval, void *pData, uint nDataSize, void **pDest)
- функция отличается от zend_hash_add()
только новым,четвертым параметром hashval
. Параметр принимает предварительно расчитанный хэш ассоциативного индекса. Функция возвращает SUCCESS
в случае успеха, иначе FAILURE
. Также см. zend_get_hash_value()
Параметры:
ht
- указатель на хэш-таблицу в которую добавляются данныеarrKey
- ассоциативный индексnKeyLength
- длина ассоциативного ключаhashval
- предварительно вычисленный хэш ассоциативного ключаpData
- данныеnDataSize
- размер данныхpDest
- указатель, если передан, по которому будет скопирован указатель на скопированные данные. Назначение параметра такое же как и у одноименного параметра функцииzend_hash_find()
Пример:
zval *myvar = NULL;
unsigned long hash = 0;
hash = zend_get_hash_value("my_var", sizeof("my_var"));
MAKE_STD_ZVAL(myvar);
ZVAL_STRING(myvar, "My string", 1);
zend_hash_quick_add(&EG(symbol_table), "my_var", sizeof("my_var"), hash, (void **)&myvar, sizeof(zval*), NULL);
Обновление данных
int zend_hash_update(HashTable *ht, char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest)
- функция обновления данных ассоциативно индексируемого элемента в хэш-таблице. Функция возвращает SUCCESS
в случае успеха, иначе FAILURE
.
Параметры:
ht
- указатель на хэш-таблицу в которую добавляются данныеarKey
- ассоциативный индекс элемента, данные которого обновляютсяnKeyLength
- длина ассоциативного индексаpData
- данныеnDataSize
- размер данныхpDest
- указатель, если передан, по которому будет скопирован указатель на скопированные данные. Назначение параметра такое же как и у одноименного параметра функцииzend_hash_find()
Пример:
zval *myvar = NULL;
MAKE_STD_ZVAL(myvar);
ZVAL_STRING(myvar, "My string 2", 1);
zend_hash_update(&EG(symbol_table), "my_var", sizeof("my_var"), (void **)&myvar, sizeof(zval*), NULL);
Если ассоциативный индекс, передаваемый через параметр arKey
, не существует в таблице, указатель которой предан через параметр ht
, то функция работает как zend_hash_find()
int zend_hash_index_update(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest)
- функция обновления данных, индексируемого числовым индексом, элемента в хэш-таблице. Функция возвращает SUCCESS
в случае успеха, иначе FAILURE
.
Параметры:
ht
- указатель на хэш-таблицу в которую добавляются данные
h
- числовой индекс обновляемого элемента
pData
- данные
nDataSize
- размер данных
pDest
- указатель, если передан, по которому будет скопирован указатель на скопированные данные. Назначение параметра такое же как и у одноименного параметра функции zend_hash_find()
Если индекс, передаваемый через параметр h
, не существует в таблице, указатель которой предан через параметр ht
, то функция работает как zend_hash_next_index_insert()
int zend_hash_quick_update(HashTable *ht, char *arKey, uint nKeyLength, ulong hashval, void *pData, uint nDataSize, void **pDest)
- функция отличается от zend_hash_update()
четвертым параметром hashval. Параметр принимает предварительно расчитанный хэш ассоциативного индекса. Функция возвращает SUCCESS
в случае успеха, иначе FAILURE
. Также см. zend_get_hash_value()
Пример:
zval *myvar = NULL;
unsigned long hash = 0;
hash = zend_get_hash_value("my_var", sizeof("my_var"));
MAKE_STD_ZVAL(myvar);
ZVAL_STRING(myvar, "My string 2", 1);
zend_hash_quik_update(&EG(symbol_table), "my_var", sizeof("my_var"), hash, (void **)&myvar, sizeof(zval*), NULL);
Поиск данных
int zend_hash_find(HashTable *ht, char *arKey, uint nKeyLength, void **pDest)
- функция поиска данных по ассоциативному индексу в хэш-таблице. Функция возвращает SUCCESS
в случае успеха, иначе FAILURE
.
Параметры:
ht
- указатель на хэш-таблицу в которой ищутся данныеarKey
- ассоциативный индекс элемента, данные связанные с которым ищутсяnKeyLength
- длина ассоциативного ключаpDest
- указатель по которому будет скопирован указатель на данные
Пример:
zval **myvar = NULL;
if (zend_hash_find(&EG(symbol_table), "my_var", sizeof("my_var"),
(void**)&myvar) == SUCCESS) {
zend_printf("The value of $my_var: ");
ZEND_WRITE(Z_STRVAL_PP(myvar), Z_STRLEN_PP(myvar));
} else {
zend_printf("$my_var is not defined.");
}
int zend_hash_index_find(HashTable *ht, ulong h, void **pData)
- функция поиска данных по числовому индексу в хэш-таблице. Функция возвращает SUCCESS
в случае успеха, иначе FAILURE
.
Параметры:
ht
- указатель на хэш-таблицу в которой ищутся данныеh
- числовой индекс данные связанные с которым обновляютсяpDest
- указатель по которому будет скопирован указатель на данные
Пример:
zval **retrival_data = NULL;
zval *myvar = NULL;
MAKE_STD_ZVAL(myvar);
ZVAL_STRING(myvar, "My string", 1);
/* Добавляем данные в хэш-таблицу */
unsigned long index = zend_hash_next_free_element(my_table);
zend_hash_index_update(my_table, index, (void **)&myvar, sizeof(zval *), NULL);
if(zend_hash_index_find(my_table, index, (void **)&retrival_data) == SUCCESS) {
zend_printf("The value of element: ");
ZEND_WRITE(Z_STRVAL_PP(retrival_data), Z_STRLEN_PP(retrival_data));
}
int zend_hash_quick_find(HashTable *ht, char *arKey, uint nKeyLen, ulong hashval, void **pData)
- функция отличается от zend_hash_find()
четвертым параметром hashval
. Параметр принимает предварительно расчитанный хэш ассоциативного индекса. Функция возвращает SUCCESS
в случае успеха, иначе FAILURE
.
Пример:
zval **myvar = NULL;
unsigned long hash = 0;
hash = zend_get_hash_value("my_var", sizeof("my_var"));
if (zend_hash_quick_find(&EG(symbol_table), "my_var", sizeof("my_var"),
hash, (void**)&myvar) == SUCCESS) {
zend_printf("The value of $my_var: ");
ZEND_WRITE(Z_STRVAL_PP(myvar), Z_STRLEN_PP(myvar));
} else {
zend_printf("$my_var is not defined.");
}
int zend_hash_exists(HashTable *ht, char *arKey, uint nKeyLen)
- функция проверяет существование ассоциативного индекса в хэш-таблице. Функция возвращает 1 если индекс существует в хэш-таблице, иначе 0.
Параметры:
ht
- указатель на переменную хэш-таблицу в которую добавляются данныеarKey
- ассоциативный индекс, существование которого проверяетсяnKeyLength
- длина ассоциативного ключа
Пример:
if (zend_hash_exists(&EG(symbol_table), "my_var", sizeof("my_var")) == SUCCESS ) {
/* some code */
} else {
/* some code */
}
int zend_hash_index_exists(HashTable *ht, ulong h)
- функция проверяет существование числового индекса в хэш-таблице. Функция возвращает 1 если индекс существует в хэш-таблице, иначе 0.
Параметры:
ht
- указатель на хэш-таблицу в которую добавляются данныеh
- числовой индекс данные связанные с которым обновляются
Пример:
unsigned long index = 1;
if(zend_hash_index_exists(my_table, index ) == SUCCESS) {
/* some code */
} else {
/* some code */
}
int zend_hash_quick_exists(HashTable *ht, char *arKey, uint nKeyLen, ulong hashval)
- функция отличается от zend_hash_exists()
четвертым переметром hashval
. Параметр принимает предварительно расчитанный хэш ассоциативного индекса. Функция возвращает 1 если индекс существует в хэш-таблице, иначе 0.
Пример:
unsigned long hash = 0;
hash = zend_get_hash_value("my_var", sizeof("my_var"));
if (zend_hash_quick_exists(&EG(symbol_table), "my_var", sizeof("my_var"), hash) == SUCCESS ) {
/* some code */
} else {
/* some code */
}
Удаление элементов
int zend_hash_del(HashTable *ht, const char *arKey, uint nKeyLength)
- удаляет ассоциативно индексированный элемент из хэш-таблицы. При удалении элемента будет вызываться деструктор, заданный при инициализации хэш-таблицы (параметр pDestructor
функции zend_hash_init()
). Функция возвращает SUCCESS
в случае успеха, иначе FAILURE
.
Параметры:
ht
- указатель на хэш-таблицу из которой удаляется элементarrKey
- ассоциативный индексnKeyLength
- длина ассоциативного индекса
Пример:
if(zend_hash_del(my_table, "my_var", sizeof("my_var") ) == SUCCESS) {
zend_printf("The item was deleted <br />");
}
int zend_hash_index_del(HashTable *ht, ulong h)
- удаляет индексированный числовым индексом элемент из хэш-таблицы. При удалении элемента будет вызываться деструктор, заданный при инициализации хэш-таблицы (параметр pDestructor
функции zend_hash_init()
). Функция возвращает SUCCESS
в случае успеха, иначе FAILURE
.
Параметры:
ht
- указатель на хэш-таблицу из которой удаляется элементh
- числовой индекс
Пример:
if(zend_hash_index_del(my_table, 10) ) == SUCCESS) {
zend_printf("The item was deleted <br />");
}
int zend_hash_quick_del(HashTable *ht, const char *arKey, uint nKeyLength, ulong hashval)
- функция отличается от zend_hash_del()
четвертым параметром hashval
. Параметр принимает предварительно расчитанный хэш ассоциативного индекса. Функция возвращает SUCCESS
в случае успеха, иначе FAILURE
.
Пример:
unsigned long hashval = zend_get_hash_value("my_var", sizeof("my_var"));
if(zend_hash_del(my_table, "my_var", sizeof("my_var"), hashval ) == SUCCESS) {
zend_printf("The item was deleted <br />");
}
Другие функции
int zend_hash_num_elements(const HashTable *ht)
- Возвращает фактическое кол-во элементов в хэш-таблице ht
ulong zend_hash_next_free_element(const HashTable *ht)
- Возвращает следующий свободный числовой индекс в хэш-таблице ht
. При добавлении нового элемента, индексируемого числовым индексом, в хэш-таблицу, именно этот индекс будет использован