.\" Translated Thu Sep 2 04:41:11 JST 2004
.\" by Yuichi SATO <ysato444@yahoo.co.jp>
.\"
-.\"WORD: circular queue ½Û´Ä¥¥å¡¼
+.\"WORD: circular queue 循ç\92°ã\82ã\83¥ã\83¼
.\"
.TH QUEUE 3 2007-12-28 "Linux" "Linux Programmer's Manual"
.\"O .SH NAME
-.SH ̾Á°
+.SH 名前
.\"O LIST_ENTRY, LIST_HEAD, LIST_INIT, LIST_INSERT_AFTER, \
.\"O LIST_INSERT_HEAD, LIST_REMOVE, TAILQ_ENTRY, TAILQ_HEAD, \
.\"O TAILQ_INIT, TAILQ_INSERT_AFTER, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, \
TAILQ_REMOVE, CIRCLEQ_ENTRY, CIRCLEQ_HEAD, CIRCLEQ_INIT, \
CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE, \
CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, \
-CIRCLEQ_REMOVE \- ¥ê¥¹¥È¡¦¥Æ¡¼¥ë (tail) ¥¥å¡¼¡¦½Û´Ä¥¥å¡¼¤Î¼ÂÁõ
+CIRCLEQ_REMOVE \- リスト・テール (tail) キュー・循環キューの実装
.\"Osato:
-.\"Osato: tail queue ¤ÎÎɤ¤Ìõ¸ì¤¬Ê¬¤«¤é¤Ê¤¤¤Î¤Ç¡¢¤È¤ê¤¢¤¨¤º¥«¥¿¥«¥Ê¤Ë¤¹¤ë¡£
+.\"Osato: tail queue の良い訳語が分からないので、とりあえずカタカナにする。
.\"Osato:
.\"O .SH SYNOPSIS
-.SH ½ñ¼°
+.SH 書式
.nf
.B #include <sys/queue.h>
.BI " TYPE *" elm ", CIRCLEQ_ENTRY " NAME );
.fi
.\"O .SH DESCRIPTION
-.SH ÀâÌÀ
+.SH 説明
.\"O These macros define and operate on three types of data structures:
.\"O lists, tail queues, and circular queues.
.\"O All three structures support the following functionality:
-¤³¤ì¤é¤Î¥Þ¥¯¥í¤Ï¡¢¼¡¤Î 3 ¤Ä¤Î¥Ç¡¼¥¿¹½Â¤¤òÄêµÁ¤·¤ÆÁàºî¤¹¤ë:
-¥ê¥¹¥È¡¦¥Æ¡¼¥ë¥¥å¡¼¡¦½Û´Ä¥¥å¡¼¡£
-3 ¤Ä¤Î¥Ç¡¼¥¿¹½Â¤¤¹¤Ù¤Æ¤Ë¤ª¤¤¤Æ°Ê²¼¤Îµ¡Ç½¤¬¥µ¥Ý¡¼¥È¤µ¤ì¤Æ¤¤¤ë:
+これらのマクロは、次の 3 つのデータ構造を定義して操作する:
+リスト・テールキュー・循環キュー。
+3 つのデータ構造すべてにおいて以下の機能がサポートされている:
.sp
.RS 4
.PD 0
.IP * 4
.\"O Insertion of a new entry at the head of the list.
-¿·¤¿¤Ê¥¨¥ó¥È¥ê¤ò¥ê¥¹¥È¤ÎÀèƬ¤ËÁÞÆþ¤¹¤ë¡£
+新たなエントリをリストの先頭に挿入する。
.IP *
.\"O Insertion of a new entry after any element in the list.
-¿·¤¿¤Ê¥¨¥ó¥È¥ê¤ò¥ê¥¹¥È¤Î¤É¤ÎÍ×ÁǤè¤ê¤â¸å¤ËÁÞÆþ¤¹¤ë¡£
+新たなエントリをリストのどの要素よりも後に挿入する。
.IP *
.\"O Removal of any entry in the list.
-¥ê¥¹¥È¤ÎǤ°Õ¤Î¥¨¥ó¥È¥ê¤òºï½ü¤¹¤ë¡£
+リストの任意のエントリを削除する。
.IP *
.\"O Forward traversal through the list.
-¥ê¥¹¥È¤ò½çÊý¸þ¤Ëé¤ë¡£
+リストを順方向に辿る。
.PD
.RE
.PP
.\"O Lists are the simplest of the three data structures and support
.\"O only the above functionality.
-¥ê¥¹¥È¤Ï 3 ¤Ä¤Î¥Ç¡¼¥¿¹½Â¤¤ÎÃæ¤ÇºÇ¤âñ½ã¤Ç¤¢¤ê¡¢
-¾åµ¤Îµ¡Ç½¤Î¤ß¤ò¥µ¥Ý¡¼¥È¤¹¤ë¡£
+リストは 3 つのデータ構造の中で最も単純であり、
+上記の機能のみをサポートする。
.\"O Tail queues add the following functionality:
-¥Æ¡¼¥ë¥¥å¡¼¤Ï°Ê²¼¤Îµ¡Ç½¤òÄɲ乤ë:
+テールキューは以下の機能を追加する:
.RS 4
.IP * 4
.\"O Entries can be added at the end of a list.
-¥¨¥ó¥È¥ê¤ò¥ê¥¹¥È¤ÎºÇ¸å¤ËÄɲäǤ¤ë¡£
+エントリをリストの最後に追加できる。
.RE
.PP
.\"O However:
-¤¿¤À¤·:
+ただし:
.sp
.RS 4
.PD 0
.IP 1. 4
.\"O All list insertions and removals must specify the head of the list.
-Á´¤Æ¤Î¥ê¥¹¥ÈÁÞÆþ¤Èºï½ü¤Ë¤ª¤¤¤Æ¡¢¥ê¥¹¥È¤ÎÀèƬ¤ò»ØÄꤷ¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£
+全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
.IP 2.
.\"O Each head entry requires two pointers rather than one.
-³ÆÀèƬ¥¨¥ó¥È¥ê¤Ï 1 ¤Ä¤Ç¤Ï¤Ê¤¯ 2 ¤Ä¤Î¥Ý¥¤¥ó¥¿¤òɬÍפȤ¹¤ë¡£
+各先頭エントリは 1 つではなく 2 つのポインタを必要とする。
.IP 3.
.\"O Code size is about 15% greater and operations run about 20% slower
.\"O than lists.
-¥ê¥¹¥È¤ÈÈæ¤Ù¤Æ¡¢¥³¡¼¥É¥µ¥¤¥º¤Ï 15% Â礤¯¤Ê¤ê¡¢Áàºî¤Ï 20% ÃÙ¤¯¤Ê¤ë¡£
+リストと比べて、コードサイズは 15% 大きくなり、操作は 20% 遅くなる。
.PD
.RE
.PP
.\"O Circular queues add the following functionality:
-½Û´Ä¥¥å¡¼¤Ï°Ê²¼¤Îµ¡Ç½¤òÄɲ乤ë:
+循環キューは以下の機能を追加する:
.sp
.RS 4
.PD 0
.IP * 4
.\"O Entries can be added at the end of a list.
-¥¨¥ó¥È¥ê¤ò¥ê¥¹¥È¤ÎºÇ¸å¤ËÄɲäǤ¤ë¡£
+エントリをリストの最後に追加できる。
.IP *
.\"O Entries can be added before another entry.
-¥¨¥ó¥È¥ê¤ò¾¤Î¥¨¥ó¥È¥ê¤ÎÁ°¤ËÄɲäǤ¤ë¡£
+エントリを他のエントリの前に追加できる。
.IP *
.\"O They may be traversed backward, from tail to head.
-µÕÊý¸þ¤ËËöÈø¤«¤éÀèƬ¤Øé¤ë¤³¤È¤¬¤Ç¤¤ë¡£
+逆方向に末尾から先頭へ辿ることができる。
.PD
.RE
.PP
.\"O However:
-¤¿¤À¤·:
+ただし:
.sp
.RS 4
.PD 0
.IP 1. 4
.\"O All list insertions and removals must specify the head of the list.
-Á´¤Æ¤Î¥ê¥¹¥ÈÁÞÆþ¤Èºï½ü¤Ë¤ª¤¤¤Æ¡¢¥ê¥¹¥È¤ÎÀèƬ¤ò»ØÄꤷ¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£
+全てのリスト挿入と削除において、リストの先頭を指定しなければならない。
.IP 2.
.\"O Each head entry requires two pointers rather than one.
-³ÆÀèƬ¥¨¥ó¥È¥ê¤Ï 1 ¤Ä¤Ç¤Ï¤Ê¤¯ 2 ¤Ä¤Î¥Ý¥¤¥ó¥¿¤òɬÍפȤ¹¤ë¡£
+各先頭エントリは 1 つではなく 2 つのポインタを必要とする。
.IP 3.
.\"O The termination condition for traversal is more complex.
-é¤ëºÝ¤Î½ªÎ»¾ò·ï¤¬¤è¤êÊ£»¨¤Ç¤¢¤ë¡£
+辿る際の終了条件がより複雑である。
.IP 4.
.\"O Code size is about 40% greater and operations run about 45% slower
.\"O than lists.
-¥ê¥¹¥È¤ÈÈæ¤Ù¤Æ¡¢¥³¡¼¥É¥µ¥¤¥º¤Ï 40% Â礤¯¤Ê¤ê¡¢Áàºî¤Ï 45% ÃÙ¤¯¤Ê¤ë¡£
+リストと比べて、コードサイズは 40% 大きくなり、操作は 45% 遅くなる。
.PD
.RE
.PP
.\"O .BR CIRCLEQ_ENTRY ,
.\"O named
.\"O .IR NAME .
-¥Þ¥¯¥íÄêµÁ¤Ë¤ª¤¤¤Æ
+マクロ定義において
.I TYPE
-¤Ï¥æ¡¼¥¶ÄêµÁ¹½Â¤ÂΤÎ̾Á°¤Ç¤¢¤ê¡¢
+はユーザ定義構造体の名前であり、
.BR LIST_ENTRY ,
.BR TAILQ_ENTRY ,
.BR CIRCLEQ_ENTRY
-¤Î²¿¤ì¤«·¿¤Î¥Õ¥£¡¼¥ë¥É¤È
-»ØÄꤵ¤ì¤¿
+の何れか型のフィールドと
+指定された
.I NAME
-¤ò´Þ¤Þ¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£
+を含まなければならない。
.\"O The argument
.\"O .I HEADNAME
.\"O is the name of a user-defined structure that must be declared
.\"O .BR TAILQ_HEAD ,
.\"O or
.\"O .BR CIRCLEQ_HEAD .
-°ú¤¿ô
+引き数
.I HEADNAME
-¤Ï¥æ¡¼¥¶ÄêµÁ¹½Â¤ÂΤÎ̾Á°¤Ç¤¢¤ê¡¢
-¥Þ¥¯¥í
+はユーザ定義構造体の名前であり、
+マクロ
.BR LIST_HEAD ,
.BR TAILQ_HEAD ,
.BR CIRCLEQ_HEAD
-¤òÍѤ¤¤ÆÀë¸À¤µ¤ì¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£
+を用いて宣言されなければならない。
.\"O See the examples below for further explanation of how these
.\"O macros are used.
-¤³¤ì¤é¤Î¥Þ¥¯¥í¤¬¤É¤Î¤è¤¦¤Ë»È¤ï¤ì¤ë¤«¤Ë¤Ä¤¤¤Æ¤Î¹¹¤Ê¤ëÀâÌÀ¤Ï¡¢
-°Ê²¼¤ÎÎã¤ò»²¾È¤¹¤ë¤³¤È¡£
+これらのマクロがどのように使われるかについての更なる説明は、
+以下の例を参照すること。
.\"O .SS LISTS
-.SS ¥ê¥¹¥È
+.SS リスト
.\"O A list is headed by a structure defined by the
.\"O .B LIST_HEAD
.\"O macro.
-¥ê¥¹¥È¤ÎÀèƬ¤Ë¤Ï¡¢
+リストの先頭には、
.B LIST_HEAD
-¥Þ¥¯¥í¤ÇÄêµÁ¤µ¤ì¤ë¹½Â¤ÂΤ¬ÃÖ¤«¤ì¤ë¡£
+マクロで定義される構造体が置かれる。
.\"O This structure contains a single pointer to the first element
.\"O on the list.
-¤³¤Î¹½Â¤ÂΤϥꥹ¥È¤ÎºÇ½é¤ÎÍ×ÁǤؤΥݥ¤¥ó¥¿¤ò 1 ¤Ä´Þ¤à¡£
+この構造体はリストの最初の要素へのポインタを 1 つ含む。
.\"O The elements are doubly linked so that an arbitrary element can be
.\"O removed without traversing the list.
-Í×ÁÇ¤Ï 2 ½Å¤Ë¥ê¥ó¥¯¤µ¤ì¤Æ¤ª¤ê¡¢
-Ǥ°Õ¤ÎÍ×ÁǤϥꥹ¥È¤òé¤é¤º¤Ëºï½ü¤Ç¤¤ë¡£
+要素は 2 重にリンクされており、
+任意の要素はリストを辿らずに削除できる。
.\"O New elements can be added to the list after an existing element or
.\"O at the head of the list.
-¿·¤·¤¤Í×ÁǤϴû¸¤ÎÍ×ÁǤθå¤Þ¤¿¤Ï¥ê¥¹¥È¤ÎÀèƬ¤ËÄɲäǤ¤ë¡£
+新しい要素は既存の要素の後またはリストの先頭に追加できる。
.\"O A
.\"O .B LIST_HEAD
.\"O structure is declared as follows:
.B LIST_HEAD
-¹½Â¤ÂΤϰʲ¼¤Î¤è¤¦¤ËÀë¸À¤µ¤ì¤Æ¤¤¤ë:
+構造体は以下のように宣言されている:
.in +4n
.nf
.\"O is the name of the structure to be defined, and
.\"O .I TYPE
.\"O is the type of the elements to be linked into the list.
-¤³¤³¤Ç
+ここで
.I HEADNAME
-¤ÏÄêµÁ¤µ¤ì¤ë¹½Â¤ÂΤÎ̾Á°¤Ç¤¢¤ê¡¢
+は定義される構造体の名前であり、
.I TYPE
-¤Ï¥ê¥ó¥¯Æâ¤Ç¥ê¥ó¥¯¤µ¤ì¤ëÍ×ÁǤη¿¤Ç¤¢¤ë¡£
+はリンク内でリンクされる要素の型である。
.\"O A pointer to the head of the list can later be declared as:
-¥ê¥¹¥È¤ÎÀèƬ¤Ø¤Î¥Ý¥¤¥ó¥¿¤Ï¡¢¤½¤Î¸å¤Ç¼¡¤Î¤è¤¦¤ËÀë¸À¤µ¤ì¤ë:
+リストの先頭へのポインタは、その後で次のように宣言される:
.in +4n
.nf
.\"O and
.\"O .IR "headp"
.\"O are user selectable.)
-(̾Á°
+(名前
.IR "head"
-¤È
+と
.IR "headp"
-¤Ï¥æ¡¼¥¶¤¬ÁªÂò¤Ç¤¤ë¡£)
+はユーザが選択できる。)
.PP
.\"O The macro
.\"O .B LIST_ENTRY
.\"O declares a structure that connects the elements in
.\"O the list.
-¥Þ¥¯¥í
+マクロ
.B LIST_ENTRY
-¤Ï¥ê¥¹¥È¤ÎÍ×ÁǤòÀܳ¤¹¤ë¹½Â¤ÂΤòÀë¸À¤¹¤ë¡£
+はリストの要素を接続する構造体を宣言する。
.PP
.\"O The macro
.\"O .B LIST_INIT
.\"O initializes the list referenced by
.\"O .IR head .
-¥Þ¥¯¥í
+マクロ
.B LIST_INIT
-¤Ï
+は
.I head
-¤Ç»²¾È¤µ¤ì¤ë¥ê¥¹¥È¤ò½é´ü²½¤¹¤ë¡£
+で参照されるリストを初期化する。
.PP
.\"O The macro
.\"O .B LIST_INSERT_HEAD
.\"O inserts the new element
.\"O .I elm
.\"O at the head of the list.
-¥Þ¥¯¥í
+マクロ
.B LIST_INSERT_HEAD
-¤Ï¿·¤¿¤ÊÍ×ÁÇ
+は新たな要素
.I elm
-¤ò¥ê¥¹¥È¤ÎÀèƬ¤ËÁÞÆþ¤¹¤ë¡£
+をリストの先頭に挿入する。
.PP
.\"O The macro
.\"O .B LIST_INSERT_AFTER
.\"O .I elm
.\"O after the element
.\"O .I listelm .
-¥Þ¥¯¥í
+マクロ
.B LIST_INSERT_AFTER
-¤Ï¿·¤¿¤ÊÍ×ÁÇ
+は新たな要素
.I elm
-¤òÍ×ÁÇ
+を要素
.I listelm
-¤Î¸å¤ËÁÞÆþ¤¹¤ë¡£
+の後に挿入する。
.PP
.\"O The macro
.\"O .B LIST_REMOVE
.\"O removes the element
.\"O .I elm
.\"O from the list.
-¥Þ¥¯¥í
+マクロ
.B LIST_REMOVE
-¤ÏÍ×ÁÇ
+は要素
.I elm
-¤ò¥ê¥¹¥È¤«¤éºï½ü¤¹¤ë¡£
+をリストから削除する。
.\"O .SS LIST EXAMPLE
-.SS ¥ê¥¹¥È¤ÎÎã
+.SS リストの例
.nf
LIST_HEAD(listhead, entry) head;
.\"O struct listhead *headp; /* List head. */
-struct listhead *headp; /* ¥ê¥¹¥È¤ÎÀèƬ¡£*/
+struct listhead *headp; /* リストの先頭。*/
struct entry {
.\"O ...
.\"O LIST_ENTRY(entry) entries; /* List. */
.\"O ...
...
- LIST_ENTRY(entry) entries; /* ¥ê¥¹¥È¡£ */
+ LIST_ENTRY(entry) entries; /* リスト。 */
...
} *n1, *n2, *np;
.\"O LIST_INIT(&head); /* Initialize the list. */
-LIST_INIT(&head); /* ¥ê¥¹¥È¤ò½é´ü²½¤¹¤ë¡£*/
+LIST_INIT(&head); /* リストを初期化する。*/
.\"O n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
-n1 = malloc(sizeof(struct entry)); /* ÀèƬ¤ËÁÞÆþ¤¹¤ë¡£*/
+n1 = malloc(sizeof(struct entry)); /* 先頭に挿入する。*/
LIST_INSERT_HEAD(&head, n1, entries);
.\"O n2 = malloc(sizeof(struct entry)); /* Insert after. */
-n2 = malloc(sizeof(struct entry)); /* ¸å¤í¤ËÁÞÆþ¤¹¤ë¡£*/
+n2 = malloc(sizeof(struct entry)); /* 後ろに挿入する。*/
LIST_INSERT_AFTER(n1, n2, entries);
.\"O /* Forward traversal. */
- /* ½çÊý¸þ¤Ëé¤ë¡£*/
+ /* 順方向に辿る。*/
for (np = head.lh_first; np != NULL; np = np\->entries.le_next)
np\-> ...
.\"O while (head.lh_first != NULL) /* Delete. */
-while (head.lh_first != NULL) /* ºï½ü¤¹¤ë¡£*/
+while (head.lh_first != NULL) /* 削除する。*/
LIST_REMOVE(head.lh_first, entries);
.fi
.\"O .SS Tail Queues
-.SS ¥Æ¡¼¥ë¥¥å¡¼
+.SS ã\83\86ã\83¼ã\83«ã\82ã\83¥ã\83¼
.\"O A tail queue is headed by a structure defined by the
.\"O .B TAILQ_HEAD
.\"O macro.
-¥Æ¡¼¥ë¥¥å¡¼¤ÎÀèƬ¤Ë¤Ï
+テールキューの先頭には
.B TAILQ_HEAD
-¥Þ¥¯¥í¤ÇÄêµÁ¤µ¤ì¤ë¹½Â¤ÂΤ¬ÃÖ¤«¤ì¤ë¡£
+マクロで定義される構造体が置かれる。
.\"O This structure contains a pair of pointers,
.\"O one to the first element in the tail queue and the other to
.\"O the last element in the tail queue.
-¤³¤Î¹½Â¤ÂÎ¤Ï 1 ÁȤΥݥ¤¥ó¥¿¤ò´Þ¤ó¤Ç¤¤¤ë¡£
-1 ¤Ä¤Ï¥Æ¡¼¥ë¥¥å¡¼¤ÎºÇ½é¤ÎÍ×ÁǤؤΥݥ¤¥ó¥¿¤Ç¤¢¤ê¡¢
-¤â¤¦ 1 ¤Ä¤Ï¥Æ¡¼¥ë¥¥å¡¼¤ÎºÇ¸å¤ÎÍ×ÁǤؤΥݥ¤¥ó¥¿¤Ç¤¢¤ë¡£
+この構造体は 1 組のポインタを含んでいる。
+1 つはテールキューの最初の要素へのポインタであり、
+もう 1 つはテールキューの最後の要素へのポインタである。
.\"O The elements are doubly linked so that an arbitrary element can be
.\"O removed without traversing the tail queue.
-Í×ÁÇ¤Ï 2 ½Å¤Ë¥ê¥ó¥¯¤µ¤ì¤Æ¤ª¤ê¡¢
-Ǥ°Õ¤ÎÍ×ÁǤϥơ¼¥ë¥¥å¡¼¤òé¤é¤º¤Ëºï½ü¤Ç¤¤ë¡£
+要素は 2 重にリンクされており、
+任意の要素はテールキューを辿らずに削除できる。
.\"O New elements can be added to the tail queue after an existing element,
.\"O at the head of the tail queue, or at the end of the tail queue.
-¿·¤·¤¤Í×ÁǤϴû¸¤ÎÍ×ÁǤθå¤Þ¤¿¤Ï¥Æ¡¼¥ë¥¥å¡¼¤ÎÀèƬ¤Þ¤¿¤ÏËöÈø¤ËÄɲäǤ¤ë¡£
+新しい要素は既存の要素の後またはテールキューの先頭または末尾に追加できる。
.\"O A
.\"O .B TAILQ_HEAD
.\"O structure is declared as follows:
.B TAILQ_HEAD
-¹½Â¤ÂΤϰʲ¼¤Î¤è¤¦¤ËÄêµÁ¤µ¤ì¤Æ¤¤¤ë:
+構造体は以下のように定義されている:
.in +4n
.nf
.\"O is the name of the structure to be defined, and
.\"O .IR "TYPE"
.\"O is the type of the elements to be linked into the tail queue.
-¤³¤³¤Ç
+ここで
.Li HEADNAME
-¤ÏÄêµÁ¤µ¤ì¤ë¹½Â¤ÂΤÎ̾Á°¤Ç¤¢¤ê¡¢
+は定義される構造体の名前であり、
.Li TYPE
-¤Ï¥Æ¡¼¥ë¥¥å¡¼Æâ¤Ç¥ê¥ó¥¯¤µ¤ì¤ëÍ×ÁǤη¿¤Ç¤¢¤ë¡£
+はテールキュー内でリンクされる要素の型である。
.\"O A pointer to the head of the tail queue can later be declared as:
-¥Æ¡¼¥ë¥¥å¡¼¤ÎÀèƬ¤Ø¤Î¥Ý¥¤¥ó¥¿¤Ï¡¢¤½¤Î¸å¤Ç¼¡¤Î¤è¤¦¤ËÀë¸À¤µ¤ì¤ë:
+テールキューの先頭へのポインタは、その後で次のように宣言される:
.in +4n
.nf
.\"O and
.\"O .IR "headp"
.\"O are user selectable.)
-(̾Á°
+(名前
.IR "head"
-¤È
+と
.IR "headp"
-¤Ï¥æ¡¼¥¶¤¬ÁªÂò¤Ç¤¤ë¡£)
+はユーザが選択できる。)
.PP
.\"O The macro
.\"O .B TAILQ_ENTRY
.\"O declares a structure that connects the elements in
.\"O the tail queue.
-¥Þ¥¯¥í
+マクロ
.B TAILQ_ENTRY
-¤Ï¥Æ¡¼¥ë¥¥å¡¼¤ÎÍ×ÁǤòÀܳ¤¹¤ë¹½Â¤ÂΤòÀë¸À¤¹¤ë¡£
+はテールキューの要素を接続する構造体を宣言する。
.PP
.\"O The macro
.\"O .B TAILQ_INIT
.\"O initializes the tail queue referenced by
.\"O .IR head .
-¥Þ¥¯¥í
+マクロ
.B TAILQ_INIT
-¤Ï
+は
.I head
-¤Ç»²¾È¤µ¤ì¤ë¥Æ¡¼¥ë¥¥å¡¼¤ò½é´ü²½¤¹¤ë¡£
+で参照されるテールキューを初期化する。
.PP
.\"O The macro
.\"O .B TAILQ_INSERT_HEAD
.\"O inserts the new element
.\"O .I elm
.\"O at the head of the tail queue.
-¥Þ¥¯¥í
+マクロ
.B TAILQ_INSERT_HEAD
-¤Ï¿·¤¿¤ÊÍ×ÁÇ
+は新たな要素
.I elm
-¤ò¥Æ¡¼¥ë¥¥å¡¼¤ÎÀèƬ¤ËÁÞÆþ¤¹¤ë¡£
+をテールキューの先頭に挿入する。
.PP
.\"O The macro
.\"O .B TAILQ_INSERT_TAIL
.\"O inserts the new element
.\"O .I elm
.\"O at the end of the tail queue.
-¥Þ¥¯¥í
+マクロ
.B TAILQ_INSERT_TAIL
-¤Ï¿·¤¿¤ÊÍ×ÁÇ
+は新たな要素
.I elm
-¤ò¥Æ¡¼¥ë¥¥å¡¼¤ÎËöÈø¤ËÁÞÆþ¤¹¤ë¡£
+をテールキューの末尾に挿入する。
.PP
.\"O The macro
.\"O .B TAILQ_INSERT_AFTER
.\"O .I elm
.\"O after the element
.\"O .I listelm .
-¥Þ¥¯¥í
+マクロ
.B TAILQ_INSERT_AFTER
-¤Ï¿·¤¿¤ÊÍ×ÁÇ
+は新たな要素
.I elm
-¤òÍ×ÁÇ
+を要素
.Fa listelm
-¤Î¸å¤ËÁÞÆþ¤¹¤ë¡£
+の後に挿入する。
.PP
.\"O The macro
.\"O .B TAILQ_REMOVE
.\"O removes the element
.\"O .I elm
.\"O from the tail queue.
-¥Þ¥¯¥í
+マクロ
.B TAILQ_REMOVE
-¤ÏÍ×ÁÇ
+は要素
.I elm
-¤ò¥Æ¡¼¥ë¥¥å¡¼¤«¤éºï½ü¤¹¤ë¡£
+をテールキューから削除する。
.\"O .SS Tail Queue Example
-.SS ¥Æ¡¼¥ë¥¥å¡¼¤ÎÎã
+.SS テールキューの例
.nf
TAILQ_HEAD(tailhead, entry) head;
.\"O struct tailhead *headp; /* Tail queue head. */
-struct tailhead *headp; /* ¥Æ¡¼¥ë¥¥å¡¼¤ÎÀèƬ¡£*/
+struct tailhead *headp; /* テールキューの先頭。*/
struct entry {
...
.\"O TAILQ_ENTRY(entry) entries; /* Tail queue. */
- TAILQ_ENTRY(entry) entries; /* ¥Æ¡¼¥ë¥¥å¡¼¡£*/
+ TAILQ_ENTRY(entry) entries; /* テールキュー。*/
...
} *n1, *n2, *np;
.\"O TAILQ_INIT(&head); /* Initialize the queue. */
-TAILQ_INIT(&head); /* ¥¥å¡¼¤ò½é´ü²½¤¹¤ë¡£*/
+TAILQ_INIT(&head); /* キューを初期化する。*/
.\"O n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
-n1 = malloc(sizeof(struct entry)); /* ÀèƬ¤ËÁÞÆþ¤¹¤ë¡£*/
+n1 = malloc(sizeof(struct entry)); /* 先頭に挿入する。*/
TAILQ_INSERT_HEAD(&head, n1, entries);
.\"O n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
-n1 = malloc(sizeof(struct entry)); /* ËöÈø¤ËÁÞÆþ¤¹¤ë¡£*/
+n1 = malloc(sizeof(struct entry)); /* 末尾に挿入する。*/
TAILQ_INSERT_TAIL(&head, n1, entries);
.\"O n2 = malloc(sizeof(struct entry)); /* Insert after. */
-n2 = malloc(sizeof(struct entry)); /* ¸å¤í¤ËÁÞÆþ¤¹¤ë¡£*/
+n2 = malloc(sizeof(struct entry)); /* 後ろに挿入する。*/
TAILQ_INSERT_AFTER(&head, n1, n2, entries);
.\"O /* Forward traversal. */
- /* ½çÊý¸þ¤Ëé¤ë¡£*/
+ /* 順方向に辿る。*/
for (np = head.tqh_first; np != NULL; np = np\->entries.tqe_next)
np\-> ...
.\"O /* Delete. */
- /* ºï½ü¤¹¤ë¡£*/
+ /* 削除する。*/
while (head.tqh_first != NULL)
TAILQ_REMOVE(&head, head.tqh_first, entries);
.fi
.\"O .SS Circular Queues
-.SS ½Û´Ä¥¥å¡¼
+.SS 循ç\92°ã\82ã\83¥ã\83¼
.\"O A circular queue is headed by a structure defined by the
.\"O .B CIRCLEQ_HEAD
.\"O macro.
-½Û´Ä¥¥å¡¼¤ÎÀèƬ¤Ë¤Ï
+循環キューの先頭には
.B CIRCLEQ_HEAD
-¥Þ¥¯¥í¤ÇÄêµÁ¤µ¤ì¤ë¹½Â¤ÂΤ¬ÃÖ¤«¤ì¤ë¡£
+マクロで定義される構造体が置かれる。
.\"O This structure contains a pair of pointers,
.\"O one to the first element in the circular queue and the other to the
.\"O last element in the circular queue.
-¤³¤Î¹½Â¤ÂÎ¤Ï 1 ÁȤΥݥ¤¥ó¥¿¤ò´Þ¤ó¤Ç¤¤¤ë¡£
-1 ¤Ä¤Ï½Û´Ä¥¥å¡¼¤ÎºÇ½é¤ÎÍ×ÁǤؤΥݥ¤¥ó¥¿¤Ç¤¢¤ê¡¢
-¤â¤¦ 1 ¤Ä¤Ï½Û´Ä¥¥å¡¼¤ÎºÇ¸å¤ÎÍ×ÁǤؤΥݥ¤¥ó¥¿¤Ç¤¢¤ë¡£
+この構造体は 1 組のポインタを含んでいる。
+1 つは循環キューの最初の要素へのポインタであり、
+もう 1 つは循環キューの最後の要素へのポインタである。
.\"O The elements are doubly linked so that an arbitrary element can be
.\"O removed without traversing the queue.
-Í×ÁÇ¤Ï 2 ½Å¤Ë¥ê¥ó¥¯¤µ¤ì¤Æ¤ª¤ê¡¢
-Ǥ°Õ¤ÎÍ×ÁǤϥ¥å¡¼¤òé¤é¤º¤Ëºï½ü¤Ç¤¤ë¡£
+要素は 2 重にリンクされており、
+任意の要素はキューを辿らずに削除できる。
.\"O New elements can be added to the queue after an existing element,
.\"O before an existing element, at the head of the queue, or at the end
.\"O of the queue.
-¿·¤·¤¤Í×ÁǤϡ¢´û¸¤ÎÍ×ÁǤθå¤Þ¤¿¤ÏÁ°¡¢¤Þ¤¿¤Ï¥¥å¡¼¤ÎÀèƬ¤Þ¤¿¤ÏËöÈø¤ËÄɲäǤ¤ë¡£
+新しい要素は、既存の要素の後または前、またはキューの先頭または末尾に追加できる。
A
.\"O .B CIRCLEQ_HEAD
.\"O structure is declared as follows:
.B CIRCLEQ_HEAD
-¹½Â¤ÂΤϰʲ¼¤Î¤è¤¦¤ËÄêµÁ¤µ¤ì¤Æ¤¤¤ë:
+構造体は以下のように定義されている:
.in +4n
.nf
.\"O is the name of the structure to be defined, and
.\"O .IR "TYPE"
.\"O is the type of the elements to be linked into the circular queue.
-¤³¤³¤Ç
+ここで
.IR "HEADNAME"
-¤ÏÄêµÁ¤µ¤ì¤ë¹½Â¤ÂΤÎ̾Á°¤Ç¤¢¤ê¡¢
+は定義される構造体の名前であり、
.IR "TYPE"
-¤Ï½Û´Ä¥¥å¡¼Æâ¤Ç¥ê¥ó¥¯¤µ¤ì¤ëÍ×ÁǤη¿¤Ç¤¢¤ë¡£
+は循環キュー内でリンクされる要素の型である。
.\"O A pointer to the head of the circular queue can later be declared as:
-½Û´Ä¥¥å¡¼¤ÎÀèƬ¤Ø¤Î¥Ý¥¤¥ó¥¿¤Ï¡¢¤½¤Î¸å¤Ç¼¡¤Î¤è¤¦¤ËÀë¸À¤µ¤ì¤ë:
+循環キューの先頭へのポインタは、その後で次のように宣言される:
.in +4n
.nf
.\"O and
.\"O .IR "headp"
.\"O are user selectable.)
-(̾Á°
+(名前
.I head
-¤È
+と
.I headp
-¤Ï¥æ¡¼¥¶¤¬ÁªÂò¤Ç¤¤ë¡£)
+はユーザが選択できる。)
.PP
.\"O The macro
.\"O .B CIRCLEQ_ENTRY
.\"O declares a structure that connects the elements in
.\"O the circular queue.
-¥Þ¥¯¥í
+マクロ
.B CIRCLEQ_ENTRY
-¤Ï½Û´Ä¥¥å¡¼¤ÎÍ×ÁǤòÀܳ¤¹¤ë¹½Â¤ÂΤòÀë¸À¤¹¤ë¡£
+は循環キューの要素を接続する構造体を宣言する。
.PP
.\"O The macro
.\"O .B CIRCLEQ_INIT
.\"O initializes the circular queue referenced by
.\"O .IR head .
-¥Þ¥¯¥í
+マクロ
.B CIRCLEQ_INIT
-¤Ï
+は
.I head
-¤Ç»²¾È¤µ¤ì¤ë½Û´Ä¥¥å¡¼¤ò½é´ü²½¤¹¤ë¡£
+で参照される循環キューを初期化する。
.PP
.\"O The macro
.\"O .B CIRCLEQ_INSERT_HEAD
.\"O inserts the new element
.\"O .I elm
.\"O at the head of the circular queue.
-¥Þ¥¯¥í
+マクロ
.B CIRCLEQ_INSERT_HEAD
-¤Ï¿·¤¿¤ÊÍ×ÁÇ
+は新たな要素
.I elm
-¤ò½Û´Ä¥¥å¡¼¤ÎÀèƬ¤ËÁÞÆþ¤¹¤ë¡£
+を循環キューの先頭に挿入する。
.PP
.\"O The macro
.\"O .B CIRCLEQ_INSERT_TAIL
.\"O inserts the new element
.\"O .I elm
.\"O at the end of the circular queue.
-¥Þ¥¯¥í
+マクロ
.B CIRCLEQ_INSERT_TAIL
-¤Ï¿·¤¿¤ÊÍ×ÁÇ
+は新たな要素
.I elm
-¤ò½Û´Ä¥¥å¡¼¤ÎËöÈø¤ËÁÞÆþ¤¹¤ë¡£
+を循環キューの末尾に挿入する。
.PP
.\"O The macro
.\"O .B CIRCLEQ_INSERT_AFTER
.\"O .I elm
.\"O after the element
.\"O .IR listelm .
-¥Þ¥¯¥í
+マクロ
.B CIRCLEQ_INSERT_AFTER
-¤Ï¿·¤¿¤ÊÍ×ÁÇ
+は新たな要素
.I elm
-¤òÍ×ÁÇ
+を要素
.I listelm
-¤Î¸å¤ËÁÞÆþ¤¹¤ë¡£
+の後に挿入する。
.PP
.\"O The macro
.\"O .B CIRCLEQ_INSERT_BEFORE
.\"O .I elm
.\"O before the element
.\"O .IR listelm .
-¥Þ¥¯¥í
+マクロ
.B CIRCLEQ_INSERT_AFTER
-¤Ï¿·¤¿¤ÊÍ×ÁÇ
+は新たな要素
.I elm
-¤òÍ×ÁÇ
+を要素
.I listelm
-¤ÎÁ°¤ËÁÞÆþ¤¹¤ë¡£
+の前に挿入する。
.PP
.\"O The macro
.\"O .B CIRCLEQ_REMOVE
.\"O removes the element
.\"O .I elm
.\"O from the circular queue.
-¥Þ¥¯¥í
+マクロ
.B CIRCLEQ_REMOVE
-¤ÏÍ×ÁÇ
+は要素
.I elm
-¤ò½Û´Ä¥¥å¡¼¤«¤éºï½ü¤¹¤ë¡£
+を循環キューから削除する。
.\"O .SS Circular Queue Example
-.SS ½Û´Ä¥¥å¡¼¤ÎÎã
+.SS 循環キューの例
.nf
CIRCLEQ_HEAD(circleq, entry) head;
.\"O struct circleq *headp; /* Circular queue head. */
-struct circleq *headp; /* ½Û´Ä¥¥å¡¼¤ÎÀèƬ¡£*/
+struct circleq *headp; /* 循環キューの先頭。*/
struct entry {
...
.\"O CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */
- CIRCLEQ_ENTRY(entry) entries; /* ½Û´Ä¥¥å¡¼¡£*/
+ CIRCLEQ_ENTRY(entry) entries; /* 循環キュー。*/
...
} *n1, *n2, *np;
.\"O CIRCLEQ_INIT(&head); /* Initialize the circular queue. */
-CIRCLEQ_INIT(&head); /* ½Û´Ä¥¥å¡¼¤ò½é´ü²½¤¹¤ë¡£*/
+CIRCLEQ_INIT(&head); /* 循環キューを初期化する。*/
.\"O n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
-n1 = malloc(sizeof(struct entry)); /* ÀèƬ¤ËÁÞÆþ¤¹¤ë¡£*/
+n1 = malloc(sizeof(struct entry)); /* 先頭に挿入する。*/
CIRCLEQ_INSERT_HEAD(&head, n1, entries);
.\"O n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
-n1 = malloc(sizeof(struct entry)); /* ËöÈø¤ËÁÞÆþ¤¹¤ë¡£*/
+n1 = malloc(sizeof(struct entry)); /* 末尾に挿入する。*/
CIRCLEQ_INSERT_TAIL(&head, n1, entries);
.\"O n2 = malloc(sizeof(struct entry)); /* Insert after. */
-n2 = malloc(sizeof(struct entry)); /* ¸å¤í¤ËÁÞÆþ¤¹¤ë¡£*/
+n2 = malloc(sizeof(struct entry)); /* 後ろに挿入する。*/
CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
.\"O n2 = malloc(sizeof(struct entry)); /* Insert before. */
-n2 = malloc(sizeof(struct entry)); /* Á°¤ËÁÞÆþ¤¹¤ë¡£*/
+n2 = malloc(sizeof(struct entry)); /* 前に挿入する。*/
CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
.\"O /* Forward traversal. */
- /* ½çÊý¸þ¤Ëé¤ë¡£*/
+ /* 順方向に辿る。*/
for (np = head.cqh_first; np != (void *)&head; np = np\->entries.cqe_next)
np\-> ...
.\"O /* Reverse traversal. */
- /* µÕÊý¸þ¤Ëé¤ë¡£*/
+ /* 逆方向に辿る。*/
for (np = head.cqh_last; np != (void *)&head; np = np\->entries.cqe_prev)
np\-> ...
.\"O /* Delete. */
- /* ºï½ü¤¹¤ë¡£*/
+ /* 削除する。*/
while (head.cqh_first != (void *)&head)
CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
.fi
.\"O .SH "CONFORMING TO"
-.SH ½àµò
+.SH 準拠
.\"O Not in POSIX.1-2001.
.\"O Present on the BSDs.
.\"O The
.\"O queue functions first appeared in
.\"O 4.4BSD.
-POSIX.1-2001 ¤Ë¤Ï¤Ê¤¤¡£
-BSD ·Ï¤Ë¸ºß¤¹¤ë¡£
-queue ´Ø¿ô¤Ï 4.4BSD ¤Ç½é¤á¤ÆÅо줷¤¿¡£
+POSIX.1-2001 にはない。
+BSD 系に存在する。
+queue 関数は 4.4BSD で初めて登場した。
OSDN Git Service
