日本語 man コマンド類 (ja-man-1.1j_5) と日本語 man ドキュメント (ja-man-doc-5.4 (5.4-RELEASE 用) など) をインストールすると、以下のような man コマンド閲覧、キーワード検索が コンソールからできるようになります。
4.11-RELEASE-K, 5.4-RELEASE-K, 5.5-RELEASE-K, 6.0-RELEASE-K から 6.4-RELEASE-K, 7.0-RELEASE-K から 7.4-RELEASE-K, 8.0-RELEASE-K から 8.4-RELEASE-K, 9.0-RELEASE-K から 9.3-RELEASE-K, 10.0-RELEASE-K から 10.3-RELEASE-K, 11.0-RELEASE-K から 11.4-RELEASE-K, 12.0-RELEASE-K, 12.1-RELEASE-K は、 プライベート版 (小金丸が編集してまとめたもの) ですが、 より多くの翻訳したファイルが含まれています。 (5.4-RELEASE-K から 6.4-RELEASE-K, 7.0-RELEASE-K から 7.4-RELEASE-K, 8.0-RELEASE-K から 8.4-RELEASE-K, 9.0-RELEASE-K から 9.3-RELEASE-K, 10.0-RELEASE-K から 10.3-RELEASE-K, 11.0-RELEASE-K から 11.4-RELEASE-K, 12.0-RELEASE-K から 12.4-RELEASE-K, 13.0-RELEASE-K から 13.3-RELEASE-K, 14.0-RELEASE-K から 14.1-RELEASE-K は、全翻訳済み)
13.3-STABLE-K, 15.0-CURRENT-K は現在、作成中で日々更新されています。
Table of Contents
TREE(3) FreeBSD ライブラリ関数マニュアル TREE(3)
名称
SPLAY_PROTOTYPE, SPLAY_GENERATE, SPLAY_ENTRY, SPLAY_HEAD,
SPLAY_INITIALIZER, SPLAY_ROOT, SPLAY_EMPTY, SPLAY_NEXT, SPLAY_MIN,
SPLAY_MAX, SPLAY_FIND, SPLAY_LEFT, SPLAY_RIGHT, SPLAY_FOREACH,
SPLAY_INIT, SPLAY_INSERT, SPLAY_REMOVE, RB_PROTOTYPE,
RB_PROTOTYPE_STATIC, RB_PROTOTYPE_INSERT, RB_PROTOTYPE_INSERT_COLOR,
RB_PROTOTYPE_REMOVE, RB_PROTOTYPE_REMOVE_COLOR, RB_PROTOTYPE_FIND,
RB_PROTOTYPE_NFIND, RB_PROTOTYPE_NEXT, RB_PROTOTYPE_PREV,
RB_PROTOTYPE_MINMAX, RB_GENERATE, RB_GENERATE_STATIC, RB_GENERATE_INSERT,
RB_GENERATE_INSERT_COLOR, RB_GENERATE_REMOVE, RB_GENERATE_REMOVE_COLOR,
RB_GENERATE_FIND, RB_GENERATE_NFIND, RB_GENERATE_NEXT, RB_GENERATE_PREV,
RB_GENERATE_MINMAX, RB_ENTRY, RB_HEAD, RB_INITIALIZER, RB_ROOT, RB_EMPTY,
RB_NEXT, RB_PREV, RB_MIN, RB_MAX, RB_FIND, RB_NFIND, RB_LEFT, RB_RIGHT,
RB_PARENT, RB_FOREACH, RB_FOREACH_FROM, RB_FOREACH_SAFE,
RB_FOREACH_REVERSE, RB_FOREACH_REVERSE_FROM, RB_FOREACH_REVERSE_SAFE,
RB_INIT, RB_INSERT, RB_REMOVE -- スプレイ (斜角) と赤黒ツリーの実装
書式
#include <sys/tree.h>
SPLAY_PROTOTYPE(NAME, TYPE, FIELD, CMP);
SPLAY_GENERATE(NAME, TYPE, FIELD, CMP);
SPLAY_ENTRY(TYPE);
SPLAY_HEAD(HEADNAME, TYPE);
struct TYPE *
SPLAY_INITIALIZER(SPLAY_HEAD *head);
SPLAY_ROOT(SPLAY_HEAD *head);
bool
SPLAY_EMPTY(SPLAY_HEAD *head);
struct TYPE *
SPLAY_NEXT(NAME, SPLAY_HEAD *head, struct TYPE *elm);
struct TYPE *
SPLAY_MIN(NAME, SPLAY_HEAD *head);
struct TYPE *
SPLAY_MAX(NAME, SPLAY_HEAD *head);
struct TYPE *
SPLAY_FIND(NAME, SPLAY_HEAD *head, struct TYPE *elm);
struct TYPE *
SPLAY_LEFT(struct TYPE *elm, SPLAY_ENTRY NAME);
struct TYPE *
SPLAY_RIGHT(struct TYPE *elm, SPLAY_ENTRY NAME);
SPLAY_FOREACH(VARNAME, NAME, SPLAY_HEAD *head);
void
SPLAY_INIT(SPLAY_HEAD *head);
struct TYPE *
SPLAY_INSERT(NAME, SPLAY_HEAD *head, struct TYPE *elm);
struct TYPE *
SPLAY_REMOVE(NAME, SPLAY_HEAD *head, struct TYPE *elm);
RB_PROTOTYPE(NAME, TYPE, FIELD, CMP);
RB_PROTOTYPE_STATIC(NAME, TYPE, FIELD, CMP);
RB_PROTOTYPE_INSERT(NAME, TYPE, ATTR);
RB_PROTOTYPE_INSERT_COLOR(NAME, TYPE, ATTR);
RB_PROTOTYPE_REMOVE(NAME, TYPE, ATTR);
RB_PROTOTYPE_REMOVE_COLOR(NAME, TYPE, ATTR);
RB_PROTOTYPE_FIND(NAME, TYPE, ATTR);
RB_PROTOTYPE_NFIND(NAME, TYPE, ATTR);
RB_PROTOTYPE_NEXT(NAME, TYPE, ATTR);
RB_PROTOTYPE_PREV(NAME, TYPE, ATTR);
RB_PROTOTYPE_MINMAX(NAME, TYPE, ATTR);
RB_GENERATE(NAME, TYPE, FIELD, CMP);
RB_GENERATE_STATIC(NAME, TYPE, FIELD, CMP);
RB_GENERATE_INSERT(NAME, TYPE, FIELD, CMP, ATTR);
RB_GENERATE_INSERT_COLOR(NAME, TYPE, FIELD, ATTR);
RB_GENERATE_REMOVE(NAME, TYPE, FIELD, ATTR);
RB_GENERATE_REMOVE_COLOR(NAME, TYPE, FIELD, ATTR);
RB_GENERATE_FIND(NAME, TYPE, FIELD, CMP, ATTR);
RB_GENERATE_NFIND(NAME, TYPE, FIELD, CMP, ATTR);
RB_GENERATE_NEXT(NAME, TYPE, FIELD, ATTR);
RB_GENERATE_PREV(NAME, TYPE, FIELD, ATTR);
RB_GENERATE_MINMAX(NAME, TYPE, FIELD, ATTR);
RB_ENTRY(TYPE);
RB_HEAD(HEADNAME, TYPE);
RB_INITIALIZER(RB_HEAD *head);
struct TYPE *
RB_ROOT(RB_HEAD *head);
bool
RB_EMPTY(RB_HEAD *head);
struct TYPE *
RB_NEXT(NAME, RB_HEAD *head, struct TYPE *elm);
struct TYPE *
RB_PREV(NAME, RB_HEAD *head, struct TYPE *elm);
struct TYPE *
RB_MIN(NAME, RB_HEAD *head);
struct TYPE *
RB_MAX(NAME, RB_HEAD *head);
struct TYPE *
RB_FIND(NAME, RB_HEAD *head, struct TYPE *elm);
struct TYPE *
RB_NFIND(NAME, RB_HEAD *head, struct TYPE *elm);
struct TYPE *
RB_LEFT(struct TYPE *elm, RB_ENTRY NAME);
struct TYPE *
RB_RIGHT(struct TYPE *elm, RB_ENTRY NAME);
struct TYPE *
RB_PARENT(struct TYPE *elm, RB_ENTRY NAME);
RB_FOREACH(VARNAME, NAME, RB_HEAD *head);
RB_FOREACH_FROM(VARNAME, NAME, POS_VARNAME);
RB_FOREACH_SAFE(VARNAME, NAME, RB_HEAD *head, TEMP_VARNAME);
RB_FOREACH_REVERSE(VARNAME, NAME, RB_HEAD *head);
RB_FOREACH_REVERSE_FROM(VARNAME, NAME, POS_VARNAME);
RB_FOREACH_REVERSE_SAFE(VARNAME, NAME, RB_HEAD *head, TEMP_VARNAME);
void
RB_INIT(RB_HEAD *head);
struct TYPE *
RB_INSERT(NAME, RB_HEAD *head, struct TYPE *elm);
struct TYPE *
RB_REMOVE(NAME, RB_HEAD *head, struct TYPE *elm);
解説
これらのマクロは、異なったタイプのツリーのためのデータ構造体を定義します:
スプレイ (斜角) ツリーと赤黒ツリーです。
マクロ定義では、TYPE は、タイプ SPLAY_ENTRY または RB_ENTRY と名前が付け
られた ENTRYNAME フィールドを含まなければならない、ユーザが定義した構造体
の名前タグです。引数 HEADNAME は、マクロ SPLAY_HEAD() または RB_HEAD() を
使用して定義しなければならない、ユーザが定義した構造体の名前タグです。引
数 NAME は、定義されるあらゆるツリーのためのユニークな名前の接頭辞でなけ
ればなりません。
関数プロトタイプは、SPLAY_PROTOTYPE(), RB_PROTOTYPE() または
RB_PROTOTYPE_STATIC() で宣言されます。関数本体は、SPLAY_GENERATE(),
RB_GENERATE() または RB_GENERATE_STATIC() で生成されます。これらのマクロ
がどのように使用されているかの詳細な説明については以下の例を参照してくだ
さい。
スプレイ (斜角) ツリー
スプレイツリーは、自己編成のデータ構造です。ツリーにおけるあらゆる操作
は、スプレイが起こります。スプレイは、要求されたノードをツリーのルートに
移動し、部分的に再バランスのとれた状態にします。
これは、要求されたノードがツリーの先端に移動するとき、要求場所が、より速
く検索される利点があります。いっぽうで、あらゆる検索でメモリの書き込みが
起きます。
バランス定理 (Balance Theorem) は O((m + n)lg n) のような初期の空のツリー
で m 操作と n 挿入するための総アクセス時間を抑制します。スプレイツリーへ
の m アクセスのシーケンスのための償却コストは O(lg n) です。
スプレイツリーは SPLAY_HEAD() マクロによって定義された構造体が先頭となり
ます。構造体は、次のように宣言されます:
SPLAY_HEAD(HEADNAME, TYPE) head;
ここで、HEADNAME は、定義される構造体の名前であり、struct TYPE は、ツリー
に挿入される要素のタイプです。
SPLAY_ENTRY() マクロは、ツリーに接続されることができる要素の構造体を宣言
します。
ツリー構造体を操作する関数を使用するために、それらのプロトタイプは、
SPLAY_PROTOTYPE() マクロで宣言される必要があります。ここで、NAME は、この
特定のツリーのためのユニークな識別子です。TYPE 引数は、ツリーによって管理
されている構造体のタイプです。FIELD 引数は SPLAY_ENTRY() によって定義され
た要素の名前です。
関数本体は、SPLAY_GENERATE() マクロで生成されます。それは、
SPLAY_PROTOTYPE() マクロと同じ引数を取りますが、一度だけ使用されるべきで
す。
最後に、CMP 引数は、互いにツリーのノードを比較するために使用される関数の
名前です。関数は、タイプ struct TYPE * の 2 つの引数を取ります。最初の引
数が 2 番目より小さいなら、関数は、0 より小さな値を返します。それらが等し
いなら、関数は、0 を返します。そうでなければ、それは、0 以上の値を返すべ
きです。比較関数は、ツリーの要素の順序を定義します。
SPLAY_INIT() マクロは head によって参照されるツリーを初期化します。
スプレイツリーは、次のように SPLAY_INITIALIZER() マクロを使用することに
よって、静的に初期化することもできます:
SPLAY_HEAD(HEADNAME, TYPE) head = SPLAY_INITIALIZER(&head);
SPLAY_INSERT() マクロは、新しい要素 elm をツリーに挿入します。
SPLAY_REMOVE() マクロは head によって指されたツリーから要素 elm を削除し
ます。
SPLAY_FIND() マクロは、ツリーの中の特定の要素を見つけるために使用すること
ができます。
struct TYPE find, *res;
find.key = 30;
res = SPLAY_FIND(NAME, head, &find);
SPLAY_ROOT(), SPLAY_MIN(), SPLAY_MAX() と SPLAY_NEXT() マクロは、ツリーを
横断するために使用することができます:
for (np = SPLAY_MIN(NAME, &head); np != NULL;
np = SPLAY_NEXT(NAME, &head, np))
または、簡単に、SPLAY_FOREACH() マクロを使用することができます:
SPLAY_FOREACH(np, NAME, head)
SPLAY_EMPTY() マクロは、スプレイツリーが空であるかどうかチェックするのに
使用されます。
赤黒ツリー
赤黒ツリーは、特別な属性としてノードの色がある二分検索木です。それは、1
組の条件を実現します:
1. あらゆるルート (根) からリーフ (葉) までのパスの検索は同じ数の
黒のノードから成ります。
2. それぞれの赤のノード (ルートを除いて) は、黒の親があります。
3. それぞれのリーフのノードは、黒です。
赤黒ツリーにおけるあらゆる操作は O(lg n) に束縛されます。赤黒ツリーの最大
の高さは 2lg(n + 1) です。
赤黒ツリーは RB_HEAD() マクロによって定義された構造体が先頭となります。構
造体は、次のように宣言されます:
RB_HEAD(HEADNAME, TYPE) head;
ここで、HEADNAME は、定義される構造体の名前であり、struct TYPE は、ツリー
に挿入される要素のタイプです。
RB_ENTRY() マクロは、ツリーに接続されることができる要素の構造体を宣言しま
す。
ツリー構造体を操作する関数を使用するために、それらのプロトタイプは、
RB_PROTOTYPE() または RB_PROTOTYPE_STATIC() マクロで宣言される必要があり
ます。ここで、NAME は、この特定のツリーのためのユニークな識別子です。TYPE
引数は、ツリーによって管理されている構造体のタイプです。FIELD 引数は
RB_ENTRY() によって定義された要素の名前です。すべての関数が要求されない場
合に、RB_PROTOTYPE_INSERT(), RB_PROTOTYPE_INSERT_COLOR(),
RB_PROTOTYPE_REMOVE(), RB_PROTOTYPE_REMOVE_COLOR(), RB_PROTOTYPE_FIND(),
RB_PROTOTYPE_NFIND(), RB_PROTOTYPE_NEXT(), RB_PROTOTYPE_PREV() と
RB_PROTOTYPE_MINMAX() で個別のプロトタイプを宣言することができます。個別
のプロトタイプマクロは、NAME, TYPE と ATTR 引数を要求します。ATTR 引数
は、グローバルな関数に対して空、または静的な関数に対して static でなけれ
ばなりません。
関数本体は、RB_GENERATE() または RB_GENERATE_STATIC() マクロで生成されま
す。それらのマクロは、RB_PROTOTYPE() と RB_PROTOTYPE_STATIC() マクロと同
じ引数を取りますが、一度だけ使用されるべきです。代わりの個別の関数の本体
は、RB_GENERATE_INSERT(), RB_GENERATE_INSERT_COLOR(),
RB_GENERATE_REMOVE(), RB_GENERATE_REMOVE_COLOR(), RB_GENERATE_FIND(),
RB_GENERATE_NFIND(), RB_GENERATE_NEXT(), RB_GENERATE_PREV() と
RB_GENERATE_MINMAX() マクロによって生成されます。
最後に、CMP 引数は、互いにツリーのノードを比較するために使用される関数の
名前です。関数は、タイプ struct TYPE * の 2 つの引数を取ります。最初の引
数が 2 番目より小さいなら、関数は、0 より小さな値を返します。それらが等し
いなら、関数は、0 を返します。そうでなければ、それは、0 以上の値を返すべ
きです。比較関数は、ツリーの要素の順序を定義します。
RB_INIT() マクロは、head によって参照されるツリーを初期化します。
赤黒ツリーは、次のように RB_INITIALIZER() マクロを使用することによって、
静的に初期化することもできます:
RB_HEAD(HEADNAME, TYPE) head = RB_INITIALIZER(&head);
RB_INSERT() マクロは、新しい要素 elm をツリーに挿入します。
RB_REMOVE() マクロは、head によって指されたツリーから要素 elm を削除しま
す。
ツリー中の特定の要素を見つけるために、RB_FIND() と RB_NFIND() マクロを使
用することができます。
struct TYPE find, *res;
find.key = 30;
res = RB_FIND(NAME, head, &find);
RB_ROOT(), RB_MIN(), RB_MAX(), RB_NEXT() と RB_PREV() マクロは、ツリーを
横断するために使用することができます:
for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME,
&head, np))
または、簡単に、RB_FOREACH() または RB_FOREACH_REVERSE() マクロを使用する
ことができます:
RB_FOREACH(np, NAME, head)
マクロ RB_FOREACH_SAFE() と RB_FOREACH_REVERSE_SAFE() は、各要素を順番に
np に割り当てて、それぞれ前方または逆方向で head によって参照されるツリー
を横断します。しかしながら、それらの安全でない同等の物と異なり、それら
は、横断 (traversal) を妨げずに、ループの内部からそれを安全に解放するのと
同様に np の削除を両方に可能にします。
RB_FOREACH_FROM() と RB_FOREACH_REVERSE_FROM() の両方は、それぞれ、前方ま
たは逆方向で割り込まれた横断を継続するために使用されます。head ポインタ
は、必要ではありません。横断を再開するところからのノードへのポインタは、
それらの最後の引数として渡されるべきであり、安全な横断を提供するために上
書きされます。
RB_EMPTY() マクロは、赤黒ツリーが空であるかどうかチェックするのに使用され
ます。
注
次の方法でツリーを解放する試みは、一般的にエラーです:
SPLAY_FOREACH(var, NAME, head) {
SPLAY_REMOVE(NAME, head, var);
free(var);
}
free(head);
var が解放されるので、FOREACH() マクロは、既に再割り付けされるポインタを
参照します。適切なコードは、2 番目の変数を必要とします。
for (var = SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
nxt = SPLAY_NEXT(NAME, head, var);
SPLAY_REMOVE(NAME, head, var);
free(var);
}
成功して要素がツリーに挿入されたなら、RB_INSERT() と SPLAY_INSERT() の両
方は、NULL を返します。そうでなければ、それらは、衝突したキーの要素へのポ
インタを返します。
それに従って、RB_REMOVE() と SPLAY_REMOVE() は、削除された要素へのポイン
タを返します。そうでなければ、それらは、エラーを示すために NULL を返しま
す。
関連項目
queue(3)
作者
ツリーマクロの作者は、Niels Provos です。
FreeBSD 11.4 January 24, 2015 FreeBSD 11.4