Xref: utzoo comp.lang.eiffel:308 comp.lang.c++:3963 comp.lang.misc:3068
Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!apple!bionet!ames!haven!mimsy!pugh
From: pugh@mimsy.UUCP (Bill Pugh)
Newsgroups: comp.lang.eiffel,comp.lang.c++,comp.lang.misc
Subject: Record layout for multiple inheritance
Message-ID: <18498@mimsy.UUCP>
Date: 11 Jul 89 19:58:59 GMT
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 33

I've several rumors about techniques for record layout with multiple
inheritance, but no solid information. Does anyone know for any 
results in this area?

The basic problem is as follows. We have record types with the following
fields:
  type x = {a : int, b : int}; 
	y = {a : int, c : int};
	z = {a : int, b : int, c : int};

  We wish to have z be a subtype of both x and y. How can we layout the
fields in x, y and z so that, for example, we can extract the field c
in constant time from a record that might be either type y or z.

  One answer is to place a at offset 0, b at offset 4 and c at offset -4. 
By not always having pointers to records point to the first field, we
can get simple constant time access to fields. It is not always possible
to layout fields this way (for example, it is not possible in the case of
triple inheritance).

  I heard that Bjarne Stroustrup originated this idea, but have been unable
to find any references. In his book, Bertrand Meyer also claims to have a 
technique for doing constant-time access (section 15.4.2), although he
does not give any details. Is this described anywhere?

In summary, does anyone have pointers to published work on this technique?

	Bill Pugh
	Assistant Professor
	University of Maryland, College Park
	pugh@mimsy.umd.edu