#include <search.h>
void *tsearch(const void *key, void **rootp,
int (*compar)(const void *, const void *));
void *tfind(const void *key, const void **rootp,
int (*compar)(const void *, const void *));
void *tdelete(const void *key, void **rootp,
int (*compar)(const void *, const void *));
void twalk(const void *root, void (*action)(const void *nodep,
const VISIT which,
const int depth));
#define _GNU_SOURCE
#include <search.h>
void tdestroy(void *root, void (*free_node)(void *nodep));
tsearch() は、木構造からアイテムを検索する関数である。 key は、検索するアイテムへのポインタである。 rootp は木構造の根へのポインタへのポインタである。 木構造がノードを含まない場合、rootp の参照している変数は NULL に設定されていなければならない。 木構造にアイテムが見つかった場合、 tsearch() はそのアイテムへのポインタを返す。 見つからなかった場合は、アイテムを木構造に追加し、 追加したアイテムへのポインタを返す。
tfind() は、 tsearch() に似ているが、 アイテムが見つからなかった場合 NULL を返す点が異なる。
tdelete() は木構造からアイテムを削除する。 引数は tsearch() と同じである。
twalk() は、二分木を深さ優先 (depth-first) で、 左から右にたどっていく関数である。 root は起点となるノードへのポインタである。 root に根以外のノードを指定すると、部分木が対象となる。 twalk() は、ノードを訪れる度に (つまり、内部ノードに対しては 3 回、葉に対しては 1 回) ユーザ関数 action を呼び出す。 action には以下の順に 3 つの引数が与えられる。 最初の引数は訪れたノードへのポインタである。 2 つ目の引数には、内部ノードの場合は訪問回数に応じて preorder, postorder, endorder が、 葉の場合は leaf が与えられる。 (これらのシンボルは <search.h> で定義されている。) 3 つ目の引数はノードの深さで、根の場合は 0 である。
(より一般的には、preorder, postorder, endorder は preorder, inorder, postorder として知られている: それぞれ、子要素を辿る前・最初の子要素を辿った後かつ 2 番目の子要素を辿る前・ 子要素を辿った後ということを表している。 よって postorder という名前を選ぶのは少し紛らわしい。)
tdestroy() は root が指す木構造全体を削除し、 tsearch() 関数で確保されたリソースを全て解放する。 木構造の各ノードについて、関数 free_node が呼び出される。 データへのポインタがこの関数の引数として渡される。 そのような動作が必要でなければ、 free_node は何もしない関数へのポインタでなければならない。
tdelete() は削除したアイテムの親へのポインタを返す。 アイテムが見つからなかった場合は NULL を返す。
rootp が NULL の場合、 tsearch(), tfind(), tdelete() は NULL を返す。
twalk() においては、postorder は 「左の部分木の後で、右の部分木の前」を意味している。 しかし、人によってはこれを "inorder" と呼んで、 "postorder" を「両方の部分木の後」とする場合もある。
tdelete() は、削除したノードの使用していたメモリを解放するが、 ノードに対応するデータのメモリは、ユーザが解放しなければならない。
下のプログラム例は、ユーザ関数が "endorder" か "leaf" を引数にして 呼び出されて以降は、 twalk() がそのノードを参照しないことを前提としている。 これは GNU ライブラリの実装では機能するが、SysV のマニュアルには存在しない。
#include <search.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
void *root = NULL;
void *
xmalloc(unsigned n)
{
void *p;
p = malloc(n);
if (p)
return p;
fprintf(stderr, "insufficient memory\n");
exit(EXIT_FAILURE);
}
int
compare(const void *pa, const void *pb)
{
if (*(int *) pa < *(int *) pb)
return -1;
if (*(int *) pa > *(int *) pb)
return 1;
return 0;
}
void
action(const void *nodep, const VISIT which, const int depth)
{
int *datap;
switch (which) {
case preorder:
break;
case postorder:
datap = *(int **) nodep;
printf("%6d\n", *datap);
break;
case endorder:
break;
case leaf:
datap = *(int **) nodep;
printf("%6d\n", *datap);
break;
}
}
int
main(void)
{
int i, *ptr;
void *val;
srand(time(NULL));
for (i = 0; i < 12; i++) {
ptr = (int *) xmalloc(sizeof(int));
*ptr = rand() & 0xff;
val = tsearch((void *) ptr, &root, compare);
if (val == NULL)
exit(EXIT_FAILURE);
}
twalk(root, action);
exit(EXIT_SUCCESS);
}