docs.ltx

一些常用的数据结构库

    prior to the operation, that node had a predecessor, that predecessor
    shall become the new last node of the list. Otherwise, the list
    shall become empty.

    The new value of the list count shall be one less than its value
    prior to the call to this function.

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

\subsubsection{The {\tt list_delete} function}

    \indexfunc{list_delete}
    \index{List!deletion}
    \index{delete!arbitrary node of a list}
    \synopsis
    \begin{verbatim}
    lnode_t *list_delete(list_t *, lnode_t *);\end{verbatim}

    \constraints
    The second argument shall point to a node that is inside the list
    pointed at by the first argument.

    \description
    The \verb|list_delete| function removes the node pointed at by its
    second argument from the list pointed at by its first argument.
    A pointer to the deleted node is returned.

\subsubsection{The {\tt list_destroy} function}

    \indexfunc{list_destroy}
    \index{List!destruction of}
    \synopsis
    \begin{verbatim}
    void list_destroy(list_t *);\end{verbatim}

    \constraints
    The argument shall point to an empty list.

    \description
    The empty list pointed at by the argument is destroyed. If the list has
    not been created by a call to the \verb|list_create| function, the
    behavior is undefined.

    A pointer that previously referred to a list that has been disposed by
    \verb|list_destroy| has an indeterminate value.

\subsubsection{The {\tt list_destroy_nodes} function}

    \indexfunc{list_destroy_nodes}
    \synopsis
    \begin{verbatim}
    void list_destroy_nodes(list_t *);\end{verbatim}

    \description
    The nodes, if any, contained in the list pointed at by the argument are
    disposed of as if by a call to the \verb|lnode_destroy| function. If any
    node contained in the list was created by means other than the
    \verb|lnode_create| function, the behavior is undefined.

    After the operation, the list is empty.

    Any pointer that referred to any of the destroyed nodes takes on an
    indeterminate value.

\subsubsection{The {\tt list_extract} function}

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

    \constraints
    The second argument points to the {\it source list}. The third
    argument is either null, or points to a node that is an occupant
    of the source list. This node is called the {\it starting node}.
    The fourth argument is either null, or points to a node that is
    an occupant of the source list. This node is called the {\it ending
    node}. If the starting node and ending node are both specified, and are
    distinct nodes, then the starting node shall appear earlier in the source
    list than the ending node.

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

    \description
    The \verb|list_extract| function moves nodes from the source
    list to the {\it destination list\/} pointed at by the first
    argument.\footnote{This right-to-left direction of transfer is consistent
    with the semantics of standard C library functions such as {\tt memmove} or
    {\tt strcpy}.}

    If the third and fourth arguments are not null, the entire range of nodes
    from the starting node and to the ending node, inclusive, is transferred
    from the source list to the end of the destination list, where they appear
    in their original order. Other nodes in the source list, if any, are
    unaffected.

    If the third and fourth arguments both point to the same node, that
    node alone is transferred to the end of the destination list.

    If either the third argument or the fourth argument is null, or both are null,
    no transfer of nodes takes place.

    The source and destination list may be the same object.

\subsubsection{The {\tt list_first} function}

    \index{List!first node}
    \indexfunc{list_first}
    \synopsis
    \begin{verbatim}
    lnode_t *list_first(list_t *);\end{verbatim}

    \description
    If the list pointed at by the argument is an empty list, a null pointer
    is returned. Otherwise, a pointer to the first node in that list is
    returned.

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

\subsubsection{The {\tt list_init} function}

    \indexfunc{list_init}
    \synopsis
    \begin{verbatim}
    list_t *list_init(list_t *, listcount_t);\end{verbatim}

    \constraints
    The second argument shall not have a zero value.

    \description
    The \verb|list_init| function initializes the list object pointed at by the
    first argument, turning it into a valid, empty list. If the object is an
    already initialized list, the behavior is undefined. A list returned by
    \verb|list_create| is considered initialized. The second argument 
    specifies the maximum number of nodes that may simultaneously occupy the
    list.

    The value returned is that of the first argument.

\subsubsection{The {\tt list_ins_after} function}

    \indexfunc{list_ins_after}
    \index{insert!node into list}
    \index{List!insertion}
    \synopsis
    \begin{verbatim}
    void list_ins_after(list_t *, lnode_t *, lnode_t *);\end{verbatim}

    \constraints
    The first argument shall point to a list that is not already full.  The
    second argument shall point to a node, called the {\it new node}, that is not
    already an occupant of the list pointed at by the first argument, nor
    of any other list or node pool object. The third
    argument shall point to a node, called the {\it reference node}, that is an
    occupant of the list.

    \description
    The new node becomes an occupant of the list, such that its predecessor
    is the reference node. If the reference node has a successor, the
    new node is inserted between the reference node and that successor.
    Otherwise, the new node becomes the last node of the list.

\subsubsection{The {\tt list_ins_before} function}

    \indexfunc{list_ins_before}
    \index{insert!node into list}
    \index{List!insertion}
    \synopsis
    \begin{verbatim}
    void list_ins_before(list_t *, lnode_t *, lnode_t *);\end{verbatim}

    \constraints
    The first argument shall point to a list that is not already full.  The
    second argument shall point to a node, called the {\it new node}, that is not
    already an occupant of the list pointed at by the first argument, nor
    of any other list or node pool object. The third
    argument shall point to a node, called the {\it reference node}, that is an
    occupant of the list.

    \description
    The new node becomes an occupant of the list, such that its successor
    is the reference node. If the reference node has a predecessor, the
    new node is inserted between the reference node and that predecessor.
    Otherwise, the new node becomes the first node of the list.
    
\subsubsection{The {\tt list_is_sorted} function}
\label{list:is:sorted}
    \indexfunc{list_is_sorted}

    \synopsis
    \begin{verbatim}
    int list_is_sorted(list_t *,
            int (const void *, const void *));\end{verbatim}

    \description
    The first argument points to a list object. The second is assumed to
    point to a comparison function.
    
    If the list has exactly one node or is empty, $1$ is returned
    unconditionally.  Otherwise, nodes of the list are examined to
    determine whether they are in a sorted order according to the comparison
    function. This is true if the integer ranks of their data items,
    examined from the first node of the list through to the last node, form a
    monotonically increasing sequence. If the nodes are in order, the value $1$
    is returned. Otherwise $0$ is returned.
    
    If the list has two or more nodes, and the second argument is a pointer to
    a function that has the correct type, but does not satisfy the semantic
    properties of a comparison function, the result is unpredictable, but is
    guaranteed to be one of the values~$0$~or~$1$. 

\subsubsection{The {\tt list_isempty} function}

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

    \description
    The \verb|list_isempty| function returns $1$ if the list pointed at by
    the first argument is empty. Otherwise it returns $0$.

\subsubsection{The {\tt list_isfull} function}

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

    \description
    The \verb|list_isfull| function returns $1$ if the list pointed at by
    the first argument is full. Otherwise it returns $0$.
    A list is considered full when it contains the maximum number of nodes
    that was specified upon its initialization.

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

\subsubsection{The {\tt list_last} function}

    \index{List!last node}
    \indexfunc{list_last}
    \synopsis
    \begin{verbatim}
    lnode_t *list_last(list_t *);\end{verbatim}

    \description
    If the list pointed at by its first argument is empty, the \verb|list_last|
    function returns a null pointer. Otherwise it returns a pointer to the
    last node.

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

\subsubsection{The {\tt list_merge} function}

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

    \constraints
    The list pointed at by the first argument is called the {\it destination
    list}. The second argument points to the {\it source list}. The third
    argument points to a comparison function.  The sum of the number of nodes
    occupying the source list and the destination list shall not exceed the
    maximum number of nodes that are permitted to occupy the destination list.
    Furthermore, both the source and destination list shall be sorted such that
    a call to \verb|list_is_sorted| given a pointer to either list as a first
    argument, and the pointer to the comparison function as its second
    argument, shall yield the value $1$.

    \description
    Nodes from the sorted source list are merged into the sorted destination
    list. After the operation, the source list is empty and the destination
    list contains all of the nodes it contained prior to the operation, as well
    as all of the nodes that the source list contained. The nodes are in sorted
    order according to the comparison function.

    If the third argument is a pointer to a function that has the correct type,
    but does not fulfill the semantic properties of a comparison function, the
    order of the nodes in the destination list is unpredictable.

    If the source and destination list are the same object, the
    \verb|list_merge| operation has no effect.

\subsubsection{The {\tt list_next} function}

    \indexfunc{list_next}
    \synopsis
    \begin{verbatim}
    lnode_t *list_next(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 successor, a pointer to
    that successor is returned. Otherwise, a null pointer is returned.

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