From: mjd@saul.cis.upenn.edu (Not Kathryn Hess' Little Brother in disguise)
Newsgroups: comp.programming
Subject: Recursive structure copying
Date: 16 Apr 92 06:55:59 GMT
Distribution: comp
Organization: Eaters of Wisdom


I have a program which has a number of different kinds of structures;
each kind contains members which are pointers to some of the other
kinds.  For example:

	struct person {
		struct person_list *friends;
		struct person *best_friend;
	};

	struct person_list {
		struct person *who;
		struct person_list *next;
	};


    (The actual situation was rather more complicated; the structures
represented components in an internal description of a dataflow
computer.  I wanted to copy because I had biult up an internal
representation of a sub-machine `class', such as a machine that adds.  I
wanted to be able to create several different instantiations of the
class to install in a supermachine, since a large machine might contain
several separate adders.)

    Now imagine I have a pointer to a struct person, which includes
information about that person's friends, which structs include
information about the friends' friends, and soforth.  Suppose I want to
copy the entire graph of structures.  What is a good way to do this?

    The first cut is to write a pair of functions:


	/*
	 * No good --- stack overflows 
	 */

	struct person *
	copy_person (struct person *s) 
	{
	  struct person *d = (struct person *) malloc(sizeof(struct person));

	  d->best_friend = copy_person(s->best_friend);
	  d->friends = copy_person_list(s->friends);

	  return d;
	}

	struct person_list *
	copy_person_list (struct person_list *s)
	{
	   /* etc. */
	}

but of course this doesn't work at all: It fails when, for example, we
try to copy Christopher Robin, when Pooh is on Christopher Robin's
friend list and vice versa.

    It's not enough just to copy pointer values from the old struct to
the new struct:

	/*
	 * No good --- is not a complete copy function 
	 */

	struct person *
	copy_person ( struct person *s)
	{
	  struct person *d = (struct person *) malloc(sizeof(struct person));

	  d->best_friend = s->best_friend; /* Wrongo */
	  [...]
	}

because then the copy has pointers into parts of the old struct, and we
want it to be a completely separate object.  The goal here is that
modifying the original struct should not affect the new copy, and vice
versa.  
	  
    I considered using two different internal representations of a
`person': one would be the one I described above, which is easy to use
because the information is arranged logically.  The other would be a
representation which is easy to copy and easy to translate into the
first representation, but not so good for finding what you want.  User
input would be translated into the easy-to-copy representation and
instantiated in the easy-to-use form as necessary.  I decided that this
would be Too Much Work.

    The solution I eventually adopted was to write the copy functions as
above, but to include an extra parameter in each.  The extra parameter
was for passing a 2xn table of pointers.  Each time any copy function
was given a pointer P to an object to copy, it would look in the table
to see if there was an entry of the form (P, Q). 

    If not, it would do the recursive copy as described above.  The
first thing to do would be to create a structure NEW that was a copy of
*P.  It would install the pair (P, &NEW) into the table and then call
other copy routines to make copies of the things pointed to by *P's
members.  

    If (P, Q) is already in the table for some Q, it means we've copied
the struct at P already, and the copy is at Q, so we don't need to do
any more work; just return Q right away.

	/* 
	 * This works
	 */
	struct person *
	copy_person(struct person *s, (struct {void *old, *new} pmap[])
	{
           struct person *rv;

	    if ((rv = lookup_in_pmap((void *) s, pmap)) == NULL) {
	      struct person *d = 
		(struct person *) malloc(sizeof(struct person));
	      install_in_pmap((void *) s, (void *) d);
	      /* It wasn't there, so we didn't copy this struct
	       * yet.  Do the recursive copy thing */
	      [...]
              return d;
	    } else {
	      /* We already copied this. */
	      return rv;
	    }
	}

    This method worked pretty well and wasn't too hard to code.  It
bothered me a little: it depends very strongly on having a generic
pointer type.  If I'd been writing in pascal I suppose I would have been
out of luck.  I feel like I'm playing fast and loose with pointer values
and handling them in an inappropriate way.  In particular,
lookup_in_pmap() is troublesome; you compare (void *) pointers that were
originally completely different types, for equality.  I thought about it
a lot and eventually decided that the whole thing was permitted by the
standard.  It seems like a better answer now than it did when I first
did it; I originally intended to replace it with the
two-different-representations methhod when I got a chance.  

    In any case, the whole problem seemed sufficiently interesting to be
worth bringing up here.  Are there any worthwhile solutions I've
overlooked?  Any comments?  What would you have done in a similar
situation?  Is there a language that makes these things easier?  (Sure;
I could have written it in LISP.)
--

           Millions for defense, but not one cent for tribute.
Mark-Jason Dominus 	  			    mjd@central.cis.upenn.edu