Linked Lists

The "Pointer Example" presented a C data structure and its associated XDR routines for an individual's gross assets and liabilities. Example A-14 uses a linked list to duplicate the pointer example.

Example A-14 Linked List

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

Now assume that you want to implement a linked list of such information. A data structure could be constructed as follows:

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

The head of the linked list can be thought of as the data object; that is, the head is not merely a convenient shorthand for a structure. Similarly the gn_next field is used to indicate whether the object has terminated. Unfortunately, if the object continues, the gn_next field is also the address of where it continues. The link addresses carry no useful information when the object is serialized.

The XDR data description of this linked list is described by the recursive declaration of gnumbers_list:

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

In this description, the Boolean indicates whether there is more data following it. If the Boolean is FALSE, it is the last data field of the structure. If it is TRUE, it is followed by a gnumbers structure and (recursively) by a gnumbers_list. Note that the C declaration has no Boolean explicitly declared in it (though the gn_next field implicitly carries the information), while the XDR data description has no pointer explicitly declared in it.

Hints for writing the XDR routines for a gnumbers_list follow easily from the XDR description above. Note how the primitive xdr_pointer() is used to implement the XDR union above.

Example 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}

The unfortunate side effect of using XDR on a list with these routines is that the C stack grows linearly with respect to the number of nodes in the list. This is due to the recursion. Example A-16 collapses the above two mutually recursive routines into a single, nonrecursive one.

Example A-16 Nonrecursive Stack in 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);
}

The first task is to find out whether there is more data, so that this Boolean information can be serialized. Notice that this statement is unnecessary in the XDR_DECODE case, since the value of more_data is not known until you deserialize it in the next statement.

The next statement implements XDR on the more_data field of the XDR union. Then if there is truly no more data, you set this last pointer to NULL to indicate the end of the list, and return TRUE because you are done. Note that setting the pointer to NULL is only important in the XDR_DECODE case, since it is already NULL in the XDR_ENCODE and XDR_FREE cases.

Next, if the direction is XDR_FREE, the value of nextp is set to indicate the location of the next pointer in the list. We do this now because you need to dereference gnp to find the location of the next item in the list, and after the next statement, the storage pointed to by gnp will be freed up and no be longer valid. We can't do this for all directions though, because in the XDR_DECODE direction the value of gnp won't be set until the next statement.

Next, you XDR the data in the node using the primitive xdr_reference(). xdr_reference() is like xdr_pointer() which you used before, but it does not send over the Boolean indicating whether there is more data. We use it instead of xdr_pointer() because you have already used XDR on this information yourself. Notice that the XDR routine passed is not the same type as an element in the list. The routine passed is xdr_gnumbers(), but each element in the list is actually of type gnumbers_node. You don't pass xdr_gnumbers_node() because it is recursive. Instead use xdr_gnumbers() which uses XDR on all of the nonrecursive part. Note that this trick works only if the gn_numbers field is the first item in each element, so that their addresses are identical when passed to xdr_reference().

Finally, you update gnp to point to the next item in the list. If the direction is XDR_FREE, you set it to the previously saved value; otherwise you can dereference gnp to get the proper value. Though harder to understand than the recursive version, this nonrecursive routine will run more efficiently since much of the procedure call overhead has been removed. Most lists are small though (in the hundreds of items or less) and the recursive version should be sufficient for them.