Lines Matching full:node
61 * To traverse a #QTree, calling a function for each node visited in
87 gpointer key; /* key for this node */
88 gpointer value; /* value stored at this node */
106 static QTreeNode *q_tree_node_balance(QTreeNode *node);
109 static QTreeNode *q_tree_node_search(QTreeNode *node,
112 static QTreeNode *q_tree_node_rotate_left(QTreeNode *node);
113 static QTreeNode *q_tree_node_rotate_right(QTreeNode *node);
115 static void q_tree_node_check(QTreeNode *node);
122 QTreeNode *node = g_new(QTreeNode, 1); in q_tree_node_new() local
124 node->balance = 0; in q_tree_node_new()
125 node->left = NULL; in q_tree_node_new()
126 node->right = NULL; in q_tree_node_new()
127 node->left_child = FALSE; in q_tree_node_new()
128 node->right_child = FALSE; in q_tree_node_new()
129 node->key = key; in q_tree_node_new()
130 node->value = value; in q_tree_node_new()
132 return node; in q_tree_node_new()
219 * Returns the first in-order node of the tree, or %NULL
222 * Returns: (nullable) (transfer none): the first node in the tree
248 * @node: a #QTree node
250 * Returns the previous in-order node of the tree, or %NULL
251 * if the passed node was already the first one.
253 * Returns: (nullable) (transfer none): the previous node in the tree
258 q_tree_node_previous(QTreeNode *node) in q_tree_node_previous() argument
262 g_return_val_if_fail(node != NULL, NULL); in q_tree_node_previous()
264 tmp = node->left; in q_tree_node_previous()
266 if (node->left_child) { in q_tree_node_previous()
277 * @node: a #QTree node
279 * Returns the next in-order node of the tree, or %NULL
280 * if the passed node was already the last one.
282 * Returns: (nullable) (transfer none): the next node in the tree
287 q_tree_node_next(QTreeNode *node) in q_tree_node_next() argument
291 g_return_val_if_fail(node != NULL, NULL); in q_tree_node_next()
293 tmp = node->right; in q_tree_node_next()
295 if (node->right_child) { in q_tree_node_next()
316 QTreeNode *node; in q_tree_remove_all() local
321 node = q_tree_node_first(tree); in q_tree_remove_all()
323 while (node) { in q_tree_remove_all()
324 next = q_tree_node_next(node); in q_tree_remove_all()
327 tree->key_destroy_func(node->key); in q_tree_remove_all()
330 tree->value_destroy_func(node->value); in q_tree_remove_all()
332 g_free(node); in q_tree_remove_all()
339 node = next; in q_tree_remove_all()
438 * Returns: (transfer none): the inserted (or set) node.
447 QTreeNode *node; in q_tree_insert_node() local
451 node = q_tree_insert_internal(tree, key, value, FALSE); in q_tree_insert_node()
457 return node; in q_tree_insert_node()
469 * only this function does not return the inserted or set node.
495 * Returns: (transfer none): the inserted (or set) node.
504 QTreeNode *node; in q_tree_replace_node() local
508 node = q_tree_insert_internal(tree, key, value, TRUE); in q_tree_replace_node()
514 return node; in q_tree_replace_node()
524 * only this function does not return the inserted or set node.
541 QTreeNode *node, *retnode; in q_tree_insert_internal() local
555 node = tree->root; in q_tree_insert_internal()
558 int cmp = tree->key_compare(key, node->key, tree->key_compare_data); in q_tree_insert_internal()
562 tree->value_destroy_func(node->value); in q_tree_insert_internal()
565 node->value = value; in q_tree_insert_internal()
569 tree->key_destroy_func(node->key); in q_tree_insert_internal()
572 node->key = key; in q_tree_insert_internal()
580 return node; in q_tree_insert_internal()
582 if (node->left_child) { in q_tree_insert_internal()
583 path[idx++] = node; in q_tree_insert_internal()
584 node = node->left; in q_tree_insert_internal()
588 child->left = node->left; in q_tree_insert_internal()
589 child->right = node; in q_tree_insert_internal()
590 node->left = child; in q_tree_insert_internal()
591 node->left_child = TRUE; in q_tree_insert_internal()
592 node->balance -= 1; in q_tree_insert_internal()
600 if (node->right_child) { in q_tree_insert_internal()
601 path[idx++] = node; in q_tree_insert_internal()
602 node = node->right; in q_tree_insert_internal()
606 child->right = node->right; in q_tree_insert_internal()
607 child->left = node; in q_tree_insert_internal()
608 node->right = child; in q_tree_insert_internal()
609 node->right_child = TRUE; in q_tree_insert_internal()
610 node->balance += 1; in q_tree_insert_internal()
627 gboolean left_node = (bparent && node == bparent->left); in q_tree_insert_internal()
628 g_assert(!bparent || bparent->left == node || bparent->right == node); in q_tree_insert_internal()
630 if (node->balance < -1 || node->balance > 1) { in q_tree_insert_internal()
631 node = q_tree_node_balance(node); in q_tree_insert_internal()
633 tree->root = node; in q_tree_insert_internal()
635 bparent->left = node; in q_tree_insert_internal()
637 bparent->right = node; in q_tree_insert_internal()
641 if (node->balance == 0 || bparent == NULL) { in q_tree_insert_internal()
651 node = bparent; in q_tree_insert_internal()
729 QTreeNode *node, *parent, *balance; in q_tree_remove_internal() local
742 node = tree->root; in q_tree_remove_internal()
745 int cmp = tree->key_compare(key, node->key, tree->key_compare_data); in q_tree_remove_internal()
750 if (!node->left_child) { in q_tree_remove_internal()
754 path[idx++] = node; in q_tree_remove_internal()
755 node = node->left; in q_tree_remove_internal()
757 if (!node->right_child) { in q_tree_remove_internal()
761 path[idx++] = node; in q_tree_remove_internal()
762 node = node->right; in q_tree_remove_internal()
771 g_assert(!parent || parent->left == node || parent->right == node); in q_tree_remove_internal()
772 left_node = (parent && node == parent->left); in q_tree_remove_internal()
774 if (!node->left_child) { in q_tree_remove_internal()
775 if (!node->right_child) { in q_tree_remove_internal()
780 parent->left = node->left; in q_tree_remove_internal()
784 parent->right = node->right; in q_tree_remove_internal()
788 /* node has a right child */ in q_tree_remove_internal()
789 QTreeNode *tmp = q_tree_node_next(node); in q_tree_remove_internal()
790 tmp->left = node->left; in q_tree_remove_internal()
793 tree->root = node->right; in q_tree_remove_internal()
795 parent->left = node->right; in q_tree_remove_internal()
798 parent->right = node->right; in q_tree_remove_internal()
803 /* node has a left child */ in q_tree_remove_internal()
804 if (!node->right_child) { in q_tree_remove_internal()
805 QTreeNode *tmp = q_tree_node_previous(node); in q_tree_remove_internal()
806 tmp->right = node->right; in q_tree_remove_internal()
809 tree->root = node->left; in q_tree_remove_internal()
811 parent->left = node->left; in q_tree_remove_internal()
814 parent->right = node->left; in q_tree_remove_internal()
818 /* node has a both children (pant, pant!) */ in q_tree_remove_internal()
819 QTreeNode *prev = node->left; in q_tree_remove_internal()
820 QTreeNode *next = node->right; in q_tree_remove_internal()
821 QTreeNode *nextp = node; in q_tree_remove_internal()
826 /* find the immediately next node (and its parent) */ in q_tree_remove_internal()
836 if (nextp != node) { in q_tree_remove_internal()
845 next->right = node->right; in q_tree_remove_internal()
847 node->balance -= 1; in q_tree_remove_internal()
856 /* prepare 'next' to replace 'node' */ in q_tree_remove_internal()
858 next->left = node->left; in q_tree_remove_internal()
859 next->balance = node->balance; in q_tree_remove_internal()
907 tree->key_destroy_func(node->key); in q_tree_remove_internal()
910 tree->value_destroy_func(node->value); in q_tree_remove_internal()
914 g_free(node); in q_tree_remove_internal()
926 * Gets the tree node corresponding to the given key. Since a #QTree is
930 * Returns: (nullable) (transfer none): the tree node corresponding to
960 QTreeNode *node; in q_tree_lookup() local
962 node = q_tree_lookup_node(tree, key); in q_tree_lookup()
964 return node ? node->value : NULL; in q_tree_lookup()
988 QTreeNode *node; in q_tree_lookup_extended() local
992 node = q_tree_find_node(tree, lookup_key); in q_tree_lookup_extended()
994 if (node) { in q_tree_lookup_extended()
996 *orig_key = node->key; in q_tree_lookup_extended()
999 *value = node->value; in q_tree_lookup_extended()
1010 * @func: the function to call for each node visited.
1028 QTreeNode *node; in q_tree_foreach() local
1036 node = q_tree_node_first(tree); in q_tree_foreach()
1038 while (node) { in q_tree_foreach()
1039 if ((*func)(node->key, node->value, user_data)) { in q_tree_foreach()
1043 node = q_tree_node_next(node); in q_tree_foreach()
1057 * 0 for a key/value pair, then the corresponding node is returned as
1063 * Returns: (nullable) (transfer none): the node corresponding to the
1106 QTreeNode *node; in q_tree_search() local
1108 node = q_tree_search_node(tree, search_func, user_data); in q_tree_search()
1110 return node ? node->value : NULL; in q_tree_search()
1120 * If the #QTree contains only one root node the height is 1.
1121 * If the root node has children the height is 2, etc.
1128 QTreeNode *node; in q_tree_height() local
1138 node = tree->root; in q_tree_height()
1141 height += 1 + MAX(node->balance, 0); in q_tree_height()
1143 if (!node->left_child) { in q_tree_height()
1147 node = node->left; in q_tree_height()
1168 q_tree_node_balance(QTreeNode *node) in q_tree_node_balance() argument
1170 if (node->balance < -1) { in q_tree_node_balance()
1171 if (node->left->balance > 0) { in q_tree_node_balance()
1172 node->left = q_tree_node_rotate_left(node->left); in q_tree_node_balance()
1174 node = q_tree_node_rotate_right(node); in q_tree_node_balance()
1175 } else if (node->balance > 1) { in q_tree_node_balance()
1176 if (node->right->balance < 0) { in q_tree_node_balance()
1177 node->right = q_tree_node_rotate_right(node->right); in q_tree_node_balance()
1179 node = q_tree_node_rotate_left(node); in q_tree_node_balance()
1182 return node; in q_tree_node_balance()
1189 QTreeNode *node; in q_tree_find_node() local
1192 node = tree->root; in q_tree_find_node()
1193 if (!node) { in q_tree_find_node()
1198 cmp = tree->key_compare(key, node->key, tree->key_compare_data); in q_tree_find_node()
1200 return node; in q_tree_find_node()
1202 if (!node->left_child) { in q_tree_find_node()
1206 node = node->left; in q_tree_find_node()
1208 if (!node->right_child) { in q_tree_find_node()
1212 node = node->right; in q_tree_find_node()
1218 q_tree_node_search(QTreeNode *node, in q_tree_node_search() argument
1224 if (!node) { in q_tree_node_search()
1229 dir = (*search_func)(node->key, data); in q_tree_node_search()
1231 return node; in q_tree_node_search()
1233 if (!node->left_child) { in q_tree_node_search()
1237 node = node->left; in q_tree_node_search()
1239 if (!node->right_child) { in q_tree_node_search()
1243 node = node->right; in q_tree_node_search()
1249 q_tree_node_rotate_left(QTreeNode *node) in q_tree_node_rotate_left() argument
1255 right = node->right; in q_tree_node_rotate_left()
1258 node->right = right->left; in q_tree_node_rotate_left()
1260 node->right_child = FALSE; in q_tree_node_rotate_left()
1263 right->left = node; in q_tree_node_rotate_left()
1265 a_bal = node->balance; in q_tree_node_rotate_left()
1274 node->balance = a_bal - 1; in q_tree_node_rotate_left()
1281 node->balance = a_bal - b_bal - 1; in q_tree_node_rotate_left()
1288 q_tree_node_rotate_right(QTreeNode *node) in q_tree_node_rotate_right() argument
1294 left = node->left; in q_tree_node_rotate_right()
1297 node->left = left->right; in q_tree_node_rotate_right()
1299 node->left_child = FALSE; in q_tree_node_rotate_right()
1302 left->right = node; in q_tree_node_rotate_right()
1304 a_bal = node->balance; in q_tree_node_rotate_right()
1313 node->balance = a_bal - b_bal + 1; in q_tree_node_rotate_right()
1320 node->balance = a_bal + 1; in q_tree_node_rotate_right()
1328 q_tree_node_height(QTreeNode *node) in q_tree_node_height() argument
1333 if (node) { in q_tree_node_height()
1337 if (node->left_child) { in q_tree_node_height()
1338 left_height = q_tree_node_height(node->left); in q_tree_node_height()
1341 if (node->right_child) { in q_tree_node_height()
1342 right_height = q_tree_node_height(node->right); in q_tree_node_height()
1351 static void q_tree_node_check(QTreeNode *node) in q_tree_node_check() argument
1358 if (node) { in q_tree_node_check()
1359 if (node->left_child) { in q_tree_node_check()
1360 tmp = q_tree_node_previous(node); in q_tree_node_check()
1361 g_assert(tmp->right == node); in q_tree_node_check()
1364 if (node->right_child) { in q_tree_node_check()
1365 tmp = q_tree_node_next(node); in q_tree_node_check()
1366 g_assert(tmp->left == node); in q_tree_node_check()
1372 if (node->left_child) { in q_tree_node_check()
1373 left_height = q_tree_node_height(node->left); in q_tree_node_check()
1375 if (node->right_child) { in q_tree_node_check()
1376 right_height = q_tree_node_height(node->right); in q_tree_node_check()
1380 g_assert(balance == node->balance); in q_tree_node_check()
1382 if (node->left_child) { in q_tree_node_check()
1383 q_tree_node_check(node->left); in q_tree_node_check()
1385 if (node->right_child) { in q_tree_node_check()
1386 q_tree_node_check(node->right); in q_tree_node_check()