名前¶

書式¶

#include <search.h>

void *tsearch(const void *key, void **rootp,
                int (*compar)(const void *, const void *));

void *tfind(const void *key, void *const *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         /* feature_test_macros(7) 参照 */


#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() は、ノードを訪れる度にユーザー関数 action を呼び出す (内部ノードに対しては 3 回、葉に対しては 1 回呼び出しが行われる)。 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 を返す。

準拠¶

注意¶

tdelete() は、削除したノードの使用していたメモリーを解放するが、 ノードに対応するデータのメモリーは、ユーザーが解放しなければならない。

下のプログラム例は、ユーザー関数が "endorder" か "leaf" を引き数にして 呼び出されて以降は、 twalk() がそのノードを参照しないことを前提としている。 これは GNU ライブラリの実装では機能するが、System V のマニュアルには存在しない。

例¶

#define _GNU_SOURCE     /* Expose declaration of tdestroy() */
#include <search.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
static void *root = NULL;
static void *
xmalloc(unsigned n)
{
    void *p;
    p = malloc(n);
    if (p)
        return p;
    fprintf(stderr, "insufficient memory\n");
    exit(EXIT_FAILURE);
}
static int
compare(const void *pa, const void *pb)
{
    if (*(int *) pa < *(int *) pb)
        return -1;
    if (*(int *) pa > *(int *) pb)
        return 1;
    return 0;
}
static 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 = xmalloc(sizeof(int));
        *ptr = rand() & 0xff;
        val = tsearch((void *) ptr, &root, compare);
        if (val == NULL)
            exit(EXIT_FAILURE);
        else if ((*(int **) val) != ptr)
            free(ptr);
    }
    twalk(root, action);
    tdestroy(root, free);
    exit(EXIT_SUCCESS);
}

関連項目¶

この文書について¶