listnode
読み：リストノード
外語：listnode

　Androidで使われている連結リスト。この構造体のほか、関連する関数やマクロなどが多数定義されている。
目次
書式
　#include <cutils/list.h>
概要
定義
　struct listnodeは、Linuxで実装された画期的な連結リストlist_headと同様の機能を持った連結リストである。
　Linux用のlist_headがGPLv2なのに対して、Android用のlistnodeはApache License 2.0としてフルスクラッチで書き直されたものであるが、基本的な設計思想は大差がない。Androidの場合、カーネル層は一般にLinuxカーネルなのでlist_headが使えるが、ユーザー空間以上ではこのlistnodeを使うことになる。
　具体的には次のように定義されている。
struct listnode
{
    struct listnode *next;
    struct listnode *prev;
};
　前と次へのポインターしかない。これでどうやって目的のデータを数珠繋ぎにするのか。それが、このstruct listnodeと、その元祖であるstruct list_headの持つ、最大の特徴となる。
発想
　普通に連結リストを作ろうとしたなら、普通のプログラマーであれば前と次へのポインターの他に、実際のデータか、またはデータへのポインターを構造体の中に含めるだろう。
　こうして、この管理用の構造体の中に繋ぎたいデータを「含む」ことで、データは数珠繋ぎの連結リストとなる。
　しかしこのstruct listnodeと、その元祖であるstruct list_headは違う。
　簡単に説明すると、struct listnodeは、リストとして繋ぎたい要素を「含む」のではなく、リストとして繋ぎたい要素に「埋め込む」のである。
使い方
　以下は、struct list_headとの違いに触れながら、struct listnodeの使い方を説明する。
挿入
　繋ぎたい構造体の中に、struct listnodeを埋め込む。
struct data_struct {
   int id;
   char name[128];
   struct listnode node;
}
　通常の発想のものなら構造体の先頭ポインターで管理するところだが、struct listnodeの場合は、構造体の中のどこかにあればよい。どこでも良い。
　この場合、struct listnode nodeのアドレスがリストに追加されることになる。構造体の先頭アドレスではない。
先頭
　一つのリストごとに一つ、ソース中のどこかに、先頭に相当するstruct listnodeを定義する必要がある。以降、ここではこれを「先頭アイテム」と呼ぶことにする。
　複数の関数で使うことが多いため、一般にはグローバル変数として定義して用いる。
struct listnode data_list;
　先頭アイテムの初期化は次のようにする。
list_init(&data_list);
　ここで使われるlist_initは関数で、system/core/libcutils/list.cで、次のように定義される。
void list_init(struct listnode *node)
{
    node->next = node;
    node->prev = node;
}
　また、元祖list_headにあるLIST_HEAD()マクロに相当のマクロとして、list_declareもある。
list_declare(data_list);
　このマクロは、system/core/include/cutils/list.h で次のように定義されている。
#define list_declare(name) \
    struct listnode name = { \
        .next = &name, \
        .prev = &name, \
    }
　ただこのマクロは人気がないらしく、Androidでは使われている形跡がない。
　list_init()関数での初期化またはlist_declare()での定義時点で、prevとnextには与えられたstruct listnodeのポインターが代入されることが分かる。nextを見て、そのポインターが先頭に相当するstruct listnodeなら、それ以降はないものとして判断できる。
node_to_item
　構造体中のstruct list_headのアドレス(ノード)から、その構造体(アイテム)の先頭アドレスを得るためのマクロnode_to_itemが定義されている。従って、struct listnodeは構造体の中のどこにあってもよい。これは元祖list_headではlist_entryに対応する。
#define node_to_item(node, container, member) \
    (container *) (((char*) (node)) - offsetof(container, member))
　offsetofは stddef.h で定義される。AndroidのLinuxカーネルでは external/kernel-headers/original/linux/stddef.h に存在する。
#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif
　登録するリストがstruct listnode data_list;として定義されているとすると、次のように使う。
struct listnode *node;
struct data_struct *item;
for (node = data_list.next; node != &data_list; node = node->next) {
    item = node_to_item(node, struct data_struct, node);
    printf("%d\n", item->id);
}
list_for_each
　なお、無限ループしないように順番に見ていく場合は、次のマクロを使うのが便利である。
#define list_for_each(node, list) \
    for (node = (list)->next; node != (list); node = node->next)

#define list_for_each_reverse(node, list) \
    for (node = (list)->prev; node != (list); node = node->prev)
　実体はfor文だが、要素二つだけのマクロとなるため、読みやすくなる。こうなる。
struct listnode *node;
struct data_struct *item;
list_for_each(node, &data_list) {
    item = node_to_item(node, struct data_struct, node);
    printf("%d\n", item->id);
}
再検索