.\" peter memishian -- meem@gnu.ai.mit.edu
.\" $Id: insque.3,v 1.2 1996/10/30 21:03:39 meem Exp meem $
+.\" and Copyright (c) 2010, Michael Kerrisk <mtk.manpages@gmail.com>
.\"
.\" Permission is granted to make and distribute verbatim copies of this
.\" manual provided the copyright notice and this permission notice are
.\" Permission is granted to copy and distribute modified versions of this
.\" manual under the conditions for verbatim copying, provided that the
.\" entire resulting derived work is distributed under the terms of a
-.\" permission notice identical to this one
+.\" permission notice identical to this one.
.\"
.\" Since the Linux kernel and libraries are constantly changing, this
.\" manual page may be incorrect or out-of-date. The author(s) assume no
.\" Curry's "UNIX Systems Programming for SVR4" (O'Reilly & Associates 1996)
.\"
.\" Changed to POSIX, 2003-08-11, aeb+wh
+.\" mtk, 2010-09-09: Noted glibc 2.4 bug, added info on circular
+.\" lists, added example program
.\"
-.\" Japanese Version Copyright (c) 1998 AKAMATSU Kazuo
-.\" all rights reserved.
-.\" Translated Thu Jan 7 16:00 JST 1999
-.\" by AKAMATSU Kazuo
-.\" Updated Sun Sep 14 JST 2003 by Kentaro Shirakata <argrath@ub32.org>
+.\"*******************************************************************
.\"
-.TH INSQUE 3 2008-07-11 "" "Linux Programmer's Manual"
+.\" This file was generated with po4a. Translate the source file.
+.\"
+.\"*******************************************************************
+.TH INSQUE 3 2010\-09\-09 "" "Linux Programmer's Manual"
.SH 名前
insque, remque \- キューにアイテムを挿入/削除する
.SH 書式
.nf
-.B #include <search.h>
+\fB#include <search.h>\fP
.sp
-.BI "void insque(void *" elem ", void *" prev );
+\fBvoid insque(void *\fP\fIelem\fP\fB, void *\fP\fIprev\fP\fB);\fP
-.BI "void remque(void *" elem );
+\fBvoid remque(void *\fP\fIelem\fP\fB);\fP
.fi
.sp
.in -4n
-glibc 向けの機能検査マクロの要件
-.RB ( feature_test_macros (7)
-参照):
+glibc 向けの機能検査マクロの要件 (\fBfeature_test_macros\fP(7) 参照):
.in
.sp
-.BR insque (),
-.BR remque ():
-_SVID_SOURCE || _XOPEN_SOURCE\ >=\ 500
+.ad l
+\fBinsque\fP(), \fBremque\fP():
+.RS 4
+_SVID_SOURCE || _XOPEN_SOURCE\ >=\ 500 || _XOPEN_SOURCE\ &&\ _XOPEN_SOURCE_EXTENDED
+.RE
+.ad
.SH 説明
-.BR insque ()
-と
-.BR remque ()
-は双方向連結リスト (doubly-linked list) を操作する関数である。
-リスト中のそれぞれの要素は、最初の二つの構造体要素が
-次と前へのポインタであるような構造体である。
-
-.BR insque ()
-は \fIelem\fP で示される要素を \fIprev\fP で示される
-要素の直後に挿入する。 \fIprev\fP は NULL であってはならない。
-
-.BR remque ()
-は \fIelem\fP で示される要素を双方向連結リストから取り除く。
+関数 \fBinsque\fP() と \fBremque\fP() は双方向連結リスト (doubly\-linked list) を
+操作する。リスト中のそれぞれの要素は、最初の二つの要素がそれぞれ次と前への
+ポインタであるような構造体である。
+リンクリストは、線形 (linear) か環状 (circular) のどちらかになる
+(線形の場合には、リストの末尾では次へのポインタが NULL になり、
+リストの先頭では前へのポインタが NULL になる)。
+
+\fBinsque\fP() 関数は \fIelem\fP で示される要素を \fIprev\fP で示される
+要素の直後に挿入する。
+
+リストが線形の場合、\fIinsque(elem, NULL)\fP を呼び出すと、
+リストの最初の要素を挿入することができる。
+この呼び出しを行うと \fIelem\fP の次へのポインタと前へのポインタに
+共に NULL が設定される。
+
+リストが環状の場合、呼び出す側が、最初の要素の次へのポインタと前へのポインタ
+が自分自身を指し、また \fBinsque\fP() の呼び出しで \fIprev\fP 引き数が最初の要素
+を指すように保証しなければならない。
+
+\fBremque\fP() 関数は \fIelem\fP で示される要素を双方向連結リストから取り除く。
.SH 準拠
-POSIX.1-2001.
+POSIX.1\-2001.
.SH 注意
-伝統的に (SunOS, Linux libc 4,5 では) これらの関数の引数は
-\fIstruct qelem *\fP型であり、これは以下のように定義されている。
+伝統的に (SunOS, Linux libc 4,5 では) これらの関数の引数は \fIstruct qelem
+*\fP型であり、これは以下のように定義されている。
.in +4n
.nf
.fi
.in
-この定義は \fI<search.h>\fP をインクルードする前に
-.B _GNU_SOURCE
-を定義することで得られる。
+この定義は \fI<search.h>\fP をインクルードする前に \fB_GNU_SOURCE\fP を定義することで得られる。
+
+これらの関数のプロトタイプの置かれる場所は、UNIX の種類により異なる。
+上記は POSIX 版である。 \fI<string.h>\fP にあるシステムもある。
+Linux libc4 と libc5 ではプロトタイプは \fI<stdlib.h>\fP に置かれている。
+.SH バグ
+glibc 2.4 以前では \fIprev\fP に NULL を指定することができなかった。
+その結果、線形のリストを作成するためには、
+呼び出し側は、最初の呼び出しで、リストの最初の 2 つの要素を持ち、
+各要素の次へのポインタと前へのポインタを適切に初期化したリストを
+作成しなければならなかった。
+.SH 例
+次のプログラムは \fBinsque\fP() の使用法を示したものである。
+下記はプログラムの実行例である。
+.in +4n
+.nf
+
+$ \fB./a.out \-c a b c\fP
+Traversing completed list:
+ a
+ b
+ c
+That was a circular list
+.fi
+.in
+.SS プログラムのソース
+\&
+.nf
+#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\en");
+ exit(EXIT_FAILURE);
+ }
-これらの関数のプロトタイプの置かれる場所は、Unix の種類により異なる。
-上記は POSIX 版である。
-\fI<string.h>\fP にあるシステムもある。
-Linux libc4 と libc5 は \fI<stdlib.h>\fP にプロトタイプを置いている。
+ 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...\en", 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:\en");
+ elem = first;
+ do {
+ printf(" %s\en", elem\->name);
+ elem = elem\->forward;
+ } while (elem != NULL && elem != first);
+
+ if (elem == first)
+ printf("That was a circular list\en");
+
+ exit(EXIT_SUCCESS);
+}
+.fi
OSDN Git Service
