Radix Tree - Linuxカーネルメモ

1. 概要 Tree検索を行うRadix TreeのLinuxでの実装メモ。 Radix Treeの機能はlib/radix-tree.cで提供される。実際の使用例としては、ページキャッシュのページを管理するのにRadix Treeを使っている。 2. データ構造 LinuxでのRadixツリーの構造を図1に示す。 2.1 Treeの管理データ Radix Treeの管理の大元のデータとしてstruct radix_tree_rootがある。このデータはRadix Tree関連関数でどのTreeに対して操作を行うのか指定するのに使われる。 このデータのrnodeがルートノード(Treeトップのノード)を指している。heightはTreeの高さを表しており、例えばheight=1だと、ルートノードのみの1段のTreeであることを意味する。 2.2 Treeのノード Treeの各ノードはstr