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
92 /* don't need to check for root node here because root->parent is
93 the sentinel nil node, and root->parent->left points back to root */
133 * node and free everything under it. Used by dict_free().
135 static void free_nodes(dict_t *dict, dnode_t *node, dnode_t *nil)
137 if (node == nil)
139 free_nodes(dict, node->left, nil);
140 free_nodes(dict, node->right, nil);
141 dict->freenode(node, dict->context);
147 * dict_next() successor function, verifying that the key of each node is
177 * three of the red black properties. It checks that every red node has only
178 * black children. It makes sure that each node is either red or black. And it
182 * mismatches. It does not check for every nil node being black, because there
183 * is only one sentinel nil node. The return value of this function is the
184 * black height of the subtree rooted at the node ``root'', or zero if the
228 * Verify that the tree contains the given node. This is done by
230 * given pointer. Returns 1 if the node is found, otherwise
233 static int verify_dict_has_node(dnode_t *nil, dnode_t *root, dnode_t *node)
236 return root == node
237 || verify_dict_has_node(nil, root->left, node)
238 || verify_dict_has_node(nil, root->right, node);
269 * Select a different set of node allocator routines.
384 /* check that the sentinel node and root node are black */
391 /* nil->left is the root node; check that its parent pointer is nil */
433 * Locate a node in the dictionary having the given key.
434 * If the node is not found, a null a pointer is returned (rather than
435 * a pointer that dictionary's nil sentinel node), otherwise a pointer to the
436 * located node is returned.
473 * Look for the node corresponding to the lowest key that is equal to or
474 * greater than the given key. If there is no such node, return null.
504 * Look for the node corresponding to the greatest key that is equal to or
505 * lower than the given key. If there is no such node, return null.
536 * Insert a node into the dictionary. The node should have been
542 void dict_insert(dict_t *dict, dnode_t *node, const void *key)
548 node->key = key;
551 dict_assert(!dict_contains(dict, node));
552 dict_assert(!dnode_is_in_a_dict(node));
570 parent->left = node;
572 parent->right = node;
574 node->parent = parent;
575 node->left = nil;
576 node->right = nil;
582 node->color = dnode_red;
592 node = grandpa;
595 if (node == parent->right) {
597 parent = node;
612 node = grandpa;
615 if (node == parent->left) {
617 parent = node;
635 * Delete the given node from the dictionary. If the given node does not belong
637 * deleted node is returned.
649 * If the node being deleted has two children, then we replace it with its
650 * successor (i.e. the leftmost node in the right subtree.) By doing this,
652 * value *only* move to the deleted node and the successor is spliced out
656 * node we are given, not some other node, and must not move contents from
657 * one node to another behind the user's back.
686 * in place of the node that we want deleted.
810 * Allocate a node using the dictionary's allocator routine, give it
815 dnode_t *node = dict->allocnode(dict->context);
817 if (node) {
818 dnode_init(node, data);
819 dict_insert(dict, node, key);
826 void dict_delete_free(dict_t *dict, dnode_t *node)
828 dict_delete(dict, node);
829 dict->freenode(node, dict->context);
834 * Return the node with the lowest (leftmost) key. If the dictionary is empty
849 * Return the node with the highest (rightmost) key. If the dictionary is empty
864 * Return the given node's successor node---the node which has the
865 * next key in the the left to right ordering. If the node has
867 * the nil node.
891 * Return the given node's predecessor, in the key order.
892 * The nil sentinel node is returned if there is no predecessor.
942 int dict_contains(dict_t *dict, dnode_t *node)
944 return verify_dict_has_node(dict_nil(dict), dict_root(dict), node);
952 static void dnode_free(dnode_t *node, void *UNUSED(context))
954 free(node);
1011 dnode_t *node = dict_first(dict), *next;
1013 while (node != NULL) {
1015 /* the next node from under us */
1016 dict_assert(dict_contains(dict, node));
1017 next = dict_next(dict, node);
1018 function(dict, node, context);
1019 node = next;