mmap() の使いかた その３。

最短路に用いる forward-star を構成したグラフのメモリデータ を書き出し、再利用するということを行っている。

以下のような配列の先頭のアドレスを格納したポインタを含む構造体でグラフデータを格納している。それらのポインタには動的に確保した領域の先頭のアドレスを格納することになるため、それぞれのデータは連続にならないため、そのまま mmap() したファイルへコピーはしにくい。


typedef struct {
　unsigned int head;
　unsigned int length;
} arc_t;

typedef struct {
　int x;
　int y;
} coord_t;

typedef struct {
　unsigned int node_num;
　unsigned int arc_num;
　unsigned int max_length;
　unsigned int min_length;
　coord_t before_min; // min coordinate before normalization
　coord_t after_max; // max coordinate after normalization
　
　unsigned int *point;
　arc_t *arc;
　coord_t *coord;
} graph_t;



簡単に考えられる打開策としては、それぞれ大きな固定長の配列にするというものがある。
つまり

　unsigned int *point;
　arc_t *arc;
　coord_t *coord;

を

　unsigned int point[large_node_num];
　arc_t arc[large_arc_num];
　coord_t coord[large_node_num];

と、してしまうことである。


しかしこれでは、小さなグラフでも同じだけの容量を食ってしまい、無駄が多くなる。また、large_node_num、large_arc_num をグラフのたびに変えてもいいのだが、グラフの数だけ実行バイナリを持たなくてはならなくなってしまい管理が面倒である。書き込みも読み取りも同じ形式で読まなければ、バスエラーとなってしまうからである。


しかしながら、今回のケースではすべて int としても良いので、大きな int 型の配列ですべて済ませてしまうことも可能である。

しかしながら書き込みは良いとしても、読み込みの際に mmap() にそのマッピングするサイズを指定しなくてはならないという新たな問題が出てくる。わざわざ実行する際に引数などを受け取るのもあまりよろしくないし、そもそも中身が分からない状態でそのグラフの点数、枝数を指定するというのはいかがなものかと。


よくよく考えてみるとそのサイズは、書き出したファイルのサイズに等しいので、stat 系の関数 fstat() を用いてサイズを取得することにした。

struct stat sb;

// fd : 書き出したファイルの fd
fstat(fd, &sb);
size = sb.st_size;


このようにすれば、どのようなグラフを持ってきても関数側で処理することができ、問題もなく快適である。

現在の shortest path online solver で、全米データ(USA) を選択すると１分ほどかかってしまうので、これを用いたいと思う。待ち時間は数秒になるだろう。