Man page - tfind(3)

Packages contains this manual

Available languages:

en fr ja ru

Manual

TSEARCH

名 前
書 式
説 明
返 り 値
バ ー ジ ョ ン
属 性
準 拠
注 意
例
関 連 項 目
こ の 文 書 に つ い て

名 前

tsearch, tfind, tdelete, twalk, tdestroy - 二 分 探 索 木 (binary search tree) の 操 作

書 式

#include <search.h>

typedef enum { preorder, postorder, endorder, leaf } VISIT;

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 , VISIT which ,
int depth ));

#define _GNU_SOURCE /* feature_test_macros(7) 参 照 */
#include <search.h>

void twalk_r(const void * root ,
void (* action )(const void * nodep , VISIT which ,
void * closure ),
void * closure );

void tdestroy(void * root , void (* free_node )(void * nodep ));

説 明

tsearch (), tfind (), twalk (), tdelete () は 二 分 探 索 木 を 操 作 す る 関 数 で あ る 。 こ れ ら の 関 数 は Knuth (6.2.2) Algorithm T に 基 づ い て い る 。 木 構 造 に お け る 各 ノ ー ド の 最 初 の フ ィ ー ル ド は 、 対 応 す る デ ー タ ア イ テ ム へ の ポ イ ン タ ー で あ る 。 (参 照 先 の デ ー タ は 、 呼 び 出 し プ ロ グ ラ ム で 用 意 す る 。 ) compar は 比 較 ル ー チ ン へ の ポ イ ン タ ー で あ る 。 比 較 ル ー チ ン は 、 ア イ テ ム へ の ポ イ ン タ ー 2 つ を 引 数 に 持 つ 。 比 較 ル ー チ ン の 返 り 値 は 、 1 つ 目 の ア イ テ ム が 2 つ 目 の ア イ テ ム よ り も 「 小 さ い 、 等 し い 、 大 き い 」 に よ っ て 、 「 負 、 0、 正 」 の 整 数 値 で な け れ ば な ら な い 。

tsearch () searches the tree for an item. key points to the item to be searched for. rootp points to a variable which points to the root of the tree. If the tree is empty, then the variable that rootp points to should be set to NULL. If the item is found in the tree, then tsearch () returns a pointer to the corresponding tree node. (In other words, tsearch () returns a pointer to a pointer to the data item.) If the item is not found, then tsearch () adds it, and returns a pointer to the corresponding tree node.

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 と い う 名 前 を 選 ぶ の は 少 し 紛 ら わ し い 。 )

twalk_r () is similar to twalk (), but instead of the depth argument, the closure argument pointer is passed to each invocation of the action callback, unchanged. This pointer can be used to pass information to and from the callback function in a thread-safe fashion, without resorting to global variables.

tdestroy () は root が 指 す 木 構 造 全 体 を 削 除 し 、 tsearch () 関 数 で 確 保 さ れ た リ ソ ー ス を 全 て 解 放 す る 。 木 構 造 の 各 ノ ー ド に つ い て 、 関 数 free_node が 呼 び 出 さ れ る 。 デ ー タ へ の ポ イ ン タ ー が こ の 関 数 の 引 数 と し て 渡 さ れ る 。 そ の よ う な 動 作 が 必 要 で な け れ ば 、 free_node は 何 も し な い 関 数 へ の ポ イ ン タ ー で な け れ ば な ら な い 。

返 り 値

tsearch () returns a pointer to a matching node in the tree, or to the newly added node, or NULL if there was insufficient memory to add the item. tfind () returns a pointer to the node, or NULL if no match is found. If there are multiple items that match the key, the item whose node is returned is unspecified.

tdelete () returns a pointer to the parent of the node deleted, or NULL if the item was not found. If the deleted node was the root node, tdelete () returns a dangling pointer that must not be accessed.

rootp が NULL の 場 合 、 tsearch (), tfind (), tdelete () は NULL を 返 す 。

バ ー ジ ョ ン

twalk_r () は glibc バ ー ジ ョ ン 2.30 以 降 で 利 用 可 能 で あ る 。

属 性

こ の 節 で 使 用 さ れ て い る 用 語 の 説 明 に つ い て は 、 attributes (7) を 参 照 。

Image grohtml-27597-1.png

準 拠

POSIX.1-2001, POSIX.1-2008, SVr4. The functions tdestroy () and twalk_r () are GNU extensions.

注 意

twalk () は 根 へ の ポ イ ン タ ー を 引 数 に と る が 、 ほ か の 関 数 は 根 へ の ポ イ ン タ ー へ の ポ イ ン タ ー で あ る 。

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

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

例

以 下 の プ ロ グ ラ ム は 12 個 の 乱 数 を 二 分 木 に 挿 入 し た 後 、 挿 入 し た 数 を 順 番 に 出 力 す る (挿 入 の 際 、 重 複 し た 乱 数 は 1 つ に ま と め ら れ る )。

#define _GNU_SOURCE /* Expose declaration of tdestroy() */
#include <search.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

static void *root = NULL;

static void *
xmalloc(size_t 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, VISIT which, 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 **val;

srand(time(NULL));
for (int i = 0; i < 12; i++) {
int *ptr = xmalloc(sizeof(*ptr));
*ptr = rand() & 0xff;
val = tsearch(ptr, &root, compare);
if (val == NULL)
exit(EXIT_FAILURE);
else if (*val != ptr)
free(ptr);
}
twalk(root, action);
tdestroy(root, free);
exit(EXIT_SUCCESS);
}

関 連 項 目

bsearch (3), hsearch (3), lsearch (3) qsort (3)

こ の 文 書 に つ い て

こ の man ペ ー ジ は Linux man-pages プ ロ ジ ェ ク ト の リ リ ー ス 5.10 の 一 部 で あ る 。 プ ロ ジ ェ ク ト の 説 明 と バ グ 報 告 に 関 す る 情 報 は https://www.kernel.org/doc/man-pages/ に 書 か れ て い る 。