GNode

GNode - это N-направленное дерево, реализованное как двусвязный список с родителем и списком детей. Поэтому, большинство операций со списками имеют аналоги в API GNode. Вы также можете проходить дерево различными способами. Вот объявление узла: typedef struct _GNode GNode; struct _GNode { gpointer data; GNode *next; GNode *prev; GNode *parent; GNode *children; }; Существуют макросы для доступа к членам GNode, показанные в списке макросов 2..6. Как и с GList, член data предполагается использовать напрямую. Эти макросы возвращают члены next, prev и children соответственно; они также проверяют, что аргумент равен NULL перед удалением ссылки на него, и возвращают NULL, если равен.

Список макросов 2..6: Доступ к членам GNode

"#include "<glib.h>


g_node_prev_sibling(node)
g_node_next_sibling(node)
g_node_first_child(node)

Для создания узла предоставляется обычная функция "_new()" (список функций 2..16). "g_node_new()" создает узел без детей и родителей, содержащий data. Обычно, "g_node_new()" используется только для создания корневого узла; есть удобные макросы, которые автоматически создают новые узлы при необходимости.

Список функций 2..16: Создание GNode

"#include "<glib.h>


GNode *g_node_new(gpointer data)

Для построения дерева используются операции, приведенные в списке функций 2..17. Каждая операция возвращает только что добавленный узел, для удобства при написании циклов или прохождении дерева. В отличии от GList, возвращаемое значение можно безопасно проигнорировать.

Список функций 2..17: Построение дерева GNode

"#include "<glib.h>


GNode *g_node_insert(GNode *parent, gint position,
                     GNode *node)
GNode *g_node_insert_before(GNode *parent, GNode *sibling,
                            GNode *node)
GNode *g_node_prepend(GNode *parent, GNode *node)

Удобные макросы, показанные в списке макросов 2..7 реализованы в терминах фундаментальных операций. "g_node_append()" аналогичен "g_node_prepend()"; остальные берут аргумент data, автоматически выделяя для него узел, и вызывают соответствующую базовую операцию.

Список макросов 2..7: Построение GNode

"#include "<glib.h>


g_node_append(parent, node)
g_node_insert_data(parent, position, data)
g_node_insert_data_before(parent, sibling, data)
g_node_prepend_data(parent, data)
g_node_append_data(parent, data)

Для удаления узла из дерева, существуют две функции, показанные в списке функций 2..18. "g_node_destroy()" удаляет узел из дерева, освобождая его и всех его детей. "g_node_unlink()" удаляет узел и превращает его в корневой узел, то есть преобразует поддерево в независимое дерево.

Список функций 2..18: Удаление GNode

"#include "<glib.h>


void g_node_destroy(GNode *root)
void g_node_unlink(GNode *node)

Есть два макроса для определения вершины и низа дерева GNode, показанные в списке макросов 2..8. Корневой узел определен как узел без родителя и одноуровневых элементов. Листовой узел не имеет детей.

Список макросов 2..8: Предикаты для GNode

"#include "<glib.h>


G_NODE_IS_ROOT(node)
G_NODE_IS_LEAF(node)

Вы можете попросить у glib нужную информацию о GNode, включая число узлов, которое оно содержит, его корневой узел, его глубину и узел, содержащий определенный указатель на данные. Эти функции приведены в списке функций 2..19.

GTraverseType был введен ранее, по отношению к GTree; вот возможные значения для GNode:

"G_NODE_ORDER" сначала обходит левого ребенка, затем сам узел, затем остальных детей узла. Это не очень полезно; в основном это предназначено для использования с GTree.
"G_PRE_ORDER" обходит текущий узел, затем каждого ребенка.
"G_POST_ORDER" обходит каждого ребенка, а затем текущий узел.
"G_LEVEL_ORDER" сначала обходит сам узел; затем каждого ребенка узла; затем детей детей; затем детей детей детей; и так далее. Таким образом, он обходит каждый узел глубины 0, затем каждый узел глубины 1, каждый узел глубины 2 и так далее.

Функции для обхода дерева GNode имеют аргумент GTraverseFlags. Это битовое поле, используемое для изменения природы обхода. В настоящее время существуют только три флага -- вы можете обходить только листовые узлы, только нелистовые узлы, или все узлы:

"G_TRAVERSE_LEAFS" означает, что обходить надо только листовые узлы.
"G_TRAVERSE_NON_LEAFS" означает, что обходить надо только нелистовые узлы.
"G_TRAVERSE_ALL" -- это просто обозначение для "(G_TRAVERSE_LEAFS | G_TRAVERSE_NON_LEAFS)".

Список функций 2..19: Свойства GNode

"#include "<glib.h>


guint g_node_n_nodes(GNode *root, GTraverseFlags flags)
GNode *g_node_get_root(GNode *node)
gboolean g_node_is_ancestor(GNode *node, GNode *descendant)
guint g_node_depth(GNode *node)
GNode *g_node_find(GNode *root, GTraverseType order,
                   GTraverseFlags flags, gpointer data)

Остальные функции GNode прямолинейны; большинство из них просто являются операциями над списком детей узла. Они приведены в списке функций 2..20. Есть также два определения функций только для GNode: typedef gboolean (*GNodeTraverseFunc) (GNode *node, gpointer data); typedef void (*GNodeForeachFunc) (GNode *node, gpointer data); Они вызываются с указателем на узел, который обходится, и пользовательские данные. GNodeTraverseFunc может возвратить TRUE для остановки обхода; поэтому вы можете использовать GNodeTraverseFunc в комбинации с "g_node_traverse()" для поиска значения в дереве.

Список функций 2..20: Доступ к GNode

"#include "<glib.h>


void g_node_traverse(GNode *root, GTraverseType order,
                     GTraverseFlags flags, gint max_depth,
                     GNodeTraverseFunc func, gpointer data)
guint g_node_max_height(GNode *root)
void g_node_children_foreach(GNode *node, GTraverseFlags flags,
                             GNodeForeachFunc func, gpointer data)
void g_node_reverse_children(GNode *node)
guint g_node_n_children(GNode *node)
GNode *g_node_nth_child(GNode *node, guint n)
GNode *g_node_last_child(GNode *node)
GNode *g_node_find_child(GNode *node, GTraverseFlags flags,
                         gpointer data)
gint g_node_child_position(GNode *node, GNode *child)
gint g_node_child_index(GNode *node, gpointer data)
GNode *g_node_first_sibling(GNode *node)
GNode *g_node_last_sibling(GNode *node)

Linux Land
2000-09-15