Lines Matching defs:node
74 static void dnode_free(dnode_t *node, void *context);
77 * Perform a ``left rotation'' adjustment on the tree. The given node P and
93 /* don't need to check for root node here because root->parent is
94 the sentinel nil node, and root->parent->left points back to root */
135 * node and free everything under it. Used by dict_free().
138 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)
140 if (node == nil)
142 free_nodes(dict, node->left, nil);
143 free_nodes(dict, node->right, nil);
144 dict->freenode(node, dict->context);
150 * dict_next() successor function, verifying that the key of each node is
180 * three of the red black properties. It checks that every red node has only
181 * black children. It makes sure that each node is either red or black. And it
185 * mismatches. It does not check for every nil node being black, because there
186 * is only one sentinel nil node. The return value of this function is the
187 * black height of the subtree rooted at the node ``root'', or zero if the
233 * Verify that the tree contains the given node. This is done by
235 * given pointer. Returns 1 if the node is found, otherwise
239 static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node)
242 return root == node
243 || verify_dict_has_node(nil, root->left, node)
244 || verify_dict_has_node(nil, root->right, node);
277 * Select a different set of node allocator routines.
399 /* check that the sentinel node and root node are black */
406 /* nil->left is the root node; check that its parent pointer is nil */
448 * Locate a node in the dictionary having the given key.
449 * If the node is not found, a null a pointer is returned (rather than
450 * a pointer that dictionary's nil sentinel node), otherwise a pointer to the
451 * located node is returned.
489 * Look for the node corresponding to the lowest key that is equal to or
490 * greater than the given key. If there is no such node, return null.
521 * Look for the node corresponding to the greatest key that is equal to or
522 * lower than the given key. If there is no such node, return null.
554 * Insert a node into the dictionary. The node should have been
561 void dict_insert(dict_t *dict, dnode_t *node, const void *key)
567 node->key = key;
570 assert (!dict_contains(dict, node));
571 assert (!dnode_is_in_a_dict(node));
589 parent->left = node;
591 parent->right = node;
593 node->parent = parent;
594 node->left = nil;
595 node->right = nil;
601 node->color = dnode_red;
611 node = grandpa;
614 if (node == parent->right) {
616 parent = node;
631 node = grandpa;
634 if (node == parent->left) {
636 parent = node;
654 * Delete the given node from the dictionary. If the given node does not belong
656 * deleted node is returned.
669 * If the node being deleted has two children, then we replace it with its
670 * successor (i.e. the leftmost node in the right subtree.) By doing this,
672 * value *only* move to the deleted node and the successor is spliced out
676 * node we are given, not some other node, and must not move contents from
677 * one node to another behind the user's back.
706 * in place of the node that we want deleted.
830 * Allocate a node using the dictionary's allocator routine, give it
836 dnode_t *node = dict->allocnode(dict->context);
838 if (node) {
839 dnode_init(node, data);
840 dict_insert(dict, node, key);
847 void dict_delete_free(dict_t *dict, dnode_t *node)
849 dict_delete(dict, node);
850 dict->freenode(node, dict->context);
855 * Return the node with the lowest (leftmost) key. If the dictionary is empty
871 * Return the node with the highest (rightmost) key. If the dictionary is empty
887 * Return the given node's successor node---the node which has the
888 * next key in the the left to right ordering. If the node has
890 * the nil node.
915 * Return the given node's predecessor, in the key order.
916 * The nil sentinel node is returned if there is no predecessor.
967 int dict_contains(dict_t *dict, dnode_t *node)
969 return verify_dict_has_node(dict_nil(dict), dict_root(dict), node);
977 static void dnode_free(dnode_t *node, void *context EXT2FS_ATTR((unused)))
979 free(node);
1032 dnode_t *node = dict_first(dict), *next;
1034 while (node != NULL) {
1036 /* the next node from under us */
1037 assert (dict_contains(dict, node));
1038 next = dict_next(dict, node);
1039 function(dict, node, context);
1040 node = next;
