% datastruct.tex  93.01.23
% man Tech datastruct .
% Copyright 1983-1992   Albert Davis
%------------------------------------------------------------------------
\section{Data Structures}
%------------------------------------------------------------------------
Note: This section was written for an older version of the program.  There
have been significant changes.  There are errors in details but it is still
a good approximation of what is there.
%------------------------------------------------------------------------
\subsection{Parts list}
\index{internals: parts list}
\index{parts list: internals}
%------------------------------------------------------------------------
\subsubsection{Ring structure}
\index{internals: ring structure}
\index{ring structure: internals}

Internally, the parts list is stored as a bi-directional linked list, in a
ring structure.  There is no explicit head or tail.  A call to the function
{\em insertbranch} makes a copy of the structure, and makes all the
appropriate links.

To insert a branch into a particular list, set up one link, before calling
{\em insertbranch}.  The rest is automatic.  If both links are set to NULL,
the new device will be placed in its own new list, with itself as the only
member.

The function {\em deletebranch} deletes the branch and its children.  (See
delete list, next subsection.)  Links of surrounding elements are patched to
close the list.

There are many such rings.  The main circuit is one.  Each subcircuit and
model has another.  Some functions, {\em acfilllist} and {\em trfilllist},
for example, take a pointer to a list.  The pointer can be to any member of
the list.  The function will act on the entire list.

Some rings do have an explicit head-tail.  A dummy element acts as both head
and tail.  There are two reasons why some lists need this explicit head and
tail.  First, it is important, for visual purposes, to preserve the start
and end of the list.  Second, it is possible to have an empty list, for
example, no circuit.  Without this dummy element, it would not be possible
to keep an empty list.  The main circuit has a dummy element.  Subcircuits
do not.
%------------------------------------------------------------------------
\subsubsection{Delete list}
\index{internals: delete}
\index{delete: internals}

The first two fields of the generic structure are links to the next member
of two singly linked delete lists.  The first ({\em chain\/}) points to
blocks belonging to the parent.  The second ({\em x\/}) points to blocks
belonging to itself.  When any element is deleted, the memory blocks pointed
to by both of these fields are also deleted, recursively.

This extends to all sub-structures used in models.  They are not necessarily
of the same type, but the first two fields must be links to the next element in
a delete list.  Since these structures are of different types, if they are
part of another list, links are not patched.  Usually, this is used to
delete an entire list.

Additional space required by this element is linked at {\em x}.  Examples of
data linked here include storage for model parameters, results of internal
calculations, and the head of a subcircuit expansion.

Examples of space linked at {\em chain} include mainly additional subcircuit
expansion elements.  The first element is linked at {\em x}.  Additional
elements are linked at {\em chain}.  To find the owner of an element linked
at {\em chain}, trace back through the linked list until one is linked at
{\em x}.
%------------------------------------------------------------------------
%------------------------------------------------------------------------
