docs.ltx

一些常用的数据结构库

\subsubsection{The {\tt list_prepend} function}

    \indexfunc{list_prepend}
    \index{List!prepending a node}
    \index{prepend node to list}
    \synopsis
    \begin{verbatim}
    void list_prepend(list_t *, lnode_t *);\end{verbatim}

    \constraints
    The second argument shall not refer to a node that is already in a list
    or in a list node pool. The first argument shall not refer to a list
    that is full.

    \description
    The prepend operation causes the node pointed at by the second
    argument to become the first node in the list pointed at by the first
    argument. After the operation, the \verb|list_first| function, when
    applied to the list, shall return a pointer to that node.
    If, prior to to the operation, the list is empty, then the prepended node
    shall become the first node in that list, otherwise, the prepended node
    becomes the predecessor of what was previously the first node.

    If the first argument is an expression with side effects, the behavior
    is undefined.\index{macros!and side effects}

\subsubsection{The {\tt list_prev} function}

    \indexfunc{list_prev}
    \synopsis
    \begin{verbatim}
    lnode_t *list_prev(list_t *, lnode_t *);\end{verbatim}

    \constraints
    The node pointed at by the second argument is an occupant of the list pointed
    at by the first argument.

    \description
    If the node pointed at by the second argument has a predecessor, a pointer to
    that predecessor is returned. Otherwise, a null pointer is returned.

    If the second argument is an expression which has side effects, the behavior
    \index{macros!and side effects}
    is undefined.

\subsubsection{The {\tt list_process} function}

    \indexfunc{list_process}
    \synopsis
    \begin{verbatim}
    void list_process(list_t *, void *,
            void (*)(list_t *, lnode_t *, void *));\end{verbatim}
    \nobreak
    \description
    The \verb|list_process| function iterates over the nodes of a list,
    and for each node invokes a callback function.\footnote{In most cases,
    it is more convenient and preferable to 
    iterate over the list using explicit calls to {\tt list_first}
    and {\tt list_next}.}
    The second argument is a {\it context pointer\/} which can have any value.
    The third argument of
    \verb|list_process| shall be a pointer to a function which is compatible
    with the specified type. If the list contains one or more nodes,
    then the function is invoked once for each node, in order from first
    to last. On each invocation, the first argument of the callback is a
    pointer to the list; the second argument is a pointer to a node, called
    the {\it subject node}; and the third argument repeats the context pointer
    value that was originally passed to \verb|list_process|.

    The callback function may delete the subject node by, for instance, calling
    \verb|list_delete|. It may insert new nodes to any place in the list;
    however, if such an insertion causes the subject node to acquire
    a new successor, it is implementation-defined whether upon returning
    from the callback function, the traversal shall continue with the
    new successor, or with the original successor.
    
    The callback function, and any function invoked from the callback
    function, shall not destroy the list or make any modifications
    other than the insertion of new nodes, or the deletion of the 
    subject node.

    The callback function may recursively invoke \verb|list_process| for the
    same list or for a different list; the callback invocations arising out of
    the nested call inherit all of the restrictions of the outer callback in
    addition to being subject to the usual restrictions.\footnote{This means,
    for instance, that if two callbacks are in progress for different
    subject nodes from the same list, the inner callback may not delete
    its subject node, because it inherits the restriction that the only
    permitted deletion is the outer callback's subject node.}

    The callback function may freely operate on a different list,
    subject to any inherited restrictions.

\subsubsection{The {\tt list_return_nodes} function}

    \indexfunc{list_return_nodes}
    \synopsis
    \begin{verbatim}
    void list_return_nodes(list_t *, lnodepool_t *);\end{verbatim}

    \description

    Every node in the list specified by the first argument
    is returned to the node pool specified by the second argument
    If the list contains a node that has not been allocated
    from that node pool, the behavior is undefined.

\subsubsection{The {\tt list_sort} function}

    \index{List!sort operation}
    \indexfunc{list_sort}
    \synopsis
    \begin{verbatim}
    void list_sort(list_t *, int (const void *, const void *));\end{verbatim}

    \description

    The \verb|list_sort| function changes the order of the nodes of the list
    specified by the first argument according to the comparison function
    pointed at by the second argument. 

    If the list is empty, or contains only one node, the comparison function is
    not called.

    Whenever the comparison function is invoked, its arguments are are the data
    pointers stored in two distinct nodes of the list.

\subsubsection{The {\tt list_find} function}

    \index{List!find operation}
    \indexfunc{list_find}
    \synopsis
    \begin{verbatim}
    lnode_t *list_find(list_t *,
           const void *, int (const void *, const void *));\end{verbatim}

    \description

    The \verb|list_find| function exhaustively searches the key for a node
    whose satellite data matches a search key according to the comparison
    function. The first argument is the list to be searched, the second
    argument specifies the search key and the third argument is a pointer
    to the comparison function.

    The comparison function is invoked to compare the key against the
    satellite data of successive nodes of the list, starting with the first
    node. A pointer to the first node for which the comparison function returns
    zero is returned.

    If the list is empty, or the comparison function returns non-zero for
    each item, a null pointer is returned.

\subsubsection{The {\tt list_transfer} function}

    \index{List!node transfer}
    \indexfunc{list_transfer}
    \synopsis
    \begin{verbatim}
    void list_transfer(list_t *, list_t *, lnode_t *);\end{verbatim}

    \constraints
    The third argument is either null, or it points at a node which is an
    occupant of the list pointed at by the second argument.

    The transfer request shall not call for the capacity of the  destination
    list to be exceeded.

    \description
    The \verb|list_transfer| function moves nodes from the list
    pointed at by the second argument to the list pointed at by
    the first argument.

    If the third argument is not null, it specifies the node in the source list
    at which the transfer begins. That node, its successor, and all 
    subsequent nodes, are transferred to the end of the destination list where
    they appear in their original order. Other nodes in the source list are
    unaffected.

    If the third argument is null, no transfer of nodes takes place.

    The source and destination list may be the same object.

    If \verb|DL|, \verb|SL| and \verb|SN| are appropriately typed expressions,
    the function call

\begin{verbatim}
    void list_transfer(DL, SL, SN);
\end{verbatim}
    is equivalent to 
\begin{verbatim}
    list_extract(DL, SL, SN, list_last(SL));
\end{verbatim}
    except that \verb|SL| is evaluated only once.

\subsubsection{The {\tt list_verify} function}

    \indexfunc{list_verify}
    \synopsis
    \begin{verbatim}
    int list_verify(list_t *list);\end{verbatim}

    \description
    The intent of the \verb|list_verify| function is to perform a verification
    on the list object, regardless of whether the Kazlib implementation is
    operated in verification or production mode. If the list objects
    and its constituent nodes have been correctly manipulated, and the
    program has not caused any undefined behaviors, the value $1$ is returned.
    Otherwise, the function may be able to, but is not guaranteed to, detect
    corruption, and return the value zero.

\subsubsection{The {\tt lnode_borrow} function}

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

    \description

    The \verb|lnode_borrow| function allocates a node from
    the pool managed by the given \verb|lnodepool_t| object.
    If the request succeeds, a pointer to the node is returned.  If the object
    has run out of nodes, the return value is a null pointer.

\subsubsection{The {\tt lnode_create} function}

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

    \description

    The \verb|lnode_create| function dynamically allocates a list node,
    stores in it the data value specified in the argument and
    returns a pointer to it. The allocation is performed by a call to the
    standard \verb|malloc| function. If the allocation fails, a null
    pointer is returned.

\subsubsection{The {\tt lnode_destroy} function}

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

    \description

    The \verb|lnode_destroy| function destroys a list node that has been
    allocated with the \verb|lnode_create| function.  The value of any pointer
    that referred to the node that was thus freed is indeterminate.

    If the node is currently the occupant of a list, the behavior is undefined
    if the list is subsequently used.

\subsubsection{The {\tt lnode_get} function}

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

    \description

    The \verb|lnode_get| function retrieves the \verb|void *| data value
    associated with a node.\footnote{This is the {\bf only} interface for
    retrieving the data element.}
    
\subsubsection{The {\tt lnode_init} function}

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

    The \verb|lnode_init| function initializes the contents
    of the specified list node object, assigning it the
    data value specified as the second argument. 
    The first argument is a pointer which refers to 
    a data object that has a suitable size and alignment
    for the representation of an \verb|lnode_t| type.
    After initialization with \verb|lnode_init|, the object is subsequently
    eligible as an operand to the functions of the List component.

\subsubsection{The {\tt lnode_is_in_a_list} function}

    \indexfunc{lnode_is_in_a_list}
    \synopsis
    \begin{verbatim}
    int lnode_is_in_a_list(lnode_t *);\end{verbatim}

    \description

    The \verb|lnode_is_in_a_list| function determines whether the given node is
    an occupant of some list. If the node is in a list, the function returns
    the value $1$.  If the node is not in any list, the return value is zero.

\subsubsection{The {\tt lnode_pool_create} function}

    \indexfunc{lnode_pool_create}
    \synopsis
    \begin{verbatim}
    lnodepool_t *lnode_pool_create(listcount_t);\end{verbatim}

    \constraints

    The value of the argument shall not be zero.