А вот задачка...

[swizard]

...любопытная кстати. Хотя бы тем, что я не могу сообразить, как ее сделать прямо.

Надо состыковать два интерфейса для обхода дерева, суть токова:

У нас есть такой:

typedef struct _node_ node_t;

typedef int (*callback)( node_t *node, void *context );

int bypass_tree( node_t *root, callback cb, void *context );
а надо поверх него

Comments

[mxax]

Полюбас надо где-то хранить стейт bypass_tree(), либо во внешней структуре, либо, опять же, POSIX makecontext()/swapcontext().

[_winnie]

longjmp не умеет возвращаться к убитому стеку.
Имхо в C не получится, если только не завести другие OS-потоки.

[mxax]

В C как раз получится, man makecontext, man swapcontext, как я сказал уже выше.

[_winnie]

Ну, если не нужна компиляция в Visual C++ под Windows, то получится.

[mxax]

Под винду есть куча реализаций или можно использовать те же fibers, но они тяжелее.

[_winnie]

Кстати, да. Теоретически, можно писать непортабельный код без потоков, через Windows Fiber API/ POSIX swapcontext

[swizard]

Класс, первая же ссылка по запросу Windows Fiber API как раз посвящена моей проблеме :) http://www.ddj.com/cpp/184401766

[ext_69439]

Зачем массив?
Любое дерево имеет строгую иерархию такую, что имея произвольную ноду можно легко получить предыдущий или последующий элемент. Это справедливо как для бинарных деревьев, так и для tries.
Если брать, например бинарное дерево, будь то avl-tree или rb-tree, то алгоритм будет такой:
Для next:
Если у ноды есть правая нода, то следующим элементом будет самая левая нода правого поддерева или сама правая нода, если у той отсутвует левое поддерево.

В противном случае, следуюшим элементом будет та нода, для которой исходная нода находится в левом поддереве.

node_t *bin_tree_next(node_t *n)
{
if (n->right) {
for (n = n->right; n->left; n = n->left);
}
else {
note_t *tmp = n;
while (tmp->parent && tmp == tmp->parent->right) {
tmp = tmp->parent;
}
if (tmp == n) {
n = NULL;
}
else {
n = tmp->parent;
}
}

return n;
}

Зеркальное отражение bin_tree_next - bin_tree_prev.

[swizard]

Да это все понятно, но задача не в том :)

Внутрь реализации я залезть не могу, мне нужно четко написать адаптер между двумя такими интерфейсами.

[cmm]

наваять классический inversion of control на Ц - это богато, да.

поглядите как реализован call/cc в SCM или Guile - отвратительно по сути (setjmp/longjmp + копирование стека кучу и обратно), но не так уж сложно и туеву хучу лет вполне себе работает.

ну или можно действительно по-индийски сделать, поскольку любое решение не через call/cc (или моральный аналог на тредах или фиберах) потребует так или иначе прошерстить всё дерево.