Lines Matching defs:node
79 #define IS_EMPTY(node) ((node)->data == NULL)
81 #define WANTEMPTYDATA_OR_DATA(options, node) \
82 ((options & DNS_RBTFIND_EMPTYDATA) != 0 || node->data != NULL)
85 * The variable length stuff stored after the node has the following
90 * NAME_DATA contains the name of the node when it was created.
91 * OLDOFFSETLEN contains the length of OFFSETS when the node was created.
92 * OFFSETS contains the offsets into name for each label when the node
96 #define NAME(node) ((unsigned char *)((node) + 1))
97 #define OFFSETS(node) (NAME(node) + node->oldnamelen + 1)
98 #define OLDOFFSETLEN(node) (OFFSETS(node)[-1])
100 #define NODE_SIZE(node) \
101 (sizeof(*node) + node->oldnamelen + OLDOFFSETLEN(node) + 1)
108 #define IS_RED(node) ((node) != NULL && (node)->color == RED)
109 #define IS_BLACK(node) ((node) == NULL || (node)->color == BLACK)
118 #define ADD_LEVEL(chain, node) \
121 (chain)->levels[(chain)->level_count++] = (node); \
125 * Initialize a dns_name_t that refers to a node's name.
128 node_name(dns_rbtnode_t *node, dns_name_t *name) {
129 name->length = node->namelen;
130 name->labels = node->offsetlen;
131 name->ndata = NAME(node);
132 name->offsets = OFFSETS(node);
133 name->attributes = (struct dns_name_attrs){ .absolute = node->absolute,
142 Name(dns_rbtnode_t *node);
144 Name(dns_rbtnode_t *node) {
148 if (node != NULL) {
149 node_name(node, &name);
157 * Upper node is the parent of the root of the passed node's
158 * subtree. The passed node must not be NULL.
161 get_upper_node(dns_rbtnode_t *node) {
162 return node->uppernode;
166 dns__rbtnode_getdistance(dns_rbtnode_t *node) {
169 while (node != NULL) {
170 if (node->is_root) {
174 node = node->parent;
192 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, const dns_name_t *name);
195 unhash_node(dns_rbt_t *rbt, dns_rbtnode_t *node);
212 rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
214 rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp);
217 addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
228 printnodename(dns_rbtnode_t *node, bool quoted, FILE *f);
234 dns__rbtnode_namelen(dns_rbtnode_t *node) {
238 REQUIRE(DNS_RBTNODE_VALID(node));
243 if (node != NULL) {
244 node_name(node, ¤t);
251 node = get_upper_node(node);
258 dns__rbtnode_getsize(dns_rbtnode_t *node) {
259 REQUIRE(DNS_RBTNODE_VALID(node));
261 return NODE_SIZE(node);
372 move_chain_to_last(dns_rbtnodechain_t *chain, dns_rbtnode_t *node) {
376 * as long as the rightmost node has a down pointer.
378 while (node->right != NULL) {
379 node = node->right;
382 if (node->down == NULL) {
386 ADD_LEVEL(chain, node);
387 node = node->down;
390 chain->end = node;
511 * name at the current node. If the name at
512 * the current node is shorter, that means the
514 * name at the current node is longer, that means
550 * node, so the current node must be adjusted
583 * current node.
597 * Fix pointers that were to the current node.
660 * The current node has no data,
700 * Find the node for "name" in the tree of trees.
704 dns_rbtnode_t **node, dns_rbtnodechain_t *chain,
720 REQUIRE(node != NULL && *node == NULL);
772 * continue rather) finding the stop-node of the search
785 * node. We try to find a matching node using
787 * here: (a) we locate the matching node, (b) we
788 * find a node to which the current node has a
877 * the right node, the next call to
918 * the current node's name length, then follow the
924 * Whack off the current node's common parts
934 *node = current;
953 * are traversed. If this is a special node,
974 * Treat this node as if it
989 * entire name at this node is not common
1004 * and either the node has data or an empty node is ok, return
1023 *node = current;
1026 *node = NULL;
1032 if (*node != NULL) {
1035 * Unwind the chain to the partial match node
1036 * to set level_matches to the level above the node,
1045 while (chain->levels[chain->level_matches] != *node) {
1073 * DNS_RBTFIND_EMPTYDATA was set and the node had no
1114 * Point current to the node that stopped
1118 * added to the algorithm, the stop node of a
1160 * present, but the stop node could be either
1164 * If the stop node is less, it is not
1166 * node has a down pointer, then the real
1169 * Move down levels until the rightmost node
1172 * When the stop node is greater, it is
1196 * case. The stop node is the
1225 ENSURE(*node == NULL || DNS_RBTNODE_VALID(*node));
1231 * Remove a node from the tree of trees.
1236 * of "b.c" caused the node "a.b.c" to be split, pushing "a" to its own level,
1245 * deleted node still exists. The first case of this is obvious; take
1257 * Finally, for reference, note that the original routine that did node
1267 dns_rbt_deletenode(dns_rbt_t *rbt, dns_rbtnode_t *node, bool recurse) {
1271 REQUIRE(DNS_RBTNODE_VALID(node));
1274 if (node->down != NULL) {
1276 node->down->parent = NULL;
1277 deletetreeflat(rbt, 0, true, &node->down);
1279 if (node->data != NULL && rbt->data_deleter != NULL) {
1280 rbt->data_deleter(node->data, rbt->deleter_arg);
1282 node->data = NULL;
1285 * Since there is at least one node below this one and
1287 * complete. The down node from this node might be all
1298 * Note the node that points to the level of the node
1299 * that is being deleted. If the deleted node is the
1302 parent = get_upper_node(node);
1305 * This node now has no down pointer, so now it needs
1308 deletefromlevel(node, parent == NULL ? &rbt->root : &parent->down);
1310 if (node->data != NULL && rbt->data_deleter != NULL) {
1311 rbt->data_deleter(node->data, rbt->deleter_arg);
1314 unhash_node(rbt, node);
1316 node->magic = 0;
1318 isc_refcount_destroy(&node->references);
1320 freenode(rbt, &node);
1329 dns_rbt_namefromnode(dns_rbtnode_t *node, dns_name_t *name) {
1330 REQUIRE(DNS_RBTNODE_VALID(node));
1334 node_name(node, name);
1338 dns_rbt_fullnamefromnode(dns_rbtnode_t *node, dns_name_t *name) {
1342 REQUIRE(DNS_RBTNODE_VALID(node));
1350 INSIST(node != NULL);
1352 node_name(node, ¤t);
1359 node = get_upper_node(node);
1366 dns_rbt_formatnodename(dns_rbtnode_t *node, char *printname,
1372 REQUIRE(DNS_RBTNODE_VALID(node));
1376 result = dns_rbt_fullnamefromnode(node, name);
1389 dns_rbtnode_t *node = NULL;
1401 * Allocate space for the node structure, the name, and the offsets.
1404 node = isc_mem_get(mctx, nodelen);
1405 *node = (dns_rbtnode_t){
1410 ISC_LINK_INIT(node, deadlink);
1412 isc_refcount_init(&node->references, 0);
1416 * stored value in the node easy: the length of the name, the number
1428 node->oldnamelen = node->namelen = region.length;
1429 OLDOFFSETLEN(node) = node->offsetlen = labels;
1430 node->absolute = name->attributes.absolute;
1432 memmove(NAME(node), region.base, region.length);
1433 memmove(OFFSETS(node), name->offsets, labels);
1436 node->magic = DNS_RBTNODE_MAGIC;
1438 return node;
1442 * Add a node to the hash table
1445 hash_add_node(dns_rbt_t *rbt, dns_rbtnode_t *node, const dns_name_t *name) {
1450 node->hashval = dns_name_hash(name);
1452 hash = isc_hash_bits32(node->hashval, rbt->hashbits[rbt->hindex]);
1453 node->hashnext = rbt->hashtable[rbt->hindex][hash];
1455 rbt->hashtable[rbt->hindex][hash] = node;
1530 dns_rbtnode_t *node = NULL;
1533 /* Find first non-empty node */
1545 /* Move the first non-empty node from old hashtable to new hashtable */
1546 for (node = oldtable[rbt->hiter]; node != NULL; node = nextnode) {
1547 uint32_t hash = isc_hash_bits32(node->hashval,
1549 nextnode = node->hashnext;
1550 node->hashnext = newtable[hash];
1551 newtable[hash] = node;
1582 * Add a node to the hash table. Rehash the hashtable if the node count
1586 hash_node(dns_rbt_t *rbt, dns_rbtnode_t *node, const dns_name_t *name) {
1587 REQUIRE(DNS_RBTNODE_VALID(node));
1597 hash_add_node(rbt, node, name);
1601 * Remove a node from the hash table
1612 * The node could be either in:
1614 * b) current table: the node has been already moved, or
1615 * c) other table: the node hasn't been moved yet.
1640 /* We haven't found any matching node, this should not be possible. */
1645 rotate_left(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
1648 REQUIRE(DNS_RBTNODE_VALID(node));
1651 child = node->right;
1654 node->right = child->left;
1656 child->left->parent = node;
1658 child->left = node;
1660 child->parent = node->parent;
1662 if (node->is_root) {
1665 node->is_root = 0;
1667 if (node->parent->left == node) {
1668 node->parent->left = child;
1670 node->parent->right = child;
1674 node->parent = child;
1678 rotate_right(dns_rbtnode_t *node, dns_rbtnode_t **rootp) {
1681 REQUIRE(DNS_RBTNODE_VALID(node));
1684 child = node->left;
1687 node->left = child->right;
1689 child->right->parent = node;
1691 child->right = node;
1693 child->parent = node->parent;
1695 if (node->is_root) {
1698 node->is_root = 0;
1700 if (node->parent->left == node) {
1701 node->parent->left = child;
1703 node->parent->right = child;
1707 node->parent = child;
1715 addonlevel(dns_rbtnode_t *node, dns_rbtnode_t *current, int order,
1722 REQUIRE(DNS_RBTNODE_VALID(node) && node->left == NULL &&
1723 node->right == NULL);
1729 * First node of a level.
1731 node->color = BLACK;
1732 node->is_root = 1;
1733 node->parent = current;
1734 *rootp = node;
1742 node_name(node, &add_name);
1749 current->left = node;
1752 current->right = node;
1755 INSIST(node->parent == NULL);
1756 node->parent = current;
1758 node->color = RED;
1760 while (node != root && IS_RED(node->parent)) {
1767 parent = node->parent;
1776 node = grandparent;
1778 if (node == parent->right) {
1780 node = parent;
1781 parent = node->parent;
1794 node = grandparent;
1796 if (node == parent->left) {
1798 node = parent;
1799 parent = node->parent;
1847 * This node has one child, on the right.
1853 * This node has one child, on the left.
1861 * This node has two children, so it cannot be directly
1885 * the tree, the pointer to the node would be unchanged.
1890 * node to be deleted. Save its existing tree pointer
1921 * Now relink the node to be deleted into the
1938 * Original location of successor node has no left.
1946 * Remove the node by removing the links from its parent.
2059 dns_rbtnode_t *node = *nodep;
2062 isc_mem_put(rbt->mctx, node, NODE_SIZE(node));
2074 * If there is a left, right or down node, walk into it
2078 dns_rbtnode_t *node = root;
2080 node->left = NULL;
2082 dns_rbtnode_t *node = root;
2084 node->right = NULL;
2086 dns_rbtnode_t *node = root;
2088 node->down = NULL;
2094 dns_rbtnode_t *node = root;
2097 if (rbt->data_deleter != NULL && node->data != NULL) {
2098 rbt->data_deleter(node->data, rbt->deleter_arg);
2101 unhash_node(rbt, node);
2108 node->magic = 0;
2110 freenode(rbt, &node);
2121 getheight_helper(dns_rbtnode_t *node) {
2125 if (node == NULL) {
2129 dl = getheight_helper(node->left);
2130 dr = getheight_helper(node->right);
2133 down_height = getheight_helper(node->down);
2144 check_properties_helper(dns_rbtnode_t *node) {
2145 if (node == NULL) {
2149 if (IS_RED(node)) {
2151 if (node->is_root) {
2156 if (IS_RED(node->left) || IS_RED(node->right)) {
2161 if ((node->down != NULL) && (!node->down->is_root)) {
2165 if (node->is_root) {
2166 if ((node->parent != NULL) && (node->parent->down != node)) {
2170 if (get_upper_node(node) != node->parent) {
2175 /* If node is assigned to the down_ pointer of its parent, it is
2178 if (((!node->parent) || (node->parent->down == node)) &&
2179 (!node->is_root))
2184 /* Repeat tests with this node's children. */
2185 return check_properties_helper(node->left) &&
2186 check_properties_helper(node->right) &&
2187 check_properties_helper(node->down);
2191 check_black_distance_helper(dns_rbtnode_t *node, size_t *distance) {
2194 if (node == NULL) {
2199 if (!check_black_distance_helper(node->left, &dl)) {
2203 if (!check_black_distance_helper(node->right, &dr)) {
2207 if (!check_black_distance_helper(node->down, &dd)) {
2211 /* Left and right side black node counts must match. */
2216 if (IS_BLACK(node)) {
2233 /* Path from a given node to all its leaves must contain the
2255 fprintf(f, "Null node\n");
2265 fprintf(f, "node lock address = %u\n", n->locknum);
2275 printnodename(dns_rbtnode_t *node, bool quoted, FILE *f) {
2281 r.length = node->namelen;
2282 r.base = NAME(node);
2357 print_dot_helper(dns_rbtnode_t *node, unsigned int *nodecount,
2361 if (node == NULL) {
2365 l = print_dot_helper(node->left, nodecount, show_pointers, f);
2366 r = print_dot_helper(node->right, nodecount, show_pointers, f);
2367 d = print_dot_helper(node->down, nodecount, show_pointers, f);
2371 fprintf(f, "node%u[label = \"<f0> |<f1> ", *nodecount);
2372 printnodename(node, false, f);
2376 fprintf(f, "|<f3> n=%p|<f4> p=%p", node, node->parent);
2381 if (IS_RED(node)) {
2390 if (node->is_root) {
2394 if (node->data == NULL) {
2400 if (node->left != NULL) {
2401 fprintf(f, "\"node%u\":f0 -> \"node%u\":f1;\n", *nodecount, l);
2404 if (node->down != NULL) {
2405 fprintf(f, "\"node%u\":f1 -> \"node%u\":f1 [penwidth=5];\n",
2408 if (node->right != NULL) {
2409 fprintf(f, "\"node%u\":f2 -> \"node%u\":f1;\n", *nodecount, r);
2422 fprintf(f, "node [shape = record,height=.1];\n");
2448 dns_name_t *origin, dns_rbtnode_t **node) {
2453 SET_IF_NOT_NULL(node, chain->end);
2506 * previous node, at least for this level.
2520 * node, at least for this level.
2535 * Found a predecessor node in this level. It might not
2542 * and repeat as long as the rightmost node has
2573 * level; the node that points to this tree is the
2651 * never find a node in the topmost level. This is
2654 * to that node, down at the second level or below.
2739 * If there is a level below this node, the next node is the
2740 * leftmost node of the next level.
2765 * successor is the node that has that left link. In
2794 * way that caused node splits
2796 * be pointing to a root node
2802 * really reached the root node
2831 * If we determine that the current node is the
2842 * never find a node in the topmost level. This is
2845 * to that node, down at the second level or below.