Changes in / [c333ed2:0b6c1c9]


Ignore:
Files:
5 added
5 deleted
27 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/mike_brooks_MMath/Makefile

    rc333ed2 r0b6c1c9  
    44Pictures = pictures
    55Programs = programs
     6
     7LaTMac = ../../LaTeXmacros
     8BibRep = ../../bibliography
    69
    710TeXSRC = ${wildcard *.tex}
    … …  
    1215BibSRC = ${wildcard *.bib}
    1316
    14 TeXLIB = .:../../LaTeXmacros:${Build}:          # common latex macros
    15 BibLIB = .:../../bibliography                   # common citation repository
     17TeXLIB = .:${LaTMac}:${Build}:                  # common latex macros
     18BibLIB = .:${BibRep}:                           # common citation repository
    1619
    1720#MAKEFLAGS = --no-print-directory # --silent
    … …  
    4851# File Dependencies
    4952
    50 %.pdf : ${TeXSRC} ${DemoTex} ${PicSRC} ${PgmSRC} ${BibSRC} Makefile | ${Build}
     53%.pdf : ${TeXSRC} ${DemoTex} ${PicSRC} ${PgmSRC} ${BibSRC} ${BibRep}/pl.bib ${LaTMac}/common.tex Makefile | ${Build}
    5154        ${LaTeX} ${BASE}
    5255        ${BibTeX} ${Build}/${BASE}

  • doc/theses/mike_brooks_MMath/background.tex

    rc333ed2 r0b6c1c9  
    395395
    396396Linked-lists are blocks of storage connected using one or more pointers.
    397 The storage block is logically divided into data and links (pointers), where the links are the only component used by the list structure.
    398 Since the data is opaque, list structures are often polymorphic over the data, which is normally homogeneous.
     397The storage block is logically divided into data (user payload) and links (list pointers), where the links are the only component used by the list structure.
     398Since the data is opaque, list structures are often polymorphic over the data, which is often homogeneous.
     399
     400Linking is used to build data structures, which are a group of nodes, containing data and links, organized in a particular format, with specific operations peculiar to that format, \eg queue, tree, hash table, \etc.
     401Because a node's existence is independent of the data structure that organizes it, all nodes are manipulated by address not value;
     402hence, all data structure routines take and return pointers to nodes and not the nodes themselves.
     403
     404
     405\begin{comment}
     406\subsection{Linked-List Packages}
     407
     408C only supports type-eraser polymorphism, with no help from the type system.
     409This approach is used in the @queue@ library providing macros that define and operate on four types of data structures: singly-linked lists, singly-linked tail queues, lists, and tail queues.
     410These linked structures are \newterm{intrusive list}, where the link fields are defined (intrude) with data fields.
     411\begin{cfa}
     412struct DS {
     413        // link fields, intrustive
     414        // data fields
     415}
     416\end{cfa}
     417
     418\uCpp~\cite{uC++} is a concurrent extension of \CC, and provides a basic set of intrusive lists, where the link fields are defined with the data fields using inheritance.
     419\begin{cfa}
     420struct DS : public uColable {
     421        // implicit link fields
     422        // data fields
     423}
     424\end{cfa}
     425
     426Intrusive nodes eliminate the need to dynamically allocate/deallocate the link fields when a node is added/removed to/from a data-structure.
     427Reducing dynamic allocation is important in concurrent programming because the heap is a shared resource with the potential for high contention.
     428The two formats are one link field, which form a \Index{collection}, and two link fields, which form a \Index{sequence}.
     429\begin{center}
     430%\input{DSLNodes}
     431\end{center}
     432@uStack@ and @uQueue@ are collections and @uSequence@ is a sequence.
     433To get the appropriate link fields associated with a user node, it must be a public descendant of @uColable@\index{uColable@@uColable@} or @uSeqable@\index{uSeqable@@uSeqable@}, respectively, e.g.:
     434%[
     435class stacknode : public uColable { ... }
     436class queuenode : public uColable { ... }
     437class seqnode : public uSeqable { ... }
     438%]
     439A node inheriting from @uSeqable@ can appear in a sequence/collection but a node inherting from @uColable@ can only appear in a collection.
     440Along with providing the appropriate link fields, the types @uColable@ and @uSeqable@ also provide one member routine:
     441%[
     442bool listed() const;
     443%]
     444which returns @true@ if the node is an element of any collection or sequence and @false@ otherwise.
     445
     446Finally, no header files are necessary to access the uC DSL.
     447
     448Some uC DSL restrictions are:
     449\begin{itemize}
     450\item
     451None of the member routines are virtual in any of the data structures for efficiency reasons.
     452Therefore, pointers to data structures must be used with care or incorrect member routines may be invoked.
     453\end{itemize}
     454\end{comment}
     455
     456
     457\subsection{Design Issues}
     458\label{toc:lst:issue}
     459
     460This section introduces the design space for linked lists that target \emph{system programmers}.
     461Within this restricted target, all design-issue discussions assume the following invariants.
     462Alternatives to the assumptions are discussed under Future Work (Section~\ref{toc:lst:futwork}).
     463\begin{itemize}
     464    \item A doubly-linked list is being designed.
     465          Generally, the discussed issues apply similarly for singly-linked lists.
     466          Circular \vs ordered linking is discussed under List identity (Section~\ref{toc:lst:issue:ident}).
     467    \item Link fields are system-managed.
     468          The user works with the system-provided API to query and modify list membership.
     469          The system has freedom over how to represent these links.
     470        \item The user data must provide storage for the list link-fields.
     471          Hence, a list node is \emph{statically} defined as data and links \vs a node that is \emph{dynamically} constructed from data and links \see{\VRef{toc:lst:issue:attach}}.
     472\end{itemize}
     473
     474
     475\subsection{Preexisting Linked-List Libraries}
     476
     477Two preexisting linked-list libraries are used throughout, to show examples of the concepts being defined,
     478and further libraries are introduced as needed.
     479\begin{enumerate}
     480    \item Linux Queue library\cite{lst:linuxq} (LQ) of @<sys/queue.h>@.
     481    \item \CC Standard Template Library's (STL)\footnote{The term STL is contentious as some people prefer the term standard library.} @std::list@\cite{lst:stl}
     482\end{enumerate}
     483A general comparison of libraries' abilities is given under Related Work (Section~\ref{toc:lst:relwork}).
     484
     485For the discussion, assume the fictional type @req@ (request) is the user's payload in examples.
     486As well, the list library is helping the user manage (organize) requests, \eg a request can be work on the level of handling a network arrival event or scheduling a thread.
     487
     488
     489\subsection{Link attachment: Intrusive vs.\ Wrapped}
     490\label{toc:lst:issue:attach}
     491
     492Link attachment deals with the question:
     493Where are the libraries' inter-element link fields stored, in relation to the user's payload data fields?
     494Figure~\ref{fig:lst-issues-attach} shows three basic styles.
     495The \newterm{intrusive} style places the link fields inside the payload structure.
     496The two \newterm{wrapped} styles place the payload inside a generic library-provided structure that then defines the link fields.
     497Library LQ is intrusive; STL is wrapped.
     498The wrapped style further distinguishes between wrapping a reference and wrapping a value, \eg @list<req *>@ or @list<req>@.
     499(For this discussion, @list<req &>@ is similar to @list<req *>@.)
     500This difference is one of user style, not framework capability.
     501
     502\begin{comment}
     503\begin{figure}
     504    \begin{tabularx}{\textwidth}{Y|Y|Y}
     505                \lstinput[language=C]{20-39}{lst-issues-intrusive.run.c}
     506        &\lstinputlisting[language=C++]{20-39}{lst-issues-wrapped-byref.run.cpp}
     507        &\lstinputlisting[language=C++]{20-39}{lst-issues-wrapped-emplaced.run.cpp}
     508      \\ & &
     509      \\
     510        \includegraphics[page=1]{lst-issues-attach.pdf}
     511        &
     512        \includegraphics[page=2]{lst-issues-attach.pdf}
     513        &
     514        \includegraphics[page=3]{lst-issues-attach.pdf}
     515      \\ & &
     516      \\
     517        (a) & (b) & (c)
     518    \end{tabularx}
     519\caption{
     520        Three styles of link attachment: (a)~intrusive, (b)~wrapped reference, and (c)~wrapped value.
     521        The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
     522        head objects are discussed in Section~\ref{toc:lst:issue:ident}.
     523        In (a), the field \lstinline{req.x} names a list direction;
     524        these are discussed in Section~\ref{toc:lst:issue:simultaneity}.
     525        In (b) and (c), the type \lstinline{node} represents a system-internal type,
     526        which is \lstinline{std::_List_node} in the GNU implementation.
     527        (TODO: cite? found in  /usr/include/c++/7/bits/stl\_list.h )
     528    }
     529     \label{fig:lst-issues-attach}
     530\end{figure}
     531\end{comment}
     532
     533\begin{figure}
     534\centering
     535\newsavebox{\myboxA}                                    % used with subfigure
     536\newsavebox{\myboxB}
     537\newsavebox{\myboxC}
     538
     539\begin{lrbox}{\myboxA}
     540\begin{tabular}{@{}l@{}}
     541\lstinput[language=C]{20-35}{lst-issues-intrusive.run.c} \\
     542\includegraphics[page=1]{lst-issues-attach.pdf}
     543\end{tabular}
     544\end{lrbox}
     545
     546\begin{lrbox}{\myboxB}
     547\begin{tabular}{@{}l@{}}
     548\lstinput[language=C++]{20-35}{lst-issues-wrapped-byref.run.cpp} \\
     549\includegraphics[page=2]{lst-issues-attach.pdf}
     550\end{tabular}
     551\end{lrbox}
     552
     553\begin{lrbox}{\myboxC}
     554\begin{tabular}{@{}l@{}}
     555\lstinput[language=C++]{20-35}{lst-issues-wrapped-emplaced.run.cpp} \\
     556\includegraphics[page=3]{lst-issues-attach.pdf}
     557\end{tabular}
     558\end{lrbox}
     559
     560\subfloat[Intrusive]{\label{f:Intrusive}\usebox\myboxA}
     561\hspace{6pt}
     562\vrule
     563\hspace{6pt}
     564\subfloat[Wrapped reference]{\label{f:WrappedRef}\usebox\myboxB}
     565\hspace{6pt}
     566\vrule
     567\hspace{6pt}
     568\subfloat[Wrapped value]{\label{f:WrappedValue}\usebox\myboxC}
     569
     570\caption{
     571        Three styles of link attachment:
     572                % \protect\subref*{f:Intrusive}~intrusive, \protect\subref*{f:WrappedRef}~wrapped reference, and \protect\subref*{f:WrappedValue}~wrapped value.
     573        The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
     574        head objects are discussed in Section~\ref{toc:lst:issue:ident}.
     575        In \protect\subref*{f:Intrusive}, the field \lstinline{req.d} names a list direction;
     576        these are discussed in Section~\ref{toc:lst:issue:simultaneity}.
     577        In \protect\subref*{f:WrappedRef} and \protect\subref*{f:WrappedValue}, the type \lstinline{node} represents a
     578                library-internal type, which is \lstinline{std::_List_node} in the GNU implementation
     579        \see{\lstinline{/usr/include/c++/X/bits/stl_list.h}, where \lstinline{X} is the \lstinline{g++} version number}.
     580    }
     581    \label{fig:lst-issues-attach}
     582\end{figure}
     583
     584Each diagrammed example is using the fewest dynamic allocations for its respective style:
     585in \subref*{f:Intrusive}, here are no dynamic allocations, in \subref*{f:WrappedRef} only the linked fields are dynamically allocated, and in \subref*{f:WrappedValue} the copied data and linked fields are dynamically allocated.
     586The advantage of intrusive attachment is the control in memory layout and storage placement.
     587Both wrapped attachment styles have independent storage layout and imply library-induced heap allocations, with lifetime that matches the item's membership in the list.
     588In all three cases, a @req@ object can enter and leave a list many times.
     589However, in \subref*{f:Intrusive} a @req@ can only be on one list at a time, unless there are separate link-fields for each simultaneous list.
     590In \subref*{f:WrappedRef}, a @req@ can appear multiple times on the same or different lists simultaneously, but since @req@ is shared via the pointer, care must be taken if updating data also occurs simultaneously, \eg concurrency.
     591In \subref*{f:WrappedValue}, the @req@ is copied, which increases storage usage, but allows independent simultaneous changes;
     592however, knowing which of the @req@ object is the ``true'' object becomes complex.
     593\see*{\VRef{toc:lst:issue:simultaneity} for further discussion.}
     594
     595The implementation of @LIST_ENTRY@ uses a trick to find the links and the node containing the links.
     596The macro @LIST_INSERT_HEAD(&reqs, &r2, d);@ takes the list header, a pointer to the node, and the offset of the link fields in the node.
     597One of the fields generated by @LIST_ENTRY@ is a pointer to the node, which is set to the node address, \eg @r2@.
     598Hence, the offset to the link fields provides an access to the entire node, \ie the node points at itself.
     599For list traversal, @LIST_FOREACH(cur, &reqs_pri, by_pri)@, there is the node cursor, the list, and the offset of the link fields within the node.
     600The traversal actually moves from link fields to link fields within a node and sets the node cursor from the pointer within the link fields back to the node.
     601
     602A further aspect of layout control is allowing the user to explicitly specify link fields controlling attributes and placement within the @req@ object.
     603LQ allows this ability through the @LIST_ENTRY@ macro\footnote{It is possible to have multiple named linked fields allowing a node to appear on multiple lists simultaneously.};
     604supplying the link fields by inheritance makes them implicit and relies on compiler placement, such as the start or end of @req@.
     605An example of an explicit attribute is cache alignment of the link fields in conjunction with other @req@ fields, improving locality and/or avoiding false sharing.
     606Wrapped reference has no control over the link fields, but the seperate data allows some control;
     607wrapped value has no control over data or links.
     608
     609Another 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.
     610In LQ, \subref*{f:Intrusive}, a @req@ pointer is the right argument type for operations @LIST_NEXT@ or @LIST_REMOVE@;
     611there is no distinguishing a @req@ from ``a @req@ in a list.''
     612The same is not true of STL, \subref*{f:WrappedRef} or \subref*{f:WrappedValue}.
     613There, the analogous operations work on a parameter of type @list<T>::iterator@;
     614they are @iterator::operator++()@, @iterator::operator*()@, and @list::erase(iterator)@.
     615There is no mapping from @req &@ to @list<req>::iterator@, except for linear search.
     616
     617The advantage of wrapped attachment is the abstraction of a data item from its list membership(s).
     618In the wrapped style, the @req@ type can come from a library that serves many independent uses,
     619which generally have no need for listing.
     620Then, a novel use can put @req@ in list, without requiring any upstream change in the @req@ library.
     621In intrusive attachment, the ability to be listed must be planned during the definition of @req@.
     622
     623Finally, for wrapper reference a single node can appear at multiple places in the same list or different list, which might be useful in certain read-only cases.
     624For intrusive and wrapper value, a node must be duplicated to appear at multiple locations, presenting additional cost.
     625This scenario becomes difficult to imagine when the nodes are written because three link styles have issues.
     626
     627\begin{figure}
     628    \lstinput[language=C++]{100-117}{lst-issues-attach-reduction.hpp}
     629    \lstinput[language=C++]{150-150}{lst-issues-attach-reduction.hpp}
     630    \caption{
     631        Reduction of wrapped attachment to intrusive attachment.
     632        Illustrated by pseudocode implementation of an STL-compatible API fragment
     633        using LQ as the underlying implementation.
     634        The gap that makes it pseudocode is that
     635        the LQ C macros do not expand to valid C++ when instantiated with template parameters---there is no \lstinline{struct El}.
     636        When using a custom-patched version of LQ to work around this issue,
     637        the programs of Figure~\ref{f:WrappedRef} and \protect\subref*{f:WrappedValue} work with this shim in place of real STL.
     638        Their executions lead to the same memory layouts.
     639    }
     640    \label{fig:lst-issues-attach-reduction}
     641\end{figure}
     642
     643Wrapped attachment has a straightforward reduction to intrusive attachment, illustrated in Figure~\ref{fig:lst-issues-attach-reduction}.
     644This shim layer performs the implicit dynamic allocations that pure intrusion avoids.
     645But there is no reduction going the other way.
     646No shimming can cancel the allocations to which wrapped membership commits.
     647
     648So intrusion is a lower-level listing primitive.
     649And so, the system design choice is not between forcing users to use intrusion or wrapping.
     650The choice is whether or not to provide access to an allocation-free layer of functionality.
     651A wrapped-primitive library like STL forces users to incur the costs of wrapping, whether or not they access its benefits.
     652An intrusive-primitive library like LQ lets users choose when to make this tradeoff.
     653
     654
     655\subsection{Simultaneity: Single vs.\ Multi-Static vs.\ Dynamic}
     656\label{toc:lst:issue:simultaneity}
     657
     658\begin{figure}
     659    \parbox[t]{3.5in} {
     660        \lstinput[language=C++]{20-60}{lst-issues-multi-static.run.c}
     661    }\parbox[t]{20in} {
     662        ~\\
     663        \includegraphics[page=1]{lst-issues-direct.pdf} \\
     664        ~\\
     665        \hspace*{1.5in}\includegraphics[page=2]{lst-issues-direct.pdf}
     666    }
     667    \caption{
     668        Example of simultaneity using LQ lists. 
     669        The zoomed-out diagram (right/top) shows the complete multi-linked data structure.
     670        This structure can navigate all requests in priority order, and navigate among requests with a common request value.
     671        The zoomed-in diagram (right/bottom) shows how the link fields connect the nodes on different lists.
     672    }
     673    \label{fig:lst-issues-multi-static}
     674\end{figure}
     675
     676\newterm{Simultaneity} deals with the question:
     677In how many different lists can a node be stored, at the same time?
     678Figure~\ref{fig:lst-issues-multi-static} shows an example that can traverse all requests in priority order (field @pri@) or navigate among requests with the same request value (field @rqr@).
     679Each of ``by priority'' and ``by common request value'' is a separate list.
     680For example, there is a single priority-list linked in order [1, 2, 2, 3, 3, 4], where nodes may have the same priority, and there are three common request-value lists combining requests with the same values: [42, 42], [17, 17, 17], and [99], giving four head nodes one for each list.
     681The example shows a list can encompass all the nodes (by-priority) or only a subset of the nodes (three request-value lists).
     682
     683As stated, the limitation of intrusive attachment is knowing apriori how many groups of links are needed for the maximum number of simultaneous lists.
     684Thus, the intrusive LQ example supports multiple, but statically many, link lists.
     685Note, it is possible to reuse links for different purposes, \eg if a list in linked one at one time and another way at another time, and these times do not overlap, the two different linkings can use the same link fields.
     686This feature is used in the \CFA runtime where a thread node may be on a blocked or running list, both never on both simultaneously.
     687
     688Now consider the STL in the wrapped-reference arrangement of Figure~\ref{f:WrappedRef}.
     689Here it is possible to construct the same simultaneity by creating multiple STL lists, each pointing at the appropriate nodes.
     690Each group of intrusive links become the links for each separate STL list.
     691The upside is the unlimited number of a lists a node can be associated with simultaneously, any number of STL lists can be created dynamically.
     692The downside is the dynamic allocation of the link nodes and manging multiple lists.
     693Note, it might be possible to wrap the multiple lists in another type to hide this implementation issue.
     694
     695Now consider the STL in the wrapped-value arrangement of Figure~\ref{f:WrappedValue}.
     696Again, it is possible to construct the same simultaneity by creating multiple STL lists, each copying the appropriate nodes, where the intrusive links become the links for each separate STL list.
     697The upside is the same as for wrapped-reference arrangement with an unlimited number of a list bindings.
     698The downside is the dynamic allocation and significant storage usage due to copying.
     699As well, it is unclear how node updates work in this scenario, without some notation of ultimately merging node information.
     700
     701% 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;`
     702
     703% When allowing multiple static directions, frameworks differ in their ergonomics for
     704% the typical case: when the user needs only one direction, vs.\ the atypical case, when the user needs several.
     705% LQ's ergonomics are well-suited to the uncommon case of multiple list directions.
     706% Its intrusion declaration and insertion operation both use a mandatory explicit parameter naming the direction.
     707% This decision works well in Figure~\ref{fig:lst-issues-multi-static}, where the names @by_pri@ and @by_rqr@ work well,
     708% but it clutters Figure~\ref{f:Intrusive}, where a contrived name must be invented and used.
     709% The example uses @x@; @reqs@ would be a more readily ignored choice. \PAB{wording?}
     710
     711\uCpp offers an intrusive list that makes the opposite ergonomic choice.  TODO: elaborate on inheritance for first direction and acrobatics for subsequent directions.
     712
     713STL may seem to have similar ergonomics to LQ, but in fact, the current ergonomic distinction is not applicable there,
     714where one static direction is enough to achieve multiple dynamic directions.
     715Note that all options in Figure~\ref{fig:lst-issues-attach} have a \emph{variable} named @refs@
     716just as both Figure~\ref{fig:lst-issues-multi-static} and Figure~(TODO~new) have \emph{variables} with names including @pri@ vs @rqr@.
     717But only the intrusive model has this naming showing up within the definition of a structure.
     718This lack of named parts of a structure lets Figure~\ref{fig:lst-issues-attach} \subref*{f:WrappedRef} and \subref*{f:WrappedValue}, just like \uCpp,
     719insert into a list without mentioning a part's name, while only version \subref*{f:Intrusive} has to mention @x@ at this step.
     720LQ demands this same extraneous part-naming when removing, iterating, and even asking for a neighbour.
     721At issue in this distinction is whether an API that offers multiple static directions (and so requires these to be named differently)
     722allows the sole direction (when several are not wanted) to be \emph{implicit}.
     723\uCpp allows it, LQ does not, and STL does not have this question as applicable.
     724
     725
     726\subsection{User integration: Preprocessed vs.\ Type-System Mediated}
     727
     728% example of poor error message due to LQ's preprocessed integration
     729% programs/lst-issues-multi-static.run.c:46:1: error: expected identifier or '(' before 'do'
     730%    46 | LIST_INSERT_HEAD(&reqs_rtr_42, &r42b, by_rqr);
     731%       | ^~~~~~~~~~~~~~~~
     732%
     733% ... not a wonderful example; it was a missing semicolon on the preceding line; but at least real
     734
     735
     736\subsection{List identity: Headed vs.\ Ad-hoc}
     737\label{toc:lst:issue:ident}
     738
     739All examples so far have used distinct user-facing types:
     740an item found in a list (type @req@, of variables like @r1@), and
     741a list (type @reql@ or @list<req>@, of variables like @reqs@ or @reqs_rqr_42@).
     742\see{Figure~\ref{fig:lst-issues-attach} and Figure~\ref{fig:lst-issues-multi-static}}
     743The latter type is a head, and these examples are of headed lists.
     744
     745A bespoke ``pointer to next @req@'' implementation often omits the latter type.
     746Such a list model is ad-hoc.
     747
     748In headed thinking, there are length-zero lists (heads with no elements), and an element can be listed or not listed.
     749In ad-hoc thinking, there are no length-zero lists and every element belongs to a list of length at least one.
     750\PAB{Create a figure for this.}
     751
     752By omitting the head, elements can enter into an adjacency relationship,
     753without requiring that someone allocate room for the head of the possibly-resulting list,
     754or being able to find a correct existing head.
     755
     756A head defines one or more element roles, among elements that share a transitive adjacency.
     757``First'' and ``last'' are element roles.
     758One moment's ``first'' need not be the next moment's.
     759
     760There is a cost to maintaining these roles.
     761A runtime component of this cost is evident in LQ's offering the choice of type generators @LIST@ vs.~@TAILQ@.
     762Its @LIST@ maintains a ``first,'' but not a ``last;'' its @TAILQ@ maintains both roles.
     763(Both types are doubly linked and an analogous choice is available for singly linked.)
     764
     765TODO: finish making this point
     766
     767See WIP in lst-issues-adhoc-*.ignore.*.
     768
     769The code-complexity component of the cost ...
     770
     771Ability 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.
     772
     773\subsection{End treatment: Uniform }
    399774
    400775
    … …  
    406781An integer character constant is a sequence of one or more multibyte characters enclosed in single-quotes, as in @'x'@.
    407782A wide character constant is the same, except prefixed by the letter @L@, @u@, or @U@.
    408 With a few exceptions detailed later, the elements of the sequence are any members of the source character set;
     783Except for escape sequences, the elements of the sequence are any members of the source character set;
    409784they are mapped in an implementation-defined manner to members of the execution character set.
    410785
    … …  
    416791For wide string literals prefixed by the letter @L@, the array elements have type @wchar_t@ and are initialized with the sequence of wide characters corresponding to the multibyte character sequence, as defined by the @mbstowcs@ function with an implementation-defined current locale.
    417792For wide string literals prefixed by the letter @u@ or @U@, the array elements have type @char16_t@ or @char32_t@, respectively, and are initialized with the sequence of wide characters corresponding to the multibyte character sequence, as defined by successive calls to the @mbrtoc16@, or @mbrtoc32@ function as appropriate for its type, with an implementation-defined current locale.
    418 The value of a string literal containing a multibyte character or escape sequence not represented in the executioncharacter set is implementation-defined.
     793The value of a string literal containing a multibyte character or escape sequence not represented in the execution character set is implementation-defined.
    419794
    420795

  • doc/theses/mike_brooks_MMath/list.tex

    rc333ed2 r0b6c1c9  
    1212TODO: more summary
    1313
    14 
    15 \section{Design Issues}
    16 \label{toc:lst:issue}
    17 
    18 This section introduces the design space for linked lists that target system programmers.
    19 
    20 All design-issue discussions assume the following invariants.
    21 \PAB{They are stated here to clarify that none of the discussed design issues refers to one of these.}
    22 Alternatives to the assumptions are discussed under Future Work (Section~\ref{toc:lst:futwork}).
    23 \begin{itemize}
    24     \item A doubly-linked list is being designed.
    25           Generally, the discussed issues apply similarly for singly-linked lists.
    26           Circular vs ordered linking is discussed under List identity (Section~\ref{toc:lst:issue:ident}).
    27     \item Link fields are system-managed.
    28           The user works with the system-provided API to query and modify list membership.
    29           The system has freedom over how to represent these links.
    30           The library is not providing applied wrapper operations that consume a user's hand-implemented list primitives.
    31     \item \PAB{These issues are compared at a requirement/functional level.}
    32 \end{itemize}
    33 
    34 Two preexisting linked-list libraries are used throughout, to show examples of the concepts being defined,
    35 and further libraries are introduced as needed.
    36 \begin{description}
    37     \item[LQ] Linux Queue library\cite{lst:linuxq} of @<sys/queue.h>@.
    38     \item[STL] C++ Standard Template Library's @std::list@\cite{lst:stl}
    39 \end{description}
    40 A general comparison of libraries' abilities is given under Related Work (Section~\ref{toc:lst:relwork}).
    41 
    42 The fictional type @req@ (request) is the user's payload in examples.
    43 The list library is helping the user track requests.
    44 A request represents work that the user must do but has not done yet.
    45 This work is on the level of handling a network arrival event or scheduling a thread.
    46 
    47 
    48 
    49 \subsection{Link attachment: Intrusive vs.\ Wrapped}
    50 \label{toc:lst:issue:attach}
    51 
    52 Link attachment deals with the question:
    53 Where are the system's inter-element link fields stored, in relation to the user's payload data fields?
    54 An intrusive list places the link fields inside the payload structure.
    55 A wrapped list places the payload inside a generic system-provided structure that also defines the link fields.
    56 LQ is intrusive; STL is wrapped.
    57 
    58 The wrapped style admits the further distinction between wrapping a reference and wrapping a value.
    59 This distinction is pervasive in all STL collections; @list<req *>@ wraps a reference; @list<req>@ wraps a value.
    60 (For this discussion, @list<req &>@ is similar to @list<req *>@.)
    61 This difference is one of user style, not framework capability.
    62 Figure~\ref{fig:lst-issues-attach} compares the three styles.
    63 
    64 \begin{comment}
    65 \begin{figure}
    66     \begin{tabularx}{\textwidth}{Y|Y|Y}
    67                 \lstinput[language=C]{20-39}{lst-issues-intrusive.run.c}
    68         &\lstinputlisting[language=C++]{20-39}{lst-issues-wrapped-byref.run.cpp}
    69         &\lstinputlisting[language=C++]{20-39}{lst-issues-wrapped-emplaced.run.cpp}
    70       \\ & &
    71       \\
    72         \includegraphics[page=1]{lst-issues-attach.pdf}
    73         &
    74         \includegraphics[page=2]{lst-issues-attach.pdf}
    75         &
    76         \includegraphics[page=3]{lst-issues-attach.pdf}
    77       \\ & &
    78       \\
    79         (a) & (b) & (c)
    80     \end{tabularx}
    81 \caption{
    82         Three styles of link attachment: (a)~intrusive, (b)~wrapped reference, and (c)~wrapped value.
    83         The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
    84         head objects are discussed in Section~\ref{toc:lst:issue:ident}.
    85         In (a), the field \lstinline{req.x} names a list direction;
    86         these are discussed in Section~\ref{toc:lst:issue:derection}.
    87         In (b) and (c), the type \lstinline{node} represents a system-internal type,
    88         which is \lstinline{std::_List_node} in the GNU implementation.
    89         (TODO: cite? found in  /usr/include/c++/7/bits/stl\_list.h )
    90     }
    91      \label{fig:lst-issues-attach}
    92 \end{figure}
    93 \end{comment}
    94 
    95 \begin{figure}
    96 \centering
    97 \newsavebox{\myboxA}                                    % used with subfigure
    98 \newsavebox{\myboxB}
    99 \newsavebox{\myboxC}
    100 
    101 \begin{lrbox}{\myboxA}
    102 \begin{tabular}{@{}l@{}}
    103 \lstinput[language=C]{20-39}{lst-issues-intrusive.run.c} \\
    104 \ \\
    105 \includegraphics[page=1]{lst-issues-attach.pdf}
    106 \end{tabular}
    107 \end{lrbox}
    108 
    109 \begin{lrbox}{\myboxB}
    110 \begin{tabular}{@{}l@{}}
    111 \lstinput[language=C++]{20-39}{lst-issues-wrapped-byref.run.cpp} \\
    112 \ \\
    113 \includegraphics[page=2]{lst-issues-attach.pdf}
    114 \end{tabular}
    115 \end{lrbox}
    116 
    117 \begin{lrbox}{\myboxC}
    118 \begin{tabular}{@{}l@{}}
    119 \lstinput[language=C++]{20-39}{lst-issues-wrapped-emplaced.run.cpp} \\
    120 \ \\
    121 \includegraphics[page=3]{lst-issues-attach.pdf}
    122 \end{tabular}
    123 \end{lrbox}
    124 
    125 \subfloat[Intrusive]{\label{f:Intrusive}\usebox\myboxA}
    126 \hspace{10pt}
    127 \vrule
    128 \hspace{10pt}
    129 \subfloat[Wrapped reference]{\label{f:WrappedRef}\usebox\myboxB}
    130 \hspace{10pt}
    131 \vrule
    132 \hspace{10pt}
    133 \subfloat[Wrapped value]{\label{f:WrappedValue}\usebox\myboxC}
    134 
    135 \caption{
    136         Three styles of link attachment: \protect\subref*{f:Intrusive}~intrusive, \protect\subref*{f:WrappedRef}~wrapped
    137         reference, and \protect\subref*{f:WrappedValue}~wrapped value.
    138         The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
    139         head objects are discussed in Section~\ref{toc:lst:issue:ident}.
    140         In \protect\subref*{f:Intrusive}, the field \lstinline{req.x} names a list direction;
    141         these are discussed in Section~\ref{toc:lst:issue:derection}.
    142         In \protect\subref*{f:WrappedRef} and \protect\subref*{f:WrappedValue}, the type \lstinline{node} represents a
    143         system-internal type, which is \lstinline{std::_List_node} in the GNU implementation.
    144         (TODO: cite? found in  /usr/include/c++/7/bits/stl\_list.h )
    145     }
    146     \label{fig:lst-issues-attach}
    147 \end{figure}
    148 
    149 The advantage of intrusive attachment is the control that it gives the user over memory layout.
    150 Each diagrammed example is using the fewest dynamic allocations that its respective style allows.
    151 Both wrapped attachment styles imply system-induced heap allocations.
    152 Such an allocation has a lifetime that matches the item's membership in the list.
    153 In \subref*{f:Intrusive} and \subref*{f:WrappedRef}, one @req@ object can enter and leave a list many times.
    154 In \subref*{f:WrappedRef}, it implies a dynamic allocation/deallocation for each enter/leave; in \subref*{f:Intrusive}, it does not.
    155 
    156 A further aspect of layout control is allowing the user to specify the location of the link fields within the @req@ object.
    157 LQ allows this ability; a different mechanism of intrusion, such as inheriting from a @linkable@ base type, may not.
    158 Having this control means the user can allocate the link fields to cache lines along with the other @req@ fields.
    159 Doing this allocation sensibly can help improve locality or avoid false sharing.
    160 With an attachment mechanism that does not offer this control,
    161 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@.
    162 All wrapping realizations have this limitation in their wrapped-value configurations.
    163 
    164 Another subtle advantage of intrusive arrangement is that
    165 a reference to a user-level item (@req@) is sufficient to navigate or manage the item's membership.
    166 In LQ, \subref*{f:Intrusive}, a @req@ pointer is the right argument type for operations @LIST_NEXT@ or @LIST_REMOVE@;
    167 there is no distinguishing a @req@ from ``a @req@ in a list.''
    168 The same is not true of STL, \subref*{f:WrappedRef} or \subref*{f:WrappedValue}.
    169 There, the analogous operations work on a parameter of type @list<T>::iterator@;
    170 they are @iterator::operator++()@, @iterator::operator*()@, and @list::erase(iterator)@.
    171 There is no mapping from @req &@ to @list<req>::iterator@, except for linear search.
    172 
    173 The advantage of wrapped attachment is the abstraction of a data item from its list membership(s).
    174 In the wrapped style, the @req@ type can come from a library that serves many independent uses,
    175 which generally have no need for listing.
    176 Then, a novel use can still put @req@ in a (further) list, without requiring any upstream change in the @req@ library.
    177 In intrusive attachment, the ability to be listed must be planned during the definition of @req@.
    178 Similarly, style \subref*{f:WrappedRef} allows for one @req@ to occur at several positions in one list.
    179 Styles \subref*{f:Intrusive} and \subref*{f:WrappedValue} do not support this ability.
    180 \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.}
    181 
    182 \begin{figure}
    183     \lstinput[language=C++]{100-117}{lst-issues-attach-reduction.hpp}
    184     \lstinput[language=C++]{150-150}{lst-issues-attach-reduction.hpp}
    185     \caption{
    186         Reduction of wrapped attachment to intrusive attachment.
    187         Illustrated by pseudocode implementation of an STL-compatible API fragment
    188         using LQ as the underlying implementation.
    189         The gap that makes it pseudocode is that
    190         the LQ C macros do not expand to valid C++ when instantiated with template parameters---there is no \lstinline{struct El}.
    191         When using a custom-patched version of LQ to work around this issue,
    192         the programs of Figure~\ref{f:WrappedRef} and \protect\subref*{f:WrappedValue} work with this shim in place of real STL.
    193         Their executions lead to the same memory layouts.
    194     }
    195     \label{fig:lst-issues-attach-reduction}
    196 \end{figure}
    197 
    198 Wrapped attachment has a straightforward reduction to intrusive attachment, illustrated in Figure~\ref{fig:lst-issues-attach-reduction}.
    199 This shim layer performs the implicit dynamic allocations that pure intrusion avoids.
    200 But there is no reduction going the other way.
    201 No shimming can cancel the allocations to which wrapped membership commits.
    202 
    203 So intrusion is a lower-level listing primitive.
    204 And so, the system design choice is not between forcing users to use intrusion or wrapping.
    205 The choice is whether or not to provide access to an allocation-free layer of functionality.
    206 A wrapped-primitive library like STL forces users to incur the costs of wrapping, whether or not they access its benefits.
    207 An intrusive-primitive library like LQ lets users choose when to make this tradeoff.
    208 
    209 
    210 \subsection{Directionality: Single vs.\ Multi-Static vs.\ Dynamic}
    211 \label{toc:lst:issue:derection}
    212 
    213 Axis?
    214 
    215 \PAB{I'm not sure about the term \newterm{Directionality}. Directionality to me, means going forward or backwards through a list.
    216 Would \newterm{dimensionality} work? Think of each list containing the node as a different dimension in which the node sits.}
    217 
    218 Directionality deals with the question:
    219 In how many different lists can an item be stored, at a given time?
    220 
    221 Consider STL in the wrapped-value arrangement of Figure~\ref{f:WrappedValue}.
    222 The STL API completely hides its @node@ type from a user; the user cannot configure this choice or impose a custom one.
    223 STL's @node@ type offers the sole set of links shown in the diagram.
    224 Therefore, every @req@ in existence is allocated either to belong to an occurrence of the diagrammed arrangement,
    225 or to be apart from all occurrences of it.
    226 In the first case, the @req@ belongs to exactly one list (of the style in question).
    227 STL with wrapped values supports a single link direction.
    228 
    229 \begin{figure}
    230     \parbox[t]{3.5in} {
    231         \lstinput[language=C++]{20-60}{lst-issues-multi-static.run.c}
    232     }\parbox[t]{20in} {
    233         ~\\
    234         \includegraphics[page=1]{lst-issues-direct.pdf} \\
    235         ~\\
    236         \hspace*{1.5in}\includegraphics[page=2]{lst-issues-direct.pdf}
    237     }
    238     \caption{
    239         Example of two link directions, with an LQ realization. 
    240         The zoomed-out diagram portion shows the whole example dataset, conceptually.
    241         A consumer of this structure can navigate all requests in priority order, and navigate among requests from a common requestor.
    242         The code is the LQ implementation.
    243         The zoomed-in diagram portion shows the field-level state that results from running the LQ code.
    244     }
    245     \label{fig:lst-issues-multi-static}
    246 \end{figure}
    247 
    248 
    249 The user may benefit from a further link direction.
    250 Suppose the user must both: navigate all requests in priority order, and navigate among requests from a common requestor.
    251 Figure~\ref{fig:lst-issues-multi-static} shows such a situation.
    252 Each of its ``by priority'' and ``by requestor'' is a link direction.
    253 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).
    254 
    255 The limitation of intrusive attachment presented in Section~\ref{toc:lst:issue:attach}
    256 has a straightforward extension to multiple directions.
    257 The set of directions by which an item is to be listed must be planned during the definition of the item.
    258 Thus, intrusive LQ supports multiple, but statically many, link directions.
    259 
    260 % 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;`
    261 
    262 The corresponding flexibility of wrapped attachment means
    263 the STL wrapped-reference arrangement supports an item being a member of arbitrarily many lists.
    264 This support also applies to the wrapped-value list because the @req@ is copied,
    265 but wrapped-reference lists provide further link directions.
    266 \PAB{Explain how}
    267 STL with wrapped references supports dynamic link directions.
    268 \PAB{Expand}
    269 
    270 When allowing multiple static directions, frameworks differ in their ergonomics for
    271 the typical case: when the user needs only one direction, vs.\ the atypical case, when the user needs several.
    272 LQ's ergonomics are well-suited to the uncommon case of multiple list directions.
    273 Its intrusion declaration and insertion operation both use a mandatory explicit parameter naming the direction.
    274 This decision works well in Figure~\ref{fig:lst-issues-multi-static}, where the names @by_pri@ and @by_rqr@ work well,
    275 but it clutters Figure~\ref{f:Intrusive}, where a contrived name must be invented and used.
    276 The example uses @x@; @reqs@ would be a more readily ignored choice. \PAB{wording?}
    277 
    278 \uCpp offers an intrusive list that makes the opposite choice.  TODO: elaborate on inheritance for first direction and acrobatics for subsequent directions.
    279 
    280 
    281 \subsection{User integration: Preprocessed vs.\ Type-System Mediated}
    282 
    283 % example of poor error message due to LQ's preprocessed integration
    284 % programs/lst-issues-multi-static.run.c:46:1: error: expected identifier or '(' before 'do'
    285 %    46 | LIST_INSERT_HEAD(&reqs_rtr_42, &r42b, by_rqr);
    286 %       | ^~~~~~~~~~~~~~~~
    287 %
    288 % ... not a wonderful example; it was a missing semicolon on the preceding line; but at least real
    289 
    290 
    291 \subsection{List identity: Headed vs.\ Ad-hoc}
    292 \label{toc:lst:issue:ident}
    293 
    294 All examples so far have used distinct user-facing types:
    295 an item found in a list (type @req@, of variables like @r1@), and
    296 a list (type @reql@ or @list<req>@, of variables like @reqs@ or @reqs_rqr_42@).
    297 \see{Figure~\ref{fig:lst-issues-attach} and Figure~\ref{fig:lst-issues-multi-static}}
    298 The latter type is a head, and these examples are of headed lists.
    299 
    300 A bespoke ``pointer to next @req@'' implementation often omits the latter type.
    301 Such a list model is ad-hoc.
    302 
    303 In headed thinking, there are length-zero lists (heads with no elements), and an element can be listed or not listed.
    304 In ad-hoc thinking, there are no length-zero lists and every element belongs to a list of length at least one.
    305 \PAB{Create a figure for this.}
    306 
    307 By omitting the head, elements can enter into an adjacency relationship,
    308 without requiring that someone allocate room for the head of the possibly-resulting list,
    309 or being able to find a correct existing head.
    310 
    311 A head defines one or more element roles, among elements that share a transitive adjacency.
    312 ``First'' and ``last'' are element roles.
    313 One moment's ``first'' need not be the next moment's.
    314 
    315 There is a cost to maintaining these roles.
    316 A runtime component of this cost is evident in LQ's offering the choice of type generators @LIST@ vs.~@TAILQ@.
    317 Its @LIST@ maintains a ``first,'' but not a ``last;'' its @TAILQ@ maintains both roles.
    318 (Both types are doubly linked and an analogous choice is available for singly linked.)
    319 
    320 TODO: finish making this point
    321 
    322 See WIP in lst-issues-adhoc-*.ignore.*.
    323 
    324 The code-complexity component of the cost ...
    325 
    326 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.
    327 
    328 \subsection{End treatment: Uniform }
    32914
    33015
    … …  
    424109Links in GDB.
    425110
    426 \section{Related Work}
    427 \label{toc:lst:relwork}

  • doc/theses/mike_brooks_MMath/programs/lst-issues-intrusive.run.c

    rc333ed2 r0b6c1c9  
    2222struct req {
    2323        int pri, rqr;
    24         LIST_ENTRY(req) x;
     24        LIST_ENTRY(req) d;
    2525};
    26 
    2726LIST_HEAD(reql, req);
    2827
    … …  
    3029LIST_INIT(&reqs);
    3130
    32 struct req
    33         r1 = {1, 42},
    34         r2 = {2, 42};
     31struct req r1 = {1, 42}, r2 = {2, 42};
    3532
    36 LIST_INSERT_HEAD(
    37         &reqs, &r2, x);
    38 LIST_INSERT_HEAD(
    39         &reqs, &r1, x);
     33LIST_INSERT_HEAD(&reqs, &r2, d);
     34LIST_INSERT_HEAD(&reqs, &r1, d);
    4035
    4136
    … …  
    5045
    5146struct req *cur;
    52 LIST_FOREACH(cur, &reqs, x)
     47LIST_FOREACH(cur, &reqs, d)
    5348        printf("{%d %d} ", cur->pri, cur->rqr);
    5449printf("\n");

  • doc/theses/mike_brooks_MMath/programs/lst-issues-multi-static.run.c

    rc333ed2 r0b6c1c9  
    2626LIST_HEAD(reql, req);
    2727
    28 struct reql reqs_pri_global;
     28struct reql reqs_pri;
    2929struct reql reqs_rqr_42;
    3030struct reql reqs_rqr_17;
    3131struct reql reqs_rqr_99;
    3232
    33 LIST_INIT(&reqs_pri_global);
     33LIST_INIT(&reqs_pri);
    3434LIST_INIT(&reqs_rqr_42);
    3535LIST_INIT(&reqs_rqr_17);
    … …  
    4444        r99a = {3, 99};
    4545
    46 LIST_INSERT_HEAD(&reqs_pri_global, &r17c, by_pri);
    47 LIST_INSERT_HEAD(&reqs_pri_global, &r99a, by_pri);
    48 LIST_INSERT_HEAD(&reqs_pri_global, &r17b, by_pri);
    49 LIST_INSERT_HEAD(&reqs_pri_global, &r42b, by_pri);
    50 LIST_INSERT_HEAD(&reqs_pri_global, &r17a, by_pri);
    51 LIST_INSERT_HEAD(&reqs_pri_global, &r42a, by_pri);
     46LIST_INSERT_HEAD(&reqs_pri, &r17c, by_pri);
     47LIST_INSERT_HEAD(&reqs_pri, &r99a, by_pri);
     48LIST_INSERT_HEAD(&reqs_pri, &r17b, by_pri);
     49LIST_INSERT_HEAD(&reqs_pri, &r42b, by_pri);
     50LIST_INSERT_HEAD(&reqs_pri, &r17a, by_pri);
     51LIST_INSERT_HEAD(&reqs_pri, &r42a, by_pri);
    5252
    5353LIST_INSERT_HEAD(&reqs_rqr_42, &r42b, by_rqr);
    … …  
    6767
    6868struct req *cur;
    69 LIST_FOREACH(cur, &reqs_pri_global, by_pri)
     69LIST_FOREACH(cur, &reqs_pri, by_pri)
    7070        printf("{%d %d} ", cur->pri, cur->rqr);
    7171printf("| ");

  • doc/theses/mike_brooks_MMath/programs/lst-issues-wrapped-byref.run.cpp

    rc333ed2 r0b6c1c9  
    2222struct req {
    2323        int pri, rqr;
     24
    2425};
    2526
    2627
     28list<req *> reqs;
    2729
    2830
    29 list<req*> reqs;
     31req r1 = {1, 42}, r2 = {2, 42};
    3032
    31 
    32 req
    33         r1 = {1, 42},
    34         r2 = {2, 42};
    35 
    36 reqs.push_front(
    37         &r2);
    38 reqs.push_front(
    39         &r1);
     33reqs.push_front(&r2);
     34reqs.push_front(&r1);
    4035
    4136

  • doc/theses/mike_brooks_MMath/programs/lst-issues-wrapped-emplaced.run.cpp

    rc333ed2 r0b6c1c9  
    2222struct req {
    2323        int pri, rqr;
     24
    2425};
    25 
    26 
    2726
    2827
    … …  
    3231
    3332
    34 
    35 
    36 reqs.emplace_front(
    37         2, 42);
    38 reqs.emplace_front(
    39         1, 42);
     33reqs.emplace_front(2, 42);
     34reqs.emplace_front(1, 42);
    4035
    4136

  • doc/theses/mike_brooks_MMath/uw-ethesis-frontpgs.tex

    rc333ed2 r0b6c1c9  
    11% T I T L E   P A G E
    22% -------------------
    3 % Last updated October 23, 2020, by Stephen Carr, IST-Client Services
     3% Last updated August 16, 2022, by IST-Client Services
    44% The title page is counted as page `i' but we need to suppress the
    55% page number. Also, we don't want any headers or footers.
    … …  
    4545\end{titlepage}
    4646
    47 % The rest of the front pages should contain no headers and be numbered using
    48 % Roman numerals starting with `ii'.
     47% The rest of the front pages should contain no headers and be numbered using Roman numerals starting with `ii'
    4948\pagestyle{plain}
    5049\setcounter{page}{2}
    5150
    52 \cleardoublepage % Ends the current page and causes all figures and tables
    53 % that have so far appeared in the input to be printed. In a two-sided
    54 % printing style, it also makes the next page a right-hand (odd-numbered)
    55 % page, producing a blank page if necessary.
     51\cleardoublepage % Ends the current page and causes all figures and tables that have so far appeared in the input to be printed.
     52% In a two-sided printing style, it also makes the next page a right-hand (odd-numbered) page, producing a blank page if necessary.
     53\phantomsection    % allows hyperref to link to the correct page
    5654
    5755\begin{comment}
    5856% E X A M I N I N G   C O M M I T T E E (Required for Ph.D. theses only)
    5957% Remove or comment out the lines below to remove this page
     58\addcontentsline{toc}{chapter}{Examining Committee}
    6059\begin{center}\textbf{Examining Committee Membership}\end{center}
    6160  \noindent
    62 The following served on the Examining Committee for this thesis.
    63 The decision of the Examining Committee is by majority vote.
     61The following served on the Examining Committee for this thesis. The decision of the Examining Committee is by majority vote.
    6462  \bigskip
    6563
    … …  
    110108% D E C L A R A T I O N   P A G E
    111109% -------------------------------
    112   % The following is a sample Delaration Page as provided by the GSO
     110  % The following is a sample Declaration Page as provided by the GSO
    113111  % December 13th, 2006.  It is designed for an electronic thesis.
     112 \addcontentsline{toc}{chapter}{Author's Declaration}
    114113 \begin{center}\textbf{Author's Declaration}\end{center}
    115114
    116115 \noindent
    117 I hereby declare that I am the sole author of this thesis. This is a true copy
    118 of the thesis, including any required final revisions, as accepted by my
    119 examiners.
     116I hereby declare that I am the sole author of this thesis. This is a true copy of the thesis, including any required final revisions, as accepted by my examiners.
    120117
    121118  \bigskip
    … …  
    125122
    126123\cleardoublepage
     124\phantomsection    % allows hyperref to link to the correct page
    127125
    128126% A B S T R A C T
    129127% ---------------
    130 
     128\addcontentsline{toc}{chapter}{Abstract}
    131129\begin{center}\textbf{Abstract}\end{center}
    132130
    … …  
    134132
    135133\cleardoublepage
     134\phantomsection    % allows hyperref to link to the correct page
    136135
    137136% A C K N O W L E D G E M E N T S
    138137% -------------------------------
    139 
     138\addcontentsline{toc}{chapter}{Acknowledgements}
    140139\begin{center}\textbf{Acknowledgements}\end{center}
    141140
    142141I would like to thank all the little people who made this thesis possible.
    143142\cleardoublepage
     143\phantomsection    % allows hyperref to link to the correct page
    144144
    145145\begin{comment}
    146146% D E D I C A T I O N
    147147% -------------------
    148 
     148\addcontentsline{toc}{chapter}{Dedication}
    149149\begin{center}\textbf{Dedication}\end{center}
    150150
    … …  
    174174\phantomsection         % allows hyperref to link to the correct page
    175175
     176\begin{comment}
     177% L I S T   O F   A B B R E V I A T I O N S
     178% ---------------------------
     179\renewcommand*{\abbreviationsname}{List of Abbreviations}
     180\printglossary[type=abbreviations]
     181\cleardoublepage
     182\phantomsection         % allows hyperref to link to the correct page
     183
     184% L I S T   O F   S Y M B O L S
     185% ---------------------------
     186\printglossary[type=symbols]
     187\cleardoublepage
     188\phantomsection         % allows hyperref to link to the correct page
     189\end{comment}
     190
    176191% Change page numbering back to Arabic numerals
    177192\pagenumbering{arabic}

  • libcfa/prelude/builtins.def

    rc333ed2 r0b6c1c9  
    867867/* Object size checking builtins.  */
    868868DEF_GCC_BUILTIN        (BUILT_IN_OBJECT_SIZE, "object_size", BT_FN_SIZE_CONST_PTR_INT, ATTR_PURE_NOTHROW_LEAF_LIST)
     869DEF_GCC_BUILTIN        (BUILT_IN_DYNAMIC_OBJECT_SIZE, "dynamic_object_size", BT_FN_SIZE_CONST_PTR_INT, ATTR_PURE_NOTHROW_LEAF_LIST)
    869870DEF_EXT_LIB_BUILTIN_CHKP (BUILT_IN_MEMCPY_CHK, "__memcpy_chk", BT_FN_PTR_PTR_CONST_PTR_SIZE_SIZE, ATTR_RET1_NOTHROW_NONNULL_LEAF)
    870871DEF_EXT_LIB_BUILTIN_CHKP (BUILT_IN_MEMMOVE_CHK, "__memmove_chk", BT_FN_PTR_PTR_CONST_PTR_SIZE_SIZE, ATTR_RET1_NOTHROW_NONNULL_LEAF)

  • libcfa/src/stdhdr/math.h

    rc333ed2 r0b6c1c9  
    1010// Created On       : Mon Jul  4 23:25:26 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Fri Feb  7 19:05:27 2020
    13 // Update Count     : 15
     12// Last Modified On : Tue May  7 16:41:02 2024
     13// Update Count     : 22
    1414//
    1515
    … …  
    1818#define exception ``exception                                                   // make keyword an identifier
    1919#define __CFA_MATH_H__
     20#endif
     21
     22#if __aarch64__ && __GNUC__ == 13                                               // TEMPORARY: gcc-13 problem on ARM in /usr/include/aarch64-linux-gnu/bits/math-vector.h
     23typedef double __Float32x4_t;
     24typedef double __Float64x2_t;
     25typedef float __SVFloat32_t;
     26typedef float __SVFloat64_t;
     27typedef int __SVBool_t;
    2028#endif
    2129

  • src/AST/BasicKind.hpp

    rc333ed2 r0b6c1c9  
    1919
    2020// GENERATED START, DO NOT EDIT
    21 // GENERATED BY BasicTypes-gen.cc
     21// GENERATED BY BasicTypes-gen.cpp
    2222enum BasicKind {
    2323        Bool,

  • src/AST/Print.cpp

    rc333ed2 r0b6c1c9  
    2323#include "Type.hpp"
    2424#include "TypeSubstitution.hpp"
    25 #include "CompilationState.h"
     25#include "CompilationState.hpp"
    2626#include "Common/Iterate.hpp"
    2727

  • src/AST/Type.cpp

    rc333ed2 r0b6c1c9  
    5050
    5151// GENERATED START, DO NOT EDIT
    52 // GENERATED BY BasicTypes-gen.cc
     52// GENERATED BY BasicTypes-gen.cpp
    5353const char * BasicType::typeNames[] = {
    5454        "_Bool",

  • src/AST/TypeEnvironment.cpp

    rc333ed2 r0b6c1c9  
    3434#include "ResolvExpr/Unify.h"      // for unifyInexact
    3535#include "Tuples/Tuples.h"         // for isTtype
    36 #include "CompilationState.h"
     36#include "CompilationState.hpp"
    3737
    3838using ResolvExpr::WidenMode;

  • src/CodeGen/FixNames.cc

    rc333ed2 r0b6c1c9  
    2525#include "FixMain.h"               // for FixMain
    2626#include "SymTab/Mangler.h"        // for Mangler
    27 #include "CompilationState.h"
     27#include "CompilationState.hpp"
    2828
    2929namespace CodeGen {

  • src/InitTweak/GenInit.cc

    rc333ed2 r0b6c1c9  
    2727#include "AST/Node.hpp"
    2828#include "AST/Stmt.hpp"
    29 #include "CompilationState.h"
     29#include "CompilationState.hpp"
    3030#include "CodeGen/OperatorTable.h"
    3131#include "Common/SemanticError.h"      // for SemanticError

  • src/MakeLibCfa.cpp

    rc333ed2 r0b6c1c9  
    1414//
    1515
    16 #include "MakeLibCfa.h"
     16#include "MakeLibCfa.hpp"
    1717
    1818#include "AST/Copy.hpp"

  • src/Makefile.am

    rc333ed2 r0b6c1c9  
    1919ACLOCAL_AMFLAGS  = -I automake
    2020
    21 SRC = main.cc \
    22         CompilationState.cc \
    23         CompilationState.h \
     21SRC = main.cpp \
     22        CompilationState.cpp \
     23        CompilationState.hpp \
    2424        MakeLibCfa.cpp \
    25         MakeLibCfa.h
     25        MakeLibCfa.hpp
    2626
    27 SRCDEMANGLE = CompilationState.cc
     27SRCDEMANGLE = CompilationState.cpp
    2828
    2929MAINTAINERCLEANFILES =
    … …  
    5555$(addprefix $(srcdir)/, ResolvExpr/ConversionCost.cc ResolvExpr/CommonType.cc SymTab/ManglerCommon.cc) : $(srcdir)/AST/BasicKind.hpp
    5656
    57 $(srcdir)/AST/BasicKind.hpp : BasicTypes-gen.cc
     57$(srcdir)/AST/BasicKind.hpp : BasicTypes-gen.cpp
    5858        ${AM_V_GEN}${CXXCOMPILE} $< -o BasicTypes-gen -Wall -Wextra -Werror=return-type
    5959        @./BasicTypes-gen

  • src/ResolvExpr/CandidateFinder.cpp

    rc333ed2 r0b6c1c9  
    2626#include "Candidate.hpp"
    2727#include "CastCost.hpp"           // for castCost
    28 #include "CompilationState.h"
     28#include "CompilationState.hpp"
    2929#include "ConversionCost.h"       // for conversionCast
    3030#include "Cost.h"

  • src/ResolvExpr/CommonType.cc

    rc333ed2 r0b6c1c9  
    3939
    4040        // GENERATED START, DO NOT EDIT
    41         // GENERATED BY BasicTypes-gen.cc
     41        // GENERATED BY BasicTypes-gen.cpp
    4242        #define BT ast::BasicKind::
    4343        static const ast::BasicKind commonTypes[BT NUMBER_OF_BASIC_TYPES][BT NUMBER_OF_BASIC_TYPES] = { // nearest common ancestor

  • src/ResolvExpr/ConversionCost.cc

    rc333ed2 r0b6c1c9  
    3535
    3636        // GENERATED START, DO NOT EDIT
    37         // GENERATED BY BasicTypes-gen.cc
     37        // GENERATED BY BasicTypes-gen.cpp
    3838        /* EXTENDED INTEGRAL RANK HIERARCHY (root to leaves)
    3939                                 _Bool
    … …  
    6060
    6161        // GENERATED START, DO NOT EDIT
    62         // GENERATED BY BasicTypes-gen.cc
     62        // GENERATED BY BasicTypes-gen.cpp
    6363        static const int costMatrix[ast::BasicKind::NUMBER_OF_BASIC_TYPES][ast::BasicKind::NUMBER_OF_BASIC_TYPES] = { // path length from root to node
    6464                /*               B    C   SC   UC   SI  SUI    I   UI   LI  LUI  LLI LLUI   IB  UIB  _FH  _FH   _F  _FC    F   FC  _FX _FXC   FD _FDC    D   DC F80X_FDXC  F80  _FB_FLDC   FB   LD  LDC _FBX_FLDXC */
    … …  
    108108
    109109        // GENERATED START, DO NOT EDIT
    110         // GENERATED BY BasicTypes-gen.cc
     110        // GENERATED BY BasicTypes-gen.cpp
    111111        static const int signMatrix[ast::BasicKind::NUMBER_OF_BASIC_TYPES][ast::BasicKind::NUMBER_OF_BASIC_TYPES] = { // number of sign changes in safe conversion
    112112                /*               B    C   SC   UC   SI  SUI    I   UI   LI  LUI  LLI LLUI   IB  UIB  _FH  _FH   _F  _FC    F   FC  _FX _FXC   FD _FDC    D   DC F80X_FDXC  F80  _FB_FLDC   FB   LD  LDC _FBX_FLDXC */

  • src/ResolvExpr/Cost.h

    rc333ed2 r0b6c1c9  
    1010// Created On       : Sun May 17 09:39:50 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Fri Jun 21 11:39:13 2019
    13 // Update Count     : 63
     12// Last Modified On : Fri May  3 17:15:41 2024
     13// Update Count     : 64
    1414//
    1515
    … …  
    1919#include <cassert>
    2020#include <climits>
     21#include <cstdint>
    2122
    2223namespace ResolvExpr {

  • src/ResolvExpr/Resolver.cc

    rc333ed2 r0b6c1c9  
    2828#include "typeops.h"                     // for extractResultType
    2929#include "Unify.h"                       // for unify
    30 #include "CompilationState.h"
     30#include "CompilationState.hpp"
    3131#include "AST/Decl.hpp"
    3232#include "AST/Init.hpp"

  • src/SymTab/ManglerCommon.cc

    rc333ed2 r0b6c1c9  
    2626
    2727// GENERATED START, DO NOT EDIT
    28 // GENERATED BY BasicTypes-gen.cc
     28// GENERATED BY BasicTypes-gen.cpp
    2929// NOTES ON MANGLING:
    3030// * Itanium spec says that Float80 encodes to "e" (like LongDouble), but the distinct lengths cause resolution problems.

  • src/Validate/Autogen.cpp

    rc333ed2 r0b6c1c9  
    4242#include "SymTab/GenImplicitCall.hpp"  // for genImplicitCall
    4343#include "SymTab/Mangler.h"        // for Mangler
    44 #include "CompilationState.h"
     44#include "CompilationState.hpp"
    4545
    4646namespace Validate {

  • tests/pybin/tools.py

    rc333ed2 r0b6c1c9  
    120120                return (False, "'file EXPECT' failed with code {} '{}'".format(code, err))
    121121
    122         match = re.search(".*: (.*)", out)
     122        match = re.search(r".*: (.*)", out)
    123123
    124124        if not match:
    … …  
    306306                sys.exit(1)
    307307
    308         re_jobs = re.search("--jobserver-(auth|fds)", out)
     308        re_jobs = re.search(r"--jobserver-(auth|fds)", out)
    309309        if not re_jobs:
    310310                print("ERROR: cannot find Makefile jobserver version", file=sys.stderr)

  • tests/test.py

    rc333ed2 r0b6c1c9  
    2323
    2424        def match_test(path):
    25                 match = re.search("^%s\/([\w\/\-_]*).expect\/([\w\-_\+]+)(\.[\w\-_]+)?\.txt$" % settings.SRCDIR, path)
     25                match = re.search(r'^%s\/([\w\/\-_]*).expect\/([\w\-_\+]+)(\.[\w\-_]+)?\.txt$' % settings.SRCDIR, path)
    2626                if match :
    2727                        test = Test()
    … …  
    359359                                sys.exit(1)
    360360
    361                         print(' '.join(re.findall('([^\s]+\.cfa)', out)), end=' ')
     361                        print(' '.join(re.findall(r'([^\s]+\.cfa)', out)), end=' ')
    362362
    363363                print('')
Note: See TracChangeset for help on using the changeset viewer.