Documentation/networking/fib_trie.rst

1 .. SPDX-License-Identifier: GPL-2.0
4 LC-trie implementation notes
8 ----------
10 	An end node with data. This has a copy of the relevant key, along
16 	indexed	through a subset of the key. See Level Compression.
19 ------------------------
21 	The number of bits in the key segment used for indexing into the
22 	child array - the "child index". See Level Compression.
25 	The position (in the key) of the key segment used for indexing into
30 	a segment of the key specified by the parent's "pos" and "bits"
33 	in the key skipped over because they represent a single path with no
37 	verify that they actually do match the key we are searching for.
41 	children of a full child (see "full_children") up one level, so that
46 	in order to avoid ever-increasing child arrays.
61 ---------
64 possible to allow verification and help up reviewing.
76 	Looks up a key, deletes it and runs the level compression algorithm.
79 	The key function for the dynamic trie after any change in the trie
94 	Halves the size of the child array within a tnode - the inverse of
112 -------
114 fib_lock is used for an RW-lock in the same way that this is done in fib_hash.
120 ---------------------
124 trie, key segment by key segment, until we find a leaf. check_leaf() does
130 starting out at the same as the key length, is reduced one step at a time,
140 At this point we backtrack (t->stats.backtrack++) up the trie, continuing to
141 chop off part of the key in order to find the longest matching prefix.