antonio's blog

antonio's blog


Блог о всяком разном, связанном с разработкой ПО. Пишу редко, когда есть время и желание.

Anton Dobkin
Author

Share


Tags


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

Anton DobkinAnton Dobkin

Хэш-таблицы являются основным контейнером данных в 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.

Параметры:

DJBX33A - быстрый, умеренно стойкий к коллизиям алгоритм хеширования буквенно-цифровых индексов

Использование функции 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) - функция вычисления хэша ассоциативного индекса

Параметры:

Пример:

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.

Параметры:

Пример:

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.

Параметры:

int zend_hash_next_index_insert(HashTable *ht, void *pData, uint nDataSize, void **pDest) - функция добавления элемента, индексируемого числовым индексом, в хэш-таблицу. Функция возвращает SUCCESS в случае успеха, иначе FAILURE.

Параметры:

Пример:

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()

Параметры:

Пример:

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.

Параметры:

Пример:

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.

Параметры:

Пример:

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.

Параметры:

Пример:

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.

Параметры:

Пример:

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.

Параметры:

Пример:

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.

Параметры:

Пример:

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.

Параметры:

Пример:

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. При добавлении нового элемента, индексируемого числовым индексом, в хэш-таблицу, именно этот индекс будет использован

Anton Dobkin
Author

Anton Dobkin

Comments