%% $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-documentedprogramming 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 tablemodule, a dictionary module and an exception handling module. The referenceimplementations of the first three of these are based on, respectively, thefollowing 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 theKazlib 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 definitionsbelow. Other terms appearing in this document shall be defined upon theirfirst mention, indicated by {\it italic\/} type. Any terms not explicitlydefined in this document should be interpreted according to ISO 9899-1990,clause 3. Failing that, they should be interpreted according to other workslisted in section \ref{sec:references}.\nobreak\defsubsection{implementation}: A library and set of C language headerswhich conforms to the specifications of this Document.\index{production mode}\indexmacro{NDEBUG}\defsubsection{production mode}: A mode of operating the implementationin such a way that maximum efficiency of execution is achieved at the expenseof the verification of constraints. An implementation shall providea production mode, which is enabled in an implementation-definedmanner.\footnote{An implementation may have to supply a separate set oflibraries for production and for verification use, for instance. Themanner of selecting libraries varies with each programming environment.}  Eachtranslation unit of the program which includes a Kazlib header shall ensure that the macro {\ttNDEBUG} is defined prior to the inclusion of that header, otherwise theimplementation is not said to be operated in production mode.\index{verification mode}\defsubsection{verification mode}: A mode of operating the implementation insuch a way that maximum error checking is obtained at the cost ofexecution efficiency. An implementation shall provide a verification mode, whichis enabled in an implementation-defined manner. If any translation unit whichincludes a Kazlib header defines the macro name {\tt NDEBUG}\footnote{Theintent is that the standard {\tt assert} macro may be exploitedby the implementation's headers for the purpose of provisioning verificationmode.} prior to including that header, the implementation is not said to be inverification mode. The least requirements of a Kazlib implementation operatedin verification mode, is that it shall stop translation or execution of anyprogram which violates a constraint. \index{undefined behavior}\defsubsection{undefined behavior}: Behavior of a program, upon violation of arequirement with respect to the use of Kazlib, or upon use of corrupt orincorrect 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 inthis document, if that program was built using Kazlib in productionmode;\footnote{The intent is that violations of constraints are diagnosed bythe implementation in verification mode, and hence do not lead to undefinedbehavior.}\item a violation of any requirement stated in this document thatis 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 deducedfrom this document.\end{itemize}If a program invokes undefined behavior of any kind, the Kazlib implementationis absolved from any requirements as to what events should ensue.  Theimplementation may respond by invoking undefined behavior in the C languagesense, or it may detect the behavior and terminate with a diagnostic message.\defsubsection{implementation-defined}: An adjective which, when appearingin the description of a feature, represents a requirement that theimplementor must supply a definition, and document thatdefinition. This adjective is applied to both behavior and to results.Implementation-defined behavior is behavior which depends on thecharacteristics of an implementation.\footnote{It is not considered adequatefor the implementor to allow implementation-defined behavior to produceunpredictable effects or to terminate the program when such behavior isinvoked.}  When said of a result,implementation-defined means that a value is successfully computed, but dependson the characteristics of the implementation. It is possible for the presence of arequirement on a program to be described as implementation-defined, giving theimplementor a choice whether to make that requirement or not. If a programviolates a requirement whose presence is implementation-defined, that program'sbehavior is undefined in any implementation which elects to in fact impose thatrequirement.\index{implementation-defined}\defsubsection{unpredictable result}: A successfully computed value which isunreliable because some procedure or data failed to satisfy a property requiredby the computation.\defsubsection{constraint}: A semantic restriction with which a program mustcomply. Some sections of this Document contain paragraphs under the heading{\it Constraints\/} which list all constraints pertaining to the describedfeature. When operated in production mode, the Kazlib implementationis not required to diagnose constraint violations. When operated inverification mode, the Kazlib implementation must halt translation orexecution 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 ona ranking comparison of these arguments, and which satisfies the followingadditional semantic properties. If the two arguments are deemed to be equal, thefunction must return zero. If the first argument is determined to have agreater rank than the second, a positive value is returned. Otherwise if thefirst argument is determined to have a lesser rank than the second, a negativevalue is returned. The rank is computed as if each value has associated with itan integer, not necessarily unique, and as if these integers are compared for ordinary equality orinequality when values are said to be compared.  The assignment of integers isup to the designer of the comparison function, and does not change betweensuccessive invocations of the function.\footnote{Of course, an actualcomparison function need not assign actual integer ranks to data items, but itmust behave as if such ranks were assigned.}If a comparison function is invoked in the context of an operation on some datastructure, it shall not invoke any operation on any component of that samestructure.\footnote{Thus, if a comparison function is invoked from, forinstance, {\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 isnot documented, and which is intended to be manipulated only using thedocumented interface, which consists of a set of functions.  Many data types inKazlib are described as opaque. A program which bypasses the documentedinterfaces in inspecting or manipulating these data types invokes undefinedbehavior, 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 programto 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 implementationof the C language which meets the following additional minimal requirements:\begin{enumerate}\item The C implementation distinguishes external names by at least theirinitial 15 characters\footnote{The ISO 9899:1990 standard demands only thatexternal names be distinguished by their initial six characters.}. Externalnames that are distinct in their first 15 characters are treated by theimplementation as distinct names.  Upper and lower case letters in externalidentifiers 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++ implementationmeets these additional requirements:\begin{enumerate}\item the C++ implementation identifies itself by predefining the preprocessorsymbol \verb|__cplusplus|;\item the C++ implementation is be capable of linkage againstthe 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 claimedby 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{Theintent 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 multiplethreads of execution an implementation of Kazlib may be designated as {\itthread safe}.  To be called thread safe, it must guarantee that the use of anobject by one thread cannot visibly interact or interfere with the concurrentor interleaved use of another object by another thread. If a Kazlibimplementation that is not thread safe is provided for an environment whichsupports threads, it shall be accompanied by documentation which describesthe 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 objectcan be interrupted by delivery of an asynchronous signal and from within thecatching function for that signal, it is safe to perform an operation onanother 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 thanonce. Prior to the inclusion of a Kazlib header, the translation unit shall notdefine any macro name that has the same spelling as a C language keyword. TheKazlib headers may behave as though they include arbitrary standard C headers,so any requirements related to the inclusion of standard headers apply toKazlib headers.  A header shall be included before the first reference to anyof 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 ofthis document that defines the contents of that header. It may also defineadditional 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 exceptas explicitly permitted, and are safe to use wherever the correspondingfunction call would be. These function-like macros may be subject to\verb|#undef|.\footnote{In principle, an implementation may provide, within thereserved namespaces, additional functions not specified in this document, andfunction-like macro equivalents of these functions. A program that uses suchidentifiers in a block or function scope should use {\tt \#undef} on theseidentifiers 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 correspondingsection in this document. Moreover, each header may define additional suchnames that fall into the documented reserved namespaces.The behavior is undefined if a translation unit that includes a Kazlib headerdefines any identifier that is the same as an identifier reserved by the headerin the same scope and namespace.\footnote{Therefore, it is permitted to redeclareor redefine the identifiers reserved by a previously included Kazlib header,provided that the declarations or definitions are in a different namespace orscope. Reserved names may be redeclared in a block scope, or used asstatement labels which have function scope and are in their own namespace.}