Home
last modified time | relevance | path

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

/linux/kernel/bpf/
H A Dlpm_trie.c168 size_t __longest_prefix_match(const struct lpm_trie *trie, in __longest_prefix_match() argument
183 if (trie->data_size >= 8) { in __longest_prefix_match()
196 while (trie->data_size >= i + 4) { in __longest_prefix_match()
208 if (trie->data_size >= i + 2) { in __longest_prefix_match()
220 if (trie->data_size >= i + 1) { in __longest_prefix_match()
230 static size_t longest_prefix_match(const struct lpm_trie *trie, in longest_prefix_match() argument
234 return __longest_prefix_match(trie, node, key); in longest_prefix_match()
240 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_lookup_elem() local
244 if (key->prefixlen > trie->max_prefixlen) in trie_lookup_elem()
249 for (node = rcu_dereference_check(trie->root, rcu_read_lock_bh_held()); in trie_lookup_elem()
[all …]
/linux/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/net/ipv4/
H A Dfib_trie.c167 struct trie { struct
174 static struct key_vector *resize(struct trie *t, struct key_vector *tn); argument
502 static struct key_vector *replace(struct trie *t, in replace()
531 static struct key_vector *inflate(struct trie *t, in inflate()
627 static struct key_vector *halve(struct trie *t, in halve()
682 static struct key_vector *collapse(struct trie *t, in collapse()
842 static struct key_vector *resize(struct trie *t, struct key_vector *tn) in resize()
930 static struct key_vector *fib_find_node(struct trie *t, in fib_find_node()
1017 struct trie *t; in fib_find_matching_alias()
1023 t = (struct trie *)tb->tb_data; in fib_find_matching_alias()
[all …]
/linux/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/fs/unicode/
H A 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/Documentation/networking/devlink/
H A Ddevlink-dpipe.rst34 Level Path Compression trie (LPC-trie) in hardware.