ノード侵入型ダブルリンクリストモジュール [詳解]

Xintrusive_list 連携図

データ構造
struct	XIntrusiveList
	リストノードデータを格納するコンテナ [詳解]

struct	XIntrusiveNode
	双方向リンリストリストノード [詳解]

マクロ定義
#define	xilist_foreach(list, ite)
	コンテナ先頭から順方向走査します [詳解]

#define	xilist_rforeach(list, ite)
	コンテナ末尾から逆方向走査します [詳解]

#define	xnode_entry(ptr, type, member) X_CONTAINER_OF(ptr, type, member)
	XIntrusiveNodeにオーバーラップする型のポインタを取り出します [詳解]

関数
static XIntrusiveNode *	xilist_back (const XIntrusiveList *self)
	コンテナの末尾ノードを返します

static void	xilist_clear (XIntrusiveList *self)
	コンテナを空にします

static bool	xilist_empty (const XIntrusiveList *self)
	コンテナが空かどうかを返します

static XIntrusiveNode *	xilist_end (const XIntrusiveList *self)
	コンテナの終端を指すノードを返します

static XIntrusiveNode *	xilist_front (const XIntrusiveList *self)
	コンテナの先頭ノードを返します

static XIntrusiveNode *	xilist_head (XIntrusiveList *self)
	コンテナのルートノードのポインタを返します

static void	xilist_init (XIntrusiveList *self)
	コンテナを初期化します

static bool	xilist_is_singular (const XIntrusiveList *self)
	ノード数が1つかどうかを返します

static void	xilist_move_back (XIntrusiveList self, XIntrusiveNode node)
	ノードのリンクを解除してから末尾に追加します [詳解]

static void	xilist_move_front (XIntrusiveList self, XIntrusiveNode node)
	ノードのリンクを解除してから先頭に追加しま。 [詳解]

static XIntrusiveNode *	xilist_pop_back (const XIntrusiveList *self)
	末尾ノードをコンテナから除去して返します

static XIntrusiveNode *	xilist_pop_front (const XIntrusiveList *self)
	先頭ノードをコンテナから除去して返します

static void	xilist_push_back (XIntrusiveList self, XIntrusiveNode node)
	ノードを末尾に追加します [詳解]

static void	xilist_push_front (XIntrusiveList self, XIntrusiveNode node)
	ノードを先頭に追加します [詳解]

static size_t	xilist_size (const XIntrusiveList *self)
	ノード数を返します

static void	xilist_splice_back (XIntrusiveList self, XIntrusiveList other)
	otherを末尾に連結します [詳解]

static void	xilist_splice_front (XIntrusiveList self, XIntrusiveList other)
	otherを先頭に連結します [詳解]

static void	xilist_swap (XIntrusiveList self, XIntrusiveList other)
	2つのリストの中身を入れ替えます [詳解]

static void	xilist_transfer_back (XIntrusiveList self, XIntrusiveList other, XIntrusiveNode *pos)
	末尾にotherの先頭要素からpos(pos自身も含む)までを転送します [詳解]

static void	xilist_transfer_front (XIntrusiveList self, XIntrusiveList other, XIntrusiveNode *pos)
	先頭にotherの先頭要素からpos(pos自身も含む)までを転送します [詳解]

static void	xnode_insert_next (XIntrusiveNode p1, XIntrusiveNode p2)
	p1の前にp2を挿入します

static void	xnode_insert_prev (XIntrusiveNode p1, XIntrusiveNode p2)
	p1の後ろにp2を挿入します

static void	xnode_replace (XIntrusiveNode p1, XIntrusiveNode p2)
	p1のリンクをにp2に置換えます

static void	xnode_splice (XIntrusiveNode prev, XIntrusiveNode next, XIntrusiveList *list)
	prev, next間にlistを連結します

static void	xnode_unlink (XIntrusiveNode *node)
	ノードのリンクを解除します [詳解]

詳解

ノード侵入型ダブルリンクリストモジュール

通常のリストコンテナでは、データの格納時に動的メモリ確保が必須ですが、ノード侵入型の場合、ノード侵入型の場合、データ自身がノードをメンバとして保持しているので、動的メモリ確保が不要です。

データのコピーがおこわれないため、使い方に癖がありますが、強力なデータ構造なので、特にOSの実装でよく使用されています。

マクロ定義詳解

#define xilist_foreach	(	list,
		ite
	)

値:

for (ite  = xilist_front(list);  \
         ite != xilist_end(list);    \
         ite  = ite->next)

コンテナ先頭から順方向走査します

引数

ite	XIntrusiveNode* ループ毎に、iteratorには次要素が格納されます

注意: ループ中にノードを除去したり、コンテナを操作する場合はforeach()を使用しないでください。iterator自身がコンテナから除去されると、ループが行えなくなるからです。イテレータが除去されるループは面倒ですが自分でループを書く必要があります。

 // [NG] リンクを解除した時点でイテレートできなくなる
 XIntrusiveNode* ite;
 xilist_foreach(&list, ite)
 {
     if (...)
         xnode_unlink(ite);
 }

 // [OK] 1つだけ除去してループを抜けるなら問題なし。
 XIntrusiveNode* ite;
 xilist_foreach(&list, ite)
 {
     if (...)
     {
         xnode_unlink(ite);
         break;
     }
 }

 // [OK] 1つ以上のノードを除去するならイテレータの管理は自分で行う
 XIntrusiveNode* ite = xilist_front(&ilist);
 const XIntrusiveList* const end = xilist_end(&list);
 while (ite != end)
 {
     if (...)
     {
         // 次の要素でiteratorを上書きしてから除去する。
         XIntrusiveNode* tmp = ite;
         ite = ite->next;
         xnode_unlink(tmp);
     }
     else
     {
         ite = ite->next;
     }
 }

#define xilist_rforeach	(	list,
		ite
	)

値:

for (ite  = xilist_back(list);   \
         ite != xilist_end(list);    \
         ite  = ite->prev)

コンテナ末尾から逆方向走査します

参照: xilist_foreach

#define xnode_entry	(	ptr,
		type,
		member
	)	X_CONTAINER_OF(ptr, type, member)

XIntrusiveNodeにオーバーラップする型のポインタを取り出します

引数

ptr	XIntrusiveNode*
type	取り出す型
member	型に対応するノードメンバ名 1 typedef struct ListData 2 { 3 int x; 4 XIntrusiveNode node; 5 } ListData; 6 ListData* p = xnode_entry(ptr, ListData, node);

関数詳解

static void xilist_move_back	(	XIntrusiveList *	self,
		XIntrusiveNode *	node
	)

inlinestatic

ノードのリンクを解除してから末尾に追加します

事前条件

node != NULL

static void xilist_move_front	(	XIntrusiveList *	self,
		XIntrusiveNode *	node
	)

inlinestatic

ノードのリンクを解除してから先頭に追加しま。

事前条件

node != NULL

static void xilist_push_back	(	XIntrusiveList *	self,
		XIntrusiveNode *	node
	)

inlinestatic

ノードを末尾に追加します

事前条件

node != NULL

static void xilist_push_front	(	XIntrusiveList *	self,
		XIntrusiveNode *	node
	)

inlinestatic

ノードを先頭に追加します

事前条件

node != NULL

static void xilist_splice_back	(	XIntrusiveList *	self,
		XIntrusiveList *	other
	)

inlinestatic

otherを末尾に連結します

事前条件

other != NULL

static void xilist_splice_front	(	XIntrusiveList *	self,
		XIntrusiveList *	other
	)

inlinestatic

otherを先頭に連結します

事前条件

other != NULL

static void xilist_swap	(	XIntrusiveList *	self,
		XIntrusiveList *	other
	)

inlinestatic

2つのリストの中身を入れ替えます

事前条件

other != NULL

static void xilist_transfer_back	(	XIntrusiveList *	self,
		XIntrusiveList *	other,
		XIntrusiveNode *	pos
	)

inlinestatic

末尾にotherの先頭要素からpos(pos自身も含む)までを転送します

事前条件

other != NULL
pos != NULL
posはotherに含まれる要素であること

static void xilist_transfer_front	(	XIntrusiveList *	self,
		XIntrusiveList *	other,
		XIntrusiveNode *	pos
	)

inlinestatic

先頭にotherの先頭要素からpos(pos自身も含む)までを転送します

事前条件

other != NULL
pos != NULL
posはotherに含まれる要素であること

static void xnode_unlink ( XIntrusiveNode * node )

inlinestatic

ノードのリンクを解除します

事前条件

nodeはどこかのリストに格納済みであること