source: doc/theses/mike_brooks_MMath/list.tex @ e78966e

\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{Design Issues}
\label{toc:lst:issue}

This section introduces the design space for linked lists that target system programmers.

All design-issue discussions assume the following invariants.
\PAB{They are stated here to clarify that none of the discussed design issues refers to one of these.}
Alternatives to the assumptions are discussed under Future Work (Section~\ref{toc:lst:futwork}).
\begin{itemize}
    \item A doubly-linked list is being designed.
          Generally, the discussed issues apply similarly for singly-linked lists.
          Circular vs ordered linking is discussed under List identity (Section~\ref{toc:lst:issue:ident}).
    \item Link fields are system-managed.
          The user works with the system-provided API to query and modify list membership.
          The system has freedom over how to represent these links.
          The library is not providing applied wrapper operations that consume a user's hand-implemented list primitives.
    \item \PAB{These issues are compared at a requirement/functional level.}
\end{itemize}

Two preexisting linked-list libraries are used throughout, to show examples of the concepts being defined,
and further libraries are introduced as needed.
\begin{description}
    \item[LQ] Linux Queue library\cite{lst:linuxq} of @<sys/queue.h>@.
    \item[STL] C++ Standard Template Library's @std::list@\cite{lst:stl}
\end{description}
A general comparison of libraries' abilities is given under Related Work (Section~\ref{toc:lst:relwork}).

The fictional type @req@ (request) is the user's payload in examples.
The list library is helping the user track requests.
A request represents work that the user must do but has not done yet.
This work is on the level of handling a network arrival event or scheduling a thread.



\subsection{Link attachment: Intrusive vs.\ Wrapped}
\label{toc:lst:issue:attach}

Link attachment deals with the question:
Where are the system's inter-element link fields stored, in relation to the user's payload data fields?
An intrusive list places the link fields inside the payload structure.
A wrapped list places the payload inside a generic system-provided structure that also defines the link fields.
LQ is intrusive; STL is wrapped.

The wrapped style admits the further distinction between wrapping a reference and wrapping a value.
This distinction is pervasive in all STL collections; @list<req *>@ wraps a reference; @list<req>@ wraps a value.
(For this discussion, @list<req &>@ is similar to @list<req *>@.)
This difference is one of user style, not framework capability.
Figure~\ref{fig:lst-issues-attach} compares the three styles.

\begin{comment}
\begin{figure}
    \begin{tabularx}{\textwidth}{Y|Y|Y}
                \lstinput[language=C]{20-39}{lst-issues-intrusive.run.c}
        &\lstinputlisting[language=C++]{20-39}{lst-issues-wrapped-byref.run.cpp}
        &\lstinputlisting[language=C++]{20-39}{lst-issues-wrapped-emplaced.run.cpp}
      \\ & &
      \\
        \includegraphics[page=1]{lst-issues-attach.pdf}
        &
        \includegraphics[page=2]{lst-issues-attach.pdf}
        &
        \includegraphics[page=3]{lst-issues-attach.pdf}
      \\ & &
      \\
        (a) & (b) & (c)
    \end{tabularx}
\caption{
        Three styles of link attachment: (a)~intrusive, (b)~wrapped reference, and (c)~wrapped value. 
        The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
        head objects are discussed in Section~\ref{toc:lst:issue:ident}. 
        In (a), the field \lstinline{req.x} names a list direction;
        these are discussed in Section~\ref{toc:lst:issue:derection}.
        In (b) and (c), the type \lstinline{node} represents a system-internal type,
        which is \lstinline{std::_List_node} in the GNU implementation.
        (TODO: cite? found in  /usr/include/c++/7/bits/stl\_list.h )
    }
     \label{fig:lst-issues-attach}
\end{figure}
\end{comment}

\begin{figure}
\centering
\newsavebox{\myboxA}                                    % used with subfigure
\newsavebox{\myboxB}
\newsavebox{\myboxC}

\begin{lrbox}{\myboxA}
\begin{tabular}{@{}l@{}}
\lstinput[language=C]{20-39}{lst-issues-intrusive.run.c} \\
\ \\
\includegraphics[page=1]{lst-issues-attach.pdf}
\end{tabular}
\end{lrbox}

\begin{lrbox}{\myboxB}
\begin{tabular}{@{}l@{}}
\lstinput[language=C++]{20-39}{lst-issues-wrapped-byref.run.cpp} \\
\ \\
\includegraphics[page=2]{lst-issues-attach.pdf}
\end{tabular}
\end{lrbox}

\begin{lrbox}{\myboxC}
\begin{tabular}{@{}l@{}}
\lstinput[language=C++]{20-39}{lst-issues-wrapped-emplaced.run.cpp} \\
\ \\
\includegraphics[page=3]{lst-issues-attach.pdf}
\end{tabular}
\end{lrbox}

\subfloat[Intrusive]{\label{f:Intrusive}\usebox\myboxA}
\hspace{10pt}
\vrule
\hspace{10pt}
\subfloat[Wrapped reference]{\label{f:WrappedRef}\usebox\myboxB}
\hspace{10pt}
\vrule
\hspace{10pt}
\subfloat[Wrapped value]{\label{f:WrappedValue}\usebox\myboxC}

\caption{
        Three styles of link attachment: \protect\subref*{f:Intrusive}~intrusive, \protect\subref*{f:WrappedRef}~wrapped
        reference, and \protect\subref*{f:WrappedValue}~wrapped value. 
        The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
        head objects are discussed in Section~\ref{toc:lst:issue:ident}. 
        In \protect\subref*{f:Intrusive}, the field \lstinline{req.x} names a list direction;
        these are discussed in Section~\ref{toc:lst:issue:derection}.
        In \protect\subref*{f:WrappedRef} and \protect\subref*{f:WrappedValue}, the type \lstinline{node} represents a
        system-internal type, which is \lstinline{std::_List_node} in the GNU implementation.
        (TODO: cite? found in  /usr/include/c++/7/bits/stl\_list.h )
    }
    \label{fig:lst-issues-attach}
\end{figure}

The advantage of intrusive attachment is the control that it gives the user over memory layout.
Each diagrammed example is using the fewest dynamic allocations that its respective style allows.
Both wrapped attachment styles imply system-induced heap allocations.
Such an allocation has a lifetime that matches the item's membership in the list.
In \subref*{f:Intrusive} and \subref*{f:WrappedRef}, one @req@ object can enter and leave a list many times.
In \subref*{f:WrappedRef}, it implies a dynamic allocation/deallocation for each enter/leave; in \subref*{f:Intrusive}, it does not.

A further aspect of layout control is allowing the user to specify the location of the link fields within the @req@ object.
LQ allows this ability; a different mechanism of intrusion, such as inheriting from a @linkable@ base type, may not.
Having this control means the user can allocate the link fields to cache lines along with the other @req@ fields.
Doing this allocation sensibly can help improve locality or avoid false sharing.
With an attachment mechanism that does not offer this control,
a framework design choice or fact of the host language forces the links to be contiguous with either the beginning or end of the @req@.
All wrapping realizations have this limitation in their wrapped-value configurations.

Another subtle advantage of intrusive arrangement is that
a reference to a user-level item (@req@) is sufficient to navigate or manage the item's membership.
In LQ, \subref*{f:Intrusive}, a @req@ pointer is the right argument type for operations @LIST_NEXT@ or @LIST_REMOVE@;
there is no distinguishing a @req@ from ``a @req@ in a list.''
The same is not true of STL, \subref*{f:WrappedRef} or \subref*{f:WrappedValue}.
There, the analogous operations work on a parameter of type @list<T>::iterator@; 
they are @iterator::operator++()@, @iterator::operator*()@, and @list::erase(iterator)@.
There is no mapping from @req &@ to @list<req>::iterator@, except for linear search.

The advantage of wrapped attachment is the abstraction of a data item from its list membership(s).
In the wrapped style, the @req@ type can come from a library that serves many independent uses,
which generally have no need for listing.
Then, a novel use can still put @req@ in a (further) list, without requiring any upstream change in the @req@ library.
In intrusive attachment, the ability to be listed must be planned during the definition of @req@.
Similarly, style \subref*{f:WrappedRef} allows for one @req@ to occur at several positions in one list.
Styles \subref*{f:Intrusive} and \subref*{f:WrappedValue} do not support this ability.
\PAB{But style \subref*{f:WrappedValue} can sort of mimic this effect by have multiple copies of \lstinline{req} in the list, modulo changes to the copies are not seen by the original.}

\begin{figure}
    \lstinput[language=C++]{100-117}{lst-issues-attach-reduction.hpp}
    \lstinput[language=C++]{150-150}{lst-issues-attach-reduction.hpp}
    \caption{
        Reduction of wrapped attachment to intrusive attachment.
        Illustrated by pseudocode implementation of an STL-compatible API fragment
        using LQ as the underlying implementation.
        The gap that makes it pseudocode is that
        the LQ C macros do not expand to valid C++ when instantiated with template parameters---there is no \lstinline{struct El}.
        When using a custom-patched version of LQ to work around this issue,
        the programs of Figure~\ref{f:WrappedRef} and \protect\subref*{f:WrappedValue} work with this shim in place of real STL.
        Their executions lead to the same memory layouts.
    }
    \label{fig:lst-issues-attach-reduction}
\end{figure}

Wrapped attachment has a straightforward reduction to intrusive attachment, illustrated in Figure~\ref{fig:lst-issues-attach-reduction}.
This shim layer performs the implicit dynamic allocations that pure intrusion avoids.
But there is no reduction going the other way.
No shimming can cancel the allocations to which wrapped membership commits.

So intrusion is a lower-level listing primitive.
And so, the system design choice is not between forcing users to use intrusion or wrapping.
The choice is whether or not to provide access to an allocation-free layer of functionality.
A wrapped-primitive library like STL forces users to incur the costs of wrapping, whether or not they access its benefits.
An intrusive-primitive library like LQ lets users choose when to make this tradeoff.


\subsection{Directionality: Single vs.\ Multi-Static vs.\ Dynamic}
\label{toc:lst:issue:derection}

Axis?

\PAB{I'm not sure about the term \newterm{Directionality}. Directionality to me, means going forward or backwards through a list.
Would \newterm{dimensionality} work? Think of each list containing the node as a different dimension in which the node sits.}

Directionality deals with the question:
In how many different lists can an item be stored, at a given time?

Consider STL in the wrapped-value arrangement of Figure~\ref{f:WrappedValue}.
The STL API completely hides its @node@ type from a user; the user cannot configure this choice or impose a custom one.
STL's @node@ type offers the sole set of links shown in the diagram.
Therefore, every @req@ in existence is allocated either to belong to an occurrence of the diagrammed arrangement,
or to be apart from all occurrences of it.
In the first case, the @req@ belongs to exactly one list (of the style in question).
STL with wrapped values supports a single link direction.

\begin{figure}
    \parbox[t]{3.5in} {
        \lstinput[language=C++]{20-60}{lst-issues-multi-static.run.c}
    }\parbox[t]{20in} {
        ~\\
        \includegraphics[page=1]{lst-issues-direct.pdf} \\
        ~\\
        \hspace*{1.5in}\includegraphics[page=2]{lst-issues-direct.pdf}
    }
    \caption{
        Example of two link directions, with an LQ realization.  
        The zoomed-out diagram portion shows the whole example dataset, conceptually.
        A consumer of this structure can navigate all requests in priority order, and navigate among requests from a common requestor.
        The code is the LQ implementation.
        The zoomed-in diagram portion shows the field-level state that results from running the LQ code.
    }
    \label{fig:lst-issues-multi-static}
\end{figure}


The user may benefit from a further link direction.
Suppose the user must both: navigate all requests in priority order, and navigate among requests from a common requestor.
Figure~\ref{fig:lst-issues-multi-static} shows such a situation.
Each of its ``by priority'' and ``by requestor'' is a link direction.
The example shows that a link direction can occur either as one global list (by-priority) or as many lists (there are three by-requestor lists).

The limitation of intrusive attachment presented in Section~\ref{toc:lst:issue:attach}
has a straightforward extension to multiple directions.
The set of directions by which an item is to be listed must be planned during the definition of the item.
Thus, intrusive LQ supports multiple, but statically many, link directions.

% https://www.geeksforgeeks.org/introduction-to-multi-linked-list/ -- example of building a bespoke multi-linked list out of STL primitives (providing indication that STL doesn't offer one); offers dynamic directionality by embedding `vector<struct node*> pointers;`

The corresponding flexibility of wrapped attachment means
the STL wrapped-reference arrangement supports an item being a member of arbitrarily many lists.
This support also applies to the wrapped-value list because the @req@ is copied,
but wrapped-reference lists provide further link directions.
\PAB{Explain how}
STL with wrapped references supports dynamic link directions.
\PAB{Expand}

When allowing multiple static directions, frameworks differ in their ergonomics for
the typical case: when the user needs only one direction, vs.\ the atypical case, when the user needs several.
LQ's ergonomics are well-suited to the uncommon case of multiple list directions.
Its intrusion declaration and insertion operation both use a mandatory explicit parameter naming the direction.
This decision works well in Figure~\ref{fig:lst-issues-multi-static}, where the names @by_pri@ and @by_rqr@ work well,
but it clutters Figure~\ref{f:Intrusive}, where a contrived name must be invented and used.
The example uses @x@; @reqs@ would be a more readily ignored choice. \PAB{wording?}

\uCpp offers an intrusive list that makes the opposite choice.  TODO: elaborate on inheritance for first direction and acrobatics for subsequent directions.


\subsection{User integration: Preprocessed vs.\ Type-System Mediated}

% example of poor error message due to LQ's preprocessed integration
% programs/lst-issues-multi-static.run.c:46:1: error: expected identifier or '(' before 'do'
%    46 | LIST_INSERT_HEAD(&reqs_rtr_42, &r42b, by_rqr);
%       | ^~~~~~~~~~~~~~~~
%
% ... not a wonderful example; it was a missing semicolon on the preceding line; but at least real


\subsection{List identity: Headed vs.\ Ad-hoc}
\label{toc:lst:issue:ident}

All examples so far have used distinct user-facing types: 
an item found in a list (type @req@, of variables like @r1@), and
a list (type @reql@ or @list<req>@, of variables like @reqs@ or @reqs_rqr_42@).
\see{Figure~\ref{fig:lst-issues-attach} and Figure~\ref{fig:lst-issues-multi-static}}
The latter type is a head, and these examples are of headed lists.

A bespoke ``pointer to next @req@'' implementation often omits the latter type.
Such a list model is ad-hoc.

In headed thinking, there are length-zero lists (heads with no elements), and an element can be listed or not listed.
In ad-hoc thinking, there are no length-zero lists and every element belongs to a list of length at least one.
\PAB{Create a figure for this.}

By omitting the head, elements can enter into an adjacency relationship,
without requiring that someone allocate room for the head of the possibly-resulting list,
or being able to find a correct existing head.

A head defines one or more element roles, among elements that share a transitive adjacency.
``First'' and ``last'' are element roles.
One moment's ``first'' need not be the next moment's.

There is a cost to maintaining these roles.
A runtime component of this cost is evident in LQ's offering the choice of type generators @LIST@ vs.~@TAILQ@.
Its @LIST@ maintains a ``first,'' but not a ``last;'' its @TAILQ@ maintains both roles.
(Both types are doubly linked and an analogous choice is available for singly linked.)

TODO: finish making this point

See WIP in lst-issues-adhoc-*.ignore.*.

The code-complexity component of the cost ...

Ability to offer heads is good.  Point: Does maintaining a head mean that the user has to provide more state when manipulating the list?  Requiring the user to do so is bad, because the user may have lots of "list" typed variables in scope, and detecting that the user passed the wrong one requires testing all the listing edge cases.

\subsection{End treatment: Uniform }


\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.

\section{Related Work}
\label{toc:lst:relwork}