radix treeimplementation and API in the linux kernel:
radix treeis. Radix tree is a
compressed triewhere a trie is a data structure which implements an interface of an associative array and allows to store values as
key-value. The keys are usually strings, but any data type can be used. A trie is different from an
n-treebecause of its nodes. Nodes of a trie do not store keys; instead, a node of a trie stores single character labels. The key which is related to a given node is derived by traversing from the root of the tree to this node. For example:
cat. The compressed trie or
radix treediffers from
triein that all intermediates nodes which have only one child are removed.
height- height of the tree;
gfp_mask- tells how memory allocations will be performed;
rnode- pointer to the child node.
gfp_mask, which describes how that allocation is to be performed. These
GFP_flags which control the allocation process can have following values: (
GFP_NOIOflag) means allocation can block but must not initiate disk I/O; (
__GFP_HIGHMEMflag) means either ZONE_HIGHMEM or ZONE_NORMAL memory can be used; (
GFP_ATOMICflag) means the allocation is high-priority and must not sleep, etc.
GFP_NOIO- allocation can block but must not initiate disk I/O;
__GFP_HIGHMEM- either ZONE_HIGHMEM or ZONE_NORMAL can be used;
GFP_ATOMIC- allocation process is high-priority and must not sleep;
path- offset in parent & height from the bottom;
count- count of the child nodes;
parent- pointer to the parent node;
private_data- used by the user of a tree;
rcu_head- used for freeing a node;
private_list- used by the user of a tree;
slotsare important and interesting. Every node can contains a set of slots which are store pointers to the data. Empty slots in the Linux kernel radix tree implementation store
NULL. Radix trees in the linux kernel also supports tags which are associated with the
tagsfields in the
radix_tree_nodestructure. Tags allow individual bits to be set on records which are stored in the radix tree.
nameparameter, so with the
RADIX_TREEmacro we can define and initialize radix tree with the given name. Implementation of the
RADIX_TREEmacro we define instance of the
radix_tree_rootstructure with the given name and call
RADIX_TREE_INITmacro with the given mask. The
RADIX_TREE_INITmacro just initializes
radix_tree_rootstructure with the default values and the given mask.
radix_tree_rootstructure by hand and pass it with mask to the
radix_tree_insertfunction takes three parameters:
radix_tree_deletefunction takes the same set of parameters as the
radix_tree_insert, but without data.
radix_tree_lookupfunction takes two parameters:
radix_tree_gang_lookupfunction have the following signature
radix_tree_lookup_slotfunction will return the slot which will contain the data.