ONC+ 開発ガイド

リンクリスト

ポインタのサンプルプログラムの節では、各個人の総資産と負債に関する C のデータ構造体とそれに対する XDR ルーチンのサンプルプログラムを示しました。次のサンプルプログラムでは、リンクリストを使用して、ポインタのサンプルプログラムと同じものを作成します。

例 A–14 リンクリスト

struct gnumbers {
 	int g_assets;
 	int g_liabilities;
 };
 
bool_t
xdr_gnumbers(xdrs, gp)
 	XDR *xdrs;
 	struct gnumbers *gp;
{
 	return(xdr_int(xdrs, &(gp->g_assets) &&
 		     xdr_int(xdrs, &(gp->g_liabilities)));
}

同じ情報を持つリンクリストを作成します。構造体は次のようになります。

struct gnumbers_node {
   struct gnumbers gn_numbers;
  	struct gnumbers_node *gn_next;
};
typedef struct gnumbers_node *gnumbers_list;

リンクリストのヘッダーはデータオブジェクトと考えてください。便宜のため付けられた構造体の単なる短縮形ではありません。同様に、gn_next フィールドも、オブジェクトの終わりかどうかを示すのに使用されます。残念ながら、オブジェクトが次につながる場合も、gn_next フィールドに続きのアドレスが入ります。オブジェクトをシリアライズするときは、リンクアドレスの情報は役に立ちません。

このリンクリストを XDR データ記述言語で示すと、gnumbers_list の再帰宣言となります。

struct gnumbers {
  	int g_assets;
  	int g_liabilities;
};
struct gnumbers_node {
  	gnumbers gn_numbers;
  	gnumbers_node *gn_next;
};

この記述では、ブール値は次のデータがあるかどうかを示します。ブール値が FALSE の場合は、それが構造体の最終データフィールドとなります。ブール値が TRUE の場合は、その後に gnumbers 構造体と gnumbers_list とが再帰的に続きます。C 宣言内には明示的にブール値が宣言されていませんが、gn_next フィールドは黙示的に情報を示している点に注意してください、XDR データ記述では明示的にポインタが宣言されません。

gnumbers_list に対する XDR ルーチンを作成するためのヒントは、上の XDR についての記述から得られます。上の XDR 共用体を実現するためのプリミティブ xdr_pointer()の使用方法を参照してください。

例 A–15 `xdr_pointer`

bool_t
xdr_gnumbers_node(xdrs, gn)
 	XDR *xdrs;
 	gnumbers_node *gn;
{
	return(xdr_gnumbers(xdrs, &gn->gn_numbers) &&
	        xdr_gnumbers_list(xdrs, &gn->gn_next));
}

bool_t
xdr_gnumbers_list(xdrs, gnp)
 	XDR *xdrs;
 	gnumbers_list *gnp;
{
	return(xdr_pointer(xdrs, gnp, sizeof(struct gnumbers_node),
	                     xdr_gnumbers_node));
 xdr_pointer}

これらのルーチンを持つリスト上で XDR を使用すると、リスト内のノード数に比例して C スタックが大きくなります。これは再帰呼び出しが原因です。次の例では、互いに再帰呼び出しを行う 2 つのルーチンを 1 つにまとめて、再帰呼び出しが起こらないようにしています。

例 A–16 再帰呼び出しを行わない XDR 変換

bool_t
xdr_gnumbers_list(xdrs, gnp)
 	XDR *xdrs;
 	gnumbers_list *gnp;
{
 	bool_t more_data;
 	gnumbers_list *nextp;
 
	for(;;) {
 		more_data = (*gnp != NULL);
 		if (!xdr_bool(xdrs, &more_data))
 			return(FALSE);
 		if (! more_data)
 			break;
 		if (xdrs->x_op == XDR_FREE)
 			nextp = &(*gnp)->gn_next;
 		if (!xdr_reference(xdrs, gnp,
			sizeof(struct gnumbers_node), xdr_gnumbers))
 		return(FALSE);
 		gnp = (xdrs->x_op == XDR_FREE) ? nextp : &(*gnp)->gn_next;
 	}
 	*gnp = NULL;
 	return(TRUE);
}

最初に行うのは、次に続くデータがあるかどうかを調べ、このブール値をシリアライズできるようにします。XDR_DECODE の場合はこの文は不要なことに注意してください。なぜなら、次の文で more_data をデシリアライズするまでブール値はわからないからです。

次の文で XDR 共用体の more_data フィールドに XDR を作成します。次のデータがないことがわかれば、最終ポインタを NULL に設定してリストの終了を示し、処理は終了したので TRUE を返します。XDR_DECODE の場合だけ、ポインタを NULL に設定する意味があることに注意してください。XDR_ENCODE と XDR_FREE の場合は既に NULL になっているからです。

処理内容が XDR_FREE の場合は次に、リスト中の次のポインタアドレスを nextp の値として設定します。この値を設定するのは、リスト内の次の項目のアドレスを検出するために、 gnp を間接参照する必要があるためです。次の文以降では、gnp がポイントする記憶領域は解放され無効となります。しかし、次の文までは、XDR_DECODE 処理内容内に gnp の値が設定されていないため、すべての処理内容にはこの値を設定することはできません。

次にプリミティブ xdr_reference() を使用して、このノードのデータ上で XDR を使用します。xdr_reference() はこれまでに使用した xdr_pointer() に似ていますが、次のデータがあるかどうかを示すブール値を送信しない点が異なります。この情報に対しすでに XDR を使用しているため、xdr_pointer() の代わりに xdr_reference () を使用することができます。

ここで、リストの要素と異なる型の XDR ルーチンを渡していることに注意してください。ルーチン xdr_gnumbers() が渡されますが、実際にリストに入っている各要素の型は gnumbers_node です。xdr_gnumbers_node() を渡さないのは、このルーチンが再帰呼び出しを行うからです。代わりに渡された xdr_gnumbers() は、非再帰部分をすべて XDR 変換します。このような方法がうまくいくのは、各要素の最初の項目が gn_numbers()フィールドの場合だけです。最初のフィールドなので xdr_reference() に渡される両者のアドレスが同じだからです。

最後に gnp の値を更新して、リスト内の次の項目を指すようにします。処理内容が XDR_FREE の場合は保存しておいた値を設定し、それ以外の場合は gnp を間接参照して正しい値を取り出します。再帰呼び出しを使用する方法よりむずかしくなりますが、この方が数多くの手続き呼び出しを使用する場合のオーバヘッドがなくなってパフォーマンスも向上します。もっとも、ほとんどのリストはそれほど大きくはなく、項目数がせいぜい 100 以下のため、その場合は再帰呼び出しを行なっても問題ありません。

リンクリスト

例 A–14 リンクリスト

例 A–15 xdr_pointer

例 A–16 再帰呼び出しを行わない XDR 変換

例 A–15 `xdr_pointer`