Home
last modified time | relevance | path

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

/Linux-v5.4/kernel/bpf/
Dlpm_trie.c164 static size_t longest_prefix_match(const struct lpm_trie *trie, in longest_prefix_match() argument
179 if (trie->data_size >= 8) { in longest_prefix_match()
192 while (trie->data_size >= i + 4) { in longest_prefix_match()
204 if (trie->data_size >= i + 2) { in longest_prefix_match()
216 if (trie->data_size >= i + 1) { in longest_prefix_match()
229 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_lookup_elem() local
235 for (node = rcu_dereference(trie->root); node;) { in trie_lookup_elem()
243 matchlen = longest_prefix_match(trie, node, key); in trie_lookup_elem()
244 if (matchlen == trie->max_prefixlen) { in trie_lookup_elem()
273 return found->data + trie->data_size; in trie_lookup_elem()
[all …]
/Linux-v5.4/fs/unicode/
Dutf8-norm.c322 utf8trie_t *trie = NULL; in utf8nlookup() local
333 trie = utf8data + data->offset; in utf8nlookup()
336 offlen = (*trie & OFFLEN) >> OFFLEN_SHIFT; in utf8nlookup()
337 if (*trie & NEXTBYTE) { in utf8nlookup()
342 mask = 1 << (*trie & BITNUM); in utf8nlookup()
347 node = (*trie & RIGHTNODE); in utf8nlookup()
348 offset = trie[offlen]; in utf8nlookup()
351 offset |= trie[offlen]; in utf8nlookup()
353 trie += offset; in utf8nlookup()
354 } else if (*trie & RIGHTPATH) { in utf8nlookup()
[all …]
Dmkutf8data.c2709 utf8trie_t *trie; in utf8nlookup() local
2720 trie = utf8data + tree->index; in utf8nlookup()
2722 offlen = (*trie & OFFLEN) >> OFFLEN_SHIFT; in utf8nlookup()
2723 if (*trie & NEXTBYTE) { in utf8nlookup()
2728 mask = 1 << (*trie & BITNUM); in utf8nlookup()
2733 node = (*trie & RIGHTNODE); in utf8nlookup()
2734 offset = trie[offlen]; in utf8nlookup()
2737 offset |= trie[offlen]; in utf8nlookup()
2739 trie += offset; in utf8nlookup()
2740 } else if (*trie & RIGHTPATH) { in utf8nlookup()
[all …]
/Linux-v5.4/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 …]
/Linux-v5.4/net/ipv4/
Dfib_trie.c166 struct trie { struct
173 static struct key_vector *resize(struct trie *t, struct key_vector *tn); argument
509 static struct key_vector *replace(struct trie *t, in replace()
538 static struct key_vector *inflate(struct trie *t, in inflate()
634 static struct key_vector *halve(struct trie *t, in halve()
689 static struct key_vector *collapse(struct trie *t, in collapse()
849 static struct key_vector *resize(struct trie *t, struct key_vector *tn) in resize()
937 static struct key_vector *fib_find_node(struct trie *t, in fib_find_node()
1008 static void trie_rebalance(struct trie *t, struct key_vector *tn) in trie_rebalance()
1014 static int fib_insert_node(struct trie *t, struct key_vector *tp, in fib_insert_node()
[all …]
/Linux-v5.4/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.