docs.ltx

一些常用的数据结构库

The behavior is also undefined if the program contains a definition of an
object or function with external linkage whose name matches an external object
of unction defined  by Kazlib component that is used as part of the
program, or whose name is in a namespace reserved by that
component.\footnote{This restriction exists whether or not the corresponding Kazlib
header is included.} 

Lastly, the behavior is undefined if a translation unit defines a macro whose
name is in the space of reserved symbols of a Kazlib header that is included in
that translation unit.

\subsection{Argument aliasing}

Kazlib provides functions that operate on objects of various types.  Pointers
to objects are passed to these functions, thereby giving rise to the
possibility of {\it aliasing}---passing of objects that wholly or partially
overlap.  The program shall not present aliased objects to any Kazlib function.
Objects of distinct types shall not be aliased in a function call under any
circumstances.
The aliasing of two or more objects of compatible type is permitted only as
explicitly documented in the description of a function; in all such
circumstances, only exact overlapping is permitted.\footnote{That is to say,
where explicitly allowed, a pointer to the same object may be specified for two
(or more) parameters of like type.}

\subsection{Object initialization}

The Kazlib opaque data types can only be initialized with the initialization
functions provided by the Kazlib library, or by implementation-defined
initialization functions.\footnote{Of course, the use of implementation-defined
functions results in programs that are not portable among library
implementations.} An opaque object that is initialized by a method other than
by being passed to an appropriate initialization function, or that is not
initialized at all, has indeterminate contents.  A pointer to an object having
indeterminate contents may be passed to an initialization function; the object
then has well-determined contents.

An object whose initialization function is capable of indicating failure is
considered indeterminate if the attempt to initialize that object using that
function does in fact fail. The program shall not attempt to deinitialize such
an object. The implementation shall reclaim any resources that were allocated
for an object whose initialization failed. This reclamation need
not be immediate, but may be delayed; however, the delay shall not
give rise to the possibility of resource leaks in any correct program.

Those objects for which deinitialization operations are defined should be
subject to these operations when these objects are no longer needed.  Failure
to apply the deinitialization functions may result in the leakage of resources.

\subsection{Object copying}

Certain data types may be sensitive to their own location in memory.  This
means that copying their values by assignment or \verb|memcpy| results in the
copy having an indeterminate value which cannot be used.  All opaque types in
Kazlib are assumed to have this property; copying the value of an opaquely
typed object to another suitably typed object causes the destination
object to have indeterminate contents. 

\section{List component}

The List component provides a set of functions, macros and type declarations
which together provide a library for maintaining a possibly empty ordered set
of elements, called a {\it list}. This list has the following properties:
\index{List}\begin{enumerate}
\item If the list is not empty, a first and last element can be identified.
    In a list having only one element, that one element is both the first and
    last element.
\item Each element that is not the last element has another element as its
    {\it successor}.
    \index{successor!of a list element}
    \index{List!successor of an element}
\item Each element that is not the first element has a {\it
    predecessor}.
    \index{predecessor!of a list element}
    \index{List!predecessor of an element}
\item No element is the predecessor or successor of more than one element.
\item If one element is the successor of another, the other is necessarily the
    predecessor of the first.
\item Each element is associated with arbitrary {\it satellite\/} data.
\end{enumerate}
The {\it size} of a list, also known as the {\it list count}, is simply the
number of elements contained in it.\index{size!of a list}\index{List!count}

A list imposes a maximum value on the number of nodes that may be in it
simultaneously. This is known as the list's {\it capacity}. A list that
has the maximum number of nodes is said to be full.

\subsection{Interface}

\subsubsection{The {\tt list.h} header}

Each C or C++ translation unit that is to use the functionality of
the List component shall include the header \verb|list.h|. This header
shall contain declarations of types and external functions, and definitions of
macros.
The following typedef names shall be defined:\index{List!typedef names}
\index{typedefs!defined by List}
\begin{verbatim}
    list_t                      listcount_t
    lnode_t                     lnodepool_t
\end{verbatim}
In addition, the following structure tags may be defined:\index{List!tag names}
\index{tags!defined by List}
\begin{verbatim}
    struct list_t
    struct lnode_t
    struct lnodepool_t
\end{verbatim}
The following external function names shall be declared:
\index{List!function names}\index{functions!defined by List}
\begin{verbatim}
    list_append                 list_prev                          
    list_contains               list_process                       
    list_count                  list_return_nodes                  
    list_create                 list_sort                          
    list_del_first              list_find
    list_del_last               list_transfer                      
    list_delete                 list_verify                        
    list_destroy                lnode_borrow                       
    list_destroy_nodes          lnode_create                       
    list_extract                lnode_destroy                      
    list_first                  lnode_get                          
    list_init                   lnode_init                         
    list_ins_after              lnode_is_in_a_list                 
    list_ins_before             lnode_pool_create                  
    list_is_sorted              lnode_pool_destroy                 
    list_isempty                lnode_pool_init                    
    list_isfull                 lnode_pool_isempty                 
    list_last                   lnode_pool_isfrom                  
    list_merge                  lnode_put                          
    list_next                   lnode_return                       
    list_prepend                
\end{verbatim}
The following preprocessor symbols (macros) shall be defined:
\index{List!macro names}\index{macros!defined by List}
\indexmacro{LISTCOUNT_T_MAX}
\indexmacro{LIST_H}
\begin{verbatim}
    LISTCOUNT_T_MAX
    LIST_H\end{verbatim}
\index{symbols!reserved by List}\index{List!reserved symbols}
Macro identifiers which begin with the upper-case prefix \verb|LIST| are
reserved for future extensions to the \verb|list.h| header, as are
names in the ordinary and tag namespaces which begin with
\verb|list_| or \verb|lnode_|. External names which begin with \verb|list_| or
\verb|lnode_| are reserved by the Kazlib library regardless of what header
files are included.

\subsubsection{The {\tt list_t} type}

\indextype{list_t}
The type \verb|list_t| is an opaque data type which maintains information about the
current state of a single list.  A list consists of an instance of the
\verb|list_t| type, plus zero or more instances of the type \verb|lnode_t|. An
instance of the \verb|list_t| type can be dynamically created using the
\verb|list_create| function, and destroyed by the \verb|list_destroy| function.
Alternately, the program can declare an object of type \verb|list_t| and have
it initialized via the \verb|list_init| function. 

\subsubsection{The {\tt listcount_t} type}

\indextype{listcount_t}
\indexmacro{LISTCOUNT_T_MAX}
The type \verb|listcount_t| is an unsigned integral type which represents
the number of nodes in a list. The specific choice of unsigned integral type
is implementation defined. The \verb|LISTCOUNT_T_MAX| macro expands to a
constant expression of type \verb|listcount_t| which specifies the maximum
value of that type.\footnote{For example, if the implementation defines
{\tt listcount_t} as an alias for the type unsigned long, then 
{\tt LISTCOUNT_T_MAX} must have the same value as {\tt ULONG_MAX}.}

\subsubsection{The {\tt lnode_t} type}

\indextype{lnode_t}
The type \verb|lnode_t| is an opaque type that represents a single node of a
list. A node contains a a reference to satellite data provided by the user,
and also stores the key that is associated with the node when it is inserted.
Nodes may be dynamically created by the \verb|lnode_create| function.
Alternately, the program may supply an \verb|lnode_t| object that can be
initialized by the \verb|lnode_init| function. 

\subsubsection{The {\tt lnodepool_t} type}

\indextype{lnodepool_t}
The \verb|lnodepool_t| type provides an alternate method for supplying list
nodes to the application. A user-supplied or dynamically allocated fixed size
array of nodes is converted into a a {\it pool\/} of nodes from which free
nodes may be obtained and to which they may be returned. A user-supplied node
pool is created by the function \verb|lnode_pool_init| which requires a pointer
to an object of type \verb|lnode_pool_t|, a pointer to the first element of an
array of \verb|lnode_t| objects, as well as an integer representing the size of
the array. Alternately, the function \verb|lnode_pool_create| will dynamically
allocate an object of type \verb|lnode_pool_t| containing the specified number
of list nodes. 

\subsubsection{The {\tt list_append} function}

    \indexfunc{list_append}
    \index{List!appending a node}
    \index{append node to list}
    \synopsis
    \begin{verbatim}
    void list_append(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 append operation causes the node pointed at by the second
    argument to become the last node in the list pointed at by the first
    argument.\footnote{That is to say, after the operation, the
    {\tt list_last} function, when applied to the list, shall return a pointer
    to that node.}

    If the first argument is an expression with side effects, the behavior
    is undefined.\footnote{Thus, the implementation may provide a macro
    version of {\tt list_append} which evaluates the first argument
    more than once.}
    \index{macros!and side effects}

\subsubsection{The {\tt list_contains} function}

    \indexfunc{list_contains}
    \index{List!testing for presence of node}
    \nobreak
    \synopsis
    \begin{verbatim}
    int list_contains(list_t *, lnode_t *node);\end{verbatim}
    \nobreak
    \description
    \nobreak
    The \verb|list_contains| function shall return 1 if the node
    pointed at by the second argument is in the list pointed at by the first
    argument.  Otherwise, it shall return 0.

\subsubsection{The {\tt list_count} function}

    \indexfunc{list_count}
    \index{List!count}
    \index{List!size}
    \synopsis
    \begin{verbatim}
    listcount_t list_count(list_t *);\end{verbatim}

    \description

    The \verb|list_count| function returns a value which represents the number
    of nodes currently stored in the list pointed at by the argument.

\subsubsection{The {\tt list_create} function}

    \indexfunc{list_create}
    \index{List!creation of}
    \index{create!list object}
    \synopsis
    \begin{verbatim}
    list_t *list_create(listcount_t);\end{verbatim}

    \description
    The \verb|list_create| function instantiates and initializes an object of
    type \verb|list_t|, and returns a pointer to it unless insufficient
    resources exist for the creation of the object, in which case a null
    pointer is returned.

    The value of the function's argument establishes, for the entire duration
    of the list object, its capacity.

    The newly created list object is empty.

\subsubsection{The {\tt list_del_first} function}

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

    \constraints
    The argument shall not point to an empty list.

    \description
    The \verb|list_del_first| function removes the first node from the
    list pointed at by the argument and returns a pointer to that
    node. 

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

\subsubsection{The {\tt list_del_last} function}

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

    \constraints
    The argument shall not point to an empty list.

    \description
    The \verb|list_del_last| function removes the last node from the list
    specified by the argument, and returns a pointer to that node. If,