Краткое содержание первой части
В первой части я сделал болванку расширения, заставил ее правильно работать в IDE Clion, написал функцию-аналог my_array_fill() и проверил ее работоспособность в php.
Что теперь?
Теперь я запилю код библиотеки libtrie в наше расширение.
Немного расскажу как можно заставить работать старые php5 расширения в php7.
Дальше я сделаю несколько основных функций из этой библиотеки в php и проверю, что получилось.
Поехали
Получаем код libtrie в наше расширение
Перехожу в каталог расширения
cd ~/Documents/libtrie/
Клонирую репозиторий libtrie
git clone github.com/legale/libtrie
Открываю файл с кодом расширения php_libtrie.c
и файл с кодом библиотеки libtrie/src/libtrie.c
.
Последний я буду использовать, чтобы сверяться с названиями и синтаксисом функций. Создавамые в php функции я буду использовать такие же, как и в самом библиотеке.
Прежде всего нужно включить заголовочный файл библиотеки в код нашего расширения.
Пишем в php_libtrie.c:
#include «libtrie/src/libtrie.h»
Функция yatrie_new
Делаю первую функцию, которая создаст префиксное дерево. В библиотеке она называется
trie_s *yatrie_new(uint32_t max_nodes, uint32_t max_refs, uint32_t max_deallocated_size) {...}
Как видно из кода, функция принимает на входе 3 числовых аргумента и возвращает указатель на структуру
trie_s
. Проще говоря, возвращает ссылку на созданное префиксное дерево.
Для того чтобы вытащить в PHP наше префиксное дерево в PHP предусмотрен специальный тип данных resource. Когда в PHP выполняется функция
fopen("filename.ext");
Говоря на языке Си, программа просит операционную систему открыть заданный файл, создает указатель на этот файл, который в виде ресурса и возвращается наружу в PHP.
Тоже самое мы будем делать и с нашим деревом.
Сделаем функцию в php_libtrie.c:
PHP_FUNCTION (yatrie_new) {
/* Это указатель на дерево */
trie_s *trie;
//это переменные для аргументов функции
zend_long max_nodes; //максимальное кол-во узлов доступное в нашем дереве
zend_long max_refs; /* максимальное кол-во ссылок в дереве.
* Потребность зависит от плотности записи слов в дерево. Кол-во узлов +25% должно хватать на любое дерево.
* Например, словарь русского языка OpenCorpora ~3млн. слов укладывается в 5млн. узлов и 5млн. ссылок */
zend_long max_deallocated_size; /* максимальный размер освобождаемых участков в блоке ссылок
* Зависит от плотности записи. Всего у нас 96 бит в маске узла, 1 бит зарезервирован, остается 95.
* Значит для любого узла участок памяти в блоке ссылок не может быть больше 95, что значит,
* что макс. размер освобожденного участка ссылок не может быть больше 94. */
//получаем аргументы из PHP
if (zend_parse_parameters(ZEND_NUM_ARGS(), "lll", &max_nodes, &max_refs, &max_deallocated_size) == FAILURE) {
RETURN_FALSE;
}
//создаем дерево и записываем его адрес в памяти в созданный для этого указатель
trie = yatrie_new((uint32_t)max_nodes, (uint32_t)max_refs, (uint32_t)max_deallocated_size);
//Если не удалось - завершаем работу
if (!trie) {
RETURN_NULL();
}
//тут выполняется 2 действия
/* функция zend_register_resource() регистрирует ресурс в недрах Zend,
* пишет номер этого ресурса в глобальную переменную le_libtrie, а макрос ZVAL_RES()
* сохраняет созданный ресурс в zval return_value */
ZVAL_RES(return_value, zend_register_resource(trie, le_libtrie));
}
Теперь нужно добавить созданную функцию в массив функций расширения, иначе функция не будет видна из PHP.
PHP_FE(yatrie_new, NULL)
Чтобы было совсем красиво, я добавлю декларацию функции в заголовочный файл. Этого делать не обязательно, поскольку наши PHP функции не взаимодействуют друг с другом, но я тем не менее предпочитаю декларировать все функции в заголовочном файле.
Просто добавляем строки:
PHP_FUNCTION(confirm_libtrie_compiled);
PHP_FUNCTION(my_array_fill);
PHP_FUNCTION(yatrie_new);
в файл php_libtrie.h. Куда нибудь между:
#ifndef PHP_LIBTRIE_H
#define PHP_LIBTRIE_H
и
#endif /* PHP_LIBTRIE_H */
деструктор созданного ресурса PHP
Созданная функция yatrie_new() создает дерево, а также регистрирует ресурс PHP. Теперь нужна функция, которая будет закрывать созданный ресурс и освобождать память, занятую префиксным деревом.
/**
* @brief деструктор ресурса, он принимает на входе указатель на ресурс и закрывает его
* @param rsrc : zend_resource * указатель
* @return void
*/
static void php_libtrie_dtor(zend_resource *rsrc TSRMLS_DC) {
//тут мы берем указатель на trie из ресурса
trie_s *trie = (trie_s *) rsrc->ptr;
//тут выполняется функция библиотеки, которая освобождает память,
// выделенную для trie
yatrie_free(trie);
}
Поскольку функция внутренняя в массив функций расширения она не включается. Добавлю ее декларацию в php_libtrie.h:
Теперь надо зарегистрировать созданную функцию-деструктор в PHP. Это делается через специальную функцию инициализации расширения. До этого эта функция просто сразу возвращала SUCCESS. Надо добавить туда регистрацию деструктора.
//Регистрируем в PHP функцию деструктор нашего ресурса trie
PHP_MINIT_FUNCTION (libtrie) {
le_libtrie = zend_register_list_destructors_ex(
php_libtrie_dtor,
NULL, PHP_LIBTRIE_RES_NAME, module_number);
return SUCCESS;
}
Функция удаления созданного дерева
Как у функции fopen()
есть пара fclose()
, так и моей функции создания дерева должна быть подруга, которая ее уравновесит.
/**
* @brief Удаляет дерево из памяти
* @param trie : resource
* @return true/false : bool
*/
PHP_FUNCTION (yatrie_free) {
zval *resource; //указатель для zval структуры с ресурсом
//получаем аргумент типа ресурс
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "r", &resource) == FAILURE) {
RETURN_FALSE;
}
/* тут вызывается закрытие ресурса, на входе принимается zend_resource,
* который сначала надо достать из zval. Это и делает макрос Z_RES_P()
*/
if (zend_list_close(Z_RES_P(resource)) == SUCCESS) {
//макрос пишет true в return_vale и делает return
RETURN_TRUE;
}
//макрос пишет false в return_vale и делает return
RETURN_FALSE;
}
Добавляю функцию в массив функций расширения:
PHP_FE(yatrie_free, NULL)
Добавляю декларацию функции в заголовочный файл:
PHP_FUNCTION(yatrie_free);
Как видно на скриншоте, я добавил в заголовочный файл внутреннее название ресурса в PHP, а также макросы PHP5, которые почему-то удалили из PHP7. Я их не использую, но если кто-то захочет с ними можно без труда собрать расширение PHP5 на PHP7.
#define PHP_LIBTRIE_VERSION "0.1.0" /* Replace with version number for your extension */
#define PHP_LIBTRIE_RES_NAME "libtrie data structure" /* PHP resource name */
//previously (php5) used MACROS
#define ZEND_FETCH_RESOURCE(rsrc, rsrc_type, passed_id, default_id, resource_type_name, resource_type)
(rsrc = (rsrc_type) zend_fetch_resource(Z_RES_P(*passed_id), resource_type_name, resource_type))
#define ZEND_REGISTER_RESOURCE(return_value, result, le_result) ZVAL_RES(return_value,zend_register_resource(result, le_result))
Функция добавление слова в trie
Теперь сделаем функцию добавления слова в префиксное дерево.
-
Код
/** * @brief Добавляет в trie слово и возвращает node_id последней буквы добавленного слова * @param trie : resource * @param word : string * @return node_id : int */ PHP_FUNCTION (yatrie_add) { trie_s *trie; //указатель для дерева zval *resource; //указатель для zval структуры с ресурсом unsigned char *word = NULL; //указатель для строки добавляемого слова size_t word_len; //длина слова word uint32_t node_id; //id последнего узла, добавленного слова //получаем аргументы if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "rs", &resource, &word, &word_len) == FAILURE) { RETURN_FALSE } /*получаем ресурс из недр PHP, функция принимает: * 1 аргументом сам ресурс PHP (не zval, а именно ресурс), * 2 аргументом имя ресурса * я установил его через константу в заголовочном файле * 3 аргументом числовой id ресурса, который был присвоен при регистрации ресурса * Функция возвращает указатель типа void *, поэтому надо его привести к правильному типу trie_s * * В PHP5 в этом месте использовался макрос ZEND_FETCH_RESOURCE(), который почему-то решили убрать в PHP7. */ trie = (trie_s *) zend_fetch_resource(Z_RES_P(resource), PHP_LIBTRIE_RES_NAME, le_libtrie); /* добавим слово в trie * первый аргумент - указатель на строку добавляемого слова * второй аргумент - id узла с которого начать добавление, мы добавляем с корневого узла * третий аргумент - указатель на наше дерево. */ node_id = yatrie_add(word, 0, trie); //возвращаем числовое значение RETURN_LONG(node_id); }
- Добавляю запись в массив функций:
PHP_FE(yatrie_add, NULL)
- Добавляю декларацию в заголовочный файл:
PHP_FUNCTION(yatrie_add)
Функция вывода всех слов из словаря
Теперь сделаем функцию, которая будет выбирать все слова из префиксного дерева и выводить их в PHP виде массива.
-
Код
/** * @brief обходит все ветви дерева, начиная с заданного узла, и выводит в массив все * слова, встреченные на своем пути * @param trie : resource * @param node_id : int * @param head (необязательный) : string строка, которая будет * добавлена в начало каждого найденного слова * @return array */ PHP_FUNCTION (node_traverse) { trie_s *trie; //указатель для trie words_s *words; //структура для сохранения слов из trie zval * resource; //указатель для zval ресурса zend_long node_id; //начальный узел unsigned char *head = NULL; //указатель на строку префикс size_t head_len; //длина префикса //получаем аргументы из PHP if (zend_parse_parameters(ZEND_NUM_ARGS(), "rl|s", &resource, &node_id, &head, &head_len) == FAILURE) { RETURN_NULL(); //возвращаем null в случае неудачи } //получим наше дерево из ресурса trie = (trie_s *) zend_fetch_resource(Z_RES_P(resource), PHP_LIBTRIE_RES_NAME, le_libtrie); //для сохранения слов из trie функция node_traverse() использует специальную структура words_s //выделим память под нее words = (words_s *) calloc(1, sizeof(words_s)); words->counter = 0; //установим счетчик слов на 0 //нужна еще 1 структура для передачи префикса string_s *head_libtrie = calloc(1, sizeof(string_s)); //если head задан if(head != NULL) { head_libtrie->length = (uint32_t)head_len; //присвоим длину memcpy(&head_libtrie->letters, head, head_len); //скопируем строку в head_libtrie } //теперь получим слова из trie node_traverse(words, (uint32_t) node_id, head_libtrie, trie); //теперь создадим PHP массив, размер возьмем из счетчика слов в words array_init_size(return_value, words->counter); //добавим слова в массив php while (words->counter--) { //поскольку в trie буквы хранятся в виде кодов, нужно декодировать их //это массив для декодированного слова uint8_t dst[256]; //функция из библиотеки libtrie decode_string(dst, words->words[words->counter]); //эта функция Zend API, которая добавляет в массив элемент с типом php string из типа Си char * add_next_index_string(return_value, (const char *) dst); } //теперь надо освободить память выделенную под words и head_libtrie free(words); free(head_libtrie); }
- Добавляю запись в массив функций:
PHP_FE(node_traverse, NULL)
- Добавляю декларацию в заголовочный файл:
PHP_FUNCTION(node_traverse)
Сборка расширения
Поскольку в расширении теперь используются файлы сторонней библиотеки, эти файлы надо тоже скомпилировать. Открываю файл config.m4 и добавляю туда 2 исходных файла libtrie:
libtrie/src/libtrie.c
libtrie/src/single_list.c
Вот полное содержимое файла после изменений.
PHP_ARG_ENABLE(libtrie, whether to enable libtrie support,
[ --enable-libtrie Enable libtrie support])
if test "$PHP_LIBTRIE" != "no"; then
# если понадобится включить какие-то дополнительные заголовочные файлы
# PHP_ADD_INCLUDE(libtrie/src/)
# ключевая строка
PHP_NEW_EXTENSION(libtrie,
libtrie/src/libtrie.c
libtrie/src/single_list.c
php_libtrie.c
, $ext_shared)
# PHP_NEW_EXTENSION(libtrie, php_libtrie.c libtrie/src/libtrie.c libtrie/src/single_list.c, $ext_shared,, -DZEND_ENABLE_STATIC_TSRMLS_CACHE=1)
fi
Теперь нужно заново сделать ./configure скрипт. Запускаю из корневого каталога расширения:
phpize && ./configure
Теперь собираю расширение:
make
Тестируем
Для теста лучше всего сделать php скрипт, чтобы много не писать в консоли. Я сделаю так:
nano yatrie_test.php
А это содержимое файла:
<?php
echo "Cоздаем дерево на 500 узлов и 500 ссылокnn";
$trie = yatrie_new(500, 500, 100);
echo "Готово!n Добавляем слова, сохряняя id узлов в массив $nodesn";
$nodes[] = yatrie_add($trie, "ух");
$nodes[] = yatrie_add($trie, "ухо");
$nodes[] = yatrie_add($trie, "уха");
echo "Тут хорошо видно как работает дерево.n
Первое слово из 2 букв, поэтому последний узел 2.n
Второе слово из 3 букв, но 2 буквы совпадают с первым словом,n
поэтому только 1 узел добавленn";
print_r($nodes);
print_r(node_traverse($trie, 0));
yatrie_free($trie);
Выполняем в консоли:
php -d extension=modules/libtrie.so yatrie_test.php
Вот что должно получиться:
Полученный исходный код расширения берем отсюда. Не стесняемся и ставим звездочки. :-)
Автор: johovich