OSDN Git Service

538aad0dc886c9d8106db21c864b926dae139622
[linuxjm/LDP_man-pages.git] / release / man3 / tsearch.3
1 .\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
2 .\"
3 .\" %%%LICENSE_START(VERBATIM)
4 .\" Permission is granted to make and distribute verbatim copies of this
5 .\" manual provided the copyright notice and this permission notice are
6 .\" preserved on all copies.
7 .\"
8 .\" Permission is granted to copy and distribute modified versions of this
9 .\" manual under the conditions for verbatim copying, provided that the
10 .\" entire resulting derived work is distributed under the terms of a
11 .\" permission notice identical to this one.
12 .\"
13 .\" Since the Linux kernel and libraries are constantly changing, this
14 .\" manual page may be incorrect or out-of-date.  The author(s) assume no
15 .\" responsibility for errors or omissions, or for damages resulting from
16 .\" the use of the information contained herein.  The author(s) may not
17 .\" have taken the same level of care in the production of this manual,
18 .\" which is licensed free of charge, as they might when working
19 .\" professionally.
20 .\"
21 .\" Formatted or processed versions of this manual, if unaccompanied by
22 .\" the source, must acknowledge the copyright and authors of this work.
23 .\" %%%LICENSE_END
24 .\"
25 .\"*******************************************************************
26 .\"
27 .\" This file was generated with po4a. Translate the source file.
28 .\"
29 .\"*******************************************************************
30 .\"
31 .\" Japanese Version Copyright (c) 1999 ishikawa, keisuke
32 .\"         all rights reserved.
33 .\" Translated Tue Mar  9 08:21:04 JST 1999
34 .\"         by ishikawa, keisuke <ishikawa@sgk.gr.jp>
35 .\" Updated & Modified Sun Jan 20 11:31:46 JST 2002
36 .\"         by Yuichi SATO <ysato@h4.dion.ne.jp>
37 .\" Updated 2013-05-06, Akihiro MOTOKI <amotoki@gmail.com>
38 .\"
39 .TH TSEARCH 3 2014\-01\-05 GNU "Linux Programmer's Manual"
40 .SH 名前
41 tsearch, tfind, tdelete, twalk, tdestroy \- 二分木 (binary tree) の操作
42 .SH 書式
43 .nf
44 \fB#include <search.h>\fP
45 .sp
46 \fBvoid *tsearch(const void *\fP\fIkey\fP\fB, void **\fP\fIrootp\fP\fB,\fP
47 \fB                int (*\fP\fIcompar\fP\fB)(const void *, const void *));\fP
48 .sp
49 \fBvoid *tfind(const void *\fP\fIkey\fP\fB, const void **\fP\fIrootp\fP\fB,\fP
50 \fB                int (*\fP\fIcompar\fP\fB)(const void *, const void *));\fP
51 .sp
52 \fBvoid *tdelete(const void *\fP\fIkey\fP\fB, void **\fP\fIrootp\fP\fB,\fP
53 \fB                int (*\fP\fIcompar\fP\fB)(const void *, const void *));\fP
54 .sp
55 \fBvoid twalk(const void *\fP\fIroot\fP\fB, void (*\fP\fIaction\fP\fB)(const void *\fP\fInodep\fP\fB,\fP
56 \fB                                   const VISIT \fP\fIwhich\fP\fB,\fP
57 \fB                                   const int \fP\fIdepth\fP\fB));\fP
58 .sp
59 \fB#define _GNU_SOURCE\fP         /* feature_test_macros(7) 参照 */
60 .br
61 \fB#include <search.h>\fP
62 .sp
63 \fBvoid tdestroy(void *\fP\fIroot\fP\fB, void (*\fP\fIfree_node\fP\fB)(void *\fP\fInodep\fP\fB));\fP
64 .fi
65 .SH 説明
66 \fBtsearch\fP(), \fBtfind\fP(), \fBtwalk\fP(), \fBtdelete\fP()  は 二分木を操作する関数である。 これらの関数は
67 Knuth (6.2.2) Algorithm T に基づいている。 木構造における各ノードの最初のフィールドは、対応するデータ・
68 アイテムへのポインタである。 (参照先のデータは、呼び出しプログラムで用意する。)  \fIcompar\fP は比較ルーチンへのポインタである。
69 比較ルーチンは、アイテムへのポインタ 2 つを引き数に持つ。 比較ルーチンの返り値は、1 つ目のアイテムが 2 つ目のアイテムよりも
70 「小さい、等しい、大きい」によって、 「負、0、正」の整数値でなければならない。
71 .PP
72 \fBtsearch\fP()  は、木構造からアイテムを検索する関数である。 \fIkey\fP は、検索するアイテムへのポインタである。 \fIrootp\fP
73 は木構造の根へのポインタへのポインタである。 木構造がノードを含まない場合、\fIrootp\fP の参照している変数は NULL
74 に設定されていなければならない。 木構造にアイテムが見つかった場合、 \fBtsearch\fP()  はそのアイテムへのポインタを返す。
75 見つからなかった場合は、アイテムを木構造に追加し、 追加したアイテムへのポインタを返す。
76 .PP
77 \fBtfind\fP()  は、 \fBtsearch\fP()  に似ているが、 アイテムが見つからなかった場合 NULL を返す点が異なる。
78 .PP
79 \fBtdelete\fP()  は木構造からアイテムを削除する。 引き数は \fBtsearch\fP()  と同じである。
80 .PP
81 \fBtwalk\fP()  は、二分木を深さ優先 (depth\-first) で、 左から右にたどっていく関数である。 \fIroot\fP
82 は起点となるノードへのポインタである。 \fIroot\fP に根以外のノードを指定すると、部分木が対象となる。 \fBtwalk\fP()
83 は、ノードを訪れる度にユーザ関数 \fIaction\fP を呼び出す (内部ノードに対しては 3 回、葉に対しては 1 回呼び出しが行われる)。
84 \fIaction\fP には以下の順に 3 つの引き数が与えられる。 最初の引き数は訪れたノードへのポインタである。 ノードの構造体は規定されていないが、
85 ポインタを要素へのポインタのポインタにキャストし、 ノードに格納された要素にアクセスすることができる。
86 アプリケーションは、この引き数が指す構造体を変更してはならない。 2 番目の引き数には、内部ノードの場合は訪問回数に応じて \fBpreorder\fP,
87 \fBpostorder\fP, \fBendorder\fP のいずれかの整数が、 葉を最初に訪れた場合は \fBleaf\fP の値が渡される (これらのシンボルは
88 \fI<search.h>\fP で定義されている)。  3 番目の引き数はノードの深さで、根の場合は深さ 0 である。
89 .PP
90 (より一般的には、\fBpreorder\fP, \fBpostorder\fP, \fBendorder\fP は \fBpreorder\fP, \fBinorder\fP,
91 \fBpostorder\fP として知られている: それぞれ、子要素を辿る前・最初の子要素を辿った後かつ 2 番目の子要素を辿る前・
92 子要素を辿った後ということを表している。 よって \fBpost\%order\fP という名前を選ぶのは少し紛らわしい。)
93 .PP
94 \fBtdestroy\fP()  は \fIroot\fP が指す木構造全体を削除し、 \fBtsearch\fP()  関数で確保されたリソースを全て解放する。
95 木構造の各ノードについて、関数 \fIfree_node\fP が呼び出される。 データへのポインタがこの関数の引き数として渡される。
96 そのような動作が必要でなければ、 \fIfree_node\fP は何もしない関数へのポインタでなければならない。
97 .SH 返り値
98 \fBtsearch\fP()  は、木構造に見つかったアイテムか、 新しく追加したアイテムへのポインタを返す。
99 メモリの不足のためアイテムを追加できなかった場合は NULL を返す。 \fBtfind\fP()  は、アイテムへのポインタを返す。
100 一致するアイテムが見つからない場合は NULL を返す。 検索条件に一致する要素が複数ある場合、返される値は不定である。
101 .PP
102 \fBtdelete\fP()  は削除したアイテムの親へのポインタを返す。 アイテムが見つからなかった場合は NULL を返す。
103 .PP
104 \fIrootp\fP が NULL の場合、 \fBtsearch\fP(), \fBtfind\fP(), \fBtdelete\fP()  は NULL を返す。
105 .SH 準拠
106 SVr4, POSIX.1\-2001.  関数 \fBtdestroy\fP()  は GNU の拡張である。
107 .SH 注意
108 \fBtwalk\fP()  は根へのポインタを引き数にとるが、 ほかの関数は根へのポインタへのポインタである。
109 .PP
110 \fBtdelete\fP()  は、削除したノードの使用していたメモリを解放するが、 ノードに対応するデータのメモリは、ユーザが解放しなければならない。
111 .PP
112 下のプログラム例は、ユーザ関数が "endorder" か "leaf" を引き数にして 呼び出されて以降は、 \fBtwalk\fP()
113 がそのノードを参照しないことを前提としている。 これは GNU ライブラリの実装では機能するが、System V のマニュアルには存在しない。
114 .SH 例
115 以下のプログラムは 12 個の乱数を二分木に挿入した後、 挿入した数を順番に出力する (挿入の際、重複した乱数は 1 つにまとめられる)。
116 .sp
117 .nf
118 #define _GNU_SOURCE     /* Expose declaration of tdestroy() */
119 #include <search.h>
120 #include <stdlib.h>
121 #include <stdio.h>
122 #include <time.h>
123
124 static void *root = NULL;
125
126 static void *
127 xmalloc(unsigned n)
128 {
129     void *p;
130     p = malloc(n);
131     if (p)
132         return p;
133     fprintf(stderr, "insufficient memory\en");
134     exit(EXIT_FAILURE);
135 }
136
137 static int
138 compare(const void *pa, const void *pb)
139 {
140     if (*(int *) pa < *(int *) pb)
141         return \-1;
142     if (*(int *) pa > *(int *) pb)
143         return 1;
144     return 0;
145 }
146
147 static void
148 action(const void *nodep, const VISIT which, const int depth)
149 {
150     int *datap;
151
152     switch (which) {
153     case preorder:
154         break;
155     case postorder:
156         datap = *(int **) nodep;
157         printf("%6d\en", *datap);
158         break;
159     case endorder:
160         break;
161     case leaf:
162         datap = *(int **) nodep;
163         printf("%6d\en", *datap);
164         break;
165     }
166 }
167
168 int
169 main(void)
170 {
171     int i, *ptr;
172     void *val;
173
174     srand(time(NULL));
175     for (i = 0; i < 12; i++) {
176         ptr = xmalloc(sizeof(int));
177         *ptr = rand() & 0xff;
178         val = tsearch((void *) ptr, &root, compare);
179         if (val == NULL)
180             exit(EXIT_FAILURE);
181         else if ((*(int **) val) != ptr)
182             free(ptr);
183     }
184     twalk(root, action);
185     tdestroy(root, free);
186     exit(EXIT_SUCCESS);
187 }
188 .fi
189 .SH 関連項目
190 \fBbsearch\fP(3), \fBhsearch\fP(3), \fBlsearch\fP(3)  \fBqsort\fP(3)
191 .SH この文書について
192 この man ページは Linux \fIman\-pages\fP プロジェクトのリリース 3.65 の一部
193 である。プロジェクトの説明とバグ報告に関する情報は
194 http://www.kernel.org/doc/man\-pages/ に書かれている。