Home
last modified time | relevance | path

Searched refs:trie (Results 1 – 5 of 5) sorted by relevance

/Linux-v4.19/kernel/bpf/
Dlpm_trie.c167 static size_t longest_prefix_match(const struct lpm_trie *trie, in longest_prefix_match() argument
174 for (i = 0; i < trie->data_size; i++) { in longest_prefix_match()
193 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_lookup_elem() local
199 for (node = rcu_dereference(trie->root); node;) { in trie_lookup_elem()
207 matchlen = longest_prefix_match(trie, node, key); in trie_lookup_elem()
208 if (matchlen == trie->max_prefixlen) { in trie_lookup_elem()
237 return found->data + trie->data_size; in trie_lookup_elem()
240 static struct lpm_trie_node *lpm_trie_node_alloc(const struct lpm_trie *trie, in lpm_trie_node_alloc() argument
244 size_t size = sizeof(struct lpm_trie_node) + trie->data_size; in lpm_trie_node_alloc()
247 size += trie->map.value_size; in lpm_trie_node_alloc()
[all …]
/Linux-v4.19/Documentation/networking/
Dfib_trie.txt1 LC-trie implementation notes.
10 trie node or tnode
36 the trie is kept level balanced moving, under certain conditions, the
64 straightforward trie lookup.
67 Inserts a new leaf node in the trie. This is bit more complicated than
69 level compression algorithm on part of the trie.
75 The key function for the dynamic trie after any change in the trie
76 it is run to optimize and reorganize. It will walk the trie upwards
98 This walks the full trie (using nextleaf()) and searches for empty
104 entire trie for each prefix length. In comparison, fib_hash is organized
[all …]
D00-INDEX80 - Level Compressed Trie (LC-trie) notes: a structure for routing.
/Linux-v4.19/net/ipv4/
Dfib_trie.c178 struct trie { struct
185 static struct key_vector *resize(struct trie *t, struct key_vector *tn); argument
513 static struct key_vector *replace(struct trie *t, in replace()
542 static struct key_vector *inflate(struct trie *t, in inflate()
638 static struct key_vector *halve(struct trie *t, in halve()
693 static struct key_vector *collapse(struct trie *t, in collapse()
853 static struct key_vector *resize(struct trie *t, struct key_vector *tn) in resize()
941 static struct key_vector *fib_find_node(struct trie *t, in fib_find_node()
1012 static void trie_rebalance(struct trie *t, struct key_vector *tn) in trie_rebalance()
1018 static int fib_insert_node(struct trie *t, struct key_vector *tp, in fib_insert_node()
[all …]
/Linux-v4.19/Documentation/RCU/
DRTFP.txt159 Robert Olsson described an RCU-protected trie-hash combination
1539 ,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"
1545 RCU-protected dynamic trie-hash combination.
1796 ,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"
1804 RCU-protected dynamic trie-hash combination.