NetBSD:/usr/include/sys/queue.h

• queue.h
• LIST
• SLIST
• STAILQ
• SIMPLEQ
• TAILQ
• CIRCLEQ
• APPENDIX

sys/queue.h

すべてのリスト(queue?)は、先頭、あるいは先頭と末尾の構造体(element)を指し示す 「???_HEAD」という名前のマクロで定義される構造体を持つ。

各要素(element)は、「???_ENTRY」というマクロを、使用する構造体の中にメンバとして持つ必要がある。

	HEAD用の構造体 (HEAD)
	   ↓
	要素用の構造体1 (含ENTRY)
	   ↓
	要素用の構造体2 (含ENTRY)
	   ↓
	要素用の構造体3 (含ENTRY)
	   ↓
	   :
	   ↓
	要素用の構造体N (含ENTRY)

	#define LIST_HEAD(name, type)						\
	struct name {								\
		struct type *lh_first;	/* first element */			\
	}

	#define LIST_HEAD_INITIALIZER(head)					\
		{ NULL }

	#define LIST_ENTRY(type)						\
	struct {								\
		struct type *le_next;	/* next element */			\
		struct type **le_prev;	/* address of previous next element */	\
	}

	/* HEAD の宣言と定義 */
	LIST_HEAD(,my) my_head =
	    LIST_HEAD_INITIALIZER(my_head);

	/* 構造体(element)の宣言 */
	struct my {
		char *my_member1;
		short my_member2;
		LIST_ENTRY(my) my_list;	/* LIST_ENTRY の場所はどこでも可 */
		int my_member3;
		double my_member4;
	};

	void my_add(void)
	{
		struct my *myp = malloc(sizeof(struct my));

		memset(myp, 0, sizeof(struct my));
		myp->my_member1 = ...
		myp->my_member2 = ...
		myp->my_member3 = ...

		LIST_INSERT_HEAD(my_head, myp,my_list);
	}

	void my_remove(struct my *myp)
	{
		LIST_REMOVE(myp, my_list);
	}

LIST

#define LIST_HEAD(name, type)				\
struct name {						\
	struct type *lh_first;	/* first element */	\
}

#define LIST_ENTRY(type)				\
struct {						\
	struct type *le_next;	/* next element */	\
	struct type **le_prev;	/* address of previous next element */	\
}

LIST_HEAD は最初の element へのポインタのみ持つ。
ENTRY には、次の element へのポインタと、自分を指しているポインタへのポインタ (前の element へのポインタで無いので注意)を持つ。
(自分を指しているポインタへのポインタは、INSERT_BEFORE のために必要)

LIST_PREV は存在しないが、がんばれば、LIST_PREV も実現できなくはない。
以下のようなマクロを使えば OK。(ただし head を知ってなければいけない)

#define OFFSETOF(type, member)	((size_t)(&((struct type *)0)->member))

#define LIST_PREV(head, type, elm, field)						\
	((((struct type *)((elm)->field.le_prev)) == ((struct type *)(&(head)))) ?	\
	   (struct type *)NULL :								\
	   ((struct type *)(((char*)((elm)->field.le_prev))-(OFFSETOF(type,field)))))

SLIST

#define SLIST_HEAD(name, type)						\
struct name {								\
	struct type *slh_first; /* first element */			\
}

#define SLIST_ENTRY(type)						\
struct {								\
	struct type *sle_next;	/* next element */			\
}

HEAD には最初の element へのポインタ、ENTRY には次の element へのポインタだけを持つ。

そのため、PREV も INSERT もできない。INSERT_HEAD と REMOVE_HEAD しかできないので、用途がかなり制限される。

しかし何故かマクロでは REMOVE が定義されている。
どうやって実装しているのかと思って中身を見ると、HEADから該当elementまでリストを辿るというアホなことをしている。
これはダメだろ常識的に考えて…。
SLIST_REMOVE は小さなリストでしか使ってはいけません。

STAILQ

SIMPLEQ

#define SIMPLEQ_HEAD(name, type)					\
struct name {								\
	struct type *sqh_first; /* first element */			\
	struct type **sqh_last; /* addr of last next element */ 	\
}

#define SIMPLEQ_ENTRY(type)						\
struct {								\
	struct type *sqe_next;	/* next element */			\
}

SIMPLEQ_HEAD は、最初と最後の element へのポインタを持っている。
ただし、最後のポインタ(sqh_last) は、最後の element の SIMPLEQ_ENTRY のポインタである。

SIMPLEQ_ENTRY には、次の element のポインタだけを持つ。LIST や他の queue のように 自分を差しているポインタへのポインタは持たない。
したがって、任意の element の前に element を挿入すること(SIMPLEQ_INSERT_BEFORE)はできない。

上述のように sqh_prev 相当のものを持たないので、SIMPLEQ_REMOVE さえできないことに注意。 SIMPLEQ_REMOVE_HEAD で、先頭から削除することしかできない。
もし任意の要素を REMOVE したいのならば、先頭から該当 element まで辿って…、みたいなことをしなければならない。

当然 SIMPLEQ_PREV も不可能。
これも先頭から辿ればできなくはないけど。

TAILQ

#define TAILQ_HEAD(name, type)                                  \
struct name {                                                   \
        struct type *tqh_first; /* first element */             \
        struct type **tqh_last; /* addr of last next element */ \
}

#define TAILQ_ENTRY(type)                                              \
struct {                                                               \
        struct type *tqe_next;  /* next element */                     \
        struct type **tqe_prev; /* address of previous next element */ \
}

しかし、たったこれだけの変更で、常に tqe_prev->tqe_prev と辿れることが保証され、
tqe_prev->tqe_prev->tqe_next と辿ることにより、一つ前の element を得ることができるようになってる。すごい。
(図参照。HEAD では tqe_next = tqh_first、tqe_prev = tqh_last であることを利用)

#define TAILQ_PREV(elm, headname, field)    \
	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

構造的には、かなり万能なリスト構造である。無理に欠点を探すとしたら

• HEADと各ENTRYについて、ポインタ2つ分の領域が必要
• TAILQ_INSERT_AFTER および TAILQ_REMOVE には、headのポインタが必要

CIRCLEQ

#define CIRCLEQ_HEAD(name, type)                            \
struct name {                                               \
        struct type *cqh_first;         /* first element */ \
        struct type *cqh_last;          /* last element */  \
}

#define CIRCLEQ_ENTRY(type)                                    \
struct {                                                       \
        struct type *cqe_next;          /* next element */     \
        struct type *cqe_prev;          /* previous element */ \
}

一見便利そうだが、 先頭 element の ENTRY の prev が、HEAD を差してしまっていたり、 末尾 element の ENTRY の next が、HEAD を差してしまっていたりして、結構イリーガル。

つまり先頭 element から prev を辿るときに、その先が HEAD か element かで 場合分けしなければならないし、末尾の element から next を辿るときに、 その先が HEAD か element かで場合分けしなければならない。

しかも場合分けしなければならないということは、INSERTやREOVE時にHEADを知っておく必要がある。 つまり element だけが渡された関数内で、CIRCLEQ_INSERT や CIRCLEQ_REMOVE することができない。
微妙に使いにくい。

他の queue と違い、link に関する全ての情報を持っているので、前後、先頭末尾と、 好きに辿ることができる。

おまけ

NetBSDのqueue.h

結論

PREVを辿ったり、最後尾にアクセスしたければTAILQを使う

各要素中のエントリを小さくしたいのであれば、SLIST/SIMPLEQを考える。
ただし、SLIST/STAILQ/SIMPLEQのREMOVEはコストが高いので事実上小さなリストでしか使えない。 巨大なリストでは REMOVE_HEAD しか使えないと思うべし。

SLISTとSTAILQはENTRYにポインタが一つだけなのが利点(たぶん)。 各要素を小さくしつつ、FILO を構成したい時はSLIST。 各要素を小さくしつつ、FIFO/FILO (INSERT_HEAD, INSERT_TAIL, REMOVE_HEAD) したい時は STAILQ, SIMPLEQ。

TAILQがあればCIRCLEQは要らない子。