[小ネタ]CでListとかデータ構造をどうにかして簡単に使いたい

Cの小ネタです。

##事の経緯
ピュアなCはC++みたいにSTLやらBOOSTとか便利なものはないですし、気の利いたデータ構造（俗に言うコレクション）を書こうにもわざわざ自分で書く必要があったり、やれswiftだーgoだーphpだーとか言ってるこのご時世に、データ構造を書く上での煩雑さというのが、時代というか古さを感じます。

諸事情によって、C++が使えないとかそういう人は自家製のライブラリとか使ってるのかなぁとか毎回思っております。

で、そういえばLinux Kernelは大体ピュアCで書かれておりまして(gcc拡張使いまくりだから邪道というのは置いておいて、、)、list.hとか汎用的にデータ構造を扱える仕組みがあったよなぁと思い出して、これが普通のユーザ空間で使えたら楽だし、誰か同じ事考えてないかなーと思って広いいんたーねっとを探索してみたら、やっぱり同じ事考えてる人居たという話でした。

・Linuxカーネルのlist, rbtree, sortを使ってみた！（pank7さん）
http://tech.voyagegroup.com/archives/6819729.html

仕組みはこの辺が詳しいですね
・linuxカーネルが提供するリストの使い方について（mmitouさん）
http://d.hatena.ne.jp/mmitou/20120626/1340731801

Linuxのリンクリストなんか知らんって人は若干不慣れな書き方をしますが、結構便利です。

内部はtypeof演算子が使われていて、使えないコンパイラもあるかもしれませんが、使えるようなら使っていきたいですね。

List自体の仕組みはなかなか凝っていて関心しきりです。
offsetofとかcontainer_ofの仕組みがキモで、なるほどなぁという感じです。

Linux Kernelでは要所要所でlist_headを使っているので、これに慣れておくとカーネルも読みやすくなります。

##使い方
使い方は紹介したページに大体書いてあるのですが、簡単に書いておきます。
肝心のヘッダ(list.h)は
https://github.com/pank7/pank7-lib
にあります。

###構造体の定義

typedef struct _tag_datas
{
	int num;
	char *name;
	list_head _list;
}type_line;

というように、リスト化したい構造体にlist_head _listを置きます。

###初期化
LIST_HEAD(リスト変数)で一切合切やってくれます。

LIST_HEAD(global_list);

void list_init()
{
	LIST_HEAD(local_list);
	...
}

###リストへ要素の追加
INIT_LIST_HEAD(要素のlist_head)で初期化しつつ、list_add(要素.リスト変数)かlist_add_tail(要素.リスト変数)で、リストの先頭か末尾に追加できます。

void add_init()
{
	type_line *data;
	data = (type_line *)malloc(sizeof(type_line));

	INIT_LIST_HEAD(&data->_list);
	data->num = 1;
	list_add(&data->_list, &global_list);
}

###リストへの順アクセス
リストを順番に辿っていくにはfor文を使うのではなく、list_for_each()が使用できます。
ただ、これはリストを辿るだけのもので、ここからlist_entry()で実体を取ってこないといけないので、
list_for_each_entry(要素.リスト変数,構造体のlist_headの変数名)
を使うのが楽です。

逆順に辿る場合は、list_for_each_entry_reverse()を使います。

void put_list()
{
	type_line *data;
	list_for_each_entry(data,&global_list,_list){
		printf("%d\n",data->num);
	}
}

cでfor_eachが使えるのはいいですね。

###リストの要素の削除
list_delで要素を削除します。mallocでもって自分でアロケーションした時は、delした後、要素自体をfreeで開放してください。

void remove_list()
{
	type_line *data;
	type_line *dend=NULL;

	list_for_each_entry_safe(data,dend,&global_list,_list){
		list_del(&data->_list);
		free((void *)data);
	}
}

リストの内容を全部削除する場合はこの例のようにfor_eachと組み合わせます。

##仕組み

簡単に図示するとこんな感じです。

(引用　http://www.kerneldesign.info/wiki/index.php?container_of()%2Flinux2.6 )

offset_ofで構造体先頭からlist_headを埋めておいた距離を求め、そこからcontainer_ofでptrからoffset_ofでの距離を引くことによって、構造体の頭のアドレスを逆算している…という話です。
(list_headは任意の箇所に埋まっている可能性があるので「逆算する」というニュアンスです)

これによって、構造体の頭やお尻に何があろうが関係なく構造体の頭のアドレスを計算でき、頭をピックアップできるので、任意の構造体に無理無く埋め込める…ということです。

##サンプルコードと実行例
サンプルは次のようになります。

list_demo.c

// list.h サンプル

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"

typedef struct _tag_datas
{
	int number;
	char name[64];
	list_head _list;
}type_line;

const char *ndata[]=
{
	"beagle",
	"cupcake",
	"donut",
	"eclair",
	"froyo",
	"gingerbread",
	"honeycomb",
	"icecleam",
	"jellybean",
	"kitkat",
	NULL,
};

// 渡されたリストのエントリが最後かどうか調べる
#define list_is_entry_last(pos, head, member) \
	&pos->member == (head)

int main(int argc,char *argv[])
{
	LIST_HEAD(mylist);
	int nums=1,i;
	type_line *data = NULL;
	type_line *dend = NULL;
	
	// Listへ要素の追加
	for(i=0;ndata[i] != NULL;i++){
		data = (type_line *)malloc(sizeof(type_line));

		INIT_LIST_HEAD(&data->_list);
		data->number = nums;
		strcpy(data->name,ndata[i]);
		nums++;
		list_add_tail(&data->_list, &mylist);
	}
	// Listを順にたぐる
	list_for_each_entry(data,&mylist,_list){
		printf("%d: %s\n",data->number,data->name);
	}
	
	// Listを順にたぐりつつ、探す
	list_for_each_entry(data,&mylist,_list){
		if(strcmp(data->name,ndata[4]) == 0){
			printf("found ! %d: %s\n",data->number,data->name);
			break;
		}
	}
	// Listが最後まで来たかどうか
	if(list_is_entry_last(data,&mylist,_list)){
		printf("not found\n");
	}else{
		printf("continue print\n");
		// 探せたらそこから順にたどる
		// list_for_each_entry_continue だと今dataが示しているところの次から
		// list_for_each_entry_from だと今dataが示しているところになります
		list_for_each_entry_continue(data,&mylist,_list){
			printf("%d: %s\n",data->number,data->name);
		}
	}
	
	// 後始末
	list_for_each_entry_safe(data,dend,&mylist,_list){
		list_del(&data->_list);
		free((void *)data);
	}
	
	return 0;
}

実行結果はこんな感じです。

result

$ ./list_demo 
1: beagle
2: cupcake
3: donut
4: eclair
5: froyo
6: gingerbread
7: honeycomb
8: icecleam
9: jellybean
10: kitkat
found ! 5: froyo
continue print
6: gingerbread
7: honeycomb
8: icecleam
9: jellybean
10: kitkat