docs.ltx

一些常用的数据结构库

    \description

    The \verb|lnode_pool_create| function dynamically allocates,
    by means of the standard library function \verb|malloc|
    a node pool object containing the number of nodes specified
    as the first argument. If not enough resources are available,
    a null pointer is returned, otherwise a pointer to the
    \verb|lnodepool_t| object is returned.

\subsubsection{The {\tt lnode_pool_destroy} function}

    \indexfunc{lnode_pool_destroy}
    \synopsis
    \begin{verbatim}
    void lnode_pool_destroy(lnodepool_t *);\end{verbatim}

    \description

    The \verb|lnode_pool_destroy| function deallocates a
    node pool that was allocated by \verb|lnode_pool_create|.
    The value of any pointer which referred to the
    node pool object becomes indeterminate.

\subsubsection{The {\tt lnode_pool_init} function}

    \indexfunc{lnode_pool_init}
    \synopsis
    \begin{verbatim}
    lnodepool_t *lnode_pool_init(lnodepool_t *,
            lnode_t *, listcount_t);\end{verbatim}

    \constraints

    The third argument, which specifies the node count, shall not be zero.

    \description

    The \verb|lnode_pool_init| function initializes a data object
    that has a suitable size and alignment to represent an
    \verb|lnodepool_t| type. A pointer to this object is passed
    as the first argument. The node pool thus created draws nodes
    from an array specified by the second argument, which shall be a pointer to
    an object that can behave like an array of \verb|lnode_t| objects.
    The third argument specifies the number of elements in this array.

    After this function, the object pointed at by the \verb|lnodepool_t *|
    argument is eligible for use with the node pool management functions
    of the List component. Nodes may be drawn from the pool and returned to it.

    As long as the pool continues to be used, the program should not directly
    manipulate the node array. In particular, if the program modifies any
    part of the array, then the behavior is undefined if the
    \verb|lnodepool_t| object or any nodes drawn from it are subsequently
    passed to a List function. The program shall not directly use the array
    elements as independent \verb|lnode_t| objects while the array is
    associated with the pool; in particular, it shall not pass these elements
    to Kazlib functions that operate on \verb|lnode_t|.
    
    The behavior is undefined if the same array is associated with more than
    one node pool object, or if two node pool objects are given overlapping
    arrays.

    The node array is managed in an manner that is specific to the
    implementation; the intent is that each element of the array represents a
    distinct node object, a pointer to which can be returned in response to an
    allocation request.

    The \verb|lnode_pool_init| function returns a copy of the first argument.

\subsubsection{The {\tt lnode_pool_isempty} function}

    \indexfunc{lnode_pool_isempty}
    \synopsis
    \begin{verbatim}
    int lnode_pool_isempty(lnodepool_t *);\end{verbatim}

    \description

    The \verb|lnode_pool_isempty| function tests the 
    specified \verb|lnodepool_t| object for ability to supply nodes.
    If the object has been
    subject to so many requests that it is no longer capable of
    of supplying additional list nodes, the value $1$ is returned.
    Otherwise the return value returned is zero.

\subsubsection{The {\tt lnode_pool_isfrom} function}

    \indexfunc{lnode_pool_isfrom}
    \synopsis
    \begin{verbatim}
    int lnode_pool_isfrom(lnodepool_t *, lnode_t *);\end{verbatim}

    \description

    The function \verb|lnode_pool_isfrom|, intended to serve as a software
    verification aid, determines whether a list node originates from
    a particular node pool. The return value is $1$ if this relationship is
    true, otherwise zero.

\subsubsection{The {\tt lnode_put} function}

    \indexfunc{lnode_put}
    \synopsis
    \begin{verbatim}
    void lnode_put(lnode_t *, void *);\end{verbatim}

    \description

    The function \verb|lnode_put| replaces the data element
    associated with the list node. 

\subsubsection{The {\tt lnode_return} function}

    \indexfunc{lnode_return}
    \synopsis
    \begin{verbatim}
    void lnode_return(lnodepool_t *, lnode_t *);\end{verbatim}

    \constraints

    The node pointed at by the second argument was derived by an allocation
    request from the pool pointed at by the first argument.\footnote{In
    other words, the {\tt lnode_pool_isfrom} function, were it called with
    the same two arguments, would return $1$ if this constraint is met.}

    Furthermore, the node must not be the occupant of a list.

    \description

    The \verb|lnode_return| function returns a node back to the node pool from
    which it came. The node must not be subsequently used as an argument to any
    List functions, until it happens to be allocated again. The pointer to
    the node object remains valid, and may be returned by a subsequent
    allocation request from the same node pool.

\subsection{Implementation}
\index{List!reference implementation}

This section describes the elements of the reference implementation of the
List component. No requirement is imposed that an implementation should
follow the reference implementation. The same is true of the
implementation notes for the other components.

\subsubsection{Types}
\index{implementation!List types}
\index{typedefs!implementation of List}

The reference List implementation is a doubly-linked circular list
\index{sentinel node!of linked list}
with a {\it sentinel node}. The node structure type is defined like this:
\begin{verbatim}
    typedef struct lnode_t {
        struct lnode_t *list_next;
        struct lnode_t *list_prev;
        void *list_data;
    } lnode_t;
\end{verbatim}
and the list structure is defined like this:
\begin{verbatim}
    typedef struct list_t {
        lnode_t list_nilnode;
        listcount_t list_nodecount;
        listcount_t list_maxcount;
    } list_t;
\end{verbatim}
The \verb|list_nilnode| member of the list object is the sentinel. It is
always present in the list, never deleted. When the list is empty, the sentinel
node's \verb|list_next| and \verb|list_prev| pointers simply point back at the sentinel
node.  The \verb|list_maxcount| member of the list tells how many nodes may be
inserted and \verb|list_nodecount| keeps track of the actual count.

The reason the sentinel node is called \verb|list_nilnode| is that it
acts as the successor of a list's tail node, if there is one,
and as the predecessor of the first node.  In a linked list implementation
that does not use a sentinel node, the \verb|list_next| pointer of
the the tail node and the \verb|list_prev| pointer of the first node would
be null.

Note that prefixed names are used for all of the structure members.  This is so
that the header file conforms to the documented namespace. If, for example, the
\verb|list_nilnode| member were simply called \verb|nilnode|, then
if the program contained somewhere a macro called \verb|nilnode|, there would
be a potential clash. If the program defined \verb|nilnode| prior to including
the \verb|list.h| header, the declaration of \verb|struct list_t| would
be confounded. If the program defined \verb|nilnode| after 
including \verb|list.h|, the definition would interfere with \verb|list.h|
macros whose replacement text refers to the \verb|nilnode| member.

For programming convenience, the list implementation source file defines short
macro names for the structure members:
\begin{verbatim}
    #define next list_next
    #define prev list_prev
    #define data list_data
\end{verbatim}
... and so forth. These names are private to the translation unit, which
includes only standard ANSI C headers.  Some of the examples in this section
make use of the short names; it is assumed that these macros are in effect.

\subsubsection{Selected operations}
\index{implementation!List operations}

\paragraph{Retrieving the first node}
\index{List!first node}

Given a pointer \verb|P| to a \verb|list_t| type, the \verb|list_first|
function examines the value of \verb|P->nilnode.next| which points
at the head node if the list is not empty. If the list is empty,
then this expression points back at the sentinel node. In
other words, the comparison
\begin{verbatim}
    P->nilnode.next == &P->nilnode
\end{verbatim}
yields true when the list is empty. In this case, the interface requires that
a null pointer be returned by \verb|list_first|.  The implementation actually
uses the above test, through a test for \verb|P->nodecount| being equal to
zero is also possible.

In general, any operation which produces a pointer to the nilnode that must be
returned back to the calling program  must test for that case and return a null
pointer instead to satisfy the interface requirements.

\paragraph{Node deletion}
\index{List!deletion}

Thanks to the use of the sentinel node, the list deletion operation doesn't
have to test for special cases. A node in the middle of the list is
deleted in exactly the same way as the first or the last node:
\begin{verbatim}
    lnode_t *list_delete(list_t *list, lnode_t *del)
    {
        lnode_t *next = del->next;
        lnode_t *prev = del->prev;

        assert (list_contains(list, del));

        prev->next = next;
        next->prev = prev;
        list->nodecount--;

        del->next = del->prev = NULL;

        return del;
    }
\end{verbatim}
Quite simply, the successor and predecessor of the deleted node are connected
together so that the deleted node is spliced out from the list. If the node is
the last remaining one, then the sentinel node serves as both the successor and
the predecessor. The effect of the deletion then is to set the sentinel's next
and previous links to point to itself, as they did initially when the list was
previously empty.

The next and prev pointers are set to null not only for enhanced error checking
in language implementations that trap dereferences of null pointers,
but also to indicate that the node is not on any list. The interface
function \verb|lnode_is_in_a_list| makes use of this.

It's worth discussing in some detail why the values of expressions
\verb|del->next| and \verb|del->prev| are cached in local variables.  The
actual statements that splice the node out of the list could instead have been
written:
\begin{verbatim}
    del->prev->next = del->next;
    del->next->prev = del->prev;
\end{verbatim}
However, this causes some compilers to generate less than optimal code because
they fail to apply common subexpression elimination to the double
occurrence of \verb|del->next|.  Caching this expression in a local variable
helps to get better code by making the semantics more obvious.  In any case,
modern compilers tend to do a good job of caching locals in high speed storage,
particularly on architectures generously endowed with registers, so using a few
extra locals is unlikely to lead to worse target code. The principle of using
local variables to perform ``manual CSE'' is applied throughout the Kazlib
reference implementation.

\paragraph{Node insertion}
Node insertion is also simple, thanks to the sentinel node which makes
the doubly linked list circular. All insertions are done using
the functions \verb|list_ins_before| and \verb|list_ins_after|.
These are very similar, so it suffices to show \verb|list_ins_before|:
\begin{verbatim}
    void list_ins_before(list_t *list, lnode_t *new, lnode_t *this)
    {
        lnode_t *that = this->prev;

        assert (new != NULL);
        assert (!list_contains(list, new));
        assert (!lnode_is_in_a_list(new));
        assert (this == list_nil(list) || list_contains(list, this));
        assert (list->nodecount + 1 > list->nodecount);

        new->next = this;
        new->prev = that;
        that->next = new;
        this->prev = new;
        list->nodecount++;

        assert (list->nodecount <= list->maxcount);
    }
\end{verbatim}
The node \verb|this| is the one before which the new node is being
inserted. Internally, the pointer \verb|that| points to the
node after which the insertion takes place. In other words, the function
inserts the node \verb|new| in between \verb|this| and \verb|that|.

Note the copious assertions which verify all of the documented constraints:
that the node i