Linked Lists

The Pointer Example presented a C data structure and its associated XDR routines for an individual's gross assets and liabilities. The following code example 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;

Think of the head of the linked list 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 more data follows. 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. 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 preceding XDR description. Note how the primitive xdr_pointer() is used to implement the preceding XDR union.

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 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 growth is due to the recursion. The following example collapses the last 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 more data exists, so that this Boolean information can be serialized. Notice that this statement is unnecessary in the XDR_DECODE case, because 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 no more data exists, 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, because the pointer is already NULL in the XDR_ENCODE and XDR_FREE cases.

Next, if the direction is XDR_FREE, set the value of nextp to indicate the location of the next pointer in the list. You set this value now because you need to dereference gnp to find the location of the next item in the list. After the next statement, the storage pointed to by gnp is freed up and no longer valid. You cannot set this value for all directions, though, because in the XDR_DECODE direction the value of gnp is not set until the next statement.

Next, you use XDR on 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 more data exists. You use xdr_reference() 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 runs more efficiently because much of the procedure call overhead has been removed. Most lists are small, in the hundreds of items or less, and the recursive version should be sufficient for them.