| /kernel/linux/linux-6.6/kernel/bpf/ |
| H A D | lpm_trie.c | 41 /* This trie implements a longest prefix match algorithm that can be used to
53 * For instance, let's start with a trie that was created with a prefix length
59 * As the trie is empty initially, the new node (1) will be places as root
141 * example above, (4) would be re-used if 192.168.0.0/23 is added to the trie.
143 * A fully populated trie would have a height of 32 nodes, as the trie was
147 * is a child that can be used to become more specific, the trie is traversed
159 * @trie: The trie to get internal sizes from
165 static size_t longest_prefix_match(const struct lpm_trie *trie, in longest_prefix_match() argument
230 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); trie_lookup_elem() local
282 lpm_trie_node_alloc(const struct lpm_trie *trie, const void *value) lpm_trie_node_alloc() argument
309 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); trie_update_elem() local
439 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); trie_delete_elem() local
548 struct lpm_trie *trie; trie_alloc() local
578 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); trie_free() local
618 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); trie_get_next_key() local
725 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); trie_mem_usage() local
[all...] |
| /kernel/linux/linux-5.10/kernel/bpf/ |
| H A D | lpm_trie.c | 40 /* This trie implements a longest prefix match algorithm that can be used to
52 * For instance, let's start with a trie that was created with a prefix length
58 * As the trie is empty initially, the new node (1) will be places as root
140 * example above, (4) would be re-used if 192.168.0.0/23 is added to the trie.
142 * A fully populated trie would have a height of 32 nodes, as the trie was
146 * is a child that can be used to become more specific, the trie is traversed
158 * @trie: The trie to get internal sizes from
164 static size_t longest_prefix_match(const struct lpm_trie *trie, in longest_prefix_match() argument
229 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); trie_lookup_elem() local
279 lpm_trie_node_alloc(const struct lpm_trie *trie, const void *value) lpm_trie_node_alloc() argument
306 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); trie_update_elem() local
436 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); trie_delete_elem() local
545 struct lpm_trie *trie; trie_alloc() local
591 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); trie_free() local
631 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); trie_get_next_key() local
[all...] |
| /kernel/linux/linux-6.6/fs/unicode/ |
| H A D | utf8-norm.c | 150 * The leaves of the trie are embedded in the trie, and so the same
174 * The decompositions in the trie have been fully expanded, with the
179 * The trie is constructed in such a way that leaves exist for all
182 * lookup in the trie can be used to validate the UTF-8 input.
295 * Use trie to scan s, touching at most len bytes.
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 in utf8nlookup()
[all...] |
| H A D | mkutf8data.c | 19 /* Generator for a compact trie for unicode normalization */
72 * To save space in the generated trie, the unicode version is not
145 * The leaves of the trie are embedded in the trie, and so the same
169 * The decompositions in the trie have been fully expanded.
939 * emitted trie. These values must be pre-computed because relative
1183 * Emit a trie for the given tree into the data array.
1840 printf("This program creates an a data trie used for parsing and\n"); in help()
1841 printf("normalization of UTF-8 strings. The trie is derived from\n"); in help()
2474 * trie in hangul_decompose()
2709 utf8trie_t *trie; utf8nlookup() local
[all...] |
| /kernel/linux/linux-5.10/fs/unicode/ |
| H A D | utf8-norm.c | 167 * The leaves of the trie are embedded in the trie, and so the same
191 * The decompositions in the trie have been fully expanded, with the
196 * The trie is constructed in such a way that leaves exist for all
199 * lookup in the trie can be used to validate the UTF-8 input.
312 * Use trie to scan s, touching at most len bytes.
322 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 in utf8nlookup()
[all...] |
| H A D | mkutf8data.c | 19 /* Generator for a compact trie for unicode normalization */
72 * To save space in the generated trie, the unicode version is not
145 * The leaves of the trie are embedded in the trie, and so the same
169 * The decompositions in the trie have been fully expanded.
939 * emitted trie. These values must be pre-computed because relative
1183 * Emit a trie for the given tree into the data array.
1840 printf("This program creates an a data trie used for parsing and\n"); in help()
1841 printf("normalization of UTF-8 strings. The trie is derived from\n"); in help()
2474 * trie in hangul_decompose()
2709 utf8trie_t *trie; utf8nlookup() local
[all...] |
| /kernel/linux/linux-5.10/net/ipv4/ |
| H A D | fib_trie.c | 12 * This work is based on the LPC-trie which is originally described in:
165 struct trie { struct
172 static struct key_vector *resize(struct trie *t, struct key_vector *tn);
230 * necessary. Every node in the trie has a key associated with it, but not
506 static struct key_vector *replace(struct trie *t, in replace()
535 static struct key_vector *inflate(struct trie *t, in inflate()
631 static struct key_vector *halve(struct trie *t, in halve()
686 static struct key_vector *collapse(struct trie *t, in collapse()
745 /* From "Implementing a dynamic compressed trie" by Stefan Nilsson of
841 /* One child or none, time to drop us from the trie */ in should_collapse()
[all...] |
| /kernel/linux/linux-6.6/net/ipv4/ |
| H A D | fib_trie.c | 12 * This work is based on the LPC-trie which is originally described in:
166 struct trie { struct
173 static struct key_vector *resize(struct trie *t, struct key_vector *tn);
231 * necessary. Every node in the trie has a key associated with it, but not
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()
746 /* From "Implementing a dynamic compressed trie" by Stefan Nilsson of
842 /* One child or none, time to drop us from the trie */ in should_collapse()
[all...] |
| /kernel/linux/linux-5.10/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, in add()
[all...] |
| /kernel/linux/linux-6.6/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, in add()
[all...] |