source: doc/theses/mike_brooks_MMath/list.tex @ 5aeb1a9

\chapter{Linked List}

I wrote a linked-list library for \CFA.  This chapter describes it.

The library provides a doubly-linked list that
attaches links intrusively,
supports multiple link directions,
integrates with user code via the type system, 
treats its ends uniformly, and
identifies a list using an explicit head.

TODO: more summary



\section{Features}

\subsection{Core Design Issues}

This section reviews how a user experiences my \CFA list library's position on the issues of Section~\ref{toc:lst:issue}.
The library provides a doubly-linked list that
attaches links intrusively,
supports multiple link directions,
integrates with user code via the type system, 
treats its ends uniformly, and
identifies a list using an explicit head.

The \CFA list library's version of the running @req@ example is in Figure~\ref{fig:lst-features-intro}.
Its link attachment is intrusive and the resulting memory layout is pure-stack, just as for the LQ version of Figure~\ref{f:Intrusive}.
The framework-provided type @dlink(...)@ provides the links.
The user inserts the links into the @req@ structure by using \CFA inline-inheritance (TODO: reference introduction).
Inline inheritance means the type of the field is @dlink(req)@, the field is unnamed, a reference to a @req@ is implicitly convertible to @dlink@.\footnote{
    The \CFA list examples elide the \lstinline{P9_EMBEDDED} annotations that (TODO: xref P9E future work) proposes to obviate.
    Thus, these examples illustrate a to-be state, free of what is to be historic clutter.
    The elided portions are immaterial to the discussion and the examples work with the annotations provided.
    The \CFA test suite (TODO:cite?) includes equivalent demonstrations, with the annotations included.}
These links have a nontrivial, user-specified location within the @req@ structure;
this convention encapsulates the implied pointer arithmetic safely.

\begin{figure}
    \lstinput{20-32}{lst-features-intro.run.cfa}
    \caption[Multiple link directions in \CFA list library]{
        Demonstration of the running \lstinline{req} example, done using the \CFA list library.
        This example does the same job that Figure~\ref{fig:lst-issues-attach} shows three ways.
    }
    \label{fig:lst-features-intro}
\end{figure}

\begin{figure}
\centering
\begin{tabular}{@{}ll@{}}
\begin{tabular}{@{}l@{}}
    \lstinput{20-25}{lst-features-multidir.run.cfa} \\
    \lstinput{40-67}{lst-features-multidir.run.cfa}
    \end{tabular}
        &
        \lstinput[language=C++]{20-60}{lst-issues-multi-static.run.c}
        \end{tabular}

\caption{
        Demonstration of multiple static link directions done in the \CFA list library.
        This example does the same job as Figure~\ref{fig:lst-issues-multi-static}.
    }
    \label{fig:lst-features-multidir}
\end{figure}

Figure~\ref{fig:lst-features-multidir} shows how the \CFA library supports multi-static link directionality.
The declaration of @req@ now has two inline-inheriting @dlink@ occurrences.
The first of these lines gives a type named @req.by_pri@, @req@ inherits from it, and it inherits from @dlink@.
The second line @req.by_rqr@ is similar to @req.by_pri@.
Thus, there is a diamond, non-virtual, inheritance from @req@ to @dlink@, with @by_pri@ and @by_rqr@ being the mid-level types.
Disambiguation occurs in the declarations of the list-head objects.
The type of the variable @reqs_pri_global@ is @dlist(req, req.by_pri)@,
meaning operations called on @reqs_pri_global@ are implicitly disambiguated.
In the example, the calls @insert_first(reqs_pri_global, ...)@ imply, ``here, we are working by priority.''

The \CFA library also supports the common case, of single directionality, more naturally than LQ.  
Figure~\ref{fig:lst-features-intro} shows a single-direction list done with no contrived name for the link direction,
where Figure~\ref{f:Intrusive} adds the unnecessary name, @x@.
In \CFA, a user doing a single direction (Figure~\ref{fig:lst-features-intro})
sets up a simple inheritance with @dlink@, and declares a list head to have the simpler type @dlist(...)@.
While a user doing multiple link directions (Figure~\ref{fig:lst-features-multidir})
sets up a diamond inheritance with @dlink@, and declares a list head to have the more-informed type @dlist(..., DIR)@.

The \CFA library offers a type-system mediated integration with user code.
The examples presented do not use preprocessor macros.
The touchpoints @dlink@ and @dlist@ are ordinary types.
Even though they are delivered as header-included static-inline implementations,
the \CFA compiler typechecks the list library code separately from user code.
Errors in user code are reported only with mention of the library's declarations.

The \CFA library works in headed and headless modes.  TODO: elaborate.

\subsection{Iteration-FOUNDATIONS}

TODO: This section should be moved to a Foundations chapter.  The next section stays under Linked List.


\subsection{Iteration}


\section{Future Work}
\label{toc:lst:futwork}


TODO: deal with: A doubly linked list is being designed.

TODO: deal with: Link fields are system-managed.
Links in GDB.