Lines Matching refs:node
165 const struct lpm_trie_node *node, in longest_prefix_match() argument
168 u32 limit = min(node->prefixlen, key->prefixlen); in longest_prefix_match()
180 u64 diff = be64_to_cpu(*(__be64 *)node->data ^ in longest_prefix_match()
193 u32 diff = be32_to_cpu(*(__be32 *)&node->data[i] ^ in longest_prefix_match()
205 u16 diff = be16_to_cpu(*(__be16 *)&node->data[i] ^ in longest_prefix_match()
217 prefixlen += 8 - fls(node->data[i] ^ key->data[i]); in longest_prefix_match()
230 struct lpm_trie_node *node, *found = NULL; in trie_lookup_elem() local
238 for (node = rcu_dereference(trie->root); node;) { in trie_lookup_elem()
246 matchlen = longest_prefix_match(trie, node, key); in trie_lookup_elem()
248 found = node; in trie_lookup_elem()
256 if (matchlen < node->prefixlen) in trie_lookup_elem()
262 if (!(node->flags & LPM_TREE_NODE_FLAG_IM)) in trie_lookup_elem()
263 found = node; in trie_lookup_elem()
269 next_bit = extract_bit(key->data, node->prefixlen); in trie_lookup_elem()
270 node = rcu_dereference(node->child[next_bit]); in trie_lookup_elem()
282 struct lpm_trie_node *node; in lpm_trie_node_alloc() local
288 node = kmalloc_node(size, GFP_ATOMIC | __GFP_NOWARN, in lpm_trie_node_alloc()
290 if (!node) in lpm_trie_node_alloc()
293 node->flags = 0; in lpm_trie_node_alloc()
296 memcpy(node->data + trie->data_size, value, in lpm_trie_node_alloc()
299 return node; in lpm_trie_node_alloc()
307 struct lpm_trie_node *node, *im_node = NULL, *new_node = NULL; in trie_update_elem() local
350 while ((node = rcu_dereference_protected(*slot, in trie_update_elem()
352 matchlen = longest_prefix_match(trie, node, key); in trie_update_elem()
354 if (node->prefixlen != matchlen || in trie_update_elem()
355 node->prefixlen == key->prefixlen || in trie_update_elem()
356 node->prefixlen == trie->max_prefixlen) in trie_update_elem()
359 next_bit = extract_bit(key->data, node->prefixlen); in trie_update_elem()
360 slot = &node->child[next_bit]; in trie_update_elem()
366 if (!node) { in trie_update_elem()
374 if (node->prefixlen == matchlen) { in trie_update_elem()
375 new_node->child[0] = node->child[0]; in trie_update_elem()
376 new_node->child[1] = node->child[1]; in trie_update_elem()
378 if (!(node->flags & LPM_TREE_NODE_FLAG_IM)) in trie_update_elem()
382 kfree_rcu(node, rcu); in trie_update_elem()
391 next_bit = extract_bit(node->data, matchlen); in trie_update_elem()
392 rcu_assign_pointer(new_node->child[next_bit], node); in trie_update_elem()
405 memcpy(im_node->data, node->data, trie->data_size); in trie_update_elem()
409 rcu_assign_pointer(im_node->child[0], node); in trie_update_elem()
413 rcu_assign_pointer(im_node->child[1], node); in trie_update_elem()
439 struct lpm_trie_node *node, *parent; in trie_delete_elem() local
459 while ((node = rcu_dereference_protected( in trie_delete_elem()
461 matchlen = longest_prefix_match(trie, node, key); in trie_delete_elem()
463 if (node->prefixlen != matchlen || in trie_delete_elem()
464 node->prefixlen == key->prefixlen) in trie_delete_elem()
467 parent = node; in trie_delete_elem()
469 next_bit = extract_bit(key->data, node->prefixlen); in trie_delete_elem()
470 trim = &node->child[next_bit]; in trie_delete_elem()
473 if (!node || node->prefixlen != key->prefixlen || in trie_delete_elem()
474 node->prefixlen != matchlen || in trie_delete_elem()
475 (node->flags & LPM_TREE_NODE_FLAG_IM)) { in trie_delete_elem()
485 if (rcu_access_pointer(node->child[0]) && in trie_delete_elem()
486 rcu_access_pointer(node->child[1])) { in trie_delete_elem()
487 node->flags |= LPM_TREE_NODE_FLAG_IM; in trie_delete_elem()
499 !node->child[0] && !node->child[1]) { in trie_delete_elem()
500 if (node == rcu_access_pointer(parent->child[0])) in trie_delete_elem()
507 kfree_rcu(node, rcu); in trie_delete_elem()
515 if (node->child[0]) in trie_delete_elem()
516 rcu_assign_pointer(*trim, rcu_access_pointer(node->child[0])); in trie_delete_elem()
517 else if (node->child[1]) in trie_delete_elem()
518 rcu_assign_pointer(*trim, rcu_access_pointer(node->child[1])); in trie_delete_elem()
521 kfree_rcu(node, rcu); in trie_delete_elem()
593 struct lpm_trie_node *node; in trie_free() local
604 node = rcu_dereference_protected(*slot, 1); in trie_free()
605 if (!node) in trie_free()
608 if (rcu_access_pointer(node->child[0])) { in trie_free()
609 slot = &node->child[0]; in trie_free()
613 if (rcu_access_pointer(node->child[1])) { in trie_free()
614 slot = &node->child[1]; in trie_free()
618 kfree(node); in trie_free()
630 struct lpm_trie_node *node, *next_node = NULL, *parent, *search_root; in trie_get_next_key() local
665 for (node = search_root; node;) { in trie_get_next_key()
666 node_stack[++stack_ptr] = node; in trie_get_next_key()
667 matchlen = longest_prefix_match(trie, node, key); in trie_get_next_key()
668 if (node->prefixlen != matchlen || in trie_get_next_key()
669 node->prefixlen == key->prefixlen) in trie_get_next_key()
672 next_bit = extract_bit(key->data, node->prefixlen); in trie_get_next_key()
673 node = rcu_dereference(node->child[next_bit]); in trie_get_next_key()
675 if (!node || node->prefixlen != key->prefixlen || in trie_get_next_key()
676 (node->flags & LPM_TREE_NODE_FLAG_IM)) in trie_get_next_key()
682 node = node_stack[stack_ptr]; in trie_get_next_key()
685 if (rcu_dereference(parent->child[0]) == node) { in trie_get_next_key()
695 node = parent; in trie_get_next_key()
707 for (node = search_root; node;) { in trie_get_next_key()
708 if (node->flags & LPM_TREE_NODE_FLAG_IM) { in trie_get_next_key()
709 node = rcu_dereference(node->child[0]); in trie_get_next_key()
711 next_node = node; in trie_get_next_key()
712 node = rcu_dereference(node->child[0]); in trie_get_next_key()
713 if (!node) in trie_get_next_key()
714 node = rcu_dereference(next_node->child[1]); in trie_get_next_key()