リスト

リストの先頭には、 LIST_HEAD マクロで定義される構造体が置かれる。 この構造体はリストの最初の要素へのポインターを 1 つ含む。 要素は 2 重にリンクされており、 任意の要素はリストを辿らずに削除できる。 新しい要素は既存の要素の後またはリストの先頭に追加できる。 LIST_HEAD 構造体は以下のように宣言されている:

LIST_HEAD(HEADNAME, TYPE) head;

ここで HEADNAME は定義される構造体の名前であり、 TYPE はリンク内でリンクされる要素の型である。 リストの先頭へのポインターは、その後で次のように宣言される:

struct HEADNAME *headp;

(名前 head と headp はユーザーが選択できる。)

マクロ LIST_ENTRY はリストの要素を接続する構造体を宣言する。

マクロ LIST_INIT は head で参照されるリストを初期化する。

マクロ LIST_INSERT_HEAD は新たな要素 elm をリストの先頭に挿入する。

マクロ LIST_INSERT_AFTER は新たな要素 elm を要素 listelm の後に挿入する。

マクロ LIST_REMOVE は要素 elm をリストから削除する。

リストの例

LIST_HEAD(listhead, entry) head;
struct listhead *headp;                 /* リストの先頭。*/
struct entry {


    ...


    LIST_ENTRY(entry) entries;          /* リスト。 */


    ...
} *n1, *n2, *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);


                                        /* 順方向に辿る。*/
for (np = head.lh_first; np != NULL; np = np->entries.le_next)


    np-> ...
while (head.lh_first != NULL)           /* 削除する。*/


    LIST_REMOVE(head.lh_first, entries);

テールキュー

テールキューの先頭には TAILQ_HEAD マクロで定義される構造体が置かれる。 この構造体は 1 組のポインターを含んでいる。 1 つはテールキューの最初の要素へのポインターであり、 もう 1 つはテールキューの最後の要素へのポインターである。 要素は 2 重にリンクされており、 任意の要素はテールキューを辿らずに削除できる。 新しい要素は既存の要素の後またはテールキューの先頭または末尾に追加できる。 TAILQ_HEAD 構造体は以下のように定義されている:

TAILQ_HEAD(HEADNAME, TYPE) head;

ここで HEADNAME は定義される構造体の名前であり、 TYPE はテールキュー内でリンクされる要素の型である。 テールキューの先頭へのポインターは、その後で次のように宣言される:

struct HEADNAME *headp;

(名前 head と headp はユーザーが選択できる。)

マクロ TAILQ_ENTRY はテールキューの要素を接続する構造体を宣言する。

マクロ TAILQ_INIT は head で参照されるテールキューを初期化する。

マクロ TAILQ_INSERT_HEAD は新たな要素 elm をテールキューの先頭に挿入する。

マクロ TAILQ_INSERT_TAIL は新たな要素 elm をテールキューの末尾に挿入する。

マクロ TAILQ_INSERT_AFTER は新たな要素 elm を要素 listelm の後に挿入する。

マクロ TAILQ_REMOVE は要素 elm をテールキューから削除する。

テールキューの例

TAILQ_HEAD(tailhead, entry) head;
struct tailhead *headp;                 /* テールキューの先頭。*/
struct entry {


    ...


    TAILQ_ENTRY(entry) entries;         /* テールキュー。*/


    ...
} *n1, *n2, *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);


                                        /* 順方向に辿る。*/
for (np = head.tqh_first; np != NULL; np = np->entries.tqe_next)


    np-> ...


                                        /* 削除する。*/
while (head.tqh_first != NULL)


    TAILQ_REMOVE(&head, head.tqh_first, entries);

循環キュー

循環キューの先頭には CIRCLEQ_HEAD マクロで定義される構造体が置かれる。 この構造体は 1 組のポインターを含んでいる。 1 つは循環キューの最初の要素へのポインターであり、 もう 1 つは循環キューの最後の要素へのポインターである。 要素は 2 重にリンクされており、 任意の要素はキューを辿らずに削除できる。 新しい要素は、既存の要素の後または前、またはキューの先頭または末尾に追加できる。 A CIRCLEQ_HEAD 構造体は以下のように定義されている:

CIRCLEQ_HEAD(HEADNAME, TYPE) head;

ここで HEADNAME は定義される構造体の名前であり、 TYPE は循環キュー内でリンクされる要素の型である。 循環キューの先頭へのポインターは、その後で次のように宣言される:

struct HEADNAME *headp;

(名前 head と headp はユーザーが選択できる。)

マクロ CIRCLEQ_ENTRY は循環キューの要素を接続する構造体を宣言する。

マクロ CIRCLEQ_INIT は head で参照される循環キューを初期化する。

マクロ CIRCLEQ_INSERT_HEAD は新たな要素 elm を循環キューの先頭に挿入する。

マクロ CIRCLEQ_INSERT_TAIL は新たな要素 elm を循環キューの末尾に挿入する。

マクロ CIRCLEQ_INSERT_AFTER は新たな要素 elm を要素 listelm の後に挿入する。

マクロ CIRCLEQ_INSERT_AFTER は新たな要素 elm を要素 listelm の前に挿入する。

マクロ CIRCLEQ_REMOVE は要素 elm を循環キューから削除する。

循環キューの例

CIRCLEQ_HEAD(circleq, entry) 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);


                                        /* 順方向に辿る。*/
for (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next)


    np-> ...


                                        /* 逆方向に辿る。*/
for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev)


    np-> ...


                                        /* 削除する。*/
while (head.cqh_first != (void *)&head)


    CIRCLEQ_REMOVE(&head, head.cqh_first, entries);