LIST_ENTRY の仕組みと利用方法

Windows の基本的なデータ構造 LIST_ENTRY

LIST_ENTRY とは何か？

この資料では Windows の基本的なデータ構造である LIST_ENTRY について説明します。

自分で使うことはあまり無くても、デバッグなどをしているときに必要になりますので覚えておくと良いでしょう。

LIST_ENTRY は双方向リンクリスト

LIST_ENTRY というのは MSDN でも次のように紹介されているように、非常に単純な双方向のリンクリスト (Doubly Linked List) です。

typedef struct _LIST_ENTRY {
  LIST_ENTRY* FLINK;
  LIST_ENTRY* BLINK;
} LIST_ENTRY, 
 *PLIST_ENTRY;

わかる人には、なんだそれだけか、と思われるでしょうが、これが WinNT.h や MspUtils.h などで宣言されているように、しばしば非常に便利なマクロと組み合わされて広く使用されています。

ついでに片方向リストも紹介しておくと、片方向のリストは WinNT.h で SINGLE_LIST_ENTRY として定義されており、それは次の形をしています。

typedef struct _SINGLE_LIST_ENTRY {
	struct _SINGLE_LIST_ENTRY *Next;
} SINGLE_LIST_ENTRY, 
 *PSINGLE_LIST_ENTRY;

この資料では、SINGLE LIST ENTRY については詳しく説明しません。

さて、LIST_ENTRY に話を戻します。LIST_ENTRY は Flink と Blink という二つのメンバーを持つ構造体であることが分かります。

これは、図1 のように前後のノードを指し示します。

図1

Flink, Blink はそれぞれ Forward Link、Backward Link の省略形であり、それぞれがその前後のノードの先頭を指すポインタです。

LIST_ENTRY の使用方法～埋め込んで使う

通常、これらを単独で使用することはしません。何らかのデータ構造に埋め込んで使用します。

例えば、次のような構造体を例に取ると、linkField という名前のLIST ENTRY が埋め込まれています。

typedef struct _FOO
{
	DWORD data1;
	DWORD data2;
	LIST_ENTRY linkField;
	DWORD data3;
} FOO;

このようにすることで、データ構造間に図2 のようなリンクが構成されることが分かります。

CONTAINING RECORD マクロ

前節では LIST_ENTRY 構造体を目的のデータ構造のメンバーとして埋め込むことにより、リストを構成する方法を示しました。

しかし、これだけではプログラムから使用するときに決して使いやすいものとはいえません。

なぜなら、図2 中の但し書きに書いてあるように、リストをたどって取得できるポインターは、一般に、あるデータ構造内の LIST_ENTRY フィールドを指しているからです。

図2: LIST ENTRY の埋め込み

このため、本来取得したいデータ構造の先頭 (前節の例ではMY_LISTDATA) とリンクフィールドとのオフセットを求める必要があるのです。

上述の問題を解決するために使用される、CONTAINING RECORD という便利なマクロがあります。

定義は次のとおりです。

#define CONTAINING_RECORD(address, type, field) \
     ((type *)((PCHAR)(address) - (ULONG_PTR)(&((type *)0)->field)))

ちょっとみただけでは、何をしているか分かりにくいので、具体的な使用方法を挙げて説明します。

そこで、前出のFOO 構造体をもう一度取り上げます。

typedef struct _FOO
{
	DWORD data1;
	DWORD data2;
	LIST_ENTRY linkField;
	DWORD data3;
} FOO;

ここでリストをたどることにより、linkField へのポインタpLink が取得できたとします。

FOO 構造体のすべてのメンバー (data1, data2, linkField 及び data3) へアクセスするためには、 FOO 構造体の先頭へのポインタ pFoo がわかればよいことになります。

図にすると図3 の状況です。

図3: pLink からpFoo を求める

問題設定がちょっと長くなりましたが、結局この問題を解く鍵が CONTAINING_RECORD マクロです。

pFoo は次のように取得できます。

FOO* pFoo = (FOO*) CONTAINING_RECORD(pLink, FOO, linkField);

その他のマクロ

以上まででLIST ENTRY データ構造とそれを使用する際に便利なマクロとして CONTAINING RECORD マクロを紹介しました。以下では LIST ENTRY を使用するためのその他のマクロを補足説明します。

InitializeListHead マクロ

InitializeListHead マクロはリストの先頭を初期化します。この場合、初期化時にFlink とBlink を自身を指すように設定します。

//
//  VOID
//  InitializeListHead(
//      PLIST_ENTRY ListHead
//      );
//

#define InitializeListHead(ListHead) (\
     (ListHead)->Flink = (ListHead)->Blink = (ListHead))

具体的な使用例は下記のコードの Init() を参考にしてください。

IsListEmpty マクロ

リストにノードを含むかどうか判定します。Flink が自身を指している場合、ノードが無いと判定します。

//
//  BOOLEAN
//  IsListEmpty(
//      PLIST_ENTRY ListHead
//      );
//

#define IsListEmpty(ListHead) \
     ((ListHead)->Flink == (ListHead))

具体的な使用例は下記のコードの Init() を参考にしてください。

Remove 系マクロ

リストからノードを削除する場合には、RemoveHeadList マクロあるいは RemoveTailList マクロが利用できます。ただし、その名前から分かるようにリストの先頭(Head) あるいは最後尾(Tail) からノードを取る操作にのみ対応しています。

定義は以下のようになります。

//
//  PLIST_ENTRY
//  RemoveHeadList(
//      PLIST_ENTRY ListHead
//      );
//

#define RemoveHeadList(ListHead) \
     (ListHead)->Flink;\
     {RemoveEntryList((ListHead)->Flink)}

//
//  PLIST_ENTRY
//  RemoveTailList(
//      PLIST_ENTRY ListHead
//      );
//

#define RemoveTailList(ListHead) \
     (ListHead)->Blink;\
     {RemoveEntryList((ListHead)->Blink)}

//
//  VOID
//  RemoveEntryList(
//      PLIST_ENTRY Entry
//      );
//

#define RemoveEntryList(Entry) {\
     PLIST_ENTRY _EX_Blink;\
     PLIST_ENTRY _EX_Flink;\
     _EX_Flink = (Entry)->Flink;\
     _EX_Blink = (Entry)->Blink;\
     _EX_Blink->Flink = _EX_Flink;\
     _EX_Flink->Blink = _EX_Blink;\
     }

コード例は下記コードののRemoveItem() を参照してください。

Insert 系マクロ

リストからノードを削除する場合には、InsertHeadList マクロあるいは InsertTailList マクロが利用できます。ただし、その名前から分かるようにリストの先頭 (Head) あるいは最後尾 (Tail) にノードを挿入する操作にのみ対応しています。

定義は以下のようになります。

//
//  VOID
//  InsertTailList(
//      PLIST_ENTRY ListHead,
//      PLIST_ENTRY Entry
//      );
//

#define InsertTailList(ListHead,Entry) {\
     PLIST_ENTRY _EX_Blink;\
     PLIST_ENTRY _EX_ListHead;\
     _EX_ListHead = (ListHead);\
     _EX_Blink = _EX_ListHead->Blink;\
     (Entry)->Flink = _EX_ListHead;\
     (Entry)->Blink = _EX_Blink;\
     _EX_Blink->Flink = (Entry);\
     _EX_ListHead->Blink = (Entry);\
     }

//
//  VOID
//  InsertHeadList(
//      PLIST_ENTRY ListHead,
//      PLIST_ENTRY Entry
//      );
//

#define InsertHeadList(ListHead,Entry) {\
     PLIST_ENTRY _EX_Flink;\
     PLIST_ENTRY _EX_ListHead;\
     _EX_ListHead = (ListHead);\
     _EX_Flink = _EX_ListHead->Flink;\
     (Entry)->Flink = _EX_Flink;\
     (Entry)->Blink = _EX_ListHead;\
     _EX_Flink->Blink = (Entry);\
     _EX_ListHead->Flink = (Entry);\
     }

具体的なコード例は下記のの AddItem() を参照してください。

具体的な使用例

ここでは上記のマクロを利用してコードを書いてみましょう。

マクロを試すことが目的なので、エラー処理はしないで適当に assert なんかで処理をとめてます。まねしないでくださいね。

#include <windows.h>
#include <stdio.h>
#include <tchar.h>
#include <assert.h>

// ...上記マクロの定義は省略
// SDK の MSPUTILS.H などを参考にしてください

/////////////////////////////////////////////////////////////////////////////


typedef struct _MY_LISTDATA
{
     DWORD data1;
     DWORD data2;
     LIST_ENTRY linkField;
     DWORD data3;
     TCHAR szName[256];
     DWORD data4;
} MY_LISTDATA, *PMY_LISTDATA;


LIST_ENTRY g_MyListdata;


/////////////////////////////////////////////////////////////////////


void Init() {

     InitializeListHead(&g_MyListdata);

}


/////////////////////////////////////////////////////////////////////


void AddItem( LPTSTR pszItem ) {

     PMY_LISTDATA pNode;

     _tprintf( TEXT("Adding: %s\n"), pszItem );
     
     pNode = (PMY_LISTDATA) malloc(sizeof(MY_LISTDATA));
     assert( pNode );

     ::ZeroMemory(pNode, sizeof(MY_LISTDATA));

     _stprintf(pNode->szName, pszItem );
     InsertHeadList(&g_MyListdata, &pNode->linkField);

}


/////////////////////////////////////////////////////////////////////


void AddItems() {

     _tprintf( TEXT("--- Add Three Items ---\n") );

     AddItem ( TEXT("Outlook") );
     AddItem ( TEXT("Excel") );
     AddItem ( TEXT("Word") );
     
}


/////////////////////////////////////////////////////////////////////


void PrintAllItems() {

     _tprintf( TEXT("--- Print All Items ---\n") );

     PMY_LISTDATA pData = NULL;
     PLIST_ENTRY pEntry;

     for (pEntry = g_MyListdata.Flink;
          &g_MyListdata != pEntry;
          pEntry = pEntry->Flink) {

          pData = (PMY_LISTDATA) CONTAINING_RECORD(
               pEntry, 
               MY_LISTDATA, 
               linkField);
          
          _tprintf(TEXT("Item: %s\n"), pData->szName);

     }

}


/////////////////////////////////////////////////////////////////////


void RemoveItem() {

     PLIST_ENTRY pRemovedEntry;
     PMY_LISTDATA pData;

     _tprintf( TEXT("Removing One Item: ") );

     pRemovedEntry = RemoveHeadList(&g_MyListdata);

     pData = (PMY_LISTDATA) CONTAINING_RECORD(
          pRemovedEntry,
          MY_LISTDATA,
          linkField);

     _tprintf(TEXT("%s\n"), pData->szName);

     free(pData);

}


/////////////////////////////////////////////////////////////////////


void CleanupList() {

     _tprintf( TEXT("--- Clean up All Items ---\n") );

     while(!IsListEmpty(&g_MyListdata)) {

          RemoveItem();
          
     }

}


/////////////////////////////////////////////////////////////////////


void main() {

     Init();
     AddItems();
     PrintAllItems();
     CleanupList();

}

以上をビルドし実行すると以下の結果を得ます。

> listtest.exe
--- Add Three Items ---
Adding: Outlook
Adding: Excel
Adding: Word
--- Print All Items ---
Item: Word
Item: Excel
Item: Outlook
--- Clean up All Items ---
Removing One Item: Word
Removing One Item: Excel
Removing One Item: Outlook

>

この結果の通り、Outlook, Excel, Word の順番にヘッドからノードを追加したので、内容の表示、削除共にヘッドから Flink 方向に処理すると追加と逆の順番に出力されています。