draft/man3/insque.3

   1 .\" peter memishian -- meem@gnu.ai.mit.edu
   2 .\" $Id: insque.3,v 1.2 1996/10/30 21:03:39 meem Exp meem $
   3 .\" and Copyright (c) 2010, Michael Kerrisk <mtk.manpages@gmail.com>
   4 .\"
   5 .\" Permission is granted to make and distribute verbatim copies of this
   6 .\" manual provided the copyright notice and this permission notice are
   7 .\" preserved on all copies.
   8 .\"
   9 .\" Permission is granted to copy and distribute modified versions of this
  10 .\" manual under the conditions for verbatim copying, provided that the
  11 .\" entire resulting derived work is distributed under the terms of a
  12 .\" permission notice identical to this one.
  13 .\"
  14 .\" Since the Linux kernel and libraries are constantly changing, this
  15 .\" manual page may be incorrect or out-of-date.  The author(s) assume no
  16 .\" responsibility for errors or omissions, or for damages resulting from
  17 .\" the use of the information contained herein.  The author(s) may not
  18 .\" have taken the same level of care in the production of this manual,
  19 .\" which is licensed free of charge, as they might when working
  20 .\" professionally.
  21 .\"
  22 .\" Formatted or processed versions of this manual, if unaccompanied by
  23 .\" the source, must acknowledge the copyright and authors of this work.
  24 .\"
  25 .\" References consulted:
  26 .\"   Linux libc source code (5.4.7)
  27 .\"   Solaris 2.x, OSF/1, and HP-UX manpages
  28 .\"   Curry's "UNIX Systems Programming for SVR4" (O'Reilly & Associates 1996)
  29 .\"
  30 .\" Changed to POSIX, 2003-08-11, aeb+wh
  31 .\" mtk, 2010-09-09: Noted glibc 2.4 bug, added info on circular
  32 .\"     lists, added example program
  33 .\"
  34 .\"*******************************************************************
  35 .\"
  36 .\" This file was generated with po4a. Translate the source file.
  37 .\"
  38 .\"*******************************************************************
  39 .TH INSQUE 3 2010\-09\-09 "" "Linux Programmer's Manual"
  40 .SH 名前
  41 insque, remque \- キューにアイテムを挿入/削除する
  42 .SH 書式
  43 .nf
  44 \fB#include <search.h>\fP
  45 .sp
  46 \fBvoid insque(void *\fP\fIelem\fP\fB, void *\fP\fIprev\fP\fB);\fP
  47
  48 \fBvoid remque(void *\fP\fIelem\fP\fB);\fP
  49 .fi
  50 .sp
  51 .in -4n
  52 glibc 向けの機能検査マクロの要件 (\fBfeature_test_macros\fP(7)  参照):
  53 .in
  54 .sp
  55 .ad l
  56 \fBinsque\fP(), \fBremque\fP():
  57 .RS 4
  58 _SVID_SOURCE || _XOPEN_SOURCE\ >=\ 500 || _XOPEN_SOURCE\ &&\ _XOPEN_SOURCE_EXTENDED
  59 .RE
  60 .ad
  61 .SH 説明
  62 関数 \fBinsque\fP() と \fBremque\fP() は双方向連結リスト (doubly\-linked list) を
  63 操作する。リスト中のそれぞれの要素は、最初の二つの要素がそれぞれ次と前への
  64 ポインタであるような構造体である。
  65 リンクリストは、線形 (linear) か環状 (circular) のどちらかになる
  66 (線形の場合には、リストの末尾では次へのポインタが NULL になり、
  67 リストの先頭では前へのポインタが NULL になる)。
  68
  69 \fBinsque\fP() 関数は \fIelem\fP で示される要素を \fIprev\fP で示される
  70 要素の直後に挿入する。
  71
  72 リストが線形の場合、\fIinsque(elem, NULL)\fP を呼び出すと、
  73 リストの最初の要素を挿入することができる。
  74 この呼び出しを行うと \fIelem\fP の次へのポインタと前へのポインタに
  75 共に NULL が設定される。
  76
  77 リストが環状の場合、呼び出す側が、最初の要素の次へのポインタと前へのポインタ
  78 が自分自身を指し、また  \fBinsque\fP() の呼び出しで \fIprev\fP 引き数が最初の要素
  79 を指すように保証しなければならない。
  80
  81 \fBremque\fP() 関数は \fIelem\fP で示される要素を双方向連結リストから取り除く。
  82 .SH 準拠
  83 POSIX.1\-2001.
  84 .SH 注意
  85 伝統的に (SunOS, Linux libc 4,5 では) これらの関数の引数は \fIstruct qelem
  86 *\fP型であり、これは以下のように定義されている。
  87
  88 .in +4n
  89 .nf
  90 struct qelem {
  91     struct qelem *q_forw;
  92     struct qelem *q_back;
  93     char          q_data[1];
  94 };
  95 .fi
  96 .in
  97
  98 この定義は \fI<search.h>\fP をインクルードする前に \fB_GNU_SOURCE\fP を定義することで得られる。
  99
 100 これらの関数のプロトタイプの置かれる場所は、UNIX の種類により異なる。
 101 上記は POSIX 版である。 \fI<string.h>\fP にあるシステムもある。
 102 Linux libc4 と libc5 ではプロトタイプは \fI<stdlib.h>\fP に置かれている。
 103 .SH バグ
 104 glibc 2.4 以前では \fIprev\fP に NULL を指定することができなかった。
 105 その結果、線形のリストを作成するためには、
 106 呼び出し側は、最初の呼び出しで、リストの最初の 2 つの要素を持ち、
 107 各要素の次へのポインタと前へのポインタを適切に初期化したリストを
 108 作成しなければならなかった。
 109 .SH 例
 110 次のプログラムは \fBinsque\fP() の使用法を示したものである。
 111 下記はプログラムの実行例である。
 112 .in +4n
 113 .nf
 114
 115 $ \fB./a.out \-c a b c\fP
 116 Traversing completed list:
 117     a
 118     b
 119     c
 120 That was a circular list
 121 .fi
 122 .in
 123 .SS プログラムのソース
 124 \&
 125 .nf
 126 #include <stdio.h>
 127 #include <stdlib.h>
 128 #include <unistd.h>
 129 #include <search.h>
 130
 131 struct element {
 132     struct element *forward;
 133     struct element *backward;
 134     char *name;
 135 };
 136
 137 static struct element *
 138 new_element(void)
 139 {
 140     struct element *e;
 141
 142     e = malloc(sizeof(struct element));
 143     if (e == NULL) {
 144         fprintf(stderr, "malloc() failed\en");
 145         exit(EXIT_FAILURE);
 146     }
 147
 148     return e;
 149 }
 150
 151 int
 152 main(int argc, char *argv[])
 153 {
 154     struct element *first, *elem, *prev;
 155     int circular, opt, errfnd;
 156
 157     /* The "\-c" command\-line option can be used to specify that the
 158        list is circular */
 159
 160     errfnd = 0;
 161     circular = 0;
 162     while ((opt = getopt(argc, argv, "c")) != \-1) {
 163         switch (opt) {
 164         case 'c':
 165             circular = 1;
 166             break;
 167         default:
 168             errfnd = 1;
 169             break;
 170         }
 171     }
 172
 173     if (errfnd || optind >= argc) {
 174         fprintf(stderr,  "Usage: %s [\-c] string...\en", argv[0]);
 175         exit(EXIT_FAILURE);
 176     }
 177
 178     /* Create first element and place it in the linked list */
 179
 180     elem = new_element();
 181     first = elem;
 182
 183     elem\->name = argv[optind];
 184
 185     if (circular) {
 186         elem\->forward = elem;
 187         elem\->backward = elem;
 188         insque(elem, elem);
 189     } else {
 190         insque(elem, NULL);
 191     }
 192
 193     /* Add remaining command\-line arguments as list elements */
 194
 195     while (++optind < argc) {
 196         prev = elem;
 197
 198         elem = new_element();
 199         elem\->name = argv[optind];
 200         insque(elem, prev);
 201     }
 202
 203     /* Traverse the list from the start, printing element names */
 204
 205     printf("Traversing completed list:\en");
 206     elem = first;
 207     do {
 208         printf("    %s\en", elem\->name);
 209         elem = elem\->forward;
 210     } while (elem != NULL && elem != first);
 211
 212     if (elem == first)
 213         printf("That was a circular list\en");
 214
 215     exit(EXIT_SUCCESS);
 216 }
 217 .fi