typedef void (* Destructor)(Pointer data);
typedef void (* Enumerator)(const char * key, Pointer data, void * user);
typedef Pointer (* Updater)(Pointer old, Pointer next);


typedef struct _Trie { 
  /* ... */
} Trie;


/* Создать и инициализировать префиксное дерево
 * dtor - деструктор. Этой функции будут передаваться data удаляемых элементов.
 * Если dtor = NULL, деструктор отсутствует (не будет вызываться). */
Trie * trie_create(Destructor dtor);


/* Уничтожить префиксное дерево (dtor) */
void trie_free(Trie * tr);


/* Проверка существования ключа key в дереве. 1 - есть, 0 - нет. */
int trie_has(const Trie * tr, const char * key);


/* Получить значение по ключу. Если ключа нет, вернуть NULL. */
Pointer trie_get(const Trie * tr, const char * key);


/* Записать соответствие key -> data в префиксное дерево. 
 * Если key уже существовал, соответствующее поле data будет удалено (dtor) 
 * и перезаписано. */
int trie_set(Trie * tr, const char * key, Pointer data);


/* Обновить в префиксном дереве соответствие key -> data (без вызова dtor). 
 * 
 * При обновлении вызовется ф-я up, которой передается старое значение data и
 * параметр next. Функция возвращает новое значение data. 
 * 
 * Если элемента с ключом key нет, то достраивается новая ветка дерева, 
 * а в ф-ю up вместо старого значения data передается NULL. 
 */
int trie_update(Trie * tr, const char * key, Updater up, Pointer next);


/* Удалить элемент с ключом key (dtor) из префиксного дерева (если он есть). 
 * NB!! При этом может быть удалено несколько узлов дерева. */
int trie_delete(Trie * tr, const char * key);


/* Обход дерева в глубину с посещением всех элементов. Функция en будет 
 * вызвана для всех пар (key, data). 
 * 
 * user - дополнительный пользовательский параметр для ф-ии en. 
 */
void trie_traverse(const Trie * tr, Enumerator en, void * user);

void print(const char * key, Pointer data, void * user) {
  if (user) {
    FILE * out = (FILE *) user;
    fprintf(out, "%s  %d\n", key, data);
  }
}

Pointer update(Pointer old, Pointer next) {
  return (Pointer)((int)old + (int)next);
}

void main(void)
{
  Trie * T = trie_create(NULL);

  trie_set(T, "Vasya", (Pointer)16);
  trie_set(T, "Kolya", (Pointer)10);
  trie_set(T, "Petya", (Pointer)18);

  trie_update(T, "Vasya", update, (Pointer)-3);
  trie_update(T, "", Update, (Pointer)100);

  trie_delete(T, "Kolya");

  trie_traverse(T, print, stdout);

  trie_free(T);
}