Краткое содержание первой части

Что теперь?

Поехали

Получаем код libtrie в наше расширение

cd ~/Documents/libtrie/

git clone https://github.com/legale/libtrie

#include "libtrie/src/libtrie.h"

Функция yatrie_new

trie_s *yatrie_new(uint32_t max_nodes, uint32_t max_refs, uint32_t max_deallocated_size) {...}

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

#ifndef PHP_LIBTRIE_H
#define PHP_LIBTRIE_H

#endif	/* PHP_LIBTRIE_H */

деструктор созданного ресурса 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 функцию деструктор нашего ресурса trie
PHP_MINIT_FUNCTION (libtrie) {
    le_libtrie = zend_register_list_destructors_ex(
            php_libtrie_dtor,
            NULL, PHP_LIBTRIE_RES_NAME, module_number);
    return SUCCESS;
}

Функция удаления созданного дерева

/**
 * @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))

Функция добавление слова в trie

1. 
   
   Код

   
   /**
    * @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);
   }
   

   
   
   
   
2. Добавляю запись в массив функций:
   
   

   PHP_FE(yatrie_add, NULL)
   

3. Добавляю декларацию в заголовочный файл:
   
   

   PHP_FUNCTION(yatrie_add)
   

Функция вывода всех слов из словаря

1. 
   
   Код

   /**
    * @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);
   }
   

   
   
2. Добавляю запись в массив функций:
   
   

   PHP_FE(node_traverse, NULL)
   

   
   
3. Добавляю декларацию в заголовочный файл:
   
   

   PHP_FUNCTION(node_traverse)
   

   
   

Сборка расширения

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