listnode

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 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なら、それ以降はないものとして判断できる。

構造体中の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);
}

なお、無限ループしないように順番に見ていく場合は、次のマクロを使うのが便利である。

#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);
}