Lines Matching +full:child +full:- +full:node

1 .. SPDX-License-Identifier: GPL-2.0
4 LC-trie implementation notes
7 Node types
8 ----------
10 	An end node with data. This has a copy of the relevant key, along
14 trie node or tnode
15 	An internal node, holding an array of child (leaf or tnode) pointers,
19 ------------------------
22 	child array - the "child index". See Level Compression.
26 	the child array. See Path Compression.
29 	Any given tnode is linked to from the child array of its parent, using
39 Level Compression / child arrays
41 	children of a full child (see "full_children") up one level, so that
42 	instead of a pure binary tree, each internal node ("tnode") may
44 	Conversely, a tnode with a mostly empty	child array (see empty_children)
46 	in order to avoid ever-increasing child arrays.
49 	the number of positions in the child array of a given tnode that are
61 ---------
71 	Inserts a new leaf node in the trie. This is bit more complicated than
72 	fib_find_node(). Inserting a new node means we might have to run the
85 	Analyzes a tnode and optimizes the child array size by either inflating
91 	Doubles the size of the child array within a tnode. Used by resize().
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 ---------------------
136 through the child array, chopping off (zeroing) the least significant "1" of
137 the child index until we find a match or the child index consists of nothing but
140 At this point we backtrack (t->stats.backtrack++) up the trie, continuing to