Lines Matching refs:node
21 /* Intermediate node */
51 * lead to more nodes containing more specific matches. Each node also stores
61 * As the trie is empty initially, the new node (1) will be places as root
62 * node, denoted as (R) in the example below. As there are no other node, both
72 * Next, let's add a new node (2) matching 192.168.0.0/24. As there is already
73 * a node with the same data and a smaller prefix (ie, a less specific one),
74 * node (2) will become a child of (1). In child index depends on the next bit
92 * The child[1] slot of (1) could be filled with another node which has bit #17
110 * Let's add another node (4) to the game for 192.168.1.0/24. In order to place
111 * it, node (1) is looked at first, and because (4) of the semantics laid out
113 * However, that slot is already allocated, so a new node is needed in between.
114 * That node does not have a value attached to it and it will never be
142 * An intermediate node will be turned into a 'real' node on demand. In the
148 * The lookup starts at the root node. If the current node matches and if there
150 * downwards. The last node in the traversal that is a non-intermediate one is
162 * @node: The node to operate on
163 * @key: The key to compare to @node
165 * Determine the longest prefix of @node that matches the bits in @key.
169 const struct lpm_trie_node *node,
172 u32 limit = min(node->prefixlen, key->prefixlen);
184 u64 diff = be64_to_cpu(*(__be64 *)node->data ^
197 u32 diff = be32_to_cpu(*(__be32 *)&node->data[i] ^
209 u16 diff = be16_to_cpu(*(__be16 *)&node->data[i] ^
221 prefixlen += 8 - fls(node->data[i] ^ key->data[i]);
231 const struct lpm_trie_node *node,
234 return __longest_prefix_match(trie, node, key);
241 struct lpm_trie_node *node, *found = NULL;
247 /* Start walking the trie from the root node ... */
249 for (node = rcu_dereference_check(trie->root, rcu_read_lock_bh_held());
250 node;) {
254 /* Determine the longest prefix of @node that matches @key.
258 matchlen = __longest_prefix_match(trie, node, key);
260 found = node;
265 * length of @node, bail out and return the node we have seen
268 if (matchlen < node->prefixlen)
271 /* Consider this node as return candidate unless it is an
274 if (!(node->flags & LPM_TREE_NODE_FLAG_IM))
275 found = node;
277 /* If the node match is fully satisfied, let's see if we can
281 next_bit = extract_bit(key->data, node->prefixlen);
282 node = rcu_dereference_check(node->child[next_bit],
295 struct lpm_trie_node *node;
297 node = bpf_mem_cache_alloc(&trie->ma);
299 if (!node)
302 node->flags = 0;
305 memcpy(node->data + trie->data_size, value,
308 return node;
326 struct lpm_trie_node *node, *im_node, *new_node;
341 /* Allocate and fill a new node */
355 /* Now find a slot to attach the new node. To do that, walk the tree
356 * from the root and match as many bits as possible for each node until
358 * an intermediate node.
362 while ((node = rcu_dereference(*slot))) {
363 matchlen = longest_prefix_match(trie, node, key);
365 if (node->prefixlen != matchlen ||
366 node->prefixlen == key->prefixlen)
369 next_bit = extract_bit(key->data, node->prefixlen);
370 slot = &node->child[next_bit];
376 if (!node) {
388 if (node->prefixlen == matchlen) {
389 if (!(node->flags & LPM_TREE_NODE_FLAG_IM)) {
400 new_node->child[0] = node->child[0];
401 new_node->child[1] = node->child[1];
404 free_node = node;
413 /* If the new node matches the prefix completely, it must be inserted
414 * as an ancestor. Simply insert it between @node and *@slot.
417 next_bit = extract_bit(node->data, matchlen);
418 rcu_assign_pointer(new_node->child[next_bit], node);
432 memcpy(im_node->data, node->data, trie->data_size);
436 rcu_assign_pointer(im_node->child[0], node);
440 rcu_assign_pointer(im_node->child[1], node);
443 /* Finally, assign the intermediate node to the determined slot */
463 struct lpm_trie_node *node, *parent;
477 * track of the path we traverse. We will need to know the node
478 * we wish to delete, and the slot that points to the node we want
485 while ((node = rcu_dereference(*trim))) {
486 matchlen = longest_prefix_match(trie, node, key);
488 if (node->prefixlen != matchlen ||
489 node->prefixlen == key->prefixlen)
492 parent = node;
494 next_bit = extract_bit(key->data, node->prefixlen);
495 trim = &node->child[next_bit];
498 if (!node || node->prefixlen != key->prefixlen ||
499 node->prefixlen != matchlen ||
500 (node->flags & LPM_TREE_NODE_FLAG_IM)) {
507 /* If the node we are removing has two children, simply mark it
510 if (rcu_access_pointer(node->child[0]) &&
511 rcu_access_pointer(node->child[1])) {
512 node->flags |= LPM_TREE_NODE_FLAG_IM;
516 /* If the parent of the node we are about to delete is an intermediate
517 * node, and the deleted node doesn't have any children, we can delete
524 !node->child[0] && !node->child[1]) {
525 if (node == rcu_access_pointer(parent->child[0]))
532 free_node = node;
536 /* The node we are removing has either zero or one child. If there
537 * is a child, move it into the removed node's slot then delete
538 * the node. Otherwise just clear the slot and delete the node.
540 if (node->child[0])
541 rcu_assign_pointer(*trim, rcu_access_pointer(node->child[0]));
542 else if (node->child[1])
543 rcu_assign_pointer(*trim, rcu_access_pointer(node->child[1]));
546 free_node = node;
617 struct lpm_trie_node *node;
619 /* Always start at the root and walk down to a node that has no
620 * children. Then free that node, nullify its reference in the parent
628 node = rcu_dereference_protected(*slot, 1);
629 if (!node)
632 if (rcu_access_pointer(node->child[0])) {
633 slot = &node->child[0];
637 if (rcu_access_pointer(node->child[1])) {
638 slot = &node->child[1];
643 * node without waiting for the extra RCU GP.
645 bpf_mem_cache_raw_free(node);
658 struct lpm_trie_node *node, *next_node = NULL, *parent, *search_root;
666 /* The get_next_key follows postorder. For the 4 node example in
682 /* For invalid key, find the leftmost node in the trie */
692 /* Try to find the exact node for the given key */
693 for (node = search_root; node;) {
694 node_stack[++stack_ptr] = node;
695 matchlen = longest_prefix_match(trie, node, key);
696 if (node->prefixlen != matchlen ||
697 node->prefixlen == key->prefixlen)
700 next_bit = extract_bit(key->data, node->prefixlen);
701 node = rcu_dereference(node->child[next_bit]);
703 if (!node || node->prefixlen != matchlen ||
704 (node->flags & LPM_TREE_NODE_FLAG_IM))
707 /* The node with the exactly-matching key has been found,
708 * find the first node in postorder after the matched node.
710 node = node_stack[stack_ptr];
713 if (rcu_dereference(parent->child[0]) == node) {
723 node = parent;
732 /* Find the leftmost non-intermediate node, all intermediate nodes
735 for (node = search_root; node;) {
736 if (node->flags & LPM_TREE_NODE_FLAG_IM) {
737 node = rcu_dereference(node->child[0]);
739 next_node = node;
740 node = rcu_dereference(node->child[0]);
741 if (!node)
742 node = rcu_dereference(next_node->child[1]);