| 総合手引 | セクション 3 | English | オプション |
#include <sys/queue.h>
単一リンクリストは、5 つのデータ構造の中で最も単純で、上の 5つの機能し かサポートしません。 単一リンクリストは、 データセットが大きく、削除がほとんどない、もしくは、全くないアプリケーション、 または LIFO キューの実装に理想的です。
単一リンクテールキューには以下の機能もあります。
単一リンクテールキューは、 データセットが大きく、削除がほとんどない、もしくは、全くないアプリケーション、 または FIFO キューの実装に理想的です。
二重リンクタイプのすべてのデータ構造 (リスト、テールキュー、循環キュー) には 以下の機能もあります。
リンクリストは、二重リンクデータ構造の中で最も単純で、単一リンクリストの 機能に加えて上の機能しかサポートしません。
テールキューには以下の機能もあります。
循環キューには以下の機能もあります。
マクロ定義では、 TYPE はユーザが定義した構造体の名前です。この構造体には、 NAME という名前が付いた、 SLIST_ENTRY, STAILQ_ENTRY, LIST_ENTRY, TAILQ_ENTRY, CIRCLEQ_ENTRY という型のフィールドを含める必要があります。 引数 HEADNAME は マクロ SLIST_HEAD, STAILQ_HEAD, LIST_HEAD, TAILQ_HEAD, CIRCLEQ_HEAD で宣言する必要のある、ユーザが定義した構造体の名前です。 このマクロの使用法の詳細については、以下の使用例を参照してください。
SLIST_HEAD(HEADNAME, TYPE) head;
ここで HEADNAME は定義する構造体の名前で、 TYPE はリストにリンクする要素の型です。 リストのヘッドのポインタは、後で以下のように宣言できます。
struct HEADNAME *headp;
(名前 head と headp は、ユーザが選べます。)
マクロ SLIST_HEAD_INITIALIZER はリストの head を初期化します。
マクロ SLIST_EMPTY はリストに要素がない場合に真になります。
マクロ SLIST_ENTRY はリストの要素を接続する構造体を宣言します。
マクロ SLIST_FIRST はリストの先頭の要素を、リストが空なら NULL を返します。
マクロ SLIST_FOREACH は head で参照されるリストを、各要素を順に var に割り当てて順方向に走査します。
マクロ SLIST_INIT は head が参照するリストを初期化します。
マクロ SLIST_INSERT_HEAD は新しい要素 elm をリストの先頭に挿入します。
マクロ SLIST_INSERT_AFTER は要素 listelm の後ろに新しい要素 elm を挿入します。
マクロ SLIST_NEXT はリストの次の要素を返します。
マクロ SLIST_REMOVE_HEAD はリストの先頭から要素 elm を削除します。 最適な効率を得るために、リストの先頭から要素を削除する場合には 一般的な SLIST_REMOVE マクロの代わりにこのマクロを明示的に使用すべきです。
マクロ SLIST_REMOVE はリストから要素 elm を削除します。
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);
}
STAILQ_HEAD(HEADNAME, TYPE) head;
ここで HEADNAME は定義する構造体の名前で、 TYPE はテールキューにリンクする要素の型です。 テールキューのヘッドのポインタは、後で以下のように宣言できます。
struct HEADNAME *headp;
(名前 head と headp は、ユーザが選べます。)
マクロ STAILQ_HEAD_INITIALIZER はテールキューの head を初期化します。
マクロ STAILQ_EMPTY はテールキューに要素がない場合に真になります。
マクロ STAILQ_ENTRY はテールキューの要素を接続する構造体を宣言します。
マクロ STAILQ_FIRST はテールキューの先頭の要素を、テールキューが空なら NULL を返します。
マクロ STAILQ_FOREACH は head で参照されるテールキューを、各要素を順に var に割り当てて順方向に走査します。
マクロ STAILQ_INIT は head が参照するテールキューを初期化します。
マクロ STAILQ_INSERT_HEAD は新しい要素 elm をテールキューの先頭に挿入します。
マクロ STAILQ_INSERT_TAIL は新しい要素 elm をテールキューの末尾に挿入します。
マクロ STAILQ_INSERT_AFTER は新しい要素 elm を要素 listelm の後ろに挿入します。
マクロ STAILQ_LAST はテールキューの末尾の要素を返します。 テールキューが空なら、戻り値は未定義です。
マクロ STAILQ_NEXT はテールキューの次の要素を、この要素が末尾なら NULL を返します。
マクロ STAILQ_REMOVE_HEAD はテールキューの先頭から要素 を削除します。 最適な効率を得るために、テールキューの先頭から要素を削除する場合には 一般的な STAILQ_REMOVE マクロよりもこのマクロを明示的に使用すべきです。
マクロ STAILQ_REMOVE はテールキューから要素 elm を削除します。
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);
LIST_HEAD(HEADNAME, TYPE) head;
ここで HEADNAME は定義する構造体の名前で、 TYPE はリストにリンクする要素の型です。 リストのヘッドのポインタは、後で以下のように宣言できます。
struct HEADNAME *headp;
(名前 head と headp は、ユーザが選べます。)
マクロ LIST_HEAD_INITIALIZER はリストの head を初期化します。
マクロ LIST_EMPTY はリストに要素がない場合に真になります。
マクロ LIST_ENTRY はリストの要素を接続する構造体を宣言します。
マクロ LIST_FIRST はリストの最初の要素を、リストが空なら NULL を返します。
マクロ LIST_FOREACH は head で参照されるリストを、各要素を順に var に割り当てて順方向に走査します。
マクロ LIST_INIT は head が参照するリストを初期化します。
マクロ LIST_INSERT_HEAD は新しい要素 elm をリストの先頭に挿入します。
マクロ LIST_INSERT_AFTER は新しい要素 elm を要素 listelm の後ろに挿入します。
マクロ LIST_INSERT_BEFORE は新しい要素 elm を要素 listelm の前に挿入します。
マクロ LIST_NEXT はリストの次の要素を、この要素が末尾なら NULL を返します。
マクロ LIST_REMOVE は要素 elm をリストから削除します。
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);
TAILQ_HEAD(HEADNAME, TYPE) head;
ここで HEADNAME は定義する構造体の名前で、 TYPE はテールキューにリンクする要素の型です。 テールキューのヘッドのポインタは、後で以下のように宣言されます。
struct HEADNAME *headp;
(名前 head と headp は、ユーザが選べます。)
マクロ TAILQ_HEAD_INITIALIZER はテールキューの head を初期化します。
マクロ TAILQ_EMPTY はテールキューに要素がない場合に真になります。
マクロ TAILQ_ENTRY はテールキューの要素を接続する構造体を宣言します。
マクロ TAILQ_FIRST はテールキューの最初の要素を、テールキューが空なら NULL を返します。
マクロ TAILQ_FOREACH は head で参照されるテールキューを、各要素を順に var に割り当てて順方向に走査します。
マクロ TAILQ_FOREACH_REVERSE は head で参照されるテールキューを、各要素を順に var に割り当てて逆方向に走査します。
マクロ TAILQ_INIT は head が参照するテールキューを初期化します。
マクロ TAILQ_INSERT_HEAD は新しい要素 elm をテールキューの先頭に挿入します。
マクロ TAILQ_INSERT_TAIL は新しい要素 elm をテールキューの末尾に挿入します。
マクロ TAILQ_INSERT_AFTER は新しい要素 elm を要素 listelm の後ろに挿入します。
マクロ TAILQ_INSERT_BEFORE は新しい要素 elm を要素 listelm の前に挿入します。
マクロ TAILQ_LAST はテールキューの末尾の要素を返します。 テールキューが空の場合、戻り値は未定義です。
マクロ TAILQ_NEXT はテールキューの次の要素を、その要素が末尾の場合は NULL を返します。
マクロ TAILQ_PREV はテールキューの前の要素を、その要素が先頭の場合は NULL を返します。
マクロ TAILQ_REMOVE は要素 elm をテールキューから削除します。
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);
CIRCLEQ_HEAD(HEADNAME, TYPE) head;
ここで HEADNAME は定義する構造体の名前で、 TYPE は循環キューにリンクする要素の型です。 循環キューのヘッドのポインタは、後で以下のように宣言できます。
struct HEADNAME *headp;
(名前 head と headp は、ユーザが選べます。)
マクロ CIRCLEQ_HEAD_INITIALIZER は循環キューの head を初期化します。
マクロ CIRCLEQ_EMPTY は循環キューに要素がない場合に真になります。
マクロ CIRCLEQ_ENTRY は循環キューの要素を接続する構造体を宣言します。
マクロ CIRCLEQ_FIRST は循環キューの先頭の要素を返します。
マクロ CICRLEQ_FOREACH は head で参照される循環キューを、各要素を順に var に割り当てて順方向に走査します。
マクロ CICRLEQ_FOREACH_REVERSE は head で参照される循環キューを、各要素を順に var に割り当てて逆方向に走査します。
マクロ CIRCLEQ_INIT は head が参照する循環キューを初期化します。
マクロ CIRCLEQ_INSERT_HEAD は新しい要素 elm を循環キューの先頭に挿入します。
マクロ CIRCLEQ_INSERT_TAIL は新しい要素 elm を循環キューの末尾に挿入します。
マクロ CIRCLEQ_INSERT_AFTER は新しい要素 elm を要素 listelm の後ろに挿入します。
マクロ CIRCLEQ_INSERT_BEFORE は新しい要素 elm を要素 listelm の前に挿入します。
マクロ CIRCLEQ_LAST は循環キューの末尾の要素を返します。
マクロ CIRCLEQ_NEXT は循環キューの次の要素を返します。
マクロ CIRCLEQ_PREV は循環キューの前の要素を返します。
マクロ CIRCLEQ_REMOVE は要素 elm を循環キューから削除します。
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);
| QUEUE (3) | January 24, 1994 |
| 総合手引 | セクション 3 | English | オプション |
このマニュアルページサービスについてのご意見は Ben Bullock にお知らせください。 Privacy policy.
| “ | On two occasions I have been asked [by members of Parliament], 'Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?' I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question. | ” |
| — Charles Babbage | ||