docs.ltx

一些常用的数据结构库

%
% $Id: docs.ltx,v 1.74.2.10 2001/07/25 03:37:05 kaz Exp $
% $Name: kazlib_1_20 $
%

\documentclass{article}
\usepackage{makeidx}
\usepackage[margin=1.0in]{geometry}
\makeatletter
\newcommand{\defsubsection}{\@startsection
    {subsection}
    {2}
    {0pt}
    {2.0ex plus 0.1ex minus 0.05ex}
    {-0pt}
    {\normalfont\normalsize\bfseries}}
\newcommand{\defsubsubsection}{\@startsection
    {subsection}
    {3}
    {0ex}
    {2.0ex plus 0.1ex minus 0.05ex}
    {1.0ex}
    {\normalfont\normalsize\bfseries}}
\renewcommand{\paragraph}{\@startsection
    {paragraph}
    {4}
    {0ex}
    {2.0ex plus 0.1ex minus 0.05ex}
    {1.0ex}
    {\normalsize\bfseries}}
\makeatother
\title{Kazlib---Reusable Components\\for C Programming}
\author{Kaz Kylheku}
\date{Release 1.20\\July 24, 2001}
\makeindex
\setcounter{tocdepth}{1}
\setcounter{secnumdepth}{4}
\begin{document}
\catcode`\_=11
\def\indextype#1{\index{#1@{\tt #1} type}}
\def\indexmacro#1{\index{#1@{\tt #1} macro}}
\def\indexobject#1{\index{#1@{\tt #1} object}}
\def\indexfunc#1{\index{#1@{\tt #1} function}}
\def\indexenum#1{\index{#1@{\tt #1} enum constant}}
\def\synopsis{\paragraph*{Synopsis}}
\def\constraints{\paragraph*{Constraints}}
\def\description{\paragraph*{Description}}
\def\example{\paragraph*{Example}}
\maketitle
\abstract{The aim of the Kazlib project is to provide a well-documented
programming interface featuring commonly needed programming abstractions,
accompanied by a high quality, portable reference implementation.
Kazlib consists of four independent components: a list module, a hash table
module, a dictionary module and an exception handling module. The reference
implementations of the first three of these are based on, respectively, the
following algorithms: doubly linked circular list with sentinel node,
extendible hashing, and red-black tree.}
\tableofcontents
\section{Introduction}
This document establishes the provisions required of an implementation of the
Kazlib library, and describes a reference implementation thereof.
This document specifies
\begin{itemize}
\item the names and types of identifiers and preprocessor symbols made
    available by each component;
\item identifier name spaces reserved for future use by each component;
\item the interface syntax and semantics of each component operation;
\item the conditions required for the well-defined execution of each operation;
\item the externally visible behavior of each component, including global
    side effects and the effects on the subject data structures;

\item and the implementation language of Kazlib.
\end{itemize}
Furthermore, this document describes, but does not specify
\begin{itemize}
\item the implementation details of structure objects manipulated by the
    operations of each component;
\item objects and functions that are defined by the implementation of
    each component but are not externally visible;
\item the algorithms and implementation details of the operations.
\end{itemize}
Finally, this document does {\em not\/} specify or describe
\begin{itemize}
\item the specific choices for parameters which may be adjusted by an
    installation or implementation of Kazlib.
\item the size of any data structure which will exceed the capacity of
    a particular installation.
\item the mechanisms or procedures for the translation of Kazlib and
    their integration with other translation units.
\end{itemize}

\section{References}
\label{sec:references}

\begin{trivlist}
\item ISO 9899:1990, {\it Programming Languages---C.}
\item {\it Introduction to Algorithms}, Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest, eighth printing, 1992.
\end{trivlist}

\section{Definitions and conventions}
The following terms shall be interpreted in accordance with the definitions
below. Other terms appearing in this document shall be defined upon their
first mention, indicated by {\it italic\/} type. Any terms not explicitly
defined in this document should be interpreted according to ISO 9899-1990,
clause 3. Failing that, they should be interpreted according to other works
listed in section \ref{sec:references}.
\nobreak
\defsubsection{implementation}: A library and set of C language headers
which conforms to the specifications of this Document.
\index{production mode}
\indexmacro{NDEBUG}
\defsubsection{production mode}: A mode of operating the implementation
in such a way that maximum efficiency of execution is achieved at the expense
of the verification of constraints. An implementation shall provide
a production mode, which is enabled in an implementation-defined
manner.\footnote{An implementation may have to supply a separate set of
libraries for production and for verification use, for instance. The
manner of selecting libraries varies with each programming environment.}  Each
translation unit of the program which includes a Kazlib header shall ensure that the macro {\tt
NDEBUG} is defined prior to the inclusion of that header, otherwise the
implementation is not said to be operated in production mode.
\index{verification mode}
\defsubsection{verification mode}: A mode of operating the implementation in
such a way that maximum error checking is obtained at the cost of
execution efficiency. An implementation shall provide a verification mode, which
is enabled in an implementation-defined manner. If any translation unit which
includes a Kazlib header defines the macro name {\tt NDEBUG}\footnote{The
intent is that the standard {\tt assert} macro may be exploited
by the implementation's headers for the purpose of provisioning verification
mode.} prior to including that header, the implementation is not said to be in
verification mode. The least requirements of a Kazlib implementation operated
in verification mode, is that it shall stop translation or execution of any
program which violates a constraint. 
\index{undefined behavior}
\defsubsection{undefined behavior}: Behavior of a program, upon violation of a
requirement with respect to the use of Kazlib, or upon use of corrupt or
incorrect data, for which this document does not impose any requirements.
Additional undefined behaviors are:
\begin{itemize}
\item any behavior that is undefined by the C language standard;
\item evaluation of an object whose contents are indeterminate;
\item a violation of any explicit constraint stated in
this document, if that program was built using Kazlib in production
mode;\footnote{The intent is that violations of constraints are diagnosed by
the implementation in verification mode, and hence do not lead to undefined
behavior.}
\item a violation of any requirement stated in this document that
is not designated as a constraint, and is introduced using the word
{\it shall}; and
\item any other construct for which no definition of behavior can be deduced
from this document.
\end{itemize}
If a program invokes undefined behavior of any kind, the Kazlib implementation
is absolved from any requirements as to what events should ensue.  The
implementation may respond by invoking undefined behavior in the C language
sense, or it may detect the behavior and terminate with a diagnostic message.
\defsubsection{implementation-defined}: An adjective which, when appearing
in the description of a feature, represents a requirement that the
implementor must supply a definition, and document that
definition. This adjective is applied to both behavior and to results.
Implementation-defined behavior is behavior which depends on the
characteristics of an implementation.\footnote{It is not considered adequate
for the implementor to allow implementation-defined behavior to produce
unpredictable effects or to terminate the program when such behavior is
invoked.}  When said of a result,
implementation-defined means that a value is successfully computed, but depends
on the characteristics of the implementation. It is possible for the presence of a
requirement on a program to be described as implementation-defined, giving the
implementor a choice whether to make that requirement or not. If a program
violates a requirement whose presence is implementation-defined, that program's
behavior is undefined in any implementation which elects to in fact impose that
requirement.
\index{implementation-defined}
\defsubsection{unpredictable result}: A successfully computed value which is
unreliable because some procedure or data failed to satisfy a property required
by the computation.
\defsubsection{constraint}: A semantic restriction with which a program must
comply. Some sections of this Document contain paragraphs under the heading
{\it Constraints\/} which list all constraints pertaining to the described
feature. When operated in production mode, the Kazlib implementation
is not required to diagnose constraint violations. When operated in
verification mode, the Kazlib implementation must halt translation or
execution of a program which violates a constraint.
\index{constraint}
\defsubsection{comparison function}: A function which accepts two arguments
\index{comparison function}
of type \verb|const void *| and returns a value of type int based on
a ranking comparison of these arguments, and which satisfies the following
additional semantic properties. If the two arguments are deemed to be equal, the
function must return zero. If the first argument is determined to have a
greater rank than the second, a positive value is returned. Otherwise if the
first argument is determined to have a lesser rank than the second, a negative
value is returned. The rank is computed as if each value has associated with it
an integer, not necessarily unique, and as if these integers are compared for ordinary equality or
inequality when values are said to be compared.  The assignment of integers is
up to the designer of the comparison function, and does not change between
successive invocations of the function.\footnote{Of course, an actual
comparison function need not assign actual integer ranks to data items, but it
must behave as if such ranks were assigned.}
If a comparison function is invoked in the context of an operation on some data
structure, it shall not invoke any operation on any component of that same
structure.\footnote{Thus, if a comparison function is invoked from, for
instance, {\tt list_sort}, it must not call any list operations that 
inspect or modify the list being sorted, or any of its constituent nodes.}
\defsubsection{opaque data type}: A data type whose precise definition is
not documented, and which is intended to be manipulated only using the
documented interface, which consists of a set of functions.  Many data types in
Kazlib are described as opaque. A program which bypasses the documented
interfaces in inspecting or manipulating these data types invokes undefined
behavior, and is not portable among Kazlib implementations.
\defsubsection{user}: \index{user} The program which uses Kazlib.
\defsubsection{user data}: \index{user data} Data provided by the program
to which Kazlib stores a pointer, but otherwise does not inspect or modify.

\section{Environment}
\label{sec:environment}

The translation and use of Kazlib requires a conforming, hosted implementation
of the C language which meets the following additional minimal requirements:
\begin{enumerate}
\item The C implementation distinguishes external names by at least their
initial 15 characters\footnote{The ISO 9899:1990 standard demands only that
external names be distinguished by their initial six characters.}. External
names that are distinct in their first 15 characters are treated by the
implementation as distinct names.  Upper and lower case letters in external
identifiers need not be treated as distinct.
\item The C implementation does not claim the identifier \verb|__cplusplus|
for its internal use as a preprocessor symbol or keyword.
\end{enumerate}
If Kazlib headers are used by a C++ program, the C++ implementation
meets these additional requirements:
\begin{enumerate}
\item the C++ implementation identifies itself by predefining the preprocessor
symbol \verb|__cplusplus|;
\item the C++ implementation is be capable of linkage against
the C implementation with which the Kazlib source files units were translated.
\end{enumerate}
The Kazlib headers shall not make use of any names that are claimed
by the C++ programming language, and shall ensure that the \verb|extern "C"|
mechanism is used for all declarations when they are included into a C++
translation unit, or otherwise provide compatibility with C++.\footnote{The
intent is that the Kazlib implementation could, in principle, provide 
a separate set of headers for use with each language.}

In programming environments that support the programming mechanism of multiple
threads of execution an implementation of Kazlib may be designated as {\it
thread safe}.  To be called thread safe, it must guarantee that the use of an
object by one thread cannot visibly interact or interfere with the concurrent
or interleaved use of another object by another thread. If a Kazlib
implementation that is not thread safe is provided for an environment which
supports threads, it shall be accompanied by documentation which describes
the extent of this limitation.

A Kazlib implementation can also be designated as being {\it async safe}.
The minimum requirement for this designation is that an operation on an object
can be interrupted by delivery of an asynchronous signal and from within the
catching function for that signal, it is safe to perform an operation on
another object.  An implementation shall document that it is async safe,
or the extent to which it fails to be async safe.

\section{General restrictions}

\subsection{Headers}

The Kazlib headers may be included in any order, and may be included more than
once. Prior to the inclusion of a Kazlib header, the translation unit shall not
define any macro name that has the same spelling as a C language keyword. The
Kazlib headers may behave as though they include arbitrary standard C headers,
so any requirements related to the inclusion of standard headers apply to
Kazlib headers.  A header shall be included before the first reference to any
of the functions, types or macros that it defines.

If one or more preprocessor symbols whose names begin with the sequence
\verb|KAZLIB_| are defined prior to the inclusion of a Kazlib header,
the behavior is implementation-defined.

\subsection{Reserved macros}

A Kazlib header defines all of the macros explicitly listed in the section of
this document that defines the contents of that header. It may also define
additional macros that belong to the macro namespace reserved by that header.
The translation unit that includes the header shall not \verb|#define| or
\verb|#undef| any of these macros.

A header may define function-like macros that supplement existing functions,
provided that such macros do not cause multiple evaluation of arguments except
as explicitly permitted, and are safe to use wherever the corresponding
function call would be. These function-like macros may be subject to
\verb|#undef|.\footnote{In principle, an implementation may provide, within the
reserved namespaces, additional functions not specified in this document, and
function-like macro equivalents of these functions. A program that uses such
identifiers in a block or function scope should use {\tt \#undef} on these
identifiers prior to their use.}

\subsection{Reserved symbols}

Each Kazlib header provides file scope declarations for the typedef names,
struct tags, enum constants and function names listed in its corresponding
section in this document. Moreover, each header may define additional such
names that fall into the documented reserved namespaces.

The behavior is undefined if a translation unit that includes a Kazlib header
defines any identifier that is the same as an identifier reserved by the header
in the same scope and namespace.\footnote{Therefore, it is permitted to redeclare
or redefine the identifiers reserved by a previously included Kazlib header,
provided that the declarations or definitions are in a different namespace or
scope. Reserved names may be redeclared in a block scope, or used as
statement labels which have function scope and are in their own namespace.}