% TYPE STRUCTURES
% typestruc.tex
% David.N.Williams@umich.edu
% Last revision:  July 16, 2000

\section{Type structures}\label{typestruc}

In Section~\ref{structdata} we introduced atomic data, arrays, unions,
and bit-fields as classes of structure fields.  In C they are also
basic data objects (except for bit-fields, which occur only in
structures), with unions on much the same logical footing as
structures.

During implementation, we found ourselves driven to a typing scheme
with a partial type data structure shared by all types, including each
of the atomic data types.  In this section we lay out the type data
pointed to by \adtype, \atype, \utype, and \bftype, as well as that
pointed to by the unstructured field type pointer, \ustype.  The first
three fields, i.e., {\tt size}, {\tt class}, and {\tt alignment}, are
shared by all types, including that for structures already described
in Section~\ref{structdata}.  The size in the first field is measured
in address units.

\newcommand{\mathtimes}{{$\times$}}

% Keep the spacing below!
Here are the type information layouts.  For completeness, we include 
the \stype layout given in the Section~\ref{structdata}:
\begin{alltt}
      ustype: size {\normalfont (of unstructured field)}
              class {\normalfont (0)}
              alignment {\normalfont (1)}

      stype:  size {\normalfont (including padding)}
              class {\normalfont (1)}
              alignment
              #fields
              field 1 parameters
              \vdots
              field n parameters

      adtype: size {\normalfont (of atomic data)}
              class {\normalfont (2)}
              alignment

      atype:  size {\normalfont (\verb|#elements|\mathtimes size of type at \verb|type pointer|)}
              class {\normalfont (3)}
              alignment {\normalfont (of element type at \verb|type pointer|)}
              #elements
              type pointer {\normalfont (to element type)}

\clearscreenpage

      utype:  size {\normalfont (rounded max of union field sizes)}
              class {\normalfont (4)}
              alignment {\normalfont (max of union field alignments)}
              #fields
              field 1 parameters
              \vdots
              field n parameters

      bftype: size {\normalfont (of 0, 1, or 2 containers in bytes)}
              class {\normalfont (5)}
              alignment {\normalfont (of container type)}
              size {\normalfont (of container type in bits)}
              bit offset {\normalfont (in first container field)}
              #bits {\normalfont (in bit-field)}
\end{alltt}

Although we include array fields in structures and unions, we
implement neither array data objects nor accessors for array data.  C
allows multiple array indices, which it treats by having arrays of
arrays.  We take that to be a matter of access, irrelevant for the
\atype, which does not record how many indices might be used to index
the data.\footnote%
{The \atype layout here could in principle be used for an implicit
multiple index scheme by letting the element type pointer be another
\atype, etc., in a chain ending with a non-\atype, corresponding to
the last index.  All of the alignments in the chain would be the same,
that of the final array element type.  Seems more complicated than
we're likely to need.}

The union definition table pointed to by \utype has exactly the same
form as a structure definition table, with a different interpretation
of size and alignment as indicated in the table above, and with
offsets in the field parameters all set to zero.

We found the implementation of bit-fields a major project.  The idea
is to save space by packing more than one bit-field or partial
bit-field into a system storage unit.  This is explained further in
the Section~\ref{layout}.

\clearemptydoublepage