Разработка расширений для PHP. Хэш-таблицы (HashTables). Часть 1

Хэш-таблицы являются основным контейнером данных в 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 &lt;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 &lt;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 &lt;br />");
}

Другие функции

int zend_hash_num_elements(const HashTable *ht) - Возвращает фактическое кол-во элементов в хэш-таблице ht

ulong zend_hash_next_free_element(const HashTable *ht) - Возвращает следующий свободный числовой индекс в хэш-таблице ht. При добавлении нового элемента, индексируемого числовым индексом, в хэш-таблицу, именно этот индекс будет использован

php extensions

Permalink: https://adobkin.com/2011/04/25/268/

Comments

antonio's blog

antonio

Share

Tags

Twitter

Разработка расширений для PHP. Хэш-таблицы (HashTables). Часть 1

API функции для работы с хэш-таблицами

Инициализация

Вычисление хэша ассоциативного индекса

Добавление элементов

Обновление данных

Поиск данных

Удаление элементов

Другие функции

antonio