cd ~/Documents/libtrie/
git clone https://github.com/legale/libtrie
php_libtrie.c
и файл с кодом библиотеки libtrie/src/libtrie.c
.#include "libtrie/src/libtrie.h"
trie_s *yatrie_new(uint32_t max_nodes, uint32_t max_refs, uint32_t max_deallocated_size) {...}
trie_s
. Проще говоря, возвращает ссылку на созданное префиксное дерево.fopen("filename.ext");
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_FE(yatrie_new, NULL)
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 */
/**
* @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 функцию деструктор нашего ресурса 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);
#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))
/**
* @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)
/**
* @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)
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
phpize && ./configure
make
nano yatrie_test.php
<?php
echo "Cоздаем дерево на 500 узлов и 500 ссылок\n\n";
$trie = yatrie_new(500, 500, 100);
echo "Готово!\n Добавляем слова, сохряняя id узлов в массив \$nodes\n";
$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
К сожалению, не доступен сервер mySQL