source: doc/theses/mike_brooks_MMath/list.tex@ 9d9fd81

\chapter{Linked List}

This chapter presents my work on designing and building a linked-list library for \CFA.
Due to time limitations and the needs expressed by the \CFA runtime developers, I focussed on providing a doubly-linked list, and its bidirectionally iterators for traversal. 
Simpler data-structures, like stack and queue, can be built from the doubly-linked mechanism with only a slight storage/performance cost because of the unused link field.
Reducing to data-structures with a single link follows directly from the more complex doubly-links and its iterators.


\section{Features}

The following features directed this project, where the goal is high-performance list operations required by \CFA runtime components, like the threading library.


\subsection{Core Design Issues}

The doubly-linked list 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.
This design covers system and data management issues stated in Section~\ref{toc:lst:issue}.

Figure~\ref{fig:lst-features-intro} continues the running @req@ example from Figure~\ref{fig:lst-issues-attach} using the \CFA list.
The \CFA link attachment is intrusive so the resulting memory layout is per user node, as for the LQ version of Figure~\ref{f:Intrusive}.
The \CFA framework provides generic type @dlink( T, T )@ for the two link fields (front and back).
A user inserts the links into the @req@ structure via \CFA inline-inheritance from the Plan-9 C dialect~\cite[\S~3.3]{Thompson90new}.
Inline inheritance is containment, where the inlined field is unnamed but the type's internal fields are hoisted into the containing structure.
Hence, the field names must be unique, unlike \CC nested types, but the type names are at a nested scope level, unlike aggregate nesting in C.
Note, the position of the containment is normally unimportant, unless there is some form of memory or @union@ overlay.
The key feature of inlined inheritance is that a pointer to the containing structure is automatically converted to a pointer to any anonymous inline field for assignments and function calls, providing containment inheritance with implicit subtyping.
Therefore, a reference to a @req@ is implicitly convertible to @dlink@ in assignments and function calls.
% These links have a nontrivial, user-specified location within the @req@ structure;
% this convention encapsulates the implied pointer arithmetic safely.
The links in @dlist@ point at (links) in the containing node, know the offsets of all links (data is abstract), and any field-offset arithmetic or link-value changes are safe and abstract.

\begin{figure}
    \lstinput{20-30}{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 is equivalent to the three approaches in Figure~\ref{fig:lst-issues-attach}.
    }
    \label{fig:lst-features-intro}
\end{figure}

Figure~\ref{fig:lst-features-multidir} shows how the \CFA library supports multi-inline links, so a node can be on one or more lists simultaneously.
The declaration of @req@ has two inline-inheriting @dlink@ occurrences.
The first of these 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: @reqs_pri_global@, @reqs_rqr_42@, @reqs_rqr_17@, and @reqs_rqr_99@.
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.''
As in Figure~\ref{fig:lst-issues-multi-static}, three lists are constructed, a priority list containing all nodes, a list with only nodes containing the value 42, and a list with only nodes containing the value 17.

\begin{figure}
\centering
\begin{tabular}{@{}ll@{}}
\begin{tabular}{@{}l@{}}
    \lstinput{20-31}{lst-features-multidir.run.cfa} \\
    \lstinput{43-71}{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.
        The right example is from Figure~\ref{fig:lst-issues-multi-static}.
                The left \CFA example does the same job.
    }
    \label{fig:lst-features-multidir}
\end{figure}

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 field name, @d@.
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( T )@.
In contrast, (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( T, DIR )@.

The directionality issue also has an advanced corner-case that needs treatment.
When working with multiple directions, calls like @insert_first@ benefit from implicit direction disambiguation;
however, other calls like @insert_after@ still require explicit disambiguation, \eg the call
\begin{cfa}
insert_after(r1, r2);
\end{cfa}
does not have enough information to clarify which of a request's simultaneous list directions is intended.
Is @r2@ supposed to be the next-priority request after @r1@, or is @r2@ supposed to join the same-requester list of @r1@?
As such, the \CFA compiler gives an ambiguity error for this call.
To resolve the ambiguity, the list library provides a hook for applying the \CFA language's scoping and priority rules.
It applies as:
\begin{cfa}
with ( DLINK_VIA(req, req.pri) ) insert_after(r1, r2);
\end{cfa}
Here, the @with@ statement opens the scope of the object type for the expression;
hence, the @DLINK_VIA@ result causes one of the list directions to become a more attractive candidate to \CFA's overload resolution.
This boost applies within the scope of the following statement, but could also be a custom block or an entire function body.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}ll@{}}
\begin{cfa}
void f() @with( DLINK_VIA(req, req.pri) )@ {
        ...

        insert_after(r1, r2);

        ...
}
\end{cfa}
&
\begin{cfa}
void f() {
        ...
        @with( DLINK_VIA(req, req.pri) )@ {
                ...  insert_after(r1, r2);  ...
        }
        ...
}
\end{cfa}
\end{tabular}
\end{cquote}
By using a larger scope, a user can put code within that acts as if there is only one list direction.
This boost is needed only when operating on a list with several directions, using operations that do not take the list head.
Otherwise, the sole applicable list direction ``just works.''

Unlike \CC templates container-types, the \CFA library works completely within the type system;
both @dlink@ and @dlist@ are ordinary types.
There is no textual expansion other than header-included static-inline function for performance.
Errors in user code are reported only with mention of the library's declarations.
Finally, the library is separately compiled from the usage code.

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


\section{List API}

\VRef[Figure]{f:ListAPI} shows the API for the doubly-link list operations, where each is explained.
\begin{itemize}[leftmargin=*]
\item
@isListed@ returns true if the node is an element of a list and false otherwise.
\item
@isEmpty@ returns true if the list has no nodes and false otherwise.
\item
@first@ returns a pointer to the first node of the list without removing it or @0p@ if the list is empty.
\item
@last@ returns a pointer to the last node of the list without removing it or @0p@ if the list is empty.
\item
@next@ returns a pointer to the next (successor, towards last) node after the specified node or @0p@ if the specified node is the last node in the list.
\item
@pred@ returns a pointer to the previous (predecessor, towards first) node before the specified node or @0p@ if the specified node is the first node in the list.
\item
@insert_before@ adds a node before the specified node and returns the added node for cascading.
\item
@insert_after@ adds a node after the specified node and returns the added node for cascading.
\item
@remove@ removes the specified node from the list (any location) and returns a pointer to the node.
\item
@insert_first@ adds a node to the start of the list so it becomes the first node and returns a pointer to the node for cascading.
\item
@insert_last@ adds a node to the end of the list so it becomes the last node and returns returns a pointer to the node for cascading.
\item
@insert@ is a synonym for @insert_last@.
\item
@remove_first@ removes the first node and returns a pointer to it or @0p@ if the list is empty.
\item
@remove_last@ removes the last node and returns a pointer to it or @0p@ if the list is emptyy.
\item
@transfer@ transfers all nodes from the @from@ list to the end of the @to@ list; the @from@ list is empty after the transfer.
\item
@split@ transfers the @from@ list up to node to the end of the @to@ list; the @from@ list becomes the list after the node.
The node must be in the @from@ list.
\end{itemize}

\begin{figure}
\begin{cfa}
E & ?`isEmpty( dlist( E ) & list );
E & ?`isListed( E & node );
E & ?`first( dlist( E ) & list );
E & ?`last( dlist( E ) & list );
E & ?`next( E & node );
E & ?`prev( E & node );
E & insert_before( E & before, E & node );
E & insert_after( E & after, E & node );
E & remove( E & node );
E & ?`elems( dlist( E ) & list );
E & ?`head( dlist( E ) & list );
bool ?`moveNext( E && refx );
bool ?`next( E && refx );                                                       // alternate name
bool ?`movePrev( E && refx );
bool ?`prev( E && refx );                                                       // alternate name
bool ?`hasNext( E & node );
bool ?`hasPrev( E & node );
E & insert_first( dlist( E ) & list, E & node );
E & insert_last( dlist( E ) & list, E & node );
E & insert( dlist( E ) & list, E & node );              // alternate name
E & remove_first( dlist( E ) & list );
E & remove_last( dlist( E ) & list );
void transfer( dlist( E ) & to, dlist( E ) & from ) {
void split( dlist( E ) & to, dlist( E ) & from, E & node ) {
E & try_pop_front( dlist( E ) & list );
E & try_pop_back( dlist( E ) & list );
\end{cfa}
\caption{\CFA List API}
\label{f:ListAPI}
\end{figure}


\subsection{Iteration}

It is possible to iterate through a list manually or using a set of standard macros.
\VRef[Figure]{f:IteratorExample} shows the iterator template, managing a list of nodes, used throughout the following iterator examples.
Each example assumes its loop body prints the value in the current node.

\begin{figure}
\begin{cfa}
#include <fstream.hfa>
#include <list.hfa>

struct node {
        int v;
        inline dlink(node);
};
int main() {
        dlist(node) list;
        node n1 = { 1 }, n2 = { 2 }, n3 = { 3 }, n4 = { 4 };
        insert( list, n1 );   insert( list, n2 );   insert( list, n3 );   insert( list, n4 );
        sout | nlOff;
        for ( node & it = list`first; &it; &it = &it`next ) @sout | it.v | ",";   sout | nl;@
        // other iterator examples
        remove( n1 );   remove( n2 );   remove( n3 );   remove( n4 );
}
\end{cfa}
\caption{Iterator Example}
\label{f:IteratorExample}
\end{figure}

The manual method is low level but allows complete control of the iteration.
The list cursor (index) can be either a pointer or a reference to a node in the list.
The choice depends on how the programmer wants to access the fields: @it->f@ or @it.f@.
The following examples use a reference because the loop body manipulates the node values rather than the list pointers.
The end of iteration is denoted by the loop cursor having the null pointer, denoted @0p@ in \CFA.

\noindent
Iterating forward and reverse through the entire list.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}l|l@{}}
\begin{cfa}
for ( node & it = list`@first@; &it /* != 0p */ ; &it = &it`@next@ ) ...
for ( node & it = list`@last@; &it; &it = &it`@prev@ ) ...
\end{cfa}
&
\begin{cfa}
1, 2, 3, 4,
4, 3, 2, 1,
\end{cfa}
\end{tabular}
\end{cquote}
Iterating forward and reverse from a starting node through the remaining list.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}l|l@{}}
\begin{cfa}
for ( node & it = @n2@; &it; &it = &it`@next@ ) ...
for ( node & it = @n3@; &it; &it = &it`@prev@ ) ...
\end{cfa}
&
\begin{cfa}
2, 3, 4,
3, 2, 1,
\end{cfa}
\end{tabular}
\end{cquote}
Iterating forward and reverse from a starting node to an ending node through the remaining list.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}l|l@{}}
\begin{cfa}
for ( node & it = @n2@; &it @!= &n4@; &it = &it`@next@ ) ...
for ( node & it = @n4@; &it @!= &n2@; &it = &it`@prev@ ) ...
\end{cfa}
&
\begin{cfa}
2, 3,
4, 3,
\end{cfa}
\end{tabular}
\end{cquote}
Iterating forward and reverse through the entire list using the shorthand start at the list head and pick a direction.
In this case, @next@ and @prev@ return a boolean, like \CC @while ( cin >> i )@.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}l|l@{}}
\begin{cfa}
for ( node & it = list`@head@; it`@next@; ) ...
for ( node & it = list`@head@; it`@prev@; ) ...
\end{cfa}
&
\begin{cfa}
1, 2, 3, 4,
4, 3, 2, 1,
\end{cfa}
\end{tabular}
\end{cquote}
Finally, there are convenience macros that look like @foreach@ in other programming languages.
Iterating forward and reverse through the entire list.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}l|l@{}}
\begin{cfa}
FOREACH( list, it ) ...
FOREACH_REV( list, it ) ...
\end{cfa}
&
\begin{cfa}
1, 2, 3, 4,
4, 3, 2, 1,
\end{cfa}
\end{tabular}
\end{cquote}
Iterating forward and reverse through the entire list or until a predicate is triggered.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}l|l@{}}
\begin{cfa}
FOREACH_COND( list, it, @it.v == 3@ ) ...
FOREACH_REV_COND( list, it, @it.v == 1@ ) ...
\end{cfa}
&
\begin{cfa}
1, 2,
4, 3, 2,
\end{cfa}
\end{tabular}
\end{cquote}
The ability to provide a language-level @foreach@ is a future \CFA project.
Finally, a predicate can be added to any of the manual iteration loops.
\begin{cquote}
\setlength{\tabcolsep}{15pt}
\begin{tabular}{@{}l|l@{}}
\begin{cfa}
for ( node & it = list`first; &it @&& !(it.v == 3)@; &it = &it`next ) ...
for ( node & it = list`last; &it @&& !(it.v == 1)@; &it = &it`prev ) ...
for ( node & it = list`head; it`next @&& !(it.v == 3)@; ) ...
for ( node & it = list`head; it`prev @&& !(it.v == 1)@; ) ...
\end{cfa}
&
\begin{cfa}
1, 2,
4, 3, 2,
1, 2,
4, 3, 2,
\end{cfa}
\end{tabular}
\end{cquote}

\begin{comment}
Many languages offer an iterator interface for collections, and a corresponding for-each loop syntax for consuming the items through implicit interface calls.
\CFA does not yet have a general-purpose form of such a feature, though it has a form that addresses some use cases.
This section shows why the incumbent \CFA pattern does not work for linked lists and gives the alternative now offered by the linked-list library.
Chapter 5 [TODO: deal with optimism here] presents a design that satisfies both uses and accommodates even more complex collections.

The current \CFA extensible loop syntax is:
\begin{cfa}
for( elem; end )
for( elem; begin ~ end )
for( elem; begin ~ end ~ step )
\end{cfa}
Many derived forms of @begin ~ end@ exist, but are used for defining numeric ranges, so they are excluded from the linked-list discussion.
These three forms are rely on the iterative trait:
\begin{cfa}
forall( T ) trait Iterate {
        void ?{}( T & t, zero_t );
        int ?<?( T t1, T t2 );
        int ?<=?( T t1, T t2 );
        int ?>?( T t1, T t2 );
        int ?>=?( T t1, T t2 );
        T ?+=?( T & t1, T t2 );
        T ?+=?( T & t, one_t );
        T ?-=?( T & t1, T t2 );
        T ?-=?( T & t, one_t );
}
\end{cfa}
where @zero_t@ and @one_t@ are constructors for the constants 0 and 1.
The simple loops above are abbreviates for:
\begin{cfa}
for( typeof(end) elem = @0@; elem @<@ end; elem @+=@ @1@ )
for( typeof(begin) elem = begin; elem @<@ end; elem @+=@ @1@ )
for( typeof(begin) elem = @0@; elem @<@ end; elem @+=@ @step@ )
\end{cfa}
which use a subset of the trait operations.
The shortened loop works well for iterating a number of times or through an array.
\begin{cfa}
for ( 20 ) // 20 iterations
for ( i: 1 ~= 21 ~ 2 ) // odd numbers
for ( i; n ) total += a[i]; // subscripts
\end{cfa}
which is similar to other languages, like JavaScript.
\begin{cfa}
for ( i in a ) total += a[i];
\end{cfa}
Albeit with different mechanisms for expressing the array's length.
It might be possible to take the \CC iterator:
\begin{c++}
for ( list<int>::iterator it=mylist.begin(); it != mylist.end(); ++it )
\end{c++}
and convert it to the \CFA form
\begin{cfa}
for ( it; begin() ~= end() )
\end{cfa}
by having a list operator @<=@ that just looks for equality, and @+=@ that moves to the next node, \etc.

However, the list usage is contrived, because a list does use its data values for relational comparison, only links for equality comparison.
Hence, the focus of a list iterator's stopping condition is fundamentally different.
So, iteration of a linked list via the existing loop syntax is to ask whether this syntax can also do double-duty for iterating values.
That is, to be an analog of JavaScript's @for..of@ syntax:
\begin{cfa}
for ( e of a ) total += e;
\end{cfa}

The \CFA team will likely implement an extension of this functionality that moves the @~@ syntax from being part of the loop, to being a first-class operator (with associated multi-pace operators for the elided derived forms).
With this change, both @begin ~ end@ and @end@ (in context of the latter ``two-place for'' expression) parse as \emph{ranges}, and the loop syntax becomes, simply:
\begin{cfa}
    for( elem; rangeExpr )
\end{cfa}
The expansion and underlying API are under discussion.
TODO: explain pivot from ``is at done?'' to ``has more?''
Advantages of this change include being able to pass ranges to functions, for example, projecting a numerically regular subsequence of array entries, and being able to use the loop syntax to cover more collection types, such as looping over the keys of a hashtable.

When iterating an empty list, the question, ``Is there a further element?'' needs to be posed once, receiving the answer, ``no.''
When iterating an $n$-item list, the same question gets $n$ ``yes'' answers (one for each element), plus one ``no'' answer, once there are no more elements; the question is posed $n+1$ times.

When iterating an empty list, the question, ``What is the value of the current element?'' is never posed, nor is the command, ``Move to the next element,'' issued.  When iterating an $n$-item list, each happens $n$ times.

So, asking about the existence of an element happens once more than retrieving an element's value and advancing the position.

Many iteration APIs deal with this fact by splitting these steps across different functions, and relying on the user's knowledge of iterator state to know when to call each.  In Java, the function @hasNext@ should be called $n+1$ times and @next@ should be called $n$ times (doing the double duty of advancing the iteration and returning a value).  In \CC, the jobs are split among the three actions, @it != end@, @it++@ and @*it@, the latter two being called one time more than the first.

TODO: deal with simultaneous axes: @DLINK_VIA@ just works

TODO: deal with spontaneous simultaneity, like a single-axis req, put into an array: which ``axis'' is @&req++@ navigating: array-adjacency vs link dereference.  It should sick according to how you got it in the first place: navigating dlist(req, req.pri) vs navigating array(req, 42).  (prob. future work)
\end{comment}



\section{Implementation}

\subsection{Links}

\VRef[Figure]{fig:lst-impl-links} continues the running @req@ example, now showing the \CFA list library's internal representation.
The @dlink@ structure contains exactly two pointers: @next@ and @prev@, which are opaque to a user.
Even though the user-facing list model is ordered (linear), the CFA library implements all listing as circular.
This choice helps achieve uniform end treatment and TODO finish summarizing benefit.
A link pointer targets a neighbouring @dlink@ structure, rather than a neighbouring @req@.
(Recall, the running example has the user putting a @dlink@ within a @req@.)

\begin{figure}
        \centering
        \includegraphics{lst-impl-links.pdf}
        \caption{
                \CFA list library representations for the cases under discussion.
        }
        \label{fig:lst-impl-links}
\end{figure}

Link pointers are internally tagged according to whether the link is user-visible.
Links among user-requested neighbours are left natural, with the tag bit not set.
System-added links, which produce the circular implementation, have the tag bit set.
Iteration reports ``has more elements'' when crossing natural links, and ``no more elements'' upon reaching a tagged link.

In a headed list, the list head (@dlist(req)@) acts as an extra element in the implementation-level circularly-linked list.
The content of a @dlist@ is a (private) @dlink@, with the @next@ pointer purposed for the first element, and the @prev@ pointer purposed for the last element.
Since the head wraps a @dlink@, since a @req@ does too, and since a link-pointer targets a @dlink@, the resulting cycle is among @dlink@ structures, situated inside of other things.
The tags on the links say what the wrapper is: untagged (user link) means the targeted @dlink@ is within a @req@, while tagged (system link) means the targeted @dlink@ is within a list head.

In a headless list, the circular backing list is only among @dlink@s within @req@s.  The tags are set on the links that a user cannot navigate.

No distinction is made between an unlisted item under a headed model and a singleton list under a headless model.  Both are represented as an item referring to itself, with both tags set.



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

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.
\begin{cfa}
struct mary {
        float anotherdatum;
        inline dlink(mary);
};
struct fred {
        float adatum;
        inline struct mine { inline dlink(fred); };
        inline struct yours { inline dlink(fred); };
};
\end{cfa}
like in the thesis examples.  You have to say
\begin{cfa}
struct mary {
        float anotherdatum;
        inline dlink(mary);
};
P9_EMBEDDED(mary, dlink(mary))
struct fred {
        float adatum;
        inline struct mine { inline dlink(fred); };
        inline struct yours { inline dlink(fred); };
};
P9_EMBEDDED(fred, fred.mine)
P9_EMBEDDED(fred, fred.yours)
P9_EMBEDDED(fred.mine, dlink(fred))
P9_EMBEDDED(fred.yours, dlink(fred))
\end{cfa}
like in tests/list/dlist-insert-remove.
Future work should autogen those @P9_EMBEDDED@ declarations whenever it sees a plan-9 declaration.
The exact scheme chosen should harmonize with general user-defined conversions.

Today's P9 scheme is:  mary gets a function `inner returning this as dlink(mary).
Fred gets four of them in a diamond.
They're defined so that `inner is transitive; i.e. fred has two further ambiguous overloads mapping fred to dlink(fred).
The scheme allows the dlist functions to give the assertion, "we work on any T that gives a `inner to dlink(T)."


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

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