Home
last modified time | relevance | path

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

/linux-6.1.9/kernel/bpf/
Dlpm_trie.c165 static size_t longest_prefix_match(const struct lpm_trie *trie, in longest_prefix_match() argument
180 if (trie->data_size >= 8) { in longest_prefix_match()
193 while (trie->data_size >= i + 4) { in longest_prefix_match()
205 if (trie->data_size >= i + 2) { in longest_prefix_match()
217 if (trie->data_size >= i + 1) { in longest_prefix_match()
230 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_lookup_elem() local
236 for (node = rcu_dereference_check(trie->root, rcu_read_lock_bh_held()); in trie_lookup_elem()
245 matchlen = longest_prefix_match(trie, node, key); in trie_lookup_elem()
246 if (matchlen == trie->max_prefixlen) { in trie_lookup_elem()
276 return found->data + trie->data_size; in trie_lookup_elem()
[all …]
/linux-6.1.9/fs/unicode/
Dutf8-norm.c306 utf8trie_t *trie = um->tables->utf8data + um->ntab[n]->offset; in utf8nlookup() local
317 offlen = (*trie & OFFLEN) >> OFFLEN_SHIFT; in utf8nlookup()
318 if (*trie & NEXTBYTE) { in utf8nlookup()
323 mask = 1 << (*trie & BITNUM); in utf8nlookup()
328 node = (*trie & RIGHTNODE); in utf8nlookup()
329 offset = trie[offlen]; in utf8nlookup()
332 offset |= trie[offlen]; in utf8nlookup()
334 trie += offset; in utf8nlookup()
335 } else if (*trie & RIGHTPATH) { in utf8nlookup()
337 node = (*trie & TRIENODE); 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-6.1.9/Documentation/networking/
Dfib_trie.rst4 LC-trie implementation notes
14 trie node or tnode
40 the trie is kept level balanced moving, under certain conditions, the
68 straightforward trie lookup.
71 Inserts a new leaf node in the trie. This is bit more complicated than
73 level compression algorithm on part of the trie.
79 The key function for the dynamic trie after any change in the trie
80 it is run to optimize and reorganize. It will walk the trie upwards
102 This walks the full trie (using nextleaf()) and searches for empty
108 entire trie for each prefix length. In comparison, fib_hash is organized
[all …]
/linux-6.1.9/net/ipv4/
Dfib_trie.c166 struct trie { struct
173 static struct key_vector *resize(struct trie *t, struct key_vector *tn); argument
507 static struct key_vector *replace(struct trie *t, in replace()
536 static struct key_vector *inflate(struct trie *t, in inflate()
632 static struct key_vector *halve(struct trie *t, in halve()
687 static struct key_vector *collapse(struct trie *t, in collapse()
847 static struct key_vector *resize(struct trie *t, struct key_vector *tn) in resize()
935 static struct key_vector *fib_find_node(struct trie *t, in fib_find_node()
1022 struct trie *t; in fib_find_matching_alias()
1028 t = (struct trie *)tb->tb_data; in fib_find_matching_alias()
[all …]
/linux-6.1.9/drivers/net/wireguard/
Dallowedips.c111 static struct allowedips_node *find_node(struct allowedips_node *trie, u8 bits, in find_node() argument
114 struct allowedips_node *node = trie, *found = NULL; in find_node()
149 static bool node_placement(struct allowedips_node __rcu *trie, const u8 *key, in node_placement() argument
153 struct allowedips_node *node = rcu_dereference_protected(trie, lockdep_is_held(lock)); in node_placement()
181 static int add(struct allowedips_node __rcu **trie, u8 bits, const u8 *key, in add() argument
189 if (!rcu_access_pointer(*trie)) { in add()
196 connect_node(trie, 2, node); in add()
199 if (node_placement(*trie, key, cidr, bits, &node, lock)) { in add()
213 down = rcu_dereference_protected(*trie, lockdep_is_held(lock)); in add()
228 connect_node(trie, 2, newnode); in add()
[all …]
/linux-6.1.9/Documentation/networking/devlink/
Ddevlink-dpipe.rst34 Level Path Compression trie (LPC-trie) in hardware.
/linux-6.1.9/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.