̾??

SLIST_EMPTY, SLIST_ENTRY, SLIST_FIRST, SLIST_FOREACH, SLIST_HEAD, SLIST_HEAD_INITIALIZER, SLIST_INIT, SLIST_INSERT_AFTER, SLIST_INSERT_HEAD, SLIST_NEXT, SLIST_REMOVE_HEAD, SLIST_REMOVE, STAILQ_EMPTY, STAILQ_ENTRY, STAILQ_FIRST, STAILQ_FOREACH, STAILQ_HEAD, STAILQ_HEAD_INITIALIZER, STAILQ_INIT, STAILQ_INSERT_AFTER, STAILQ_INSERT_HEAD, STAILQ_INSERT_TAIL, STAILQ_LAST, STAILQ_NEXT, STAILQ_REMOVE_HEAD, STAILQ_REMOVE, LIST_EMPTY, LIST_ENTRY, LIST_FIRST, LIST_FOREACH, LIST_HEAD, LIST_HEAD_INITIALIZER, LIST_INIT, LIST_INSERT_AFTER, LIST_INSERT_BEFORE, LIST_INSERT_HEAD, LIST_NEXT, LIST_REMOVE, TAILQ_EMPTY, TAILQ_ENTRY, TAILQ_FIRST, TAILQ_FOREACH, TAILQ_FOREACH_REVERSE, TAILQ_HEAD, TAILQ_HEAD_INITIALIZER, TAILQ_INIT, TAILQ_INSERT_AFTER, TAILQ_INSERT_BEFORE, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_LAST, TAILQ_NEXT, TAILQ_PREV, TAILQ_REMOVE, CIRCLEQ_EMPTY, CIRCLEQ_ENTRY, CIRCLEQ_FIRST, CIRCLEQ_FOREACH, CIRCLEQ_FOREACH_REVERSE, CIRCLEQ_HEAD, CIRCLEQ_HEAD_INITIALIZER, CIRCLEQ_INIT, CIRCLEQ_INSERT_AFTER, CIRCLEQ_INSERT_BEFORE, CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, CIRCLE_LAST, CIRCLE_NEXT, CIRCLE_PREV, CIRCLEQ_REMOVE — ñ?????󥯥ꥹ?ȡ?ñ?????󥯥ơ??륭?塼???ꥹ?ȡ??ơ??륭?塼?? ?۴ĥ??塼?μ???

????

<sys/queue.h> SLIST_EMPTY(SLIST_HEAD *head) SLIST_ENTRY(TYPE) SLIST_FIRST(SLIST_HEAD *head) SLIST_FOREACH(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME) SLIST_HEAD(HEADNAME, TYPE) SLIST_HEAD_INITIALIZER(SLIST_HEAD head) SLIST_INIT(SLIST_HEAD *head) SLIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, SLIST_ENTRY NAME) SLIST_INSERT_HEAD(SLIST_HEAD *head, TYPE *elm, SLIST_ENTRY NAME) SLIST_NEXT(TYPE *elm, SLIST_ENTRY NAME) SLIST_REMOVE_HEAD(SLIST_HEAD *head, SLIST_ENTRY NAME) SLIST_REMOVE(SLIST_HEAD *head, TYPE *elm, TYPE, SLIST_ENTRY NAME) STAILQ_EMPTY(STAILQ_HEAD *head) STAILQ_ENTRY(TYPE) STAILQ_FIRST(STAILQ_HEAD *head) STAILQ_FOREACH(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME) STAILQ_HEAD(HEADNAME, TYPE) STAILQ_HEAD_INITIALIZER(STAILQ_HEAD head) STAILQ_INIT(STAILQ_HEAD *head) STAILQ_INSERT_AFTER(STAILQ_HEAD *head, TYPE *listelm, TYPE *elm, STAILQ_ENTRY NAME) STAILQ_INSERT_HEAD(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME) STAILQ_INSERT_TAIL(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME) STAILQ_LAST(STAILQ_HEAD *head, TYPE, STAILQ_ENTRY NAME) STAILQ_NEXT(TYPE *elm, STAILQ_ENTRY NAME) STAILQ_REMOVE_HEAD(STAILQ_HEAD *head, STAILQ_ENTRY NAME) STAILQ_REMOVE(STAILQ_HEAD *head, TYPE *elm, TYPE, STAILQ_ENTRY NAME) LIST_EMPTY(LIST_HEAD *head) LIST_ENTRY(TYPE) LIST_FIRST(LIST_HEAD *head) LIST_FOREACH(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME) LIST_HEAD(HEADNAME, TYPE) LIST_HEAD_INITIALIZER(LIST_HEAD head) LIST_INIT(LIST_HEAD *head) LIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME) LIST_INSERT_BEFORE(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME) LIST_INSERT_HEAD(LIST_HEAD *head, TYPE *elm, LIST_ENTRY NAME) LIST_NEXT(TYPE *elm, LIST_ENTRY NAME) LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME) TAILQ_EMPTY(TAILQ_HEAD *head) TAILQ_ENTRY(TYPE) TAILQ_FIRST(TAILQ_HEAD *head) TAILQ_FOREACH(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME) TAILQ_FOREACH_REVERSE(TYPE *var, TAILQ_HEAD *head, HEADNAME, TAILQ_ENTRY NAME) TAILQ_HEAD(HEADNAME, TYPE) TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head) TAILQ_INIT(TAILQ_HEAD *head) TAILQ_INSERT_AFTER(TAILQ_HEAD *head, TYPE *listelm, TYPE *elm, TAILQ_ENTRY NAME) TAILQ_INSERT_BEFORE(TYPE *listelm, TYPE *elm, TAILQ_ENTRY NAME) TAILQ_INSERT_HEAD(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME) TAILQ_INSERT_TAIL(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME) TAILQ_LAST(TAILQ_HEAD *head, HEADNAME) TAILQ_NEXT(TYPE *elm, TAILQ_ENTRY NAME) TAILQ_PREV(TYPE *elm, HEADNAME, TAILQ_ENTRY NAME) TAILQ_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME) CIRCLEQ_EMPTY(CIRCLEQ_HEAD *head) CIRCLEQ_ENTRY(TYPE) CIRCLEQ_FIRST(CIRCLEQ_HEAD *head) CIRCLEQ_FOREACH(TYPE *var, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY NAME) CIRCLEQ_FOREACH_REVERSE(TYPE *var, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY NAME) CIRCLEQ_HEAD(HEADNAME, TYPE) CIRCLEQ_HEAD_INITIALIZER(CIRCLEQ_HEAD head) CIRCLEQ_INIT(CIRCLEQ_HEAD *head) CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *head, TYPE *listelm, TYPE *elm, CIRCLEQ_ENTRY NAME) CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *head, TYPE *listelm, TYPE *elm, CIRCLEQ_ENTRY NAME) CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME) CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME) CIRCLEQ_LAST(CIRCLEQ_HEAD *head) CIRCLEQ_NEXT(TYPE *elm, CIRCLEQ_ENTRY NAME) CIRCLE_PREV(TYPE *elm, CIRCLEQ_ENTRY NAME) CIRCLEQ_REMOVE(CIRCLEQ_HEAD *head, TYPE *elm, CIRCLEQ_ENTRY NAME)

????

???Υޥ????ϡ?ñ?????󥯥ꥹ?ȡ?ñ?????󥯥ơ??륭?塼???ꥹ?ȡ? ?ơ??륭?塼???۴ĥ??塼?Ȥ?????5 ?????Υǡ?????¤?????????Ƥ?????ư??ޤ??? 5 ?ĤΥǡ?????¤?Ϥ??٤ơ??ʲ??ε?ǽ?򥵥ݡ??Ȥ??ޤ???

?ꥹ?Ȥ???Ƭ?˿??????????ȥ??????????롣
?ꥹ?Ȥ?¸?ߤ???Ǥ?դ????Ǥθ????˿??????????ȥ??????????롣
?ꥹ?Ȥ???Ƭ???饨???ȥ??? O(1) ???????롣
?ꥹ?Ȥ?Ǥ?դΥ????ȥ??? O(n) ???????롣
?ꥹ?Ȥ??????????????롣

ñ?????󥯥ꥹ?Ȥϡ?5 ?ĤΥǡ?????¤?????ǺǤ?ñ???ǡ????? 5?Ĥε?ǽ?? ?????ݡ??Ȥ??ޤ????? ñ?????󥯥ꥹ?Ȥϡ? ?ǡ??????åȤ??礭???????????ۤȤ??ɤʤ????⤷???ϡ??????ʤ????ץꥱ?????????? ?ޤ??? LIFO ???塼?μ?????????Ū?Ǥ???

ñ?????󥯥ơ??륭?塼?ˤϰʲ??ε?ǽ?⤢???ޤ???

?ꥹ?Ȥ??????˥????ȥ????ɲä??롣

???????ʲ??????դ??Ƥ?????????

?ꥹ?Ȥ??????Ǥϡ??ꥹ?ȤΥإåɤ?ɬ?????ꤹ??ɬ?פ????롣
?ƥإåɥ????ȥ??Ǥϡ?1 ?ĤǤϤʤ? 2 ?ĤΥݥ??󥿤?ɬ?פǤ??롣
ñ?????󥯥ꥹ?Ȥ??ꡢ?????ɥ????????? 15% ?礭????ư?????? 20% ?٤???

ñ?????󥯥ơ??륭?塼?ϡ? ?ǡ??????åȤ??礭???????????ۤȤ??ɤʤ????⤷???ϡ??????ʤ????ץꥱ?????????? ?ޤ??? FIFO ???塼?μ?????????Ū?Ǥ???

???ť??󥯥????פΤ??٤ƤΥǡ?????¤ (?ꥹ?ȡ??ơ??륭?塼???۴ĥ??塼) ?ˤ? ?ʲ??ε?ǽ?⤢???ޤ???

?ꥹ?Ȥ?¸?ߤ???Ǥ?դ????Ǥ????˿??????????ȥ??????????롣
?ꥹ?Ȥ?Ǥ?դΥ????ȥ??? O(1) ???????롣

???????ʲ??????դ??Ƥ?????????

?????Ǥˤϡ?1 ?ĤǤϤʤ? 2 ?ĤΥݥ??󥿤?ɬ?פǤ??롣
ñ?????󥯥ǡ?????¤???ꡢ?????ɥ??????ȼ¹Ի??? (?????Ͻ???) ???? 2 ?ܤ? ?ʤ롣

???󥯥ꥹ?Ȥϡ????ť??󥯥ǡ?????¤?????ǺǤ?ñ???ǡ?ñ?????󥯥ꥹ?Ȥ? ??ǽ?˲ä??ƾ??ε?ǽ???????ݡ??Ȥ??ޤ?????

?ơ??륭?塼?ˤϰʲ??ε?ǽ?⤢???ޤ???

?ꥹ?Ȥ??????˥????ȥ????ɲä??롣
??????????Ƭ?ؤȵդ????????롣

???????ʲ??????դ??Ƥ?????????

?ꥹ?Ȥ??????Ⱥ????Ǥϡ??ꥹ?ȤΥإåɤ?ɬ?????ꤹ??ɬ?פ????롣
?ƥإåɥ????ȥ??Ǥϡ?1 ?ĤǤϤʤ? 2 ?ĤΥݥ??󥿤?ɬ?פǤ??롣
ñ?????󥯥ꥹ?Ȥ??ꡢ?????ɥ????????? 15% ?礭???????????֤??? 20% Ĺ????

?۴ĥ??塼?ˤϰʲ??ε?ǽ?⤢???ޤ???

?ꥹ?Ȥ??????˥????ȥ????ɲä??롣
??????????Ƭ?ؤȵդ????????롣

???????ʲ??????դ??Ƥ?????????

?ꥹ?Ȥ??????Ⱥ????Ǥϡ??ꥹ?ȤΥإåɤ?ɬ?????ꤹ??ɬ?פ????롣
?ƥإåɥ????ȥ??Ǥϡ?1 ?ĤǤϤʤ? 2 ?ĤΥݥ??󥿤?ɬ?פǤ??롣
?????ν?λ???郎????ʣ???Ǥ??롣
?ꥹ?Ȥ??ꡢ?????ɥ????????? 40% ?礭???????????֤??? 45% Ĺ????

?ޥ????????Ǥϡ? 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 ?ޥ??????????????빽¤?Τ??դ??ޤ??? ???ι?¤?Τˤϡ??ꥹ?Ȥ???Ƭ?????Ǥ??ؤ??ݥ??󥿤? 1 ?Ĵޤޤ??ޤ??? ???Ǥϡ?Ǥ?դ????Ǥ? O(n) ???????????ˤ??ơ? ???ڡ????ȥݥ??????????Υ????Хإåɤ??Ǿ??ˤʤ??褦??ñ?????󥯤????ޤ??? ?????????Ǥϡ???¸?????Ǥθ??????ꥹ?Ȥ???Ƭ?ǥꥹ?Ȥ??ɲäǤ??ޤ??? SLIST_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 ?ޥ??????????????빽¤?Τ??Ĥ??ޤ??? ???ι?¤?Τˤϥơ??륭?塼????Ƭ?????Ǥ??ؤ??ݥ??󥿤? ?ơ??륭?塼???????????Ǥ??ؤ??ݥ??󥿤? 2 ?Ĥ??ޤޤ??ޤ??? ???Ǥϡ?Ǥ?դ????Ǥ? O(n) ???????????ˤ??ơ? ???ڡ????ȥݥ??????????Υ????Хإåɤ??Ǿ??ˤʤ??褦??ñ?????󥯤????ޤ??? ?????????Ǥϡ???¸?????Ǥθ??????ơ??륭?塼????Ƭ???ơ??륭?塼???????? ?ơ??륭?塼???ɲäǤ??ޤ??? STAILQ_HEAD ??¤?Τϰʲ??Τ褦???????????ޤ???

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 ?ޥ??????????????빽¤?Τ??դ??ޤ??? ???ι?¤?Τˤϡ??ꥹ?Ȥ???Ƭ?????Ǥ??ؤ??ݥ??󥿤? 1 ?Ĵޤޤ??ޤ??? ???Ǥ????Ť˥??󥯤????Ƥ????Τǡ??ꥹ?Ȥ???????????Ǥ?դ????Ǥ??????Ǥ??ޤ??? ?????????Ǥϡ???¸?????Ǥ???????¸?????Ǥθ塢?ꥹ?Ȥ???Ƭ?? ?ꥹ?Ȥ??ɲäǤ??ޤ??? LIST_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 ?ޥ??????????????빽¤?Τ??դ??ޤ??? ???ι?¤?Τˤϡ??ơ??륭?塼?κǽ??????Ǥ??ؤ??ݥ??󥿤? ?ơ??륭?塼????Ƭ?????Ǥ??ؤ??ݥ??󥿤? 2 ?Ĥ??ޤޤ??ޤ??? ???Ǥ????Ť˥??󥯤????Ƥ????Τǡ??ơ??륭?塼???????????? Ǥ?դ????Ǥ??????Ǥ??ޤ??? ?????????Ǥϡ???¸?????Ǥ???????¸?????Ǥθ塢?ơ??륭?塼????Ƭ?? ?ơ??륭?塼???????ǥơ??륭?塼???ɲäǤ??ޤ??? TAILQ_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 ?ޥ??????????????빽¤?Τ??դ??ޤ??? ???ι?¤?Τˤϡ??۴ĥ??塼????Ƭ?????Ǥ??ؤ??ݥ??󥿤? ?۴ĥ??塼???????????Ǥ??ؤ??ݥ??󥿤? 2 ?Ĥ??ޤޤ??ޤ??? ???Ǥ????Ť˥??󥯤????Ƥ????Τǡ????塼???????????? Ǥ?դ????Ǥ??????Ǥ??ޤ??? ?????????Ǥϡ???¸?????Ǥ???????¸?????Ǥθ??????۴ĥ??塼????Ƭ?? ?۴ĥ??塼???????ǽ۴ĥ??塼???ɲäǤ??ޤ??? CIRCLEQ_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 ?ؿ??? 4.4BSD ?ǤϤ??????о줷?ޤ?????