名 前
insque, remque − キ ュ ー に ア イ テ ム を 挿 入 /削 除 す る
書 式
#include <search.h>
void insque(void *elem, void *prev);
void remque(void *elem);
glibc 向 け の 機 能 検 査 マ ク ロ の 要 件 (feature_test_macros(7) 参 照 ):
insque(), remque():
_SVID_SOURCE || _XOPEN_SOURCE >= 500 || _XOPEN_SOURCE && _XOPEN_SOURCE_EXTENDED
説 明
関 数 insque() と remque() は 双 方 向 連 結 リ ス ト (doubly−linked list) を 操 作 す る 。 リ ス ト 中 の そ れ ぞ れ の 要 素 は 、 最 初 の 二 つ の 要 素 が そ れ ぞ れ 次 と 前 へ の ポ イ ン タ ー で あ る よ う な 構 造 体 で あ る 。 リ ン ク リ ス ト は 、 線 形 (linear) か 環 状 (circular) の ど ち ら か に な る (線 形 の 場 合 に は 、 リ ス ト の 末 尾 で は 次 へ の ポ イ ン タ ー が NULL に な り 、 リ ス ト の 先 頭 で は 前 へ の ポ イ ン タ ー が NULL に な る )。
insque() 関 数 は elem で 示 さ れ る 要 素 を prev で 示 さ れ る 要 素 の 直 後 に 挿 入 す る 。 リ ス ト が 線 形 の 場 合 、 insque(elem, NULL) を 呼 び 出 す と 、 リ ス ト の 最 初 の 要 素 を 挿 入 す る こ と が で き る 。 こ の 呼 び 出 し を 行 う と elem の 次 へ の ポ イ ン タ ー と 前 へ の ポ イ ン タ ー に 共 に NULL が 設 定 さ れ る 。 リ ス ト が 環 状 の 場 合 、 呼 び 出 す 側 が 、 最 初 の 要 素 の 次 へ の ポ イ ン タ ー と 前 へ の ポ イ ン タ ー が 自 分 自 身 を 指 し 、 ま た insque() の 呼 び 出 し で prev 引 き 数 が 最 初 の 要 素 を 指 す よ う に 保 証 し な け れ ば な ら な い 。
remque() 関 数 は elem で 示 さ れ る 要 素 を 双 方 向 連 結 リ ス ト か ら 取 り 除 く 。
準 拠
POSIX.1−2001.
注 意
伝 統 的 に (SunOS, Linux libc 4,5 で は ) こ れ ら の 関 数 の 引 き 数 は struct qelem *型 で あ り 、 こ れ は 以 下 の よ う に 定 義 さ れ て い る 。
struct qelem {
struct qelem *q_forw;
struct qelem *q_back;
char q_data[1]; }; こ の 定 義
は <search.h> を イ ン
ク ル ー ド す る
前 に _GNU_SOURCE を 定
義 す る こ と で
得 ら れ る 。 こ
れ ら の 関 数 の
プ ロ ト タ イ プ
の 置 か れ る 場
所 は 、 UNIX の 種 類
に よ り 異 な る
。 上 記 は POSIX 版 で
あ る 。 <string.h> に
あ る シ ス テ ム
も あ る 。
バ グ
glibc 2.4 以 前 で は prev に NULL を 指 定 す る こ と が で き な か っ た 。 そ の 結 果 、 線 形 の リ ス ト を 作 成 す る た め に は 、 呼 び 出 し 側 は 、 最 初 の 呼 び 出 し で 、 リ ス ト の 最 初 の 2 つ の 要 素 を 持 ち 、 各 要 素 の 次 へ の ポ イ ン タ ー と 前 へ の ポ イ ン タ ー を 適 切 に 初 期 化 し た リ ス ト を 作 成 し な け れ ば な ら な か っ た 。
例
次 の プ ロ グ ラ ム は insque() の 使 用 法 を 示 し た も の で あ る 。 下 記 は プ ロ グ ラ ム の 実 行 例 で あ る 。
$ ./a.out
−c a b c
Traversing completed list:
a
b
c
That was a circular list プ ロ グ
ラ ム の ソ ー
ス
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <search.h>
struct element
{
struct element *forward;
struct element *backward;
char *name; };
static struct
element *
new_element(void)
{
struct element *e;
e =
malloc(sizeof(struct element));
if (e == NULL) {
fprintf(stderr, "malloc() failed\n");
exit(EXIT_FAILURE); }
return e; }
int
main(int argc, char *argv[])
{
struct element *first, *elem, *prev;
int circular, opt, errfnd;
/* The
"−c" command−line option can be used
to specify that the
list is circular */
errfnd = 0;
circular = 0;
while ((opt = getopt(argc, argv, "c")) !=
−1) {
switch (opt) {
case ’c’:
circular = 1;
break;
default:
errfnd = 1;
break; } }
if (errfnd ||
optind >= argc) {
fprintf(stderr, "Usage: %s [−c]
string...\n", argv[0]);
exit(EXIT_FAILURE); }
/* Create first element and place it in the linked list */
elem =
new_element();
first = elem;
elem−>name = argv[optind];
if (circular) {
elem−>forward = elem;
elem−>backward = elem;
insque(elem, elem); }
else {
insque(elem, NULL); }
/* Add remaining command−line arguments as list elements */
while (++optind
< argc) {
prev = elem;
elem =
new_element();
elem−>name = argv[optind];
insque(elem, prev); }
/* Traverse the list from the start, printing element names */
printf("Traversing
completed list:\n");
elem = first;
do {
printf(" %s\n", elem−>name);
elem = elem−>forward; }
while (elem != NULL && elem != first);
if (elem ==
first)
printf("That was a circular list\n");
exit(EXIT_SUCCESS); }
こ の 文 書 に つ い て
こ の man ペ ー ジ は Linux man−pages プ ロ ジ ェ ク ト の リ リ ー ス 3.79 の 一 部 で あ る 。 プ ロ ジ ェ ク ト の 説 明 と バ グ 報 告 に 関 す る 情 報 は http://www.kernel.org/doc/man−pages/ に 書 か れ て い る 。