linux-imx

            LC-trie implementation notes.

​

Node types

----------

leaf 

    An end node with data. This has a copy of the relevant key, along

    with 'hlist' with routing table entries sorted by prefix length.

    See struct leaf and struct leaf_info.

​

trie node or tnode

    An internal node, holding an array of child (leaf or tnode) pointers,

    indexed through a subset of the key. See Level Compression.

​

A few concepts explained

------------------------

Bits (tnode) 

    The number of bits in the key segment used for indexing into the

    child array - the "child index". See Level Compression.

​

Pos (tnode)

    The position (in the key) of the key segment used for indexing into

    the child array. See Path Compression.

​

Path Compression / skipped bits

    Any given tnode is linked to from the child array of its parent, using

    a segment of the key specified by the parent's "pos" and "bits" 

    In certain cases, this tnode's own "pos" will not be immediately

    adjacent to the parent (pos+bits), but there will be some bits

    in the key skipped over because they represent a single path with no

    deviations. These "skipped bits" constitute Path Compression.

    Note that the search algorithm will simply skip over these bits when

    searching, making it necessary to save the keys in the leaves to

    verify that they actually do match the key we are searching for.

​

Level Compression / child arrays

    the trie is kept level balanced moving, under certain conditions, the

    children of a full child (see "full_children") up one level, so that

    instead of a pure binary tree, each internal node ("tnode") may

    contain an arbitrarily large array of links to several children.

    Conversely, a tnode with a mostly empty child array (see empty_children)

    may be "halved", having some of its children moved downwards one level,

    in order to avoid ever-increasing child arrays.

​

empty_children

    the number of positions in the child array of a given tnode that are

    NULL.

​

full_children

    the number of children of a given tnode that aren't path compressed.

    (in other words, they aren't NULL or leaves and their "pos" is equal

    to this tnode's "pos"+"bits").

​

    (The word "full" here is used more in the sense of "complete" than

    as the opposite of "empty", which might be a tad confusing.)

​

Comments

---------

​

We have tried to keep the structure of the code as close to fib_hash as 

possible to allow verification and help up reviewing. 

​

fib_find_node()

    A good start for understanding this code. This function implements a

    straightforward trie lookup.

​

fib_insert_node()

    Inserts a new leaf node in the trie. This is bit more complicated than

    fib_find_node(). Inserting a new node means we might have to run the

    level compression algorithm on part of the trie.

​

trie_leaf_remove()

    Looks up a key, deletes it and runs the level compression algorithm.

​

trie_rebalance()

    The key function for the dynamic trie after any change in the trie

    it is run to optimize and reorganize. It will walk the trie upwards

    towards the root from a given tnode, doing a resize() at each step

    to implement level compression.

​

resize()

    Analyzes a tnode and optimizes the child array size by either inflating

    or shrinking it repeatedly until it fulfills the criteria for optimal

    level compression. This part follows the original paper pretty closely

    and there may be some room for experimentation here.

​

inflate()

    Doubles the size of the child array within a tnode. Used by resize().

​

halve()

    Halves the size of the child array within a tnode - the inverse of

    inflate(). Used by resize();

​