Home
last modified time | relevance | path

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

/linux-6.15/kernel/bpf/
H A Dlpm_trie.c315 if (trie->n_entries == trie->map.max_entries) in trie_check_add_elem()
317 trie->n_entries++; in trie_check_add_elem()
360 slot = &trie->root; in trie_update_elem()
425 trie->n_entries--; in trie_update_elem()
482 trim = &trie->root; in trie_delete_elem()
505 trie->n_entries--; in trie_delete_elem()
588 trie = bpf_map_area_alloc(sizeof(*trie), NUMA_NO_NODE); in trie_alloc()
589 if (!trie) in trie_alloc()
596 trie->max_prefixlen = trie->data_size * 8; in trie_alloc()
606 return &trie->map; in trie_alloc()
[all …]
/linux-6.15/fs/unicode/
H A Dutf8-norm.c318 if (*trie & NEXTBYTE) { in utf8nlookup()
329 offset = trie[offlen]; in utf8nlookup()
332 offset |= trie[offlen]; in utf8nlookup()
334 trie += offset; in utf8nlookup()
337 node = (*trie & TRIENODE); in utf8nlookup()
338 trie++; in utf8nlookup()
347 node = (*trie & LEFTNODE); in utf8nlookup()
348 trie += offlen + 1; in utf8nlookup()
355 trie++; in utf8nlookup()
365 if (LEAF_CCC(trie) == DECOMPOSE && LEAF_STR(trie)[0] == HANGUL) in utf8nlookup()
[all …]
H A Dmkutf8data.c2709 utf8trie_t *trie; in utf8nlookup() local
2723 if (*trie & NEXTBYTE) { in utf8nlookup()
2734 offset = trie[offlen]; in utf8nlookup()
2737 offset |= trie[offlen]; in utf8nlookup()
2739 trie += offset; in utf8nlookup()
2742 node = (*trie & TRIENODE); in utf8nlookup()
2743 trie++; in utf8nlookup()
2753 trie += offlen + 1; in utf8nlookup()
2760 trie++; in utf8nlookup()
2770 if (LEAF_CCC(trie) == DECOMPOSE && LEAF_STR(trie)[0] == HANGUL) in utf8nlookup()
[all …]
/linux-6.15/Documentation/networking/
H A 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.15/net/ipv4/
H A Dfib_trie.c1197 struct trie *t = (struct trie *)tb->tb_data; in fib_table_insert()
1423 struct trie *t = (struct trie *) tb->tb_data; in fib_table_lookup()
1691 struct trie *t = (struct trie *) tb->tb_data; in fib_table_delete()
1816 struct trie *t = (struct trie *)tb->tb_data; in fib_trie_free()
1933 struct trie *t = (struct trie *)tb->tb_data; in fib_table_flush_external()
2002 struct trie *t = (struct trie *)tb->tb_data; in fib_table_flush()
2092 struct trie *t = (struct trie *)tb->tb_data; in __fib_info_notify_update()
2187 struct trie *t = (struct trie *)tb->tb_data; in fib_table_notify()
2228 struct trie *t = (struct trie *)tb->tb_data; in __trie_free_rcu()
2331 struct trie *t = (struct trie *)tb->tb_data; in fib_table_dump()
[all …]
/linux-6.15/drivers/net/wireguard/
H A 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.15/Documentation/bpf/
H A Dmap_lpm_trie.rst13 Internally, data is stored in an unbalanced trie of nodes that uses
26 The value type stored in the LPM trie can be any user defined type.
96 A userspace program can iterate through the entries in an LPM trie using
101 ``-ENOENT`` if ``cur_key`` is the last key in the trie, or negative
104 ``bpf_map_get_next_key()`` will iterate through the LPM trie elements
112 of LPM trie usage from userspace. The code snippets below demonstrate
118 The following BPF code snippet shows how to declare a new LPM trie for IPv4
157 LPM trie:
171 of an LPM trie:
/linux-6.15/Documentation/networking/devlink/
H A Ddevlink-dpipe.rst34 Level Path Compression trie (LPC-trie) in hardware.
/linux-6.15/Documentation/RCU/
H A 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.