Lines Matching refs:node
18 /* Intermediate node */
48 * lead to more nodes containing more specific matches. Each node also stores
58 * As the trie is empty initially, the new node (1) will be places as root
59 * node, denoted as (R) in the example below. As there are no other node, both
69 * Next, let's add a new node (2) matching 192.168.0.0/24. As there is already
70 * a node with the same data and a smaller prefix (ie, a less specific one),
71 * node (2) will become a child of (1). In child index depends on the next bit
89 * The child[1] slot of (1) could be filled with another node which has bit #17
107 * Let's add another node (4) to the game for 192.168.1.0/24. In order to place
108 * it, node (1) is looked at first, and because (4) of the semantics laid out
110 * However, that slot is already allocated, so a new node is needed in between.
111 * That node does not have a value attached to it and it will never be
139 * An intermediate node will be turned into a 'real' node on demand. In the
145 * The lookup starts at the root node. If the current node matches and if there
147 * downwards. The last node in the traversal that is a non-intermediate one is
159 * @node: The node to operate on
160 * @key: The key to compare to @node
162 * Determine the longest prefix of @node that matches the bits in @key.
165 const struct lpm_trie_node *node,
168 u32 limit = min(node->prefixlen, key->prefixlen);
180 u64 diff = be64_to_cpu(*(__be64 *)node->data ^
193 u32 diff = be32_to_cpu(*(__be32 *)&node->data[i] ^
205 u16 diff = be16_to_cpu(*(__be16 *)&node->data[i] ^
217 prefixlen += 8 - fls(node->data[i] ^ key->data[i]);
230 struct lpm_trie_node *node, *found = NULL;
236 /* Start walking the trie from the root node ... */
238 for (node = rcu_dereference(trie->root); node;) {
242 /* Determine the longest prefix of @node that matches @key.
246 matchlen = longest_prefix_match(trie, node, key);
248 found = node;
253 * length of @node, bail out and return the node we have seen
256 if (matchlen < node->prefixlen)
259 /* Consider this node as return candidate unless it is an
262 if (!(node->flags & LPM_TREE_NODE_FLAG_IM))
263 found = node;
265 /* If the node match is fully satisfied, let's see if we can
269 next_bit = extract_bit(key->data, node->prefixlen);
270 node = rcu_dereference(node->child[next_bit]);
282 struct lpm_trie_node *node;
288 node = kmalloc_node(size, GFP_ATOMIC | __GFP_NOWARN,
290 if (!node)
293 node->flags = 0;
296 memcpy(node->data + trie->data_size, value,
299 return node;
307 struct lpm_trie_node *node, *im_node = NULL, *new_node = NULL;
323 /* Allocate and fill a new node */
343 /* Now find a slot to attach the new node. To do that, walk the tree
344 * from the root and match as many bits as possible for each node until
346 * an intermediate node.
350 while ((node = rcu_dereference_protected(*slot,
352 matchlen = longest_prefix_match(trie, node, key);
354 if (node->prefixlen != matchlen ||
355 node->prefixlen == key->prefixlen ||
356 node->prefixlen == trie->max_prefixlen)
359 next_bit = extract_bit(key->data, node->prefixlen);
360 slot = &node->child[next_bit];
366 if (!node) {
374 if (node->prefixlen == matchlen) {
375 new_node->child[0] = node->child[0];
376 new_node->child[1] = node->child[1];
378 if (!(node->flags & LPM_TREE_NODE_FLAG_IM))
382 kfree_rcu(node, rcu);
387 /* If the new node matches the prefix completely, it must be inserted
388 * as an ancestor. Simply insert it between @node and *@slot.
391 next_bit = extract_bit(node->data, matchlen);
392 rcu_assign_pointer(new_node->child[next_bit], node);
405 memcpy(im_node->data, node->data, trie->data_size);
409 rcu_assign_pointer(im_node->child[0], node);
413 rcu_assign_pointer(im_node->child[1], node);
416 /* Finally, assign the intermediate node to the determined spot */
439 struct lpm_trie_node *node, *parent;
451 * track of the path we traverse. We will need to know the node
452 * we wish to delete, and the slot that points to the node we want
459 while ((node = rcu_dereference_protected(
461 matchlen = longest_prefix_match(trie, node, key);
463 if (node->prefixlen != matchlen ||
464 node->prefixlen == key->prefixlen)
467 parent = node;
469 next_bit = extract_bit(key->data, node->prefixlen);
470 trim = &node->child[next_bit];
473 if (!node || node->prefixlen != key->prefixlen ||
474 node->prefixlen != matchlen ||
475 (node->flags & LPM_TREE_NODE_FLAG_IM)) {
482 /* If the node we are removing has two children, simply mark it
485 if (rcu_access_pointer(node->child[0]) &&
486 rcu_access_pointer(node->child[1])) {
487 node->flags |= LPM_TREE_NODE_FLAG_IM;
491 /* If the parent of the node we are about to delete is an intermediate
492 * node, and the deleted node doesn't have any children, we can delete
499 !node->child[0] && !node->child[1]) {
500 if (node == rcu_access_pointer(parent->child[0]))
507 kfree_rcu(node, rcu);
511 /* The node we are removing has either zero or one child. If there
512 * is a child, move it into the removed node's slot then delete
513 * the node. Otherwise just clear the slot and delete the node.
515 if (node->child[0])
516 rcu_assign_pointer(*trim, rcu_access_pointer(node->child[0]));
517 else if (node->child[1])
518 rcu_assign_pointer(*trim, rcu_access_pointer(node->child[1]));
521 kfree_rcu(node, rcu);
593 struct lpm_trie_node *node;
595 /* Always start at the root and walk down to a node that has no
596 * children. Then free that node, nullify its reference in the parent
604 node = rcu_dereference_protected(*slot, 1);
605 if (!node)
608 if (rcu_access_pointer(node->child[0])) {
609 slot = &node->child[0];
613 if (rcu_access_pointer(node->child[1])) {
614 slot = &node->child[1];
618 kfree(node);
630 struct lpm_trie_node *node, *next_node = NULL, *parent, *search_root;
638 /* The get_next_key follows postorder. For the 4 node example in
654 /* For invalid key, find the leftmost node in the trie */
664 /* Try to find the exact node for the given key */
665 for (node = search_root; node;) {
666 node_stack[++stack_ptr] = node;
667 matchlen = longest_prefix_match(trie, node, key);
668 if (node->prefixlen != matchlen ||
669 node->prefixlen == key->prefixlen)
672 next_bit = extract_bit(key->data, node->prefixlen);
673 node = rcu_dereference(node->child[next_bit]);
675 if (!node || node->prefixlen != key->prefixlen ||
676 (node->flags & LPM_TREE_NODE_FLAG_IM))
679 /* The node with the exactly-matching key has been found,
680 * find the first node in postorder after the matched node.
682 node = node_stack[stack_ptr];
685 if (rcu_dereference(parent->child[0]) == node) {
695 node = parent;
704 /* Find the leftmost non-intermediate node, all intermediate nodes
707 for (node = search_root; node;) {
708 if (node->flags & LPM_TREE_NODE_FLAG_IM) {
709 node = rcu_dereference(node->child[0]);
711 next_node = node;
712 node = rcu_dereference(node->child[0]);
713 if (!node)
714 node = rcu_dereference(next_node->child[1]);