/linux/kernel/bpf/ |
H A D | lpm_trie.c | 166 size_t __longest_prefix_match(const struct lpm_trie *trie, in __longest_prefix_match() argument 181 if (trie->data_size >= 8) { in __longest_prefix_match() 194 while (trie->data_size >= i + 4) { in __longest_prefix_match() 206 if (trie->data_size >= i + 2) { in __longest_prefix_match() 218 if (trie->data_size >= i + 1) { in __longest_prefix_match() 228 static size_t longest_prefix_match(const struct lpm_trie *trie, in longest_prefix_match() argument 232 return __longest_prefix_match(trie, node, key); in longest_prefix_match() 238 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_lookup_elem() local 242 if (key->prefixlen > trie->max_prefixlen) in trie_lookup_elem() 247 for (node = rcu_dereference_check(trie->root, rcu_read_lock_bh_held()); in trie_lookup_elem() [all …]
|
/linux/fs/unicode/ |
H A D | utf8-norm.c | 306 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 …]
|
H A D | mkutf8data.c | 2709 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/ |
H A D | fib_trie.rst | 4 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 D | fib_trie.c | 167 struct trie { struct 174 static struct key_vector *resize(struct trie *t, struct key_vector *tn); argument 508 static struct key_vector *replace(struct trie *t, in replace() 537 static struct key_vector *inflate(struct trie *t, in inflate() 633 static struct key_vector *halve(struct trie *t, in halve() 688 static struct key_vector *collapse(struct trie *t, in collapse() 848 static struct key_vector *resize(struct trie *t, struct key_vector *tn) in resize() 936 static struct key_vector *fib_find_node(struct trie *t, in fib_find_node() 1023 struct trie *t; in fib_find_matching_alias() 1029 t = (struct trie *)tb->tb_data; in fib_find_matching_alias() [all …]
|
/linux/drivers/net/wireguard/ |
H A D | allowedips.c | 111 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/Documentation/bpf/ |
H A D | map_lpm_trie.rst | 13 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/Documentation/networking/devlink/ |
H A D | devlink-dpipe.rst | 34 Level Path Compression trie (LPC-trie) in hardware.
|
/linux/Documentation/RCU/ |
H A D | RTFP.txt | 159 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.
|