Lines Matching refs:the
6 An end node with data. This has a copy of the relevant key, along
12 indexed through a subset of the key. See Level Compression.
17 The number of bits in the key segment used for indexing into the
18 child array - the "child index". See Level Compression.
21 The position (in the key) of the key segment used for indexing into
22 the child array. See Path Compression.
25 Any given tnode is linked to from the child array of its parent, using
26 a segment of the key specified by the parent's "pos" and "bits"
28 adjacent to the parent (pos+bits), but there will be some bits
29 in the key skipped over because they represent a single path with no
31 Note that the search algorithm will simply skip over these bits when
32 searching, making it necessary to save the keys in the leaves to
33 verify that they actually do match the key we are searching for.
36 the trie is kept level balanced moving, under certain conditions, the
45 the number of positions in the child array of a given tnode that are
49 the number of children of a given tnode that aren't path compressed.
53 (The word "full" here is used more in the sense of "complete" than
54 as the opposite of "empty", which might be a tad confusing.)
59 We have tried to keep the structure of the code as close to fib_hash as
67 Inserts a new leaf node in the trie. This is bit more complicated than
68 fib_find_node(). Inserting a new node means we might have to run the
69 level compression algorithm on part of the trie.
72 Looks up a key, deletes it and runs the level compression algorithm.
75 The key function for the dynamic trie after any change in the trie
76 it is run to optimize and reorganize. It will walk the trie upwards
77 towards the root from a given tnode, doing a resize() at each step
81 Analyzes a tnode and optimizes the child array size by either inflating
82 or shrinking it repeatedly until it fulfills the criteria for optimal
83 level compression. This part follows the original paper pretty closely
87 Doubles the size of the child array within a tnode. Used by resize().
90 Halves the size of the child array within a tnode - the inverse of
94 The route manipulation functions. Should conform pretty closely to the
98 This walks the full trie (using nextleaf()) and searches for empty
102 Dumps the routing table ordered by prefix length. This is somewhat
103 slower than the corresponding fib_hash function, as we have to walk the
110 fib_lock is used for an RW-lock in the same way that this is done in fib_hash.
111 However, the functions are somewhat separated for other possible locking
113 to avoid read_lock in the fn_trie_lookup() function.
117 fn_trie_lookup() is the main lookup function.
119 The lookup is in its simplest form just like fib_find_node(). We descend the
121 the fib_semantic_match in the leaf's sorted prefix hlist.
126 starting out at the same as the key length, is reduced one step at a time,
127 and we backtrack upwards through the trie trying to find a longest matching
128 prefix. The goal is always to reach a leaf and get a positive result from the
131 Inside each tnode, the search for longest matching prefix consists of searching
132 through the child array, chopping off (zeroing) the least significant "1" of
133 the child index until we find a match or the child index consists of nothing but
136 At this point we backtrack (t->stats.backtrack++) up the trie, continuing to
137 chop off part of the key in order to find the longest matching prefix.
141 descending into dead ends. Look for "HL_OPTIMIZE" sections in the code.
143 To alleviate any doubts about the correctness of the route selection process,