Developing distributed applications using ONC RPC and XDR

Advanced topics -- linked lists

This section describes how to pass data structures by using linked lists of arbitrary lengths. Unlike the simpler examples covered in the earlier sections, the following examples are written using both the XDR C library routines and the XDR data description language. The section ``XDR standard'' describes the XDR data definition language used below.

The last version of xdr_gnumbers in the section ``Creating portable data with XDR'' presented a C data structure and its associated XDR routines for a person'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);
   }

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

   typedef struct gnnode {
           struct gnumbers gn_numbers;
           struct gnnode nxt;
   };
   
   typedef struct gnnode 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 nxt field is used to indicate whether or not the object has terminated. Unfortunately, if the object continues, the nxt field is also 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 is described by the recursive type declaration of gnumbers_list:

   struct gnumbers {
           unsigned g_assets;
           unsigned g_liabilities;
   };
   
   typedef union switch (boolean) {
           case TRUE: struct {
                   struct gnumbers current_element;
                   gnumbers_list rest_of_list;
           };
           case FALSE: struct {};
   } gnumbers_list;

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

Hints for writing a set of XDR routines to successfully (de)serialize a linked list of entries can be found in the XDR description of the pointer-less data. The set consists of the mutually recursive routines xdr_gnumbers_list, xdr_wrap_list, and xdr_gnnode.

   bool_t
   xdr_gnnode(xdrs, gp)
           XDR xdrs;
           struct gnnode gp;
   {
           return (xdr_gnumbers(xdrs, &(gp->gn_numbers)) &&
                   xdr_gnumbers_list(xdrs, &(gp->nxt)) );
   }
   
   bool_t
   xdr_wrap_list(xdrs, glp)
           XDR xdrs;
           gnumbers_list glp;
   {
           return (xdr_reference(xdrs, glp, sizeof(struct gnnode),
               xdr_gnnode));
   }
   

   struct xdr_discrim choices[2] = {
           / called if another node needs (de)serializing /
           { TRUE, xdr_wrap_list },
            / called when there are no more nodes to be (de)serialized /
           { FALSE, xdr_void }
   }
   

   bool_t
   xdr_gnumbers_list(xdrs, glp)
           XDR xdrs;
           gnumbers_list glp;
   {
           bool_t more_data;
   

           more_data = (glp != (gnumbers_list)NULL);
           return (xdr_union(xdrs, &more_data, glp, choices, NULL));
   }

The entry routine is xdr_gnumbers_list(); its job is to translate between the boolean value more_data and the list pointer values. If there is no more data, the xdr_union() primitive calls xdr_void() and the recursion is terminated. Otherwise, xdr_union() calls xdr_wrap_list(), whose job is to dereference the list pointers. The xdr_gnnode() routine actually (de)serializes data of the current node of the linked list, and recursively calls xdr_gnumbers_list() to handle the remainder of the list. Readers should convince themselves that these routines function correctly in all three directions (XDR_ENCODE, XDR_DECODE and XDR_FREE) for linked lists of any length (including zero). Note that the boolean more_data is always initialized, but in the XDR_DECODE case it is overwritten by an externally generated value. Also note that the value of the bool_t is lost in the stack. The essence of the value is reflected in the list's pointers.

The unfortunate side effect of (de)serializing 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. The routines are also hard to code (and understand) due to the number and nature of primitives involved (such as xdr_reference, xdr_union, and xdr_void).

The following routine collapses the recursive routines. It also has other optimizations that are discussed below.

   bool_t
   xdr_gnumbers_list(xdrs, glp)
           XDR xdrs;
           gnumbers_list glp;
   {
           bool_t more_data;
   
           while (TRUE) {
              more_data = (glp != (gnumbers_list)NULL);
              if (! xdr_bool(xdrs, &more_data))
                           return (FALSE);
              if (! more_data)
                           return (TRUE);  / we are done /
              if (! xdr_reference(xdrs, glp, sizeof(struct gnnode),
                       xdr_gnumbers))
                           return (FALSE);
              glp = &((glp)->nxt);
           }
   }

The claim is that this one routine is easier to code and understand than the three recursive routines above. The parameter glp is treated as the address of the pointer to the head of the remainder of the list to be (de)serialized. Thus, glp is set to the address of the current node's nxt field at the end of the while loop. The discriminated union is implemented in line; the variable more_data has the same use in this routine as in the routines above. Its value is recomputed and again (de)serialized in each iteration of the loop. Since glp is a pointer to a node, the pointer is dereferenced using xdr_reference(). Note that the third parameter is truly the size of a node (data values plus nxt pointer), while xdr_gnumbers() only (de)serializes the data values. This optimization works only because the nxt data comes after all legitimate external data. There is a bug in this routine in the XDR_FREE case, in that xdr_reference() will free the node glp. Upon return, the assignment glp = &((glp)->nxt) cannot be guaranteed to work, since glp is no longer a legitimate node. The following code works in all cases. The hard part is to avoid dereferencing a pointer that has not been initialized or that has been freed.

   bool_t
   xdr_gnumbers_list(xdrs, glp)
           XDR xdrs;
           gnumbers_list glp;
   {
           bool_t more_data;
           bool_t freeing;
           gnumbers_list next;  / the next value of glp /
   
           freeing = (xdrs->x_op == XDR_FREE);
           while (TRUE) {
               more_data = (glp != (gnumbers_list)NULL);
               if (! xdr_bool(xdrs, &more_data))
                           return (FALSE);
               if (! more_data)
                           return (TRUE);  / we are done /
               if (freeing)
                           next = &((glp)->nxt);
               if (! xdr_reference(xdrs, glp, sizeof(struct gnnode),
                       xdr_gnumbers))
                           return (FALSE);
                   glp = (freeing) ? next : &((glp)->nxt);
           }
   }

This is the first example in this document that actually inspects the direction of the operation (xdrs->x_op). The claim is that the correct iterative implementation is still easier to understand or code than the recursive implementation. It is certainly more efficient with respect to C stack requirements.