Context Navigation

-              rf632bd50
+              rb195498
 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}.
+This design covers system and data management issues stated in \VRef{toc:lst:issue}.
+\VRef[Figure]{fig:lst-features-intro} continues the running @req@ example from \VRef[Figure]{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 \VRef[Figure]{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}.
 …
     \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}.
+        This example is equivalent to the three approaches in \VRef[Figure]{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.
+\VRef[Figure]{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 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.
+As in \VRef[Figure]{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}
 …
 \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 right example is from \VRef[Figure]{fig:lst-issues-multi-static}.
                 The left \CFA example does the same job.
+    }
 …
 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 )@.
+\VRef[Figure]{fig:lst-features-intro} shows a single-direction list done with no contrived name for the link direction,
+where \VRef[Figure]{f:Intrusive} adds the unnecessary field name, @d@.
+In \CFA, a user doing a single direction (\VRef[Figure]{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, (\VRef[Figure]{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.
 …
 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.''
+Otherwise, the sole applicable list direction \emph{just works}.
 Unlike \CC templates container-types, the \CFA library works completely within the type system;
 …
 @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.
+@first@ returns a reference to the first node of the list without removing it or @0p@ if the list is empty.
+\item
+@last@ returns a reference to the last node of the list without removing it or @0p@ if the list is empty.
 \item
 @insert_before@ adds a node before the specified node and returns the added node for cascading.
 …
 @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.
+@remove@ removes the specified node from the list (any location) and returns a reference to the node.
+\item
+@iter@ create an iterator for the list.
+\item
+@recede@ returns true if the iterator cursor is advanced to the previous (predecessor, towards first) node before the prior cursor node and false otherwise.
+\item
+@advance@ returns true if the iterator cursor is advanced to the next (successor, towards last) node after the prior cursor node and false otherwise.
+\item
+@isFirst@ returns true if the node is the first node in the list and false otherwise.
+\item
+@isLast@ returns true if the node is the last node in the list and false otherwise.
+\item
+@pred@ returns a reference 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
+@next@ returns a reference 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
+@insert_first@ adds a node to the start of the list so it becomes the first node and returns a reference 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 reference to the node for cascading.
+\item
+@remove_first@ removes the first node and returns a reference to it or @0p@ if the list is empty.
+\item
+@remove_last@ removes the last node and returns a reference to it or @0p@ if the list is empty.
 \item
 @transfer@ transfers all nodes from the @from@ list to the end of the @to@ list; the @from@ list is empty after the transfer.
 …
 \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 & isListed( E & node );
+E & isEmpty( dlist( E ) & list );
+E & first( dlist( E ) & list );
+E & last( dlist( E ) & list );
 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 & iter( dlist( E ) & list );
+bool advance( E && refx );
+bool recede( E && refx );
+bool isFirst( E & node );
+bool isLast( E & node );
+E & prev( E & node );
+E & next( 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}
 …
 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.
+\VRef[Figure]{f:IteratorTemple} 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.
 …
         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
+        for ( ... ) @sout | it.v | ",";   sout | nl;@ // iterator examples in text
         remove( n1 );   remove( n2 );   remove( n3 );   remove( n4 );
+}
 \end{cfa}
 \caption{Iterator Example}
 \label{f:IteratorExample}
+\caption{Iterator Temple}
+\label{f:IteratorTemple}
 \end{figure}
 …
 \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@ ) ...
+for ( node & it = @first@( list ); &it /* != 0p */ ; &it = &@next@( it ) ...
+for ( node & it = @last@( list ); &it; &it = &@prev@( it ) ) ...
 \end{cfa}
+&
 …
 \begin{tabular}{@{}l|l@{}}
 \begin{cfa}
 for ( node & it = @n2@; &it; &it = &it`@next@ ) ...
 for ( node & it = @n3@; &it; &it = &it`@prev@ ) ...
+for ( node & it = @n2@; &it; &it = &@next@( it ) ) ...
+for ( node & it = @n3@; &it; &it = &@prev@( it ) ) ...
 \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@ ) ...
+Iterating forward and reverse from a starting node to an ending node through the contained list.
+\begin{cquote}
+\setlength{\tabcolsep}{15pt}
+\begin{tabular}{@{}l|l@{}}
+\begin{cfa}
+for ( node & it = @n2@; &it @!= &n4@; &it = &@next@( it ) ) ...
+for ( node & it = @n4@; &it @!= &n2@; &it = &@prev@( it ) ) ...
 \end{cfa}
+&
 …
 \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@; ) ...
+In this case, @advance@ and @recede@ return a boolean, like \CC @while ( cin >> i )@.
+\begin{cquote}
+\setlength{\tabcolsep}{15pt}
+\begin{tabular}{@{}l|l@{}}
+\begin{cfa}
+for ( node & it = @iter@( list ); @advance@( it ); ) ...
+for ( node & it = @iter@( list ); @recede@( it ); ) ...
 \end{cfa}
+&
 …
 \end{tabular}
 \end{cquote}
 The ability to provide a language-level @foreach@ is a future \CFA project.
+Macros are not ideal, so future work is to provide a language-level @foreach@ statement, like \CC.
 Finally, a predicate can be added to any of the manual iteration loops.
 \begin{cquote}
 …
 \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)@; ) ...
+for ( node & it = first( list ); &it @&& !(it.v == 3)@; &it = &next( it ) ) ...
+for ( node & it = last( list ); &it @&& !(it.v == 1)@; &it = &prev( it ) ) ...
+for ( node & it = iter( list ); advance( it ) @&& !(it.v == 3)@; ) ...
+for ( node & it = iter( list ); recede( it ) @&& !(it.v == 1)@; ) ...
 \end{cfa}
+&
 …
 \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.
+Even though the user-facing list model is 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@.
 …
 \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.
+System-added link pointers (dashed lines) are internally tagged to indicate linear endpoints that are the circular pointers.
+Links among neighbour nodes are not tagged.
 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.
+The content of a @dlist@ is a (private) @dlink@, with the @next@ pointer to the first element, and the @prev@ pointer to the last element.
+Since the head wraps a @dlink@, as does a @req@ does too, and since a link-pointer targets a @dlink@, the resulting cycle is among @dlink@ structures, situated inside of header/node.
+An untagged pointer points within a @req@, while a tagged pointer points 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.

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset b195498 for doc/theses/mike_brooks_MMath/list.tex

Legend:

doc/theses/mike_brooks_MMath/list.tex

Download in other formats: