diff options
Diffstat (limited to 'ja_JP.eucJP/man/man3/queue.3')
| -rw-r--r-- | ja_JP.eucJP/man/man3/queue.3 | 1062 |
1 files changed, 0 insertions, 1062 deletions
diff --git a/ja_JP.eucJP/man/man3/queue.3 b/ja_JP.eucJP/man/man3/queue.3 deleted file mode 100644 index d756b64644..0000000000 --- a/ja_JP.eucJP/man/man3/queue.3 +++ /dev/null @@ -1,1062 +0,0 @@ -.\" Copyright (c) 1993 -.\" The Regents of the University of California. All rights reserved. -.\" -.\" Redistribution and use in source and binary forms, with or without -.\" modification, are permitted provided that the following conditions -.\" are met: -.\" 1. Redistributions of source code must retain the above copyright -.\" notice, this list of conditions and the following disclaimer. -.\" 2. Redistributions in binary form must reproduce the above copyright -.\" notice, this list of conditions and the following disclaimer in the -.\" documentation and/or other materials provided with the distribution. -.\" 3. All advertising materials mentioning features or use of this software -.\" must display the following acknowledgement: -.\" This product includes software developed by the University of -.\" California, Berkeley and its contributors. -.\" 4. Neither the name of the University nor the names of its contributors -.\" may be used to endorse or promote products derived from this software -.\" without specific prior written permission. -.\" -.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND -.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE -.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE -.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE -.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS -.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) -.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT -.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY -.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF -.\" SUCH DAMAGE. -.\" -.\" @(#)queue.3 8.2 (Berkeley) 1/24/94 -.\" %FreeBSD: src/share/man/man3/queue.3,v 1.15.2.7 2001/12/18 10:09:02 ru Exp % -.\" $FreeBSD$ -.\" -.Dd January 24, 1994 -.Dt QUEUE 3 -.Os -.Sh 名称 -.Nm SLIST_EMPTY , -.Nm SLIST_ENTRY , -.Nm SLIST_FIRST , -.Nm SLIST_FOREACH , -.Nm SLIST_HEAD , -.Nm SLIST_HEAD_INITIALIZER , -.Nm SLIST_INIT , -.Nm SLIST_INSERT_AFTER , -.Nm SLIST_INSERT_HEAD , -.Nm SLIST_NEXT , -.Nm SLIST_REMOVE_HEAD , -.Nm SLIST_REMOVE , -.Nm STAILQ_EMPTY , -.Nm STAILQ_ENTRY , -.Nm STAILQ_FIRST , -.Nm STAILQ_FOREACH , -.Nm STAILQ_HEAD , -.Nm STAILQ_HEAD_INITIALIZER , -.Nm STAILQ_INIT , -.Nm STAILQ_INSERT_AFTER , -.Nm STAILQ_INSERT_HEAD , -.Nm STAILQ_INSERT_TAIL , -.Nm STAILQ_LAST , -.Nm STAILQ_NEXT , -.Nm STAILQ_REMOVE_HEAD , -.Nm STAILQ_REMOVE , -.Nm LIST_EMPTY , -.Nm LIST_ENTRY , -.Nm LIST_FIRST , -.Nm LIST_FOREACH , -.Nm LIST_HEAD , -.Nm LIST_HEAD_INITIALIZER , -.Nm LIST_INIT , -.Nm LIST_INSERT_AFTER , -.Nm LIST_INSERT_BEFORE , -.Nm LIST_INSERT_HEAD , -.Nm LIST_NEXT , -.Nm LIST_REMOVE , -.Nm TAILQ_EMPTY , -.Nm TAILQ_ENTRY , -.Nm TAILQ_FIRST , -.Nm TAILQ_FOREACH , -.Nm TAILQ_FOREACH_REVERSE , -.Nm TAILQ_HEAD , -.Nm TAILQ_HEAD_INITIALIZER , -.Nm TAILQ_INIT , -.Nm TAILQ_INSERT_AFTER , -.Nm TAILQ_INSERT_BEFORE , -.Nm TAILQ_INSERT_HEAD , -.Nm TAILQ_INSERT_TAIL , -.Nm TAILQ_LAST , -.Nm TAILQ_NEXT , -.Nm TAILQ_PREV , -.Nm TAILQ_REMOVE , -.Nm CIRCLEQ_EMPTY , -.Nm CIRCLEQ_ENTRY , -.Nm CIRCLEQ_FIRST , -.Nm CIRCLEQ_FOREACH , -.Nm CIRCLEQ_FOREACH_REVERSE , -.Nm CIRCLEQ_HEAD , -.Nm CIRCLEQ_HEAD_INITIALIZER , -.Nm CIRCLEQ_INIT , -.Nm CIRCLEQ_INSERT_AFTER , -.Nm CIRCLEQ_INSERT_BEFORE , -.Nm CIRCLEQ_INSERT_HEAD , -.Nm CIRCLEQ_INSERT_TAIL , -.Nm CIRCLE_LAST , -.Nm CIRCLE_NEXT , -.Nm CIRCLE_PREV , -.Nm CIRCLEQ_REMOVE -.Nd 単一リンクリスト、単一リンクテールキュー、リスト、テールキュー、 -循環キューの実装 -.Sh 書式 -.In sys/queue.h -.\" -.Fn SLIST_EMPTY "SLIST_HEAD *head" -.Fn SLIST_ENTRY "TYPE" -.Fn SLIST_FIRST "SLIST_HEAD *head" -.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" -.Fn SLIST_HEAD "HEADNAME" "TYPE" -.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" -.Fn SLIST_INIT "SLIST_HEAD *head" -.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME" -.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME" -.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME" -.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME" -.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" -.\" -.Fn STAILQ_EMPTY "STAILQ_HEAD *head" -.Fn STAILQ_ENTRY "TYPE" -.Fn STAILQ_FIRST "STAILQ_HEAD *head" -.Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" -.Fn STAILQ_HEAD "HEADNAME" "TYPE" -.Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head" -.Fn STAILQ_INIT "STAILQ_HEAD *head" -.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME" -.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" -.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" -.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME" -.Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME" -.Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" -.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME" -.\" -.Fn LIST_EMPTY "LIST_HEAD *head" -.Fn LIST_ENTRY "TYPE" -.Fn LIST_FIRST "LIST_HEAD *head" -.Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" -.Fn LIST_HEAD "HEADNAME" "TYPE" -.Fn LIST_HEAD_INITIALIZER "LIST_HEAD head" -.Fn LIST_INIT "LIST_HEAD *head" -.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" -.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" -.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME" -.Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME" -.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME" -.\" -.Fn TAILQ_EMPTY "TAILQ_HEAD *head" -.Fn TAILQ_ENTRY "TYPE" -.Fn TAILQ_FIRST "TAILQ_HEAD *head" -.Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" -.Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" -.Fn TAILQ_HEAD "HEADNAME" "TYPE" -.Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head" -.Fn TAILQ_INIT "TAILQ_HEAD *head" -.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" -.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" -.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" -.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" -.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME" -.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME" -.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME" -.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" -.\" -.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head" -.Fn CIRCLEQ_ENTRY "TYPE" -.Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head" -.Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE" -.Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head" -.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head" -.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head" -.Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLE_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME" -.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" -.Sh 解説 -このマクロは、単一リンクリスト、単一リンクテールキュー、リスト、 -テールキュー、循環キューという、5 種類のデータ構造を定義してそこで動作します。 -5 つのデータ構造はすべて、以下の機能をサポートします。 -.Bl -enum -compact -offset indent -.It -リストの先頭に新しいエントリを挿入する。 -.It -リストに存在する任意の要素の後ろに新しいエントリを挿入する。 -.It -リストの先頭からエントリを O(1) 削除する。 -.It -リストの任意のエントリを O(n) 削除する。 -.It -リストを前から走査する。 -.El -.Pp -単一リンクリストは、5 つのデータ構造の中で最も単純で、上の 5つの機能し -かサポートしません。 -単一リンクリストは、 -データセットが大きく、削除がほとんどない、もしくは、全くないアプリケーション、 -または LIFO キューの実装に理想的です。 -.Pp -単一リンクテールキューには以下の機能もあります。 -.Bl -enum -compact -offset indent -.It -リストの末尾にエントリを追加する。 -.El -しかし以下に注意してください。 -.Bl -enum -compact -offset indent -.It -リストの挿入では、リストのヘッドを必ず指定する必要がある。 -.It -各ヘッドエントリでは、1 つではなく 2 つのポインタが必要である。 -.It -単一リンクリストより、コードサイズは約 15% 大きく、動作は約 20% 遅い。 -.El -.Pp -単一リンクテールキューは、 -データセットが大きく、削除がほとんどない、もしくは、全くないアプリケーション、 -または FIFO キューの実装に理想的です。 -.Pp -二重リンクタイプのすべてのデータ構造 (リスト、テールキュー、循環キュー) には -以下の機能もあります。 -.Bl -enum -compact -offset indent -.It -リストに存在する任意の要素の前に新しいエントリを挿入する。 -.It -リストの任意のエントリを O(1) 削除する。 -.El -しかし以下に注意してください。 -.Bl -enum -compact -offset indent -.It -各要素には、1 つではなく 2 つのポインタが必要である。 -.It -単一リンクデータ構造より、コードサイズと実行時間 (削除は除く) が約 2 倍に -なる。 -.El -.Pp -リンクリストは、二重リンクデータ構造の中で最も単純で、単一リンクリストの -機能に加えて上の機能しかサポートしません。 -.Pp -テールキューには以下の機能もあります。 -.Bl -enum -compact -offset indent -.It -リストの末尾にエントリを追加する。 -.It -末尾から先頭へと逆に走査する。 -.El -しかし以下に注意してください。 -.Bl -enum -compact -offset indent -.It -リストの挿入と削除では、リストのヘッドを必ず指定する必要がある。 -.It -各ヘッドエントリでは、1 つではなく 2 つのポインタが必要である。 -.It -単一リンクリストより、コードサイズは約 15% 大きく、処理時間は約 20% 長い。 -.El -.Pp -循環キューには以下の機能もあります。 -.Bl -enum -compact -offset indent -.It -リストの末尾にエントリを追加する。 -.It -末尾から先頭へと逆に走査する。 -.El -しかし以下に注意してください。 -.Bl -enum -compact -offset indent -.It -リストの挿入と削除では、リストのヘッドを必ず指定する必要がある。 -.It -各ヘッドエントリでは、1 つではなく 2 つのポインタが必要である。 -.It -走査の終了条件がより複雑である。 -.It -リストより、コードサイズは約 40% 大きく、処理時間は約 45% 長い。 -.El -.Pp -マクロ定義では、 -.Fa TYPE -はユーザが定義した構造体の名前です。この構造体には、 -.Fa NAME -という名前が付いた、 -.Li SLIST_ENTRY , -.Li STAILQ_ENTRY , -.Li LIST_ENTRY , -.Li TAILQ_ENTRY , -.Li CIRCLEQ_ENTRY -という型のフィールドを含める必要があります。 -引数 -.Fa HEADNAME -は -マクロ -.Li SLIST_HEAD , -.Li STAILQ_HEAD , -.Li LIST_HEAD , -.Li TAILQ_HEAD , -.Li CIRCLEQ_HEAD -で宣言する必要のある、ユーザが定義した構造体の名前です。 -このマクロの使用法の詳細については、以下の使用例を参照してください。 -.Sh 単一リンクリスト -単一リンクリストの最初には、 -.Nm SLIST_HEAD -マクロで定義される構造体が付きます。 -この構造体には、リストの先頭の要素を指すポインタが 1 つ含まれます。 -要素は、任意の要素の O(n) 削除を犠牲にして、 -スペースとポインタ操作のオーバヘッドが最小になるように単一リンクされます。 -新しい要素は、既存の要素の後ろ、リストの先頭でリストに追加できます。 -.Fa SLIST_HEAD -構造体は以下のように宣言されます。 -.Bd -literal -offset indent -SLIST_HEAD(HEADNAME, TYPE) head; -.Ed -.Pp -ここで -.Fa HEADNAME -は定義する構造体の名前で、 -.Fa TYPE -はリストにリンクする要素の型です。 -リストのヘッドのポインタは、後で以下のように宣言できます。 -.Bd -literal -offset indent -struct HEADNAME *headp; -.Ed -.Pp -(名前 -.Li head -と -.Li headp -は、ユーザが選べます。) -.Pp -マクロ -.Nm SLIST_HEAD_INITIALIZER -はリストの -.Fa head -を初期化します。 -.Pp -マクロ -.Nm SLIST_EMPTY -はリストに要素がない場合に真になります。 -.Pp -マクロ -.Nm SLIST_ENTRY -はリストの要素を接続する構造体を宣言します。 -.Pp -マクロ -.Nm SLIST_FIRST -はリストの先頭の要素を、リストが空なら NULL を返します。 -.Pp -マクロ -.Nm SLIST_FOREACH -は -.Fa head -で参照されるリストを、各要素を順に -.Fa var -に割り当てて順方向に走査します。 -.Pp -マクロ -.Nm SLIST_INIT -は -.Fa head -が参照するリストを初期化します。 -.Pp -マクロ -.Nm SLIST_INSERT_HEAD -は新しい要素 -.Fa elm -をリストの先頭に挿入します。 -.Pp -マクロ -.Nm SLIST_INSERT_AFTER -は要素 -.Fa listelm -の後ろに新しい要素 -.Fa elm -を挿入します。 -.Pp -マクロ -.Nm SLIST_NEXT -はリストの次の要素を返します。 -.Pp -マクロ -.Nm SLIST_REMOVE_HEAD -はリストの先頭から要素 -.Fa elm -を削除します。 -最適な効率を得るために、リストの先頭から要素を削除する場合には -一般的な -.Fa SLIST_REMOVE -マクロの代わりにこのマクロを明示的に使用すべきです。 -.Pp -マクロ -.Nm SLIST_REMOVE -はリストから要素 -.Fa elm -を削除します。 -.Sh 単一リンクリストの使用例 -.Bd -literal -SLIST_HEAD(slisthead, entry) head = - SLIST_HEAD_INITIALIZER(head); -struct slisthead *headp; /* 単一リンクリストヘッド */ -struct entry { - ... - SLIST_ENTRY(entry) entries; /* 単一リンクリスト */ - ... -} *n1, *n2, *n3, *np; - -SLIST_INIT(&head); /* リストを初期化 */ - -n1 = malloc(sizeof(struct entry)); /* 先頭に挿入 */ -SLIST_INSERT_HEAD(&head, n1, entries); - -n2 = malloc(sizeof(struct entry)); /* 後ろに挿入 */ -SLIST_INSERT_AFTER(n1, n2, entries); - -SLIST_REMOVE(&head, n2, entry, entries);/* 削除 */ -free(n2); - -n3 = SLIST_FIRST(&head); -SLIST_REMOVE_HEAD(&head, entries); /* 先頭から削除 */ -free(n3); - /* 順走査 */ -SLIST_FOREACH(np, &head, entries) - np-> ... - -while (!SLIST_EMPTY(&head)) { /* リストの削除 */ - n1 = SLIST_FIRST(&head); - SLIST_REMOVE_HEAD(&head, entries); - free(n1); -} -.Ed -.Sh 単一リンクテールキュー -単一リンクテールキューの最初には、 -.Nm STAILQ_HEAD -マクロで定義される構造体がつきます。 -この構造体にはテールキューの先頭の要素を指すポインタと -テールキューの末尾の要素を指すポインタの 2 つが含まれます。 -要素は、任意の要素の O(n) 削除を犠牲にして、 -スペースとポインタ操作のオーバヘッドが最小になるように単一リンクされます。 -新しい要素は、既存の要素の後ろ、テールキューの先頭、テールキューの末尾で -テールキューに追加できます。 -.Fa STAILQ_HEAD -構造体は以下のように宣言されます。 -.Bd -literal -offset indent -STAILQ_HEAD(HEADNAME, TYPE) head; -.Ed -.Pp -ここで -.Li HEADNAME -は定義する構造体の名前で、 -.Li TYPE -はテールキューにリンクする要素の型です。 -テールキューのヘッドのポインタは、後で以下のように宣言できます。 -.Bd -literal -offset indent -struct HEADNAME *headp; -.Ed -.Pp -(名前 -.Li head -と -.Li headp -は、ユーザが選べます。) -.Pp -マクロ -.Nm STAILQ_HEAD_INITIALIZER -はテールキューの -.Fa head -を初期化します。 -.Pp -マクロ -.Nm STAILQ_EMPTY -はテールキューに要素がない場合に真になります。 -.Pp -マクロ -.Nm STAILQ_ENTRY -はテールキューの要素を接続する構造体を宣言します。 -.Pp -マクロ -.Nm STAILQ_FIRST -はテールキューの先頭の要素を、テールキューが空なら NULL を返します。 -.Pp -マクロ -.Nm STAILQ_FOREACH -は -.Fa head -で参照されるテールキューを、各要素を順に -.Fa var -に割り当てて順方向に走査します。 -.Pp -マクロ -.Nm STAILQ_INIT -は -.Fa head -が参照するテールキューを初期化します。 -.Pp -マクロ -.Nm STAILQ_INSERT_HEAD -は新しい要素 -.Fa elm -をテールキューの先頭に挿入します。 -.Pp -マクロ -.Nm STAILQ_INSERT_TAIL -は新しい要素 -.Fa elm -をテールキューの末尾に挿入します。 -.Pp -マクロ -.Nm STAILQ_INSERT_AFTER -は新しい要素 -.Fa elm -を要素 -.Fa listelm -の後ろに挿入します。 -.Pp -マクロ -.Nm STAILQ_LAST -はテールキューの末尾の要素を返します。 -テールキューが空なら、戻り値は未定義です。 -.Pp -マクロ -.Nm STAILQ_NEXT -はテールキューの次の要素を、この要素が末尾なら NULL を返します。 -.Pp -マクロ -.Nm STAILQ_REMOVE_HEAD -はテールキューの先頭から要素 -を削除します。 -最適な効率を得るために、テールキューの先頭から要素を削除する場合には -一般的な -.Fa STAILQ_REMOVE -マクロよりもこのマクロを明示的に使用すべきです。 -.Pp -マクロ -.Nm STAILQ_REMOVE -はテールキューから要素 -.Fa elm -を削除します。 -.Sh 単一リンクテールキューの使用例 -.Bd -literal -STAILQ_HEAD(stailhead, entry) head = - STAILQ_HEAD_INITIALIZER(head); -struct stailhead *headp; /* 単一リンクテールキューヘッド */ -struct entry { - ... - STAILQ_ENTRY(entry) entries; /* テールキュー */ - ... -} *n1, *n2, *n3, *np; - -STAILQ_INIT(&head); /* キューを初期化 */ - -n1 = malloc(sizeof(struct entry)); /* 先頭に挿入 */ -STAILQ_INSERT_HEAD(&head, n1, entries); - -n1 = malloc(sizeof(struct entry)); /* 末尾に挿入 */ -STAILQ_INSERT_TAIL(&head, n1, entries); - -n2 = malloc(sizeof(struct entry)); /* 後ろに挿入 */ -STAILQ_INSERT_AFTER(&head, n1, n2, entries); - /* 削除 */ -STAILQ_REMOVE(&head, n2, entry, entries); -free(n2); - /* 先頭から削除 */ -n3 = STAILQ_FIRST(&head); -STAILQ_REMOVE_HEAD(&head, entries); -free(n3); - /* 順走査 */ -STAILQ_FOREACH(np, &head, entries) - np-> ... - /* テールキューの削除 */ -while (!STAILQ_EMPTY(&head)) { - n1 = STAILQ_FIRST(&head); - STAILQ_REMOVE_HEAD(&head, entries); - free(n1); -} - /* テールキューの高速な削除 */ -n1 = STAILQ_FIRST(&head); -while (n1 != NULL) { - n2 = STAILQ_NEXT(n1, entries); - free(n1); - n1 = n2; -} -STAILQ_INIT(&head); -.Ed -.Sh リスト -リストの最初には、 -.Nm LIST_HEAD -マクロで定義される構造体が付きます。 -この構造体には、リストの先頭の要素を指すポインタが 1 つ含まれます。 -要素は二重にリンクされているので、リストを走査せずに任意の要素を削除できます。 -新しい要素は、既存の要素の前、既存の要素の後、リストの先頭で -リストに追加できます。 -.Fa LIST_HEAD -構造体は、以下のように宣言されます。 -.Bd -literal -offset indent -LIST_HEAD(HEADNAME, TYPE) head; -.Ed -.Pp -ここで -.Fa HEADNAME -は定義する構造体の名前で、 -.Fa TYPE -はリストにリンクする要素の型です。 -リストのヘッドのポインタは、後で以下のように宣言できます。 -.Bd -literal -offset indent -struct HEADNAME *headp; -.Ed -.Pp -(名前 -.Li head -と -.Li headp -は、ユーザが選べます。) -.Pp -マクロ -.Nm LIST_HEAD_INITIALIZER -はリストの -.Fa head -を初期化します。 -.Pp -マクロ -.Nm LIST_EMPTY -はリストに要素がない場合に真になります。 -.Pp -マクロ -.Nm LIST_ENTRY -はリストの要素を接続する構造体を宣言します。 -.Pp -マクロ -.Nm LIST_FIRST -はリストの最初の要素を、リストが空なら NULL を返します。 -.Pp -マクロ -.Nm LIST_FOREACH -は -.Fa head -で参照されるリストを、各要素を順に -.Fa var -に割り当てて順方向に走査します。 -.Pp -マクロ -.Nm LIST_INIT -は -.Fa head -が参照するリストを初期化します。 -.Pp -マクロ -.Nm LIST_INSERT_HEAD -は新しい要素 -.Fa elm -をリストの先頭に挿入します。 -.Pp -マクロ -.Nm LIST_INSERT_AFTER -は新しい要素 -.Fa elm -を要素 -.Fa listelm -の後ろに挿入します。 -.Pp -マクロ -.Nm LIST_INSERT_BEFORE -は新しい要素 -.Fa elm -を要素 -.Fa listelm -の前に挿入します。 -.Pp -マクロ -.Nm LIST_NEXT -はリストの次の要素を、この要素が末尾なら NULL を返します。 -.Pp -マクロ -.Nm LIST_REMOVE -は要素 -.Fa elm -をリストから削除します。 -.Sh リストの使用例 -.Bd -literal -LIST_HEAD(listhead, entry) head = - LIST_HEAD_INITIALIZER(head); -struct listhead *headp; /* リストヘッド */ -struct entry { - ... - LIST_ENTRY(entry) entries; /* リスト */ - ... -} *n1, *n2, *n3, *np; - -LIST_INIT(&head); /* リストを初期化 */ - -n1 = malloc(sizeof(struct entry)); /* 先頭に挿入 */ -LIST_INSERT_HEAD(&head, n1, entries); - -n2 = malloc(sizeof(struct entry)); /* 後ろに挿入 */ -LIST_INSERT_AFTER(n1, n2, entries); - -n3 = malloc(sizeof(struct entry)); /* 前に挿入 */ -LIST_INSERT_BEFORE(n2, n3, entries); - -LIST_REMOVE(n2, entries); /* 削除 */ -free(n2); - /* 順走査 */ -LIST_FOREACH(np, &head, entries) - np-> ... - -while (!LIST_EMPTY(&head)) { /* リストの削除 */ - n1 = LIST_FIRST(&head); - LIST_REMOVE(n1, entries); - free(n1); -} - -n1 = LIST_FIRST(&head); /* リストの高速な削除 */ -while (n1 != NULL) { - n2 = LIST_NEXT(n1, entries); - free(n1); - n1 = n2; -} -LIST_INIT(&head); -.Ed -.Sh テールキュー -テールキューの最初には、 -.Nm TAILQ_HEAD -マクロで定義される構造体が付きます。 -この構造体には、テールキューの最初の要素を指すポインタと -テールキューの先頭の要素を指すポインタの 2 つが含まれます。 -要素は二重にリンクされているので、テールキューを走査せずに -任意の要素を削除できます。 -新しい要素は、既存の要素の前、既存の要素の後、テールキューの先頭、 -テールキューの末尾でテールキューに追加できます。 -.Fa TAILQ_HEAD -構造体は、以下のように宣言されています。 -.Bd -literal -offset indent -TAILQ_HEAD(HEADNAME, TYPE) head; -.Ed -.Pp -ここで -.Li HEADNAME -は定義する構造体の名前で、 -.Li TYPE -はテールキューにリンクする要素の型です。 -テールキューのヘッドのポインタは、後で以下のように宣言されます。 -.Bd -literal -offset indent -struct HEADNAME *headp; -.Ed -.Pp -(名前 -.Li head -と -.Li headp -は、ユーザが選べます。) -.Pp -マクロ -.Nm TAILQ_HEAD_INITIALIZER -はテールキューの -.Fa head -を初期化します。 -.Pp -マクロ -.Nm TAILQ_EMPTY -はテールキューに要素がない場合に真になります。 -.Pp -マクロ -.Nm TAILQ_ENTRY -はテールキューの要素を接続する構造体を宣言します。 -.Pp -マクロ -.Nm TAILQ_FIRST -はテールキューの最初の要素を、テールキューが空なら NULL を返します。 -.Pp -マクロ -.Nm TAILQ_FOREACH -は -.Fa head -で参照されるテールキューを、各要素を順に -.Fa var -に割り当てて順方向に走査します。 -.Pp -マクロ -.Nm TAILQ_FOREACH_REVERSE -は -.Fa head -で参照されるテールキューを、各要素を順に -.Fa var -に割り当てて逆方向に走査します。 -.Pp -マクロ -.Nm TAILQ_INIT -は -.Fa head -が参照するテールキューを初期化します。 -.Pp -マクロ -.Nm TAILQ_INSERT_HEAD -は新しい要素 -.Fa elm -をテールキューの先頭に挿入します。 -.Pp -マクロ -.Nm TAILQ_INSERT_TAIL -は新しい要素 -.Fa elm -をテールキューの末尾に挿入します。 -.Pp -マクロ -.Nm TAILQ_INSERT_AFTER -は新しい要素 -.Fa elm -を要素 -.Fa listelm -の後ろに挿入します。 -.Pp -マクロ -.Nm TAILQ_INSERT_BEFORE -は新しい要素 -.Fa elm -を要素 -.Fa listelm -の前に挿入します。 -.Pp -マクロ -.Nm TAILQ_LAST -はテールキューの末尾の要素を返します。 -テールキューが空の場合、戻り値は未定義です。 -.Pp -マクロ -.Nm TAILQ_NEXT -はテールキューの次の要素を、その要素が末尾の場合は NULL を返します。 -.Pp -マクロ -.Nm TAILQ_PREV -はテールキューの前の要素を、その要素が先頭の場合は NULL を返します。 -.Pp -マクロ -.Nm TAILQ_REMOVE -は要素 -.Fa elm -をテールキューから削除します。 -.Sh テールキューの使用例 -.Bd -literal -TAILQ_HEAD(tailhead, entry) head = - TAILQ_HEAD_INITIALIZER(head); -struct tailhead *headp; /* テールキューヘッド */ -struct entry { - ... - TAILQ_ENTRY(entry) entries; /* テールキュー */ - ... -} *n1, *n2, *n3, *np; - -TAILQ_INIT(&head); /* キューを初期化 */ - -n1 = malloc(sizeof(struct entry)); /* 先頭に挿入 */ -TAILQ_INSERT_HEAD(&head, n1, entries); - -n1 = malloc(sizeof(struct entry)); /* 末尾に挿入 */ -TAILQ_INSERT_TAIL(&head, n1, entries); - -n2 = malloc(sizeof(struct entry)); /* 後ろに挿入 */ -TAILQ_INSERT_AFTER(&head, n1, n2, entries); - -n3 = malloc(sizeof(struct entry)); /* 前に挿入 */ -TAILQ_INSERT_BEFORE(n2, n3, entries); - -TAILQ_REMOVE(&head, n2, entries); /* 削除 */ -free(n2); - /* 順走査 */ -TAILQ_FOREACH(np, &head, entries) - np-> ... - /* 逆走査 */ -TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries) - np-> ... - /* テールキューの削除 */ -while (!TAILQ_EMPTY(&head)) { - n1 = TAILQ_FIRST(&head); - TAILQ_REMOVE(&head, n1, entries); - free(n1); -} - /* テールキューの高速な削除 */ -n1 = TAILQ_FIRST(&head); -while (n1 != NULL) { - n2 = TAILQ_NEXT(n1, entries); - free(n1); - n1 = n2; -} -TAILQ_INIT(&head); -.Ed -.Sh 循環キュー -循環キューの最初には、 -.Nm CIRCLEQ_HEAD -マクロで定義される構造体が付きます。 -この構造体には、循環キューの先頭の要素を指すポインタと -循環キューの末尾の要素を指すポインタの 2 つが含まれます。 -要素は二重にリンクされているので、キューを走査せずに -任意の要素を削除できます。 -新しい要素は、既存の要素の前、既存の要素の後ろ、循環キューの先頭、 -循環キューの末尾で循環キューに追加できます。 -.Fa CIRCLEQ_HEAD -構造体は以下のように宣言されます。 -.Bd -literal -offset indent -CIRCLEQ_HEAD(HEADNAME, TYPE) head; -.Ed -.Pp -ここで -.Li HEADNAME -は定義する構造体の名前で、 -.Li TYPE -は循環キューにリンクする要素の型です。 -循環キューのヘッドのポインタは、後で以下のように宣言できます。 -.Bd -literal -offset indent -struct HEADNAME *headp; -.Ed -.Pp -(名前 -.Li head -と -.Li headp -は、ユーザが選べます。) -.Pp -マクロ -.Nm CIRCLEQ_HEAD_INITIALIZER -は循環キューの -.Fa head -を初期化します。 -.Pp -マクロ -.Nm CIRCLEQ_EMPTY -は循環キューに要素がない場合に真になります。 -.Pp -マクロ -.Nm CIRCLEQ_ENTRY -は循環キューの要素を接続する構造体を宣言します。 -.Pp -マクロ -.Nm CIRCLEQ_FIRST -は循環キューの先頭の要素を返します。 -.Pp -マクロ -.Nm CICRLEQ_FOREACH -は -.Fa head -で参照される循環キューを、各要素を順に -.Fa var -に割り当てて順方向に走査します。 -.Pp -マクロ -.Nm CICRLEQ_FOREACH_REVERSE -は -.Fa head -で参照される循環キューを、各要素を順に -.Fa var -に割り当てて逆方向に走査します。 -.Pp -マクロ -.Nm CIRCLEQ_INIT -は -.Fa head -が参照する循環キューを初期化します。 -.Pp -マクロ -.Nm CIRCLEQ_INSERT_HEAD -は新しい要素 -.Fa elm -を循環キューの先頭に挿入します。 -.Pp -マクロ -.Nm CIRCLEQ_INSERT_TAIL -は新しい要素 -.Fa elm -を循環キューの末尾に挿入します。 -.Pp -マクロ -.Nm CIRCLEQ_INSERT_AFTER -は新しい要素 -.Fa elm -を要素 -.Fa listelm -の後ろに挿入します。 -.Pp -マクロ -.Nm CIRCLEQ_INSERT_BEFORE -は新しい要素 -.Fa elm -を要素 -.Fa listelm -の前に挿入します。 -.Pp -マクロ -.Nm CIRCLEQ_LAST -は循環キューの末尾の要素を返します。 -.Pp -マクロ -.Nm CIRCLEQ_NEXT -は循環キューの次の要素を返します。 -.Pp -マクロ -.Nm CIRCLEQ_PREV -は循環キューの前の要素を返します。 -.Pp -マクロ -.Nm CIRCLEQ_REMOVE -は要素 -.Fa elm -を循環キューから削除します。 -.Sh 循環キューの使用例 -.Bd -literal -CIRCLEQ_HEAD(circlehead, entry) head = - CIRCLEQ_HEAD_INITIALIZER(head); -struct circleq *headp; /* 循環キューヘッド */ -struct entry { - ... - CIRCLEQ_ENTRY(entry) entries; /* 循環キュー */ - ... -} *n1, *n2, *np; - -CIRCLEQ_INIT(&head); /* 循環キューを初期化 */ - -n1 = malloc(sizeof(struct entry)); /* 先頭に挿入 */ -CIRCLEQ_INSERT_HEAD(&head, n1, entries); - -n1 = malloc(sizeof(struct entry)); /* 末尾に挿入 */ -CIRCLEQ_INSERT_TAIL(&head, n1, entries); - -n2 = malloc(sizeof(struct entry)); /* 後ろに挿入 */ -CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries); - -n2 = malloc(sizeof(struct entry)); /* 前に挿入 */ -CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries); - -CIRCLEQ_REMOVE(&head, n1, entries); /* 削除 */ -free(n1); - /* 順走査 */ -CIRCLEQ_FOREACH(np, &head, entries) - np-> ... - /* 逆走査 */ -CIRCLEQ_FOREACH_REVERSE(np, &head, entries) - np-> ... - /* 循環キューの削除 */ -while (CIRCLEQ_FIRST(&head) != (void *)&head) { - n1 = CIRCLEQ_HEAD(&head); - CIRCLEQ_REMOVE(&head, n1, entries); - free(n1); -} - /* 循環キューの高速な削除 */ -n1 = CIRCLEQ_FIRST(&head); -while (n1 != (void *)&head) { - n2 = CIRCLEQ_NEXT(n1, entries); - free(n1); - n1 = n2; -} -CIRCLEQ_INIT(&head); -.Ed -.Sh 歴史 -.Nm queue -関数は -.Bx 4.4 -ではじめて登場しました。 |