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

В данной части будут рассмотрены способы сравнения и сортировки хэш-таблиц. А также освободение ресурсов занимаемых хэш-таблицами

Сравнение

int zend_hash_minmax(HashTable *ht, compare_func_t compar, int flag, void **pData TSRMLS_DC) - Функция сравнения элементов в хэш-таблице. В функции организуется цикл по элементам хэш-таблицы. Для сравнения элементов используется callback-функция compar в которую передаются указатели на сравниваемые элементы.

Параметры:

ht - указатель на хэш таблицу
compar - callback-функция сравнения элементов
flag - если указано не нулевое значение, то будет найдено максимальное значение, иначе минимальное
pData - указатель на данные максимального или минимального элемента в зависимости от значения флага flag и возвращенного callback-функцией compare значения

После указателя на данные pData в функцию всегда должен передаваться макрос TSRMLS_CC. Функция возвращает FAILURE если в хэш-таблице нет элементов, иначе SUCCESS.

Прототип callback-фцнкции compar:

typedef int (*compare_func_t)(const void *a, const void *b TSRMLS_DC)

сallback-функция должна возвращать 0, если элементы равны; 1, если b "меньше" a; -1, если a_ "меньше" b

Пример использования::

int mht_item_compare(const void *a, const void *b TSRMLS_DC)  
{
    Bucket *f = *(Bucket **)a;
    Bucket *s = *(Bucket **)b;

    zval *f_data = *(zval **)f->pData;
    zval *s_data = *(zval **)s->pData;

    if(Z_LVAL_P(f_data) > Z_LVAL_P(s_data)) {
        return 1;
    } else if(Z_LVAL_P(f_data) &lt; Z_LVAL_P(s_data)) {
        return -1;
    } else {
        return 0;
    }
}

void compare() {  
    /* Создаем тестовую хэш-таблицу и помещаем в нее 3-элемента с целочисленными данными */
    HashTable *mht = NULL;
    zval *var = NULL;
    zval *var2 = NULL;
    zval *var3 = NULL;

    ALLOC_HASHTABLE(mht);
    zend_hash_init(mht, 64, NULL, NULL, 1);

    MAKE_STD_ZVAL(var);
    ZVAL_LONG(var, 10);

    MAKE_STD_ZVAL(var2);
    ZVAL_LONG(var2, 20);

    MAKE_STD_ZVAL(var3);
    ZVAL_LONG(var3, 21);

    zend_hash_add(mht, "my_var", sizeof("my_var"), (void **)&var, sizeof(zval*), NULL);
    zend_hash_add(mht, "my_var2", sizeof("my_va2r"), (void **)&var2, sizeof(zval*), NULL);
    zend_hash_add(mht, "my_var3", sizeof("my_var3"), (void **)&var3, sizeof(zval*), NULL);

    zval *data = NULL;
    if (zend_hash_minmax(ht, (compare_func_t)mht_item_compare, 0, (void **)&data) == SUCCESS) {
        zend_printf("Min: %ld&lt;br />", Z_LVAL_P(*(zval **)data));
    }
    if (zend_hash_minmax(ht, (compare_func_t)mht_item_compare, 1, (void **)&data) == SUCCESS) {
       zend_printf("Max: %ld&lt;br />", Z_LVAL_P(*(zval **)data));
    }
}

int zend_hash_compare(HashTable *hta, HashTable *htb, compare_func_t compar, zend_bool ordered TSRMLS_DC) - Функция сравнения хэш-таблиц. Функция возвращает 1, если hta "больше" htb; -1, если htb "больше" hta; 0, если они считаются равными.

Параметры:

hta - указатель на первую хэш таблицу
htb - указатель на вторую хэш таблицу
compar - указатель на callback-функцию сравнения элементов
ordered - флаг упорядоченного поиска

После флага ordered в функцию всегда должен передаваться макрос TSRMLS_CC

Первым делом функция сравнивает кол-во элементов хэш-таблиц, если какая-либо из таблиц содержит большее кол-во элементов чем другая, то эта таблица считается "большей" и функция сразу возвращает соответствующие значение, другие сравнения не выполняются. Если обе хэш-таблицы имеют одинаковое кол-во элементов, то запускается цикл по элементам хэш-таблицы hta.

Если флаг ordered имеет не нулевое значение, то текущий индекс хэш-таблицы hta сравнивается с индексом хэш-таблицы htb, для нумерованных индексов происходит сравнение их значений, а для ассоциативных индексов вначале сравниваются их длины, а затем с помощью memcmp() их значения. Если индексы не совпали, то функция возвращает соответствующие значение. Если индексы совпали, то вызывается callback-функция compare для индивидуального сравнения элементов, в callback-функцию передаются указатели на сравниваемые элементы.

Если флаг ordered имеет нулевое значение, то осуществляется поиск индекса, по всей таблице htb, с таким же значением, что и у текущего индекса хэш-таблицы hta, для поиска используются функции zend_hash_index_find() и zend_hash_quick_find(), соответственно. Если индекс не найден в таблице htb, то считается, что hta "больше" htb. Функция возвращает 1. Если индекс найден в хэш-таблице htb, то вызывается callback-функция compare для индивидуального сравнения элементов.

Если после завершения цикла по элементам хэш-таблицы hta, различия не найдены, то функция возвращает 0.

Прототип callback-фцнкции compar:

typedef int (*compare_func_t)(const void *a, const void *b TSRMLS_DC)

сallback-функция должна возвращать 0, если элементы равны; 1, если b "меньше" a; -1, если a "меньше" b

Сортировка

int zend_hash_sort(HashTable *ht, sort_func_t sort_func, compare_func_t compare_func, int renumber TSRMLS_DC) - Функция сортировки элементов хэш-таблицы. Функция возвращает SUCCESS в случае успеха, иначе FAILURE.

Параметры:

hta - указатель на хэш таблицу
sort_func - указатель callback-функцию сортировки элементов
compar_func - указатель на callback-функцию сравнения элементов
renumber - флаг переиндексации хэш-таблицы. Если флаг не нулевое значение, то хэш-таблица будет переиндексирована после выполнения сортировки. Все ассоциативные индексы будут отброшены и хэш-таблица будет индексирована числовыми индексами

Прототип callback-фцнкции sort_func:

typedef void (*sort_func_t)(void **Buckets, size_t numBuckets, size_t sizBucket, compare_func_t comp TSRMLS_DC)

Callback-функция вызывается один раз. Первым параметром в callback-функцию передается указатель на массив элементов Bucket, вторым - число элементов в массиве, третьем - размер каждого элемента (sizeof(Bucket *)) и четвертым элементом - указатель на callback-функцию индивидуального сравнения элементов.

Прототип callback-фцнкции compar_func:

typedef int (*compare_func_t)(const void *a, const void *b TSRMLS_DC)

сallback-функция должна возвращать 0, если элементы равны; 1, если b "меньше" a; -1, если a "меньше" b. Указатель на функция передается передается в callback-функцию сортировки

В Zend Engine существует предопределенная функция сортировки zend_qsort(), которая может быть использована в качестве callback-функции.

Уничтожение хэш-таблиц

void zend_hash_clean(HashTable *ht) - функция очищает хэш-таблицу. Функция удаляет все элементы хэш-таблицы в цикле. При удаляет вызывается деструктор, который был указан при инициализации хэш-таблицы(параметр pDestructor функции zend_hash_init()). После очищения хэш-таблица пригодна к повторному использованию.
void zend_hash_destroy(HashTable *ht) - функция уничтожает хэш-таблицу. Функция ведет себя подобно функции zend_hash_clean(), но в отлиии от нее, после удаления элементов из хэш-таблицы также освобождается память выделенная под внутренние ресурсы, хэш-таблица не пригодна к повторному использованию.

После уничтожения хэш-таблицы необходимо вызвать макрос FREE_HASHTABLE(HashTable *ht), для освобождения памяти выделенной под указатель HashTable.

Пример:

HashTable *mht = NULL;  
zval *var = NULL;  
zval *var2 = NULL;  
zval *var3 = NULL;

ALLOC_HASHTABLE(mht);  
zend_hash_init(mht, 64, NULL, NULL, 1);

MAKE_STD_ZVAL(var);  
ZVAL_LONG(var, 10);

MAKE_STD_ZVAL(var2);  
ZVAL_LONG(var2, 20);

MAKE_STD_ZVAL(var3);  
ZVAL_LONG(var3, 21);

zend_hash_add(mht, "my_var", sizeof("my_var"), (void **)&var, sizeof(zval*), NULL);  
zend_hash_add(mht, "my_var2", sizeof("my_va2r"), (void **)&var2, sizeof(zval*), NULL);  
zend_hash_add(mht, "my_var3", sizeof("my_var3"), (void **)&var3, sizeof(zval*), NULL);

/* ... */

zend_hash_destroy(ht);  
FREE_HASHTABLE(ht);

php extensions

Permalink: https://adobkin.com/2011/05/11/471/

Comments

antonio's blog

antonio

Share

Tags

Twitter

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

Сравнение

Сортировка

Уничтожение хэш-таблиц

antonio