   This file documents the GNU C library.

   This is Edition 0.07 DRAFT, last updated 4 Oct 1996, of `The GNU C
Library Reference Manual', for Version 2.00 Beta.

   Copyright (C) 1993, '94, '95, '96, '97 Free Software Foundation, Inc.

   Permission is granted to make and distribute verbatim copies of this
manual provided the copyright notice and this permission notice are
preserved on all copies.

   Permission is granted to copy and distribute modified versions of
this manual under the conditions for verbatim copying, provided also
that the section entitled "GNU Library General Public License" is
included exactly as in the original, and provided that the entire
resulting derived work is distributed under the terms of a permission
notice identical to this one.

   Permission is granted to copy and distribute translations of this
manual into another language, under the above conditions for modified
versions, except that the text of the translation of the section
entitled "GNU Library General Public License" must be approved for
accuracy by the Foundation.

ISO C Random Number Functions
-----------------------------

   This section describes the random number functions that are part of
the ISO C standard.

   To use these facilities, you should include the header file
`stdlib.h' in your program.

 - Macro: int RAND_MAX
     The value of this macro is an integer constant expression that
     represents the maximum possible value returned by the `rand'
     function.  In the GNU library, it is `037777777', which is the
     largest signed integer representable in 32 bits.  In other
     libraries, it may be as low as `32767'.

 - Function: int rand ()
     The `rand' function returns the next pseudo-random number in the
     series.  The value is in the range from `0' to `RAND_MAX'.

 - Function: void srand (unsigned int SEED)
     This function establishes SEED as the seed for a new series of
     pseudo-random numbers.  If you call `rand' before a seed has been
     established with `srand', it uses the value `1' as a default seed.

     To produce truly random numbers (not just pseudo-random), do `srand
     (time (0))'.

BSD Random Number Functions
---------------------------

   This section describes a set of random number generation functions
that are derived from BSD.  There is no advantage to using these
functions with the GNU C library; we support them for BSD compatibility
only.

   The prototypes for these functions are in `stdlib.h'.

 - Function: long int random ()
     This function returns the next pseudo-random number in the
     sequence.  The range of values returned is from `0' to `RAND_MAX'.

 - Function: void srandom (unsigned int SEED)
     The `srandom' function sets the seed for the current random number
     state based on the integer SEED.  If you supply a SEED value of
     `1', this will cause `random' to reproduce the default set of
     random numbers.

     To produce truly random numbers (not just pseudo-random), do
     `srandom (time (0))'.

 - Function: void * initstate (unsigned int SEED, void *STATE, size_t
          SIZE)
     The `initstate' function is used to initialize the random number
     generator state.  The argument STATE is an array of SIZE bytes,
     used to hold the state information.  The size must be at least 8
     bytes, and optimal sizes are 8, 16, 32, 64, 128, and 256.  The
     bigger the STATE array, the better.

     The return value is the previous value of the state information
     array.  You can use this value later as an argument to `setstate'
     to restore that state.

 - Function: void * setstate (void *STATE)
     The `setstate' function restores the random number state
     information STATE.  The argument must have been the result of a
     previous call to INITSTATE or SETSTATE.

     The return value is the previous value of the state information
     array.  You can use thise value later as an argument to `setstate'
     to restore that state.

Low-Level Arithmetic Functions
******************************

   This chapter contains information about functions for doing basic
arithmetic operations, such as splitting a float into its integer and
fractional parts.  These functions are declared in the header file
`math.h'.

"Not a Number" Values
=====================

   The IEEE floating point format used by most modern computers supports
values that are "not a number".  These values are called "NaNs".  "Not
a number" values result from certain operations which have no
meaningful numeric result, such as zero divided by zero or infinity
divided by infinity.

   One noteworthy property of NaNs is that they are not equal to
themselves.  Thus, `x == x' can be 0 if the value of `x' is a NaN.  You
can use this to test whether a value is a NaN or not: if it is not
equal to itself, then it is a NaN.  But the recommended way to test for
a NaN is with the `isnan' function (see Predicates on Floats.).

   Almost any arithmetic operation in which one argument is a NaN
returns a NaN.

 - Macro: double NAN
     An expression representing a value which is "not a number".  This
     macro is a GNU extension, available only on machines that support
     "not a number" values--that is to say, on all machines that
     support IEEE floating point.

     You can use `#ifdef NAN' to test whether the machine supports
     NaNs.  (Of course, you must arrange for GNU extensions to be
     visible, such as by defining `_GNU_SOURCE', and then you must
     include `math.h'.)

Predicates on Floats
====================

   This section describes some miscellaneous test functions on doubles.
Prototypes for these functions appear in `math.h'.  These are BSD
functions, and thus are available if you define `_BSD_SOURCE' or
`_GNU_SOURCE'.

 - Function: int isinf (double X)
     This function returns `-1' if X represents negative infinity, `1'
     if X represents positive infinity, and `0' otherwise.

 - Function: int isnan (double X)
     This function returns a nonzero value if X is a "not a number"
     value, and zero otherwise.  (You can just as well use `X != X' to
     get the same result).

 - Function: int finite (double X)
     This function returns a nonzero value if X is finite or a "not a
     number" value, and zero otherwise.

 - Function: double infnan (int ERROR)
     This function is provided for compatibility with BSD.  The other
     mathematical functions use `infnan' to decide what to return on
     occasion of an error.  Its argument is an error code, `EDOM' or
     `ERANGE'; `infnan' returns a suitable value to indicate this with.
     `-ERANGE' is also acceptable as an argument, and corresponds to
     `-HUGE_VAL' as a value.

     In the BSD library, on certain machines, `infnan' raises a fatal
     signal in all cases.  The GNU library does not do likewise,
     because that does not fit the ISO C specification.

   *Portability Note:* The functions listed in this section are BSD
extensions.

Absolute Value
==============

   These functions are provided for obtaining the "absolute value" (or
"magnitude") of a number.  The absolute value of a real number X is X
is X is positive, -X if X is negative.  For a complex number Z, whose
real part is X and whose imaginary part is Y, the absolute value is
`sqrt (X*X + Y*Y)'.

   Prototypes for `abs' and `labs' are in `stdlib.h'; `fabs' and `cabs'
are declared in `math.h'.

 - Function: int abs (int NUMBER)
     This function returns the absolute value of NUMBER.

     Most computers use a two's complement integer representation, in
     which the absolute value of `INT_MIN' (the smallest possible `int')
     cannot be represented; thus, `abs (INT_MIN)' is not defined.

 - Function: long int labs (long int NUMBER)
     This is similar to `abs', except that both the argument and result
     are of type `long int' rather than `int'.

 - Function: double fabs (double NUMBER)
     This function returns the absolute value of the floating-point
     number NUMBER.

 - Function: double cabs (struct { double real, imag; } Z)
     The `cabs' function returns the absolute value of the complex
     number Z, whose real part is `Z.real' and whose imaginary part is
     `Z.imag'.  (See also the function `hypot' in Exponents and Logarithms.)
     The value is:

          sqrt (Z.real*Z.real + Z.imag*Z.imag)

Normalization Functions
=======================

   The functions described in this section are primarily provided as a
way to efficiently perform certain low-level manipulations on floating
point numbers that are represented internally using a binary radix; see
Floating Point Concepts.  These functions are required to have
equivalent behavior even if the representation does not use a radix of
2, but of course they are unlikely to be particularly efficient in
those cases.

   All these functions are declared in `math.h'.

 - Function: double frexp (double VALUE, int *EXPONENT)
     The `frexp' function is used to split the number VALUE into a
     normalized fraction and an exponent.

     If the argument VALUE is not zero, the return value is VALUE times
     a power of two, and is always in the range 1/2 (inclusive) to 1
     (exclusive).  The corresponding exponent is stored in `*EXPONENT';
     the return value multiplied by 2 raised to this exponent equals
     the original number VALUE.

     For example, `frexp (12.8, &exponent)' returns `0.8' and stores
     `4' in `exponent'.

     If VALUE is zero, then the return value is zero and zero is stored
     in `*EXPONENT'.

 - Function: double ldexp (double VALUE, int EXPONENT)
     This function returns the result of multiplying the floating-point
     number VALUE by 2 raised to the power EXPONENT.  (It can be used
     to reassemble floating-point numbers that were taken apart by
     `frexp'.)

     For example, `ldexp (0.8, 4)' returns `12.8'.

   The following functions which come from BSD provide facilities
equivalent to those of `ldexp' and `frexp':

 - Function: double scalb (double VALUE, int EXPONENT)
     The `scalb' function is the BSD name for `ldexp'.

 - Function: double logb (double X)
     This BSD function returns the integer part of the base-2 logarithm
     of X, an integer value represented in type `double'.  This is the
     highest integer power of `2' contained in X.  The sign of X is
     ignored.  For example, `logb (3.5)' is `1.0' and `logb (4.0)' is
     `2.0'.

     When `2' raised to this power is divided into X, it gives a
     quotient between `1' (inclusive) and `2' (exclusive).

     If X is zero, the value is minus infinity (if the machine supports
     such a value), or else a very small number.  If X is infinity, the
     value is infinity.

     The value returned by `logb' is one less than the value that
     `frexp' would store into `*EXPONENT'.

 - Function: double copysign (double VALUE, double SIGN)
     The `copysign' function returns a value whose absolute value is the
     same as that of VALUE, and whose sign matches that of SIGN.  This
     is a BSD function.

Rounding and Remainder Functions
================================

   The functions listed here perform operations such as rounding,
truncation, and remainder in division of floating point numbers.  Some
of these functions convert floating point numbers to integer values.
They are all declared in `math.h'.

   You can also convert floating-point numbers to integers simply by
casting them to `int'.  This discards the fractional part, effectively
rounding towards zero.  However, this only works if the result can
actually be represented as an `int'--for very large numbers, this is
impossible.  The functions listed here return the result as a `double'
instead to get around this problem.

 - Function: double ceil (double X)
     The `ceil' function rounds X upwards to the nearest integer,
     returning that value as a `double'.  Thus, `ceil (1.5)' is `2.0'.

 - Function: double floor (double X)
     The `ceil' function rounds X downwards to the nearest integer,
     returning that value as a `double'.  Thus, `floor (1.5)' is `1.0'
     and `floor (-1.5)' is `-2.0'.

 - Function: double rint (double X)
     This function rounds X to an integer value according to the
     current rounding mode.  See Floating Point Parameters, for
     information about the various rounding modes.  The default
     rounding mode is to round to the nearest integer; some machines
     support other modes, but round-to-nearest is always used unless
     you explicit select another.

 - Function: double modf (double VALUE, double *INTEGER-PART)
     This function breaks the argument VALUE into an integer part and a
     fractional part (between `-1' and `1', exclusive).  Their sum
     equals VALUE.  Each of the parts has the same sign as VALUE, so
     the rounding of the integer part is towards zero.

     `modf' stores the integer part in `*INTEGER-PART', and returns the
     fractional part.  For example, `modf (2.5, &intpart)' returns
     `0.5' and stores `2.0' into `intpart'.

 - Function: double fmod (double NUMERATOR, double DENOMINATOR)
     This function computes the remainder from the division of
     NUMERATOR by DENOMINATOR.  Specifically, the return value is
     `NUMERATOR - N * DENOMINATOR', where N is the quotient of
     NUMERATOR divided by DENOMINATOR, rounded towards zero to an
     integer.  Thus, `fmod (6.5, 2.3)' returns `1.9', which is `6.5'
     minus `4.6'.

     The result has the same sign as the NUMERATOR and has magnitude
     less than the magnitude of the DENOMINATOR.

     If DENOMINATOR is zero, `fmod' fails and sets `errno' to `EDOM'.

 - Function: double drem (double NUMERATOR, double DENOMINATOR)
     The function `drem' is like `fmod' except that it rounds the
     internal quotient N to the nearest integer instead of towards zero
     to an integer.  For example, `drem (6.5, 2.3)' returns `-0.4',
     which is `6.5' minus `6.9'.

     The absolute value of the result is less than or equal to half the
     absolute value of the DENOMINATOR.  The difference between `fmod
     (NUMERATOR, DENOMINATOR)' and `drem (NUMERATOR, DENOMINATOR)' is
     always either DENOMINATOR, minus DENOMINATOR, or zero.

     If DENOMINATOR is zero, `drem' fails and sets `errno' to `EDOM'.

Integer Division
================

   This section describes functions for performing integer division.
These functions are redundant in the GNU C library, since in GNU C the
`/' operator always rounds towards zero.  But in other C
implementations, `/' may round differently with negative arguments.
`div' and `ldiv' are useful because they specify how to round the
quotient: towards zero.  The remainder has the same sign as the
numerator.

   These functions are specified to return a result R such that the
value `R.quot*DENOMINATOR + R.rem' equals NUMERATOR.

   To use these facilities, you should include the header file
`stdlib.h' in your program.

 - Data Type: div_t
     This is a structure type used to hold the result returned by the
     `div' function.  It has the following members:

    `int quot'
          The quotient from the division.

    `int rem'
          The remainder from the division.

 - Function: div_t div (int NUMERATOR, int DENOMINATOR)
     This function `div' computes the quotient and remainder from the
     division of NUMERATOR by DENOMINATOR, returning the result in a
     structure of type `div_t'.

     If the result cannot be represented (as in a division by zero), the
     behavior is undefined.

     Here is an example, albeit not a very useful one.

          div_t result;
          result = div (20, -6);

     Now `result.quot' is `-3' and `result.rem' is `2'.

 - Data Type: ldiv_t
     This is a structure type used to hold the result returned by the
     `ldiv' function.  It has the following members:

    `long int quot'
          The quotient from the division.

    `long int rem'
          The remainder from the division.

     (This is identical to `div_t' except that the components are of
     type `long int' rather than `int'.)

 - Function: ldiv_t ldiv (long int NUMERATOR, long int DENOMINATOR)
     The `ldiv' function is similar to `div', except that the arguments
     are of type `long int' and the result is returned as a structure
     of type `ldiv'.

Parsing of Numbers
==================

   This section describes functions for "reading" integer and
floating-point numbers from a string.  It may be more convenient in some
cases to use `sscanf' or one of the related functions; see
Formatted Input.  But often you can make a program more robust by
finding the tokens in the string by hand, then converting the numbers
one by one.

Parsing of Integers
-------------------

   These functions are declared in `stdlib.h'.

 - Function: long int strtol (const char *STRING, char **TAILPTR, int
          BASE)
     The `strtol' ("string-to-long") function converts the initial part
     of STRING to a signed integer, which is returned as a value of
     type `long int'.

     This function attempts to decompose STRING as follows:

        * A (possibly empty) sequence of whitespace characters.  Which
          characters are whitespace is determined by the `isspace'
          function (see Classification of Characters.).  These are
          discarded.

        * An optional plus or minus sign (`+' or `-').

        * A nonempty sequence of digits in the radix specified by BASE.

          If BASE is zero, decimal radix is assumed unless the series of
          digits begins with `0' (specifying octal radix), or `0x' or
          `0X' (specifying hexadecimal radix); in other words, the same
          syntax used for integer constants in C.

          Otherwise BASE must have a value between `2' and `35'.  If
          BASE is `16', the digits may optionally be preceded by `0x'
          or `0X'.  If base has no legal value the value returned is
          `0l' and the global variable `errno' is set to `EINVAL'.

        * Any remaining characters in the string.  If TAILPTR is not a
          null pointer, `strtol' stores a pointer to this tail in
          `*TAILPTR'.

     If the string is empty, contains only whitespace, or does not
     contain an initial substring that has the expected syntax for an
     integer in the specified BASE, no conversion is performed.  In
     this case, `strtol' returns a value of zero and the value stored in
     `*TAILPTR' is the value of STRING.

     In a locale other than the standard `"C"' locale, this function
     may recognize additional implementation-dependent syntax.

     If the string has valid syntax for an integer but the value is not
     representable because of overflow, `strtol' returns either
     `LONG_MAX' or `LONG_MIN' (see Range of Type.), as appropriate
     for the sign of the value.  It also sets `errno' to `ERANGE' to
     indicate there was overflow.

     Because the value `0l' is a correct result for `strtol' the user
     who is interested in handling errors should set the global variable
     `errno' to `0' before calling this function, so that the program
     can later test whether an error occurred.

     There is an example at the end of this section.

 - Function: unsigned long int strtoul (const char *STRING, char
          **TAILPTR, int BASE)
     The `strtoul' ("string-to-unsigned-long") function is like
     `strtol' except it deals with unsigned numbers, and returns its
     value with type `unsigned long int'.  If the number has a leading
     `-' sign the negated value is returned.  The syntax is the same as
     described above for `strtol'.  The value returned in case of
     overflow is `ULONG_MAX' (see Range of Type.).

     Like `strtol' this function sets `errno' and returns the value
     `0ul' in case the value for BASE is not in the legal range.

 - Function: long long int strtoq (const char *STRING, char **TAILPTR,
          int BASE)
     The `strtoq' ("string-to-quad-word") function is like `strtol'
     except that is deals with extra long numbers and it returns its
     value with type `long long int'.

     If the string has valid syntax for an integer but the value is not
     representable because of overflow, `strtoq' returns either
     `LONG_LONG_MAX' or `LONG_LONG_MIN' (see Range of Type.), as
     appropriate for the sign of the value.  It also sets `errno' to
     `ERANGE' to indicate there was overflow.

 - Function: long long int strtoll (const char *STRING, char **TAILPTR,
          int BASE)
     `strtoll' is only an commonly used other name for the `strtoq'
     function.  Everything said for `strtoq' applies to `strtoll' as
     well.

 - Function: unsigned long long int strtouq (const char *STRING, char
          **TAILPTR, int BASE)
     The `strtouq' ("string-to-unsigned-quad-word") function is like
     `strtoul' except that is deals with extra long numbers and it
     returns its value with type `unsigned long long int'.  The value
     returned in case of overflow is `ULONG_LONG_MAX' (see Range of Type.).

 - Function: unsigned long long int strtoull (const char *STRING, char
          **TAILPTR, int BASE)
     `strtoull' is only an commonly used other name for the `strtouq'
     function.  Everything said for `strtouq' applies to `strtoull' as
     well.

 - Function: long int atol (const char *STRING)
     This function is similar to the `strtol' function with a BASE
     argument of `10', except that it need not detect overflow errors.
     The `atol' function is provided mostly for compatibility with
     existing code; using `strtol' is more robust.

 - Function: int atoi (const char *STRING)
     This function is like `atol', except that it returns an `int'
     value rather than `long int'.  The `atoi' function is also
     considered obsolete; use `strtol' instead.

   The POSIX locales contain some information about how to format
numbers (see General Numeric.).  This mainly deals with
representing numbers for better readability for humans.  The functions
present so far in this section cannot handle numbers in this form.

   If this functionality is needed in a program one can use the
functions from the `scanf' family which know about the flag `'' for
parsing numeric input (see Numeric Input Conversions.).  Sometimes
it is more desirable to have finer control.

   In these situation one could use the function `__strtoXXX_internal'.
XXX here stands for any of the above forms.  All numeric conversion
functions (including the functions to process floating-point numbers)
have such a counterpart.  The difference to the normal form is the
extra argument at the end of the parameter list.  If this value has an
non-zero value the handling of number grouping is enabled.  The
advantage of using these functions is that the TAILPTR parameters allow
to determine which part of the input is processed.  The `scanf'
functions don't provide this information.  The drawback of using these
functions is that they are not portable.  They only exist in the GNU C
library.

   Here is a function which parses a string as a sequence of integers
and returns the sum of them:

     int
     sum_ints_from_string (char *string)
     {
       int sum = 0;

       while (1) {
         char *tail;
         int next;

         /* Skip whitespace by hand, to detect the end.  */
         while (isspace (*string)) string++;
         if (*string == 0)
           break;

         /* There is more nonwhitespace,  */
         /* so it ought to be another number.  */
         errno = 0;
         /* Parse it.  */
         next = strtol (string, &tail, 0);
         /* Add it in, if not overflow.  */
         if (errno)
           printf ("Overflow\n");
         else
           sum += next;
         /* Advance past it.  */
         string = tail;
       }

       return sum;
     }

Parsing of Floats
-----------------

   These functions are declared in `stdlib.h'.

 - Function: double strtod (const char *STRING, char **TAILPTR)
     The `strtod' ("string-to-double") function converts the initial
     part of STRING to a floating-point number, which is returned as a
     value of type `double'.

     This function attempts to decompose STRING as follows:

        * A (possibly empty) sequence of whitespace characters.  Which
          characters are whitespace is determined by the `isspace'
          function (see Classification of Characters.).  These are
          discarded.

        * An optional plus or minus sign (`+' or `-').

        * A nonempty sequence of digits optionally containing a
          decimal-point character--normally `.', but it depends on the
          locale (see Numeric Formatting.).

        * An optional exponent part, consisting of a character `e' or
          `E', an optional sign, and a sequence of digits.

        * Any remaining characters in the string.  If TAILPTR is not a
          null pointer, a pointer to this tail of the string is stored
          in `*TAILPTR'.

     If the string is empty, contains only whitespace, or does not
     contain an initial substring that has the expected syntax for a
     floating-point number, no conversion is performed.  In this case,
     `strtod' returns a value of zero and the value returned in
     `*TAILPTR' is the value of STRING.

     In a locale other than the standard `"C"' or `"POSIX"' locales,
     this function may recognize additional locale-dependent syntax.

     If the string has valid syntax for a floating-point number but the
     value is not representable because of overflow, `strtod' returns
     either positive or negative `HUGE_VAL' (see Mathematics.),
     depending on the sign of the value.  Similarly, if the value is
     not representable because of underflow, `strtod' returns zero.  It
     also sets `errno' to `ERANGE' if there was overflow or underflow.

     Since the value zero which is returned in the error case is also a
     valid result the user should set the global variable `errno' to
     zero before calling this function.  So one can test for failures
     after the call since all failures set `errno' to a non-zero value.

 - Function: float strtof (const char *STRING, char **TAILPTR)
     This function is similar to the `strtod' function but it returns a
     `float' value instead of a `double' value.  If the precision of a
     `float' value is sufficient this function should be used since it
     is much faster than `strtod' on some architectures.  The reasons
     are obvious: IEEE 754 defines `float' to have a mantissa of 23
     bits while `double' has 53 bits and every additional bit of
     precision can require additional computation.

     If the string has valid syntax for a floating-point number but the
     value is not representable because of overflow, `strtof' returns
     either positive or negative `HUGE_VALf' (see Mathematics.),
     depending on the sign of the value.

     This function is a GNU extension.

 - Function: long double strtold (const char *STRING, char **TAILPTR)
     This function is similar to the `strtod' function but it returns a
     `long double' value instead of a `double' value.  It should be
     used when high precision is needed.  On systems which define a
     `long double' type (i.e., on which it is not the same as `double')
     running this function might take significantly more time since
     more bits of precision are required.

     If the string has valid syntax for a floating-point number but the
     value is not representable because of overflow, `strtold' returns
     either positive or negative `HUGE_VALl' (see Mathematics.),
     depending on the sign of the value.

     This function is a GNU extension.

   As for the integer parsing functions there are additional functions
which will handle numbers represented using the grouping scheme of the
current locale (see Parsing of Integers.).

 - Function: double atof (const char *STRING)
     This function is similar to the `strtod' function, except that it
     need not detect overflow and underflow errors.  The `atof' function
     is provided mostly for compatibility with existing code; using
     `strtod' is more robust.

Searching and Sorting
*********************

   This chapter describes functions for searching and sorting arrays of
arbitrary objects.  You pass the appropriate comparison function to be
applied as an argument, along with the size of the objects in the array
and the total number of elements.

Defining the Comparison Function
================================

   In order to use the sorted array library functions, you have to
describe how to compare the elements of the array.

   To do this, you supply a comparison function to compare two elements
of the array.  The library will call this function, passing as arguments
pointers to two array elements to be compared.  Your comparison function
should return a value the way `strcmp' (see String/Array Comparison.)
does: negative if the first argument is "less" than the
second, zero if they are "equal", and positive if the first argument is
"greater".

   Here is an example of a comparison function which works with an
array of numbers of type `double':

     int
     compare_doubles (const double *a, const double *b)
     {
       return (int) (*a - *b);
     }

   The header file `stdlib.h' defines a name for the data type of
comparison functions.  This type is a GNU extension.

     int comparison_fn_t (const void *, const void *);

Array Search Function
=====================

   To search a sorted array for an element matching the key, use the
`bsearch' function.  The prototype for this function is in the header
file `stdlib.h'.

 - Function: void * bsearch (const void *KEY, const void *ARRAY, size_t
          COUNT, size_t SIZE, comparison_fn_t COMPARE)
     The `bsearch' function searches the sorted array ARRAY for an
     object that is equivalent to KEY.  The array contains COUNT
     elements, each of which is of size SIZE bytes.

     The COMPARE function is used to perform the comparison.  This
     function is called with two pointer arguments and should return an
     integer less than, equal to, or greater than zero corresponding to
     whether its first argument is considered less than, equal to, or
     greater than its second argument.  The elements of the ARRAY must
     already be sorted in ascending order according to this comparison
     function.

     The return value is a pointer to the matching array element, or a
     null pointer if no match is found.  If the array contains more
     than one element that matches, the one that is returned is
     unspecified.

     This function derives its name from the fact that it is implemented
     using the binary search algorithm.

Array Sort Function
===================

   To sort an array using an arbitrary comparison function, use the
`qsort' function.  The prototype for this function is in `stdlib.h'.

 - Function: void qsort (void *ARRAY, size_t COUNT, size_t SIZE,
          comparison_fn_t COMPARE)
     The QSORT function sorts the array ARRAY.  The array contains
     COUNT elements, each of which is of size SIZE.

     The COMPARE function is used to perform the comparison on the
     array elements.  This function is called with two pointer
     arguments and should return an integer less than, equal to, or
     greater than zero corresponding to whether its first argument is
     considered less than, equal to, or greater than its second
     argument.

     *Warning:* If two objects compare as equal, their order after
     sorting is unpredictable.  That is to say, the sorting is not
     stable.  This can make a difference when the comparison considers
     only part of the elements.  Two elements with the same sort key
     may differ in other respects.

     If you want the effect of a stable sort, you can get this result by
     writing the comparison function so that, lacking other reason
     distinguish between two elements, it compares them by their
     addresses.  Note that doing this may make the sorting algorithm
     less efficient, so do it only if necessary.

     Here is a simple example of sorting an array of doubles in
     numerical order, using the comparison function defined above
     (see Comparison Functions.):

          {
            double *array;
            int size;
            ...
            qsort (array, size, sizeof (double), compare_doubles);
          }

     The `qsort' function derives its name from the fact that it was
     originally implemented using the "quick sort" algorithm.

Searching and Sorting Example
=============================

   Here is an example showing the use of `qsort' and `bsearch' with an
array of structures.  The objects in the array are sorted by comparing
their `name' fields with the `strcmp' function.  Then, we can look up
individual objects based on their names.

     #include <stdlib.h>
     #include <stdio.h>
     #include <string.h>

     /* Define an array of critters to sort. */

     struct critter
       {
         const char *name;
         const char *species;
       };

     struct critter muppets[] =
       {
         {"Kermit", "frog"},
         {"Piggy", "pig"},
         {"Gonzo", "whatever"},
         {"Fozzie", "bear"},
         {"Sam", "eagle"},
         {"Robin", "frog"},
         {"Animal", "animal"},
         {"Camilla", "chicken"},
         {"Sweetums", "monster"},
         {"Dr. Strangepork", "pig"},
         {"Link Hogthrob", "pig"},
         {"Zoot", "human"},
         {"Dr. Bunsen Honeydew", "human"},
         {"Beaker", "human"},
         {"Swedish Chef", "human"}
       };

     int count = sizeof (muppets) / sizeof (struct critter);

     /* This is the comparison function used for sorting and searching. */

     int
     critter_cmp (const struct critter *c1, const struct critter *c2)
     {
       return strcmp (c1->name, c2->name);
     }

     /* Print information about a critter. */

     void
     print_critter (const struct critter *c)
     {
       printf ("%s, the %s\n", c->name, c->species);
     }
     /* Do the lookup into the sorted array. */

     void
     find_critter (const char *name)
     {
       struct critter target, *result;
       target.name = name;
       result = bsearch (&target, muppets, count, sizeof (struct critter),
                         critter_cmp);
       if (result)
         print_critter (result);
       else
         printf ("Couldn't find %s.\n", name);
     }

     /* Main program. */

     int
     main (void)
     {
       int i;

       for (i = 0; i < count; i++)
         print_critter (&muppets[i]);
       printf ("\n");

       qsort (muppets, count, sizeof (struct critter), critter_cmp);

       for (i = 0; i < count; i++)
         print_critter (&muppets[i]);
       printf ("\n");

       find_critter ("Kermit");
       find_critter ("Gonzo");
       find_critter ("Janice");

       return 0;
     }

   The output from this program looks like:

     Kermit, the frog
     Piggy, the pig
     Gonzo, the whatever
     Fozzie, the bear
     Sam, the eagle
     Robin, the frog
     Animal, the animal
     Camilla, the chicken
     Sweetums, the monster
     Dr. Strangepork, the pig
     Link Hogthrob, the pig
     Zoot, the human
     Dr. Bunsen Honeydew, the human
     Beaker, the human
     Swedish Chef, the human

     Animal, the animal
     Beaker, the human
     Camilla, the chicken
     Dr. Bunsen Honeydew, the human
     Dr. Strangepork, the pig
     Fozzie, the bear
     Gonzo, the whatever
     Kermit, the frog
     Link Hogthrob, the pig
     Piggy, the pig
     Robin, the frog
     Sam, the eagle
     Swedish Chef, the human
     Sweetums, the monster
     Zoot, the human

     Kermit, the frog
     Gonzo, the whatever
     Couldn't find Janice.

Pattern Matching
****************

   The GNU C Library provides pattern matching facilities for two kinds
of patterns: regular expressions and file-name wildcards.  The library
also provides a facility for expanding variable and command references
and parsing text into words in the way the shell does.

Wildcard Matching
=================

   This section describes how to match a wildcard pattern against a
particular string.  The result is a yes or no answer: does the string
fit the pattern or not.  The symbols described here are all declared in
`fnmatch.h'.

 - Function: int fnmatch (const char *PATTERN, const char *STRING, int
          FLAGS)
     This function tests whether the string STRING matches the pattern
     PATTERN.  It returns `0' if they do match; otherwise, it returns
     the nonzero value `FNM_NOMATCH'.  The arguments PATTERN and STRING
     are both strings.

     The argument FLAGS is a combination of flag bits that alter the
     details of matching.  See below for a list of the defined flags.

     In the GNU C Library, `fnmatch' cannot experience an "error"--it
     always returns an answer for whether the match succeeds.  However,
     other implementations of `fnmatch' might sometimes report "errors".
     They would do so by returning nonzero values that are not equal to
     `FNM_NOMATCH'.

   These are the available flags for the FLAGS argument:

`FNM_FILE_NAME'
     Treat the `/' character specially, for matching file names.  If
     this flag is set, wildcard constructs in PATTERN cannot match `/'
     in STRING.  Thus, the only way to match `/' is with an explicit
     `/' in PATTERN.

`FNM_PATHNAME'
     This is an alias for `FNM_FILE_NAME'; it comes from POSIX.2.  We
     don't recommend this name because we don't use the term "pathname"
     for file names.

`FNM_PERIOD'
     Treat the `.' character specially if it appears at the beginning of
     STRING.  If this flag is set, wildcard constructs in PATTERN
     cannot match `.' as the first character of STRING.

     If you set both `FNM_PERIOD' and `FNM_FILE_NAME', then the special
     treatment applies to `.' following `/' as well as to `.' at the
     beginning of STRING.  (The shell uses the `FNM_PERIOD' and
     `FNM_FILE_NAME' flags together for matching file names.)

`FNM_NOESCAPE'
     Don't treat the `\' character specially in patterns.  Normally,
     `\' quotes the following character, turning off its special meaning
     (if any) so that it matches only itself.  When quoting is enabled,
     the pattern `\?' matches only the string `?', because the question
     mark in the pattern acts like an ordinary character.

     If you use `FNM_NOESCAPE', then `\' is an ordinary character.

`FNM_LEADING_DIR'
     Ignore a trailing sequence of characters starting with a `/' in
     STRING; that is to say, test whether STRING starts with a
     directory name that PATTERN matches.

     If this flag is set, either `foo*' or `foobar' as a pattern would
     match the string `foobar/frobozz'.

`FNM_CASEFOLD'
     Ignore case in comparing STRING to PATTERN.

Globbing
========

   The archetypal use of wildcards is for matching against the files in
a directory, and making a list of all the matches.  This is called
"globbing".

   You could do this using `fnmatch', by reading the directory entries
one by one and testing each one with `fnmatch'.  But that would be slow
(and complex, since you would have to handle subdirectories by hand).

   The library provides a function `glob' to make this particular use
of wildcards convenient.  `glob' and the other symbols in this section
are declared in `glob.h'.

Calling `glob'
--------------

   The result of globbing is a vector of file names (strings).  To
return this vector, `glob' uses a special data type, `glob_t', which is
a structure.  You pass `glob' the address of the structure, and it
fills in the structure's fields to tell you about the results.

 - Data Type: glob_t
     This data type holds a pointer to a word vector.  More precisely,
     it records both the address of the word vector and its size.

    `gl_pathc'
          The number of elements in the vector.

    `gl_pathv'
          The address of the vector.  This field has type `char **'.

    `gl_offs'
          The offset of the first real element of the vector, from its
          nominal address in the `gl_pathv' field.  Unlike the other
          fields, this is always an input to `glob', rather than an
          output from it.

          If you use a nonzero offset, then that many elements at the
          beginning of the vector are left empty.  (The `glob' function
          fills them with null pointers.)

          The `gl_offs' field is meaningful only if you use the
          `GLOB_DOOFFS' flag.  Otherwise, the offset is always zero
          regardless of what is in this field, and the first real
          element comes at the beginning of the vector.

 - Function: int glob (const char *PATTERN, int FLAGS, int (*ERRFUNC)
          (const char *FILENAME, int ERROR-CODE), glob_t *VECTOR-PTR)
     The function `glob' does globbing using the pattern PATTERN in the
     current directory.  It puts the result in a newly allocated
     vector, and stores the size and address of this vector into
     `*VECTOR-PTR'.  The argument FLAGS is a combination of bit flags;
     see Flags for Globbing, for details of the flags.

     The result of globbing is a sequence of file names.  The function
     `glob' allocates a string for each resulting word, then allocates
     a vector of type `char **' to store the addresses of these
     strings.  The last element of the vector is a null pointer.  This
     vector is called the "word vector".

     To return this vector, `glob' stores both its address and its
     length (number of elements, not counting the terminating null
     pointer) into `*VECTOR-PTR'.

     Normally, `glob' sorts the file names alphabetically before
     returning them.  You can turn this off with the flag `GLOB_NOSORT'
     if you want to get the information as fast as possible.  Usually
     it's a good idea to let `glob' sort them--if you process the files
     in alphabetical order, the users will have a feel for the rate of
     progress that your application is making.

     If `glob' succeeds, it returns 0.  Otherwise, it returns one of
     these error codes:

    `GLOB_ABORTED'
          There was an error opening a directory, and you used the flag
          `GLOB_ERR' or your specified ERRFUNC returned a nonzero value.
          See Flags for Globbing, for an explanation of the
          `GLOB_ERR' flag and ERRFUNC.

    `GLOB_NOMATCH'
          The pattern didn't match any existing files.  If you use the
          `GLOB_NOCHECK' flag, then you never get this error code,
          because that flag tells `glob' to *pretend* that the pattern
          matched at least one file.

    `GLOB_NOSPACE'
          It was impossible to allocate memory to hold the result.

     In the event of an error, `glob' stores information in
     `*VECTOR-PTR' about all the matches it has found so far.

Flags for Globbing
------------------

   This section describes the flags that you can specify in the FLAGS
argument to `glob'.  Choose the flags you want, and combine them with
the C bitwise OR operator `|'.

`GLOB_APPEND'
     Append the words from this expansion to the vector of words
     produced by previous calls to `glob'.  This way you can
     effectively expand several words as if they were concatenated with
     spaces between them.

     In order for appending to work, you must not modify the contents
     of the word vector structure between calls to `glob'.  And, if you
     set `GLOB_DOOFFS' in the first call to `glob', you must also set
     it when you append to the results.

     Note that the pointer stored in `gl_pathv' may no longer be valid
     after you call `glob' the second time, because `glob' might have
     relocated the vector.  So always fetch `gl_pathv' from the
     `glob_t' structure after each `glob' call; *never* save the
     pointer across calls.

`GLOB_DOOFFS'
     Leave blank slots at the beginning of the vector of words.  The
     `gl_offs' field says how many slots to leave.  The blank slots
     contain null pointers.

`GLOB_ERR'
     Give up right away and report an error if there is any difficulty
     reading the directories that must be read in order to expand
     PATTERN fully.  Such difficulties might include a directory in
     which you don't have the requisite access.  Normally, `glob' tries
     its best to keep on going despite any errors, reading whatever
     directories it can.

     You can exercise even more control than this by specifying an
     error-handler function ERRFUNC when you call `glob'.  If ERRFUNC
     is not a null pointer, then `glob' doesn't give up right away when
     it can't read a directory; instead, it calls ERRFUNC with two
     arguments, like this:

          (*ERRFUNC) (FILENAME, ERROR-CODE)

     The argument FILENAME is the name of the directory that `glob'
     couldn't open or couldn't read, and ERROR-CODE is the `errno'
     value that was reported to `glob'.

     If the error handler function returns nonzero, then `glob' gives up
     right away.  Otherwise, it continues.

`GLOB_MARK'
     If the pattern matches the name of a directory, append `/' to the
     directory's name when returning it.

`GLOB_NOCHECK'
     If the pattern doesn't match any file names, return the pattern
     itself as if it were a file name that had been matched.
     (Normally, when the pattern doesn't match anything, `glob' returns
     that there were no matches.)

`GLOB_NOSORT'
     Don't sort the file names; return them in no particular order.
     (In practice, the order will depend on the order of the entries in
     the directory.)  The only reason *not* to sort is to save time.

`GLOB_NOESCAPE'
     Don't treat the `\' character specially in patterns.  Normally,
     `\' quotes the following character, turning off its special meaning
     (if any) so that it matches only itself.  When quoting is enabled,
     the pattern `\?' matches only the string `?', because the question
     mark in the pattern acts like an ordinary character.

     If you use `GLOB_NOESCAPE', then `\' is an ordinary character.

     `glob' does its work by calling the function `fnmatch' repeatedly.
     It handles the flag `GLOB_NOESCAPE' by turning on the
     `FNM_NOESCAPE' flag in calls to `fnmatch'.