Passing Linked Lists Using XDR Example

Linked lists of arbitrary length can be passed using eXternal Data Representation (XDR). To help illustrate the functions of the XDR routine for encoding, decoding, or freeing linked lists, this example creates a data structure and defines its associated XDR routine.

The "Using XDR Example" presents a C data structure and its associated XDR routines for an individual's gross assets and liabilities. The example is duplicated below:

struct gnumbers {
       long g_assets;
       long g_liabilities;
};
bool_t
xdr_gnumbers (xdrs, gp)
       XDR *xdrs;
       struct gnumbers *gp;
{
       if (xdr_long (xdrs, &(gp->g_assets)))
           return (xdr_long (xdrs, &( gp->g_liabilities)));
       return(FALSE);
}

For implementing a linked list of such information, a data structure could be constructed as follows:

struct gnumbers_node {
       struct gnumbers gn_numbers;
       struct gnnumbers_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 indicates whether or not the object has terminated. However, if the object continues, the gn_next field also specifies the address where it continues. The link addresses carry no useful information when the object is serialized.

The XDR data description of this linked list can be described by the recursive declaration of the gnumbers_list field, as follows:

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

In the following description, the Boolean indicates if more data follows it. If the Boolean is a False value, it is the last data field of the structure. If it is a True value, it is followed by a gnumbers structure and, recursively, by a gnumbers_list. 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 structure follow easily from the previous XDR description. The following primitive, xdr_pointer, implements the previous XDR union:

bool_t
xdr_gnumbers_node (xdrs, gn)
       XDR *xdrs;
       gnumbers_node *gn;
{
       return (xdr_gnumbers (xdrs, &gn->gn_numbers)  &&
           xdr_gnumbers_list (xdrs, &gp->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));

As a result of using XDR on a list with these subroutines, the C stack grows linearly with respect to the number of nodes in the list. This is due to the recursion. The following subroutine collapses the previous two recursive programs into a single, nonrecursive one:

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 statement determines whether more data exists, so that this Boolean information can be serialized. This statement is unnecessary in the XDR_DECODE case, since the value of the more_data field is not known until the next statement deserializes it.

The next statement translates the more_data field of the XDR union. If no more data exists, set this last pointer to Null to indicate the end of the list and return True because the operation is done.

Note: Setting the pointer to Null is important only in the XDR_ENCODE case because the pointer is already null in the XDR_ENCODE and XDR_FREE cases.

Next, if the direction is XDR_FREE, the value of the nextp field is set to indicate the location of the next pointer in the list. This step dereferences the gnp field to find the location of the next item in the list. After the next statement, the storage pointed to by gnp is freed and no longer valid. This step is not taken for all directions because, in the XDR_DECODE direction, the value of the gnp field will not be set until the next statement.

The next statement translates the data in the node using the xdr_reference primitive. The xdr_reference subroutine is similar to the xdr_pointer subroutine, used previously, but it does not send over the Boolean indicating whether there is more data. The program uses the xdr_reference subroutine instead of the xdr_pointer subroutine because the information is already translated by XDR. Notice that the XDR subroutine passed is not the same type as an element in the list. The subroutine passed is xdr_gnumbers, for translating gnumbers, but each element in the list is actually of the gnumbers_node type. The xdr_gnumbers_gnode subroutine is not passed because it is recursive. The program instead uses xdr_gnumbers, which translates all nonrecursive portions.

Note: This method works only if the gn_numbers field is the first item in each element, so that their addresses are identical when passed to the xdr_reference primitive.

Finally, the program updates the gnp field to point to the next item in the list. If the direction is XDR_FREE, it is set to the previously saved value. Otherwise, the program dereferences the gnp field to get the proper value. Though harder to understand than the recursive version, this nonrecursive subroutine is far less likely to cause errors in the C stack. The nonrecursive subroutine also runs more efficiently because much procedure call overhead has been removed. For small lists, containing hundreds of items or less, the recursive version of the subroutine should be sufficient.