XMLはNETWORKの基盤技術のため現代プログラマにとっては必須の技術です。XMLの作成やパースという作業を一度は経験しているのではないでしょうか？ただし、多くの場合フレームワークがXMLオブジェクトを作るためのインターフェースを準備してくれているので一からXMLの作成アルゴリズムやパーサーを作ることはないかと思います。
XMLというのは多分木構造をしており線形リストを使っての探索アルゴリズムを練習するのに非常に有用な教材です。ここではXML作成プログラムを見てみようと思います。まずはC言語で動的確保を行うアルゴリズムを見てみたいと思います。簡単なためAttributeの要素は割愛します。
次のXMLを作成してみましょう。
<root>
<tag1>
<tag2>element_start</tag2>
<tag2>element_middle</tag2>
</tag1>
<tag1>
<tag3>element_last</tag3>
</tag1>
</root>
まずは大まかな流れを考えてみます。
①データ構造を決める。
②データ送出時のプログラムを考える。
③データ構造を作成するためのインターフェースを決める。
①データ構造を決める。
root
┣ tag1
┃ ┣ tag2
┃ ┗ tag2
┗ tag1
┗ tag3
という構造ですから、rootはtag1, tag2 を指すポインタを、tag1はtag2, を２つ もしくはtag3を指すポインタを保持するようなデータ構造を考えます。そして最後のtag2とtag3は element(要素の文言)を持ちます。
構造体にするとこんな感じになるかと思います。
struct StNode{
char *element;
ｃonst char * tag;
struct StNode * next;
}
ただしこれだとnextを一つしか持てませんし最終ノードだけが持っていればいいelementを持て余す事になります。動的に子ノードを複数持つ事が出来、かつ異なる型を保持できるような構造体を考えてみましょう。
/*通常ノード*/
sturct StNode{
unsighned char enIdent;
ｃonst char * tag;
void ** next;
}
/*最終ノード*/
struct StElem{
unsighned char enIdent;
ｃonst char * tag;
char * element;
}
nextポインタをダブルポインタにします。ダブルポインタにすることでreallocでアドレス領域を拡張できるようにします。またvoid型にしておくことでデータ型を指定出来るようにしておきます。なおデータ処理するオブジェクトはnextの本当の型を知るすべがない為、識別用のメンバenIdentを追加してあります。注意しなければいけないのはこの識別子は必ず一番上で宣言する必要があることです。(正直構造体を二つに分けるのは可読性をひどく悪くさせるのであまりお勧めしないのですが、我慢してこの構造体で出来るようにします。)
②データ送出時のプログラムを考える。
データ構造が出来たとします。XMLの多分木は深さ優先探索で行きがけ順と帰りがけ順でデータを取り出す事になります。(このあたりはあまり深追いしません）深さ優先探索は再起呼び出しを使って実現します。再起呼び出しはSTACKと同じ動作になりますので、STACK構造のコードを書くことでも実現できます。
③データ構造を作成するためのインターフェースを決める。
XMLの構造が決まっている場合それを作成するのはクライアントの役割です。いかに簡単にデータ構造を作成できるインターフェースを提供できるか？プログラマの腕の見せ所かと思います。今回は、以下のようなインターフェースを考えてみました。
void make_root_node(struct StNode** node, ｃonst char *tag); void make_next_node(struct StNode** node, struct StNode** next, ｃonst char *tag);
まずルートノードを作成する関数です。ノードをダブルポインタで関数に渡していますが先ほどのポインタ配列としての使い方ではなく、渡したオブジェクトの中身を変更してもらうためにダブルポインタにしています。戻り値を代入するようにしてもよいのですがダブルポインタとして引数に渡す形の方がデータ構造を作成する場合の見通しが良いと判断しました(このあたりの設計ポリシーは現場毎に違うのかなと思います)。次に親ノードに子ノードと子ノードのタグを引っ付ける関数です。引数として並べて記載することで、どの親ノードに子ノードが引っ付くかわかりやすいかと思います。最終ノード(Element持ちのノード)を作成する関数は別に用意しますが同様のインターフェースですので割愛します。
これらを実現するソースは以下となります。
#include <stdio.h>
#include <stdlib.h>
#define EnNode 0
#define EnElem 1
struct StNode{
unsigned char enIdent;
ｃonst char * tag;
void **next;
};
struct StElem{
unsigned char enIdent;
ｃonst char * tag;
char * element;
};
void make_root_node(struct StNode** node, ｃonst char *tag);
void make_next_node(struct StNode** node, struct StNode** next, ｃonst char *tag);
void make_next_element(struct StNode** node, struct StElem** next, ｃonst char *tag );
void make_element(struct StElem** next, char *element);
void pre_order( void* node );
int _tmain(int argc, _TCHAR* argv[])
{
ｃonst char *s_root = "root";
ｃonst char *s_tag1 = "tag1";
ｃonst char *s_tag2 = "tag2";
ｃonst char *s_tag3 = "tag3";
struct StNode *stRoot = NULL, *stNode1 = NULL, *stNode2 = NULL;
struct StElem *stElem1 = NULL, *stElem2 = NULL, *stElem3 = NULL;
make_root_node(&stRoot, s_root);
make_next_node(&stRoot, &stNode1, s_tag1);
make_next_element(&stNode1, &stElem1, s_tag2);
make_element(&stElem1, "element_start");
make_next_element(&stNode1, &stElem2, s_tag2);
make_element(&stElem2, "element_middle");
make_next_node(&stRoot, &stNode2, s_tag1);
make_next_element(&stNode2, &stElem3, s_tag3);
make_element(&stElem3, "element_last");
pre_order( (void*) stRoot );
return 0;
}
void make_root_node(struct StNode** root, ｃonst char *tag ){
*root = (struct StNode *)calloc( sizeof(struct StNode));
(*root)->enIdent = EnNode;
(*root)->tag = tag;
(*root)->next = NULL;
}
void make_next_node(struct StNode** node, struct StNode** next, ｃonst char *tag){
int cnt;
if( (*node)->next == NULL ){
(*node)->next = (void **) calloc( (sizeof(void *) * 2) );
(*node)->next[1] = NULL;
(*node)->next[0] = (void *)calloc( sizeof(struct StNode));
(*next) = (struct StNode *)( (*node)->next[0]);
(*next)->enIdent = EnNode;
(*next)->tag = tag;
(*next)->next = NULL;
}else{
for( cnt=0 ; (*node)->next[cnt] != NULL; cnt++){}
(*node)->next = (void **) realloc( (*node)->next, (sizeof(void *) * (cnt+2) ) );
(*node)->next[cnt+1] = NULL;
(*node)->next[cnt] = (void *)calloc( sizeof(struct StNode));
(*next) = (struct StNode *)( (*node)->next[cnt]);
(*next)->enIdent = EnNode;
(*next)->tag = tag;
(*next)->next = NULL;
}
}
void make_next_element(struct StNode** node, struct StElem** next, ｃonst char *tag){
int cnt;
if( (*node)->next == NULL ){
(*node)->next = (void **) calloc( (sizeof(void *) * 2) );
(*node)->next[1] = NULL;
(*node)->next[0] = (void *)calloc( sizeof(struct StElem));
(*next) = (struct StElem *)( (*node)->next[0]);
(*next)->enIdent = EnElem;
(*next)->tag = tag;
(*next)->element = NULL;
}else{
for( cnt=0 ; (*node)->next[cnt] != NULL; cnt++){}
(*node)->next = (void **) realloc( (*node)->next, (sizeof(void *) * (cnt+2)) );
(*node)->next[cnt+1] = NULL;
(*node)->next[cnt] = (void *)calloc( sizeof(struct StElem));
(*next) = (struct StElem *)( (*node)->next[cnt]);
(*next)->enIdent = EnElem;
(*next)->tag = tag;
(*next)->element = NULL;
}
}
void make_element(struct StElem** node, char *element ){
(*node)->element = element;
}
void pre_order(void* node){
int cnt;
if( node == NULL ){
return ;
}
if(((struct StNode*)node)->enIdent== EnNode ){
printf("<%s>", ((struct StNode*)node)->tag );
if( ((struct StNode*)node)->next != NULL ){
printf("\n");
for( cnt=0; ((struct StNode*)node)->next[cnt]; cnt++ ){
pre_order(((struct StNode*)node)->next[cnt]);
}
printf("\n", ((struct StNode*)node)->tag);
}
}
if(((struct StElem*)node)->enIdent== EnElem ){
printf("<%s>", ((struct StElem*)node)->tag );
if( ((struct StElem*)node)->element ){
printf("%s", ((struct StElem*)node)->element);
}
printf("\n", ((struct StElem*)node)->tag);
}
}
mallocを使いながらfreeもしていないし、error処理もしていないのであまりよろしくありませんが、いくつか有用な方法論があるかと思います。子ノードの数を動的に割り当てる必要があった為、子ノードの追加が発生した段階でreallocで領域の見直しをします。またnextのアドレスをmalloc(realloc)する際一つ分のアドレスを余分にallocateしています。そのスペースにNULLポインタを割り当て文字列と同様配列の終端を知らせるようにしました。残念なのはnextを*voidで受けるためキャストだらけになってしまいました。またその為(型が不明な為に)に最後の再起呼び出しの時に条件分岐が必要になっています。
なんだか少し難しいプログラムが出来上がってしまいました。正直、静的にXMLを実現するのであればprintf文ベタ書きもありです。そこがプログラムの恐ろしいところです。どんなに熟練したプログラマが書いたコードでも、初心者プログラマと同じ出力が出てしまいユーザからは違いが判らなかったりします。しかしプロのプログラマは他の開発者が簡単に変更が出来るようにするにはどうすればいいかという視点で考えます。今回の場合はデータ構造の作成をいかに簡単にするかという事を念頭におきました。プログラムは難しいかもしれませんがXMLの構造を変更するのは簡単に出来るかと思います。また今回はC言語で記述しました。一般にC++の方が難しい言語と思われるかもしれませんが、今回のように*voidを使った多相的なプログラムはC++で書いた方がすっきりします。次回はC++で同じことをするとどうなるか見ていきましょう。
